Complexity_ A Guided Tour - Melanie Mitchell [31]
Similarly, we could encode “move right” by 000, and “move left” by 111. Finally, we could encode the ‘—’ separator symbol above as 111. Then we could, for example, encode Rule 1 as the string
111000111000111001111100111000111
which just substitutes our codes for the states and symbols in the shorthand above. The other rules would also be encoded in this way. Put the encoding strings all together, one after another, to form a single, long string, called the code of Turing machine M. To have U emulate M running on input I, U’s initial tape contains both input I and M’s code. At each step U reads the current symbol in I from the input part of the tape, decodes the appropriate rule from the M part of the tape, and carries it out on the input part, all the while keeping track (on some other part of its tape) of what state M would be in if M were actually running on the given input.
When M would have reached the halt state, U also halts, with the input (now output) part of its tape now containing the symbols M would have on its tape after it was run on the given input I. Thus we can say that “U runs M on I.” I am leaving out the actual states and rules of U, since they are pretty complicated, but I assure you that such a Turing machine can be designed. Moreover, what U does is precisely what a modern programmable computer does: it takes a program M that is stored in one part of memory, and runs it on an input I that is stored in another part of memory. It is notable that the first programmable computers were developed only ten years or so after Turing proved the existence of a universal Turing machine.
Turing’s Solution to the Entscheidungsproblem
Recall the question of the Entscheidungsproblem: Is there always a definite procedure that can decide whether or not a statement is true?
It was the existence of a universal Turing machine that enabled Turing to prove that the answer is “no.” He realized that the input I to a Turing machine M could be the code of another Turing machine. This is equivalent to the input of a computer program being the lines of another computer program. For example, you might write a program using a word processor such as Microsoft Word, save it to a file, and then run the “Word Count” program on the file. Here, your program is an input to another program (Word Count), and the output is the number of words in your program. The Word Count program doesn’t run your program; it simply counts the words in it as it would for any file of text.
Analogously, you could, without too much difficulty, design a Turing machine M that counted the 1s in its input, and then run M on the code for a second Turing machine M’. M would simply count the 1s in M’’s code. Of course, the Universal Turing Machine U could have the code for M in the “program” part of its tape, have the code for M’ in the “input” part of its tape, and run M on M’. Just to be perverse, we could put the code for M in both the “program” and “input” parts of U’s tape, and have M run on its own code! This would be like having the Word Count program run on its own lines of code, counting the number of words it contains itself. No problem!
All this may seem fairly pedestrian to your computer-sophisticated mind, but at the time Turing was developing his proof, his essential insight—that the very same string of 0s and 1s on a tape could be interpreted as either a program or as input to another program—was truly novel.
Now we’re ready to outline Turing’s proof.
Turing proved that the answer to the Entscheidungsproblem