 in fact incomputable! Finally, I will show that Kolmogorov complexity and Shannon's entropy are symptotically bounded, a most remarkable feature considering the previous property. The Turing machine The Turing machine (TM) is an abstract, idealized, or paper version of the simplest and most elementary computing device. As Fig. 7.1 illustrates, it consists of a tape and a read/write head. The tape is of indefinite length and it contains a succession of memory cells, into which are written the bit symbols 0 or 1.° By convention, cells that were never written or were left blank are read as containing the 0 bit. The tape can be made to move left or right by one cell at a time. The operations of the head and tape are defined by a table of instructions {I1, I IN} of finite size N, also called an action table. The action table is not a program to be read sequentially. Rather, it is a set of instructions corresponding to dif- ferent possibilities to be considered by the machine, as I shall clarify. At each instruction step, the machine's head is initially positioned at a single tape cell. 2 See, for instance: http://en.wikipedia.org/wiki/Kolmogorov_complexity,http://szabo.best.vwh.net/ kolmogorov.html. 3 See, for instance: http://plato.stanford.edu/archives/spr2002/entries/turing-machine/, http://en.wikipedia. org/wiki/Universal_Turing_machine www.turing.org.uk/turing/, www.alanturing.net/ www.cs.usfca.edu/ www.AlanTuring.net/turing_archive/pages/Reference%20Articles/What%20is%20a%20Turing20Machin html. 4 More generally, the symbols that can be put into the cells, including a conventional blank symbol, could be selected from any finite alphabet. Algorithmic entropy and Kolmogorov complexity Instructions 11111 ... State 3 1011 ... Cells Figure 7.1 Schematic representation of Turing machine. The machine is said to be in an input state Si, which corresponds to a specific instruction in the action table. This instruction tells the machine to perform three basic operations altogether: (a) Given the cell's content, what new c