6.3.1 Turing machines

This abstract model of a computer was invented by Alan Turing in the 1930s and is known as a Turing Machine. Turing’s model is depicted in Figure 6.4. An infinite tape divided into squares is used as the input, working storage, and output. The tape head can read the current square on the tape, write a symbol into the current tape square, and move left or right one position. The tape head keeps track of its internal state, and follows rules matching the current state and current tape square to determine what to do next.

Turing’s model is by far the most widely used model for computers today. Turing developed this model in 1936, before anything resembling a modern computer existed. Turing did not develop his model as a model of an automatic computer, but instead as a model for what could be done by a human following mechanical rules. He devised the infinite tape to model the two-dimensional graph paper students use to perform arithmetic. He argued that the number of machine states must be limited by arguing that a human could only keep a limited amount of information in mind at one time.

Figure 6.4: Turing Machine model.

Turing’s model is equivalent to the model we described earlier, but instead of using only bits as the symbols on the tape, Turing’s model uses members of any finite set of symbols, known as the alphabet of the tape. Allowing the tape alphabet to contain any set of symbols instead of just the two binary digits makes it easier to describe a Turing Machine that computes a particular function, but does not change the power of the model. That means, every computation that could be done with a Turing Machine using any alphabet set, could also be done by some Turing Machine using only the binary digits.

We could show this by describing an algorithm that takes in a description of a Turing Machine using an arbitrarily large alphabet, and produces a Turing Machine that uses only two symbols to simulate the input Turing Machine. As we saw in Chapter 1, we can map each of the alphabet symbols to a finite sequence of binary digits.

Mapping the rules is more complex: since each original input symbol is now spread over several squares, we need extra states and rules to read the equivalent of one original input. For example, suppose our original machine uses 16 alphabet symbols, and we map each symbol to a 4-bit sequence. If the original machine used a symbol X, which we map to the sequence of bits 1011, we would need four states for every state in the original machine that has a rule using X as input. These four states would read the 1, 0, 1, 1 from the tape. The last state now corresponds to the state in the original machine when an X is read from the tape. To follow the rule, we also need to use four states to write the bit sequence corresponding to the original write symbol on the tape. Then, simulating moving one square left or right on the original Turing Machine, now requires moving four squares, so requires four more states. Hence, we may need 12 states for each transition rule of the original machine, but can simulate everything it does using only two symbols.

The Turing Machine model is a universal computing machine. This means every algorithm can be implemented by some Turing Machine. Chapter 12 explores more deeply what it means to simulate every possible Turing Machine and explores the set of problems that can be solved by a Turing Machine.

Any physical machine has a limited amount of memory. If the machine does not have enough space to store a trillion bits, there is no way it can do a computation whose output would exceed a trillion bits. Nevertheless, the simplicity and robustness of the Turing Machine model make it a useful way to think about computing even if we cannot build a truly universal computing machine.

Turing’s model has proven to be remarkably robust. Despite being invented before anything resembling a modern computer existed, nearly every computing machine ever imagined or built can be modeled well using Turing’s simple model. The important thing about the model is that we can simulate any computer using a Turing Machine. Any step on any computer that operates using standard physics and be simulated with a finite number of steps on a Turing Machine. This means if we know how many steps it takes to solve some problem on a Turing Machine, the number of steps it takes on any other machine is at most some multiple of that number. Hence, if we can reason about the number of steps required for a Turing Machine to solve a given problem, then we can make strong and general claims about the number of steps it would take any standard computer to solve the problem. We will show this more convincingly in Chapter 12, but for now we assert it, and use it to reason about the cost of executing various procedures in the following chapter.

Example 6.19: Balancing Parentheses

