This topic continues coverage of the material in section 8.2 (and also covers a tiny bit of section 8.3) in the textbook.
A simple Turing machine consisting of just three rules was introduced in
topic 28. The file copy.dat in the Z:\courses\csc110\chapter8 folder contains a more complicated TM that makes a copy of a binary string. Open this file now in the
ITM applet. The input tape for this TM contains the binary string to be copied, followed by an exclamation mark (!), followed by a number of blanks (b) equal to the length of the binary string. Run this TM now and observe how the read/write head moves back and forth along the tape, copying one bit at a time; also observe how the bit to be copied, 0 or 1, is overwritten by X or Y, respectively, and then restored after it is copied. The 15 rules of this TM are:
1. (1, 0; 2, X, R) 2. (1, 1; 3, Y, R) 3. (2, !; 2, !, R) 4. (2, 0; 2, 0, R) 5. (2, 1; 2, 1, R) 6. (2, b; 4, 0, L) 7. (3, !; 3, !, R) 8. (3, 0; 3, 0, R) 9. (3, 1; 3, 1, R) 10. (3, b; 4, 1, L) 11. (4, !; 4, !, L) 12. (4, 0; 4, 0, L) 13. (4, 1; 4, 1, L) 14. (4, X; 1, 0, R) 15. (4, Y; 1, 1, R)
This TM uses four states: state 1, in which the next bit to be copied is overwritten by X or Y; state 2, in which the read/write head moves to the right and eventually writes 0 over the first b encountered; state 3, in which the read/write head moves to the right and eventually writes 1 over the first b encountered; and state 4, in which the read/write head moves to the left and eventually writes 0 or 1 over the X or Y,respectively, written earlier. The back and forth movement of the read/write head in this case is typical of many Turing machines.
Having now considered a TM of some complexity, it might be easier for you to believe the following statement: it has been proven that a Turing machine can do any data manipulation task that can be done by any computer program written in any existing programming language running on any modern computer. In fact, Turing machines are actually more powerful than any program running on any modern computer, since the unlimited length of a TM's tape gives it potentially infinite memory capacity. Of course, a TM does not run very efficiently; it does not, for example, have a random access memory but instead has to move a potentially long way along its tape to retrieve a stored symbol. However, Turing was not trying to create an efficient machine when he invented TMs; he was trying to define precisely what he called a mechanical process (also known as an effective procedure or an algorithm), which (to him and other mathematicians of that time) meant what a human being does when he/she performs a pencil and paper calculation according to an exact set of instructions. Turing defined his machines in a simple way because this made them more believable as models of mechanical processes (and it also made them conceptually easier to work with in mathematical proofs).
We will now consider the term computable (part of the second fundamental question of computing science raised near the beginning of topic 28 concerning what tasks are computable). We will say that a task is computable by Turing machine if that task can be accomplished by a TM that eventually halts. However, there are other definitions of computable, in addition to computable by Turing machine. One such definition, proposed by mathematician Alonzo Church in 1936 (the same year that Turing invented the TM), is based on recursive functions instead of Turing machines. Yet another definition was proposed (also in 1936) by mathematician Emil Post. It was soon proven that these three definitions are equivalent (i.e. they define exactly the same set of computable tasks). Later definitions of computable were also shown to be equivalent to these three. Hence, there seems to be strong evidence supporting the following claim:
The Church-Turing Thesis: Any reasonable definition of computable is equivalent to computable by Turing Machine.
A thesis, unlike a theorem, is not provable. The Church-Turing thesis is not provable because it can never be known what reasonable definitions of computable might be proposed in the future. Computing scientists believe this thesis because, so far, every such reasonable definition is provably equivalent to Turing's definition. Henceforth, based on well-justified faith in the Church-Turing thesis, we will define computable as computable by Turing machine. It is important to realize, however, that the Church-Turing thesis relates to an arguably narrow definition of computable (based on what a human being does when he/she performs a pencil and paper calculation according to an exact set of instructions) and does not preclude the invention of a marvellous new computer, possibly based on some as yet undiscovered physical principle, that performs tasks that no TM can. Some people, including the authors of your textbook, have adopted a stronger version of the Church-Turing thesis in which the phrase any reasonable definition of computable in the description of the thesis above is effectively replaced by any physically realizable computational process (Floyd and Beigel, The Language of Machines, page 444), but neither Church nor Turing ever endorsed this interpretation (B. Jack Copeland, The Church-Turing Thesis, Stanford Encyclopedia of Philosophy).
Owing to their simplicity, it is possible to associate a unique serial number (see page 280 of the textbook) with any TM. To obtain the serial number, we must first restrict the symbols allowed on the tape of a TM to a finite alphabet; we will assume, along with the textbook, that each symbol on the tape of a TM belongs to the set {0, 1, b}, where b represents a blank. We can now translate the rules of any TM into a binary serial number, as follows:
n 0s represent the state n 0 represents the symbol 0 00 represents the symbol 1 000 represents the symbol b 0 represents the move L 00 represents the move R 1 is used to separate the parts of a rule 11 is used to separate rules 111 is used before the first rule and after the last rule
As an example of this translation process, consider the TM used in topic 28 to add two positive integers in unary notation separated by an exclamation mark (!). Since we are now assuming that only the symbols 0, 1, and b are allowed on the tape of a TM, the symbol 0 will be used instead of the exclamation mark to separate the integers to be added. With this small change, the rules of this TM are
(1, 1, 2, b, R) (2, 1, 2, 1, R) (2, 0, 3, 1, R)
Applying the translation process described above, we obtain the following binary serial number for this TM:
1110100100100010011001001001001001100101000100100111
Evidently, the serial numbers for some Turing machines will be very large. Also, many binary numbers will not correspond to a valid TM; in fact, the smallest serial number for a valid TM is 111111, corresponding to a TM with no rules. Moreover, since the rules of a TM produce the same result regardless of their order, two TMs with different serial numbers may behave in exactly the same way. None of this matters. The important thing is that the binary serial number that encodes a Turing machine is unique in that the same serial number cannot encode two different TMs (since the rules of a TM can be reconstructed exactly from its serial number).
Serial numbers for Turing machines have two marvellous uses:
111111, as noted above), M2 the TM with the second smallest serial number, and so on. Thus, the infinite list M1, M2, M3, ... includes all possible Turing machines. An infinite set of items that can be listed one by one in this way is said to be countably infinite. Finite binary strings (used as input for TMs) can also be encoded in a unique way as positive integers (see page 282) and listed in this way. In section 8.3, these facts are used to show that a TM cannot perform certain tasks.