Complexity_ A Guided Tour - Melanie Mitchell [30]
Our Turing machine’s head will have four possible states: start, even, odd, and halt. The head will start on the left-most 0 and in the start state. We will write rules that cause the head to move to the right, one cell at a time, replacing the 0s and 1s it encounters with blanks. If the head reads a 1 in the current cell, the head goes into the odd state and moves one cell to the right. If it reads a 1 again it goes into the even state and moves one cell to the right, and so on, switching between the even and odd states as 1s are read.
When the head reads a 0, it has come to the end of the input, and whatever state it is in, odd or even, is the correct one. The machine will then write a corresponding 0 or 1 in its current cell and go into the halt state.
Here are the rules for the tape head that implement this algorithm:
If you are in the start state and read a 0, then change to the even state, replace the 0 with a blank (i.e., erase the 0), and move one cell to the right.
If you are in the even state and read a 1, change to the odd state, replace the 1 with a blank, and move one cell to the right.
If you are in the odd state and read a 1, change to the even state, replace the 1 with a blank, and move one cell to the right.
If you are in the odd state and read a 0, replace that 0 with a 1 and change to the halt state.
If you are in the even state and read a 0, replace that 0 with a 0 (i.e., don’t change it) and change to the halt state.
The process of starting with input symbols on the tape and letting the Turing machine serially process that input by using such rules is called “running the Turing machine on the input.”
Definite Procedures Defined as Turing Machines
In the example above, assuming that the input is in the correct format of zero or more 1s sandwiched between two 0s, running this Turing machine on the input is guaranteed to produce a correct answer for any input (including the special case of zero 1s, which is considered to be an even number). Even though it seems kind of clunky, you have to admit that this process is a “definite procedure”—a precise set of steps—for solving the even/odd problem. Turing’s first goal was to make very concrete this notion of definite procedure. The idea is that, given a particular problem to solve, you can construct a definite procedure for solving it by designing a Turing machine that solves it. Turing machines were put forth as the definition of “definite procedure,” hitherto a vague and ill-defined notion.
When formulating these ideas, Turing didn’t build any actual machines (though he built significant ones later on). Instead, all his thinking about Turing machines was done with pencil and paper alone.
Universal Turing Machines
Next, Turing proved an amazing fact about Turing machines: one can design a special universal Turing machine (let’s call it U) that can emulate the workings of any other Turing machine. For U to emulate a Turing machine M running on an input I, U starts with part of its tape containing a sequence of 0s, 1s, and blanks that encodes input I, and part of its tape containing a sequence of 0s, 1s, and blanks that encodes machine M. The concept of encoding a machine M might not be familiar to you, but it is not hard. First, we recognize that all rules (like the five given in the “simple example” above) can be written in a shorthand that looks like
—Current State—Current Symbol—New State—New Symbol—Motion—
In this shorthand, Rule 1 above would be written as:
—start—0—even—blank—right—
(The separator ‘—’ is not actually needed, but makes the rule easier for us to read.) Now to encode a rule, we simply assign different three-digit binary numbers to each of