We define a Turing Machine that solves the problem of checking parentheses are well-balanced. For example, in a Scheme expression, every opening left parenthesis must have a corresponding closing right parenthesis. For example, (()(()))() is well-balanced, but (()))(() is not. Our goal is to design a Turing Machine that takes as input a string of parentheses (with a # at the beginning and end to mark the endpoints) and produces as output a 1 on the tape if the input string is well-balanced, and a 0 otherwise. For this problem, the output is what is written in the square under the tape head; it doesn’t matter what is left on the rest of the tape.

Our strategy is to find matching pairs of parentheses and cross them out by writing an X on the tape in place of the parenthesis. If all the parentheses are crossed out at the end, the input was well-balanced, so the machine writes a 1 as its output and halts. If not, the input was not well-balanced, and the machine writes a 0 as its output and halts. The trick to the matching is that a closing parenthesis always matches the first open parenthesis found moving to the left from the closing parenthesis. The plan for the machine is to move the tape head to the right (without changing the input) until a closing parenthesis is found. Cross out that closing parenthesis by replacing it with an X, and move to the left until an open parenthesis is found. This matches the closing parenthesis, so it is replaced with an X. Then, continue to the right searching for the next closing parenthesis. If the end of the tape (marked with a #) is found, check the tape has no remaining open parenthesis.

We need three internal states: LookForClosing, in which the machine continues to the right until it finds a closing parenthesis (this is the start state); LookForOpen, in which the machine continues to the left until it finds the balancing open parenthesis; and CheckTape, in which the machine checks there are no unbalanced open parentheses on the tape starting from the right end of the tape and moving towards the left end. The full rules are shown in Figure 6.5.

State Read Next State Write Move  
LookForClosing ) LookForOpen X $\leftarrow $ Found closing.
LookForClosing ( LookForClosing ( $\rightarrow $ Keep looking.
LookForClosing X LookForClosing X $\rightarrow $ Keep looking.
LookForClosing # CheckTape # $\leftarrow $ End of tape.
LookForOpen ) - X Error Shouldn’t happen.
LookForOpen ( LookForClosing X $\rightarrow $ Found open.
LookForOpen X LookForOpen X $\leftarrow $ Keep looking.
LookForOpen # - 0 Halt Reached beginning.
CheckTape ) - 0 Error Shouldn’t happen.
CheckTape ( - 0 Halt Unbalanced open.
CheckTape X CheckTape X $\leftarrow $ Keep checking.
CheckTape # - 1 Halt Finished checking.

Figure 6.5: Rules for checking balanced parentheses Turing Machine.

Another way to depict a Turing Machine is to show the states and rules graphically. Each state is a node in the graph. For each rule, we draw an edge on the graph between the starting state and the next state, and label the edge with the read and write tape symbols (separated by a /), and move direction.

Figure 6.6 shows the same Turing Machine as a state graph. When reading a symbol in a given state produces an error (such as when a ) is encountered in the LookForOpen state), it is not necessary to draw an edge on the graph. If there is no outgoing edge for the current read symbol for the current state in the state graph, execution terminates with an error.

Figure 6.6: Checking parentheses Turing Machine.

Exercise 6.10.  Follow the rules to simulate the checking parentheses Turing Machine on each input (assume the beginning and end of the input are marked with a #):

  1. )

  2. ()

  3. empty input

  4. (()(()))()

  5. (()))(()

Exercise 6.11.  $\left[\star \right]$Design a Turing Machine for adding two arbitrary-length binary numbers. The input is of the form $a_{n-1} \ldots a_1 a_0$ + $b_{m-1} \ldots b_1 b_0$ (with # markers at both ends) where each $a_ k$ and $b_ k$ is either 0 or 1. The output tape should contain bits that represent the sum of the two inputs.

Profile: Alan Turing

David Alan Turing was born in London in 1912, and developed his computing model while at Cambridge in the 1930s. He developed the model to solve a famous problem posed by David Hilbert in 1928. The problem, known as the Entscheidungsproblem (German for “decision problem”) asked for an algorithm that could determine the truth or falsehood of a mathematical statement. To solve the problem, Turing first needed a formal model of an algorithm. For this, he invented the Turing Machine model described above, and defined an algorithm as any Turing Machine that is guaranteed to eventually halt on any input.

Alan Turing Image from Bletchley Park Ltd.

With the model, Turing was able to show that there are some problems that cannot be solved by any algorithm. We return to this in Chapter 12 and explain Turing’s proof and examples of problems that cannot be solved.

After publishing his solution to the Entscheidungsproblem in 1936, Turing went to Princeton and studied with Alonzo Church (inventor of the Lambda calculus, on which Scheme is based). With the start of World War II, Turing joined the highly secret British effort to break Nazi codes at Bletchley Park. Turing was instrumental in breaking the Enigma code which was used by the Nazis to communicate with field units and submarines. Turing designed an electro-mechanical machine known as a bombe for searching possible keys to decrypt Enigma-encrypted messages.

Bombe Rebuilt at Bletchley Park

The machines used logical operations to search the possible rotor settings on the Enigma to find the settings that were most likely to have generated an intercepted encrypted message. Bletchley Park was able to break thousands of Enigma messages during the war. The Allies used the knowledge gained from them to avoid Nazi submarines and gain a tremendous tactical advantage.

After the war, Turing continued to make both practical and theoretical contributions to computer science. Among other things, he worked on designing general-purpose computing machines and published a paper (Intelligent Machinery) speculating on the ability of computers to exhibit intelligence. Turing introduced a test for machine intelligence (now known as the Turing Test) based on a machines ability to impersonate a human and speculated that machines would be able to pass the test within 50 years (that is, by the year 2000). Turing also studied morphogenesis (how biological systems grow) including why Fibonacci numbers appear so often in plants.

In 1952, Turing’s house was broken into, and Turing reported the crime to the police. The investigation revealed that Turing was a homosexual, which at the time was considered a crime in Britain. Turing did not attempt to hide his homosexuality, and was convicted and given a choice between serving time in prison and taking hormone treatments. He accepted the treatments, and has his security clearance revoked. In 1954, at the age of 41, Turing was found dead in an apparent suicide, with a cyanide-laced partially-eaten apple next to him. The codebreaking effort at Bletchley Park was kept secret for many years after the war (Turing’s report on Enigma was not declassified until 1996), so Turing never received public recognition for his contributions to the war effort. In September 2009, instigated by an on-line petition, British Prime Minister Gordon Brown issued an apology for how the British government treated Alan Turing.Brown, Gordon