#computing #information #intelligence # [[Epistemic status]] #shower-thought # Turing machine A Turing machine can compute a single [[Algorithm]]. ![[9AFC157D-B7C4-443C-9557-F68668D230D7.png]] ![[02722091-76A7-4215-9CAB-E4A4DC5A37BA.png]] >We formalize Turing's description as follows: A Turing machine consists of a finite program, called the finite control, capable of manipulating a linear list of cells, called the tape, using one access pointer, called the head (Figure 1.1). We refer to the two directions on the tape as right and left. The finite control can be in any one of a finite set of states Q, and each tape cell can contain a 0, a 1, or a blank B. Time is discrete and the time instants are ordered 0, 1, 2, ..., with O the time at which the machine starts its computation. At any time, the head is positioned over a particular cell, which it is said to scan. At time O the head is situated on a distinguished cell on the tape called the start cell, and the finite control is in a distinguished state qo. At time 0 all cells contain B's, except for a contiguous finite sequence of cells, extending from the start cell to the right, which contain O's and 1's. This binary sequence is called the input. >~ [[Ming Li]] >We can associate a partial function with each Turing machine in the following way: The input to the Turing machine is presented as an n- tuple (21,..., In) of binary strings in the form of a single binary string consisting of self-delimiting versions of the 2's. The integer represented by the maximal binary string (bordered by blanks) of which some bit is scanned, or "O" if a blank is scanned, by the time the machine halts is called the output of the computation. > ~ [[Ming Li]] ## Computable numbers [[Algorithm]]s are, fundamentally, numbers. >functions of a real variable expressed in terms of computable numbers. According to my definition, **a number is computable if its decimal can be written down by a machine.** In 9. 10 I give some arguments with the intention of showing that the computable numbers include all numbers which could naturally be regarded as computable. ~ [[Turing]] # To consume [[Roger Penrose]] # Links https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf https://youtu.be/dNRDvLACg5Q Similar topic links: - [[Turing Machine]]: https://en.wikipedia.org/wiki/Turing_machine - [[Computable Number]]: https://en.wikipedia.org/wiki/Computable_number - [[Algorithm]]: https://en.wikipedia.org/wiki/Algorithm - [[Roger Penrose]]: https://en.wikipedia.org/wiki/Roger_Penrose