Turing Machine Computations

Explain

It is perhaps best to think of a Turing machine as a program for a special kind of imaginary mechanism. This mechanism consists of a tape and a read-write head. In our version of Turing machines, the tape is infinite in one direction (to the right), and it is divided into squares, each of which may contain a symbol from a finite alphabet. Such alphabets can contain any number of different symbols, but we will mainly make do with three: $\TMendtape$source, $\TMblank$source, and $\TMstroke$source. When the mechanism is started, the tape is empty (i.e., each square contains the symbol $\TMblank$source) except for the leftmost square, which contains $\TMendtape$source, and a finite number of squares which contain the input. At any time, the mechanism is in one of a finite number of states. At the outset, the head scans the leftmost square and in a specified initial state. At each step of the mechanism's run, the content of the square currently scanned together with the state the mechanism is in and the Turing machine program determine what happens next. The Turing machine program is given by a partial function which takes as input a state $q$source and a symbol $\sigma$source and outputs a triple $\tuple{q', \sigma', D}$source. Whenever the mechanism is in state $q$source and reads symbol $\sigma$source, it replaces the symbol on the current square with $\sigma'$source, the head moves left, right, or stays put according to whether $D$source is $\TMleft$source, $\TMright$source, or $\TMstay$source, and the mechanism goes into state $q'$source.

For instance, consider the situation in link to figure A Turing machine executing its program.

The visible part of the tape of the Turing machine contains the end-of-tape symbol $\TMendtape$source on the leftmost square, followed by three $1$source's, a $0$source, and four more $1$source's. The head is reading the third square from the left, which contains a $1$source, and is in state $q_1$source---we say “the machine is reading a $1$source in state $q_1$source.” If the program of the Turing machine returns, for input $\tuple{q_1, 1}$source, the triple $\tuple{q_2, 0, \TMstay}$source, the machine would now replace the $1$source on the third square with a $0$source, leave the read/write head where it is, and switch to state $q_2$source. If then the program returns $\tuple{q_3, 0, \TMright}$source for input $\tuple{q_2, 0}$source, the machine would now overwrite the $0$source with another $0$source (effectively, leaving the content of the tape under the read/write head unchanged), move one square to the right, and enter state $q_3$source. And so on.

We say that the machine halts when it encounters some state, $q_n$source, and symbol, $\sigma$source such that there is no instruction for $\tuple{q_n, \sigma}$source, i.e., the transition function for input $\tuple{q_n,\sigma}$source is undefined. In other words, the machine has no instruction to carry out, and at that point, it ceases operation. Halting is sometimes represented by a specific halt state $h$source. This will be demonstrated in more detail later on.

Digress

The beauty of Turing's paper, “On computable numbers,” is that he presents not only a formal definition, but also an argument that the definition captures the intuitive notion of computability. From the definition, it should be clear that any function computable by a Turing machine is computable in the intuitive sense. Turing offers three types of argument that the converse is true, i.e., that any function that we would naturally regard as computable is computable by such a machine. They are (in Turing's words):

1. A direct appeal to intuition.

2. A proof of the equivalence of two definitions (in case the new definition has a greater intuitive appeal).

3. Giving examples of large classes of numbers which are computable.

Our goal is to try to define the notion of computability “in principle,” i.e., without taking into account practical limitations of time and space. Of course, with the broadest definition of computability in place, one can then go on to consider computation with bounded resources; this forms the heart of the subject known as “computational complexity.”

History

Alan Turing invented Turing machines in 1936. While his interest at the time was the decidability of first-order logic, the paper has been described as a definitive paper on the foundations of computer design. In the paper, Turing focuses on computable real numbers, i.e., real numbers whose decimal expansions are computable; but he notes that it is not hard to adapt his notions to computable functions on the natural numbers, and so on. Notice that this was a full five years before the first working general purpose computer was built in 1941 (by the German Konrad Zuse in his parent's living room), seven years before Turing and his colleagues at Bletchley Park built the code-breaking Colossus (1943), nine years before the American ENIAC (1945), twelve years before the first British general purpose computer---the Manchester Small-Scale Experimental Machine---was built in Manchester (1948), and thirteen years before the Americans first tested the BINAC (1949). The Manchester SSEM has the distinction of being the first stored-program computer---previous machines had to be rewired by hand for each new task.

Explain

Turing machines can be represented visually by state diagrams. The diagrams are composed of state cells connected by arrows. Unsurprisingly, each state cell represents a state of the machine. Each arrow represents an instruction that can be carried out from that state, with the specifics of the instruction written above or below the appropriate arrow. Consider the following machine, which has only two internal states, $q_0$source and $q_1$source, and one instruction:

Recall that the Turing machine has a read/write head and a tape with the input written on it. The instruction can be read as if reading a $\TMblank$source in state $q_0$source, write a $\TMstroke$source, move right, and move to state $q_1$source. This is equivalent to the transition function mapping $\tuple{q_0, \TMblank}$source to $\tuple{q_1, \TMstroke, \TMright}$source.

Turing machine example

Even Machine: The following Turing machine halts if, and only if, there are an even number of $\TMstroke$source's on the tape (under the assumption that all $\TMstroke$source's come before the first $\TMblank$source on the tape).

The state diagram corresponds to the following transition function:

Explain

The above machine halts only when the input is an even number of strokes. Otherwise, the machine (theoretically) continues to operate indefinitely. For any machine and input, it is possible to trace through the configurations of the machine in order to determine the output. We will give a formal definition of configurations later. For now, we can intuitively think of configurations as a series of diagrams showing the state of the machine at any point in time during operation. Configurations show the content of the tape, the state of the machine and the location of the read/write head.

Let us trace through the configurations of the even machine if it is started with an input of four $\TMstroke$source's. In this case, we expect that the machine will halt. We will then run the machine on an input of three $\TMstroke$source's, where the machine will run forever.

The machine starts in state $q_0$source, scanning the leftmost $\TMstroke$source. We can represent the initial state of the machine as follows:

The above configuration is straightforward. As can be seen, the machine starts in state one, scanning the leftmost $\TMstroke$source. This is represented by a subscript of the state name on the first $\TMstroke$source. The applicable instruction at this point is $\delta(q_0, \TMstroke) = \tuple{q_1, \TMstroke, \TMright}$source, and so the machine moves right on the tape and changes to state $q_1$source.

Since the machine is now in state $q_1$source scanning a $\TMstroke$source, we have to “follow” the instruction $\delta(q_1, \TMstroke) = \tuple{q_0, \TMstroke, \TMright}$source. This results in the configuration

As the machine continues, the rules are applied again in the same order, resulting in the following two configurations:

The machine is now in state $q_0$source scanning a $\TMblank$source. Based on the transition diagram, we can easily see that there is no instruction to be carried out, and thus the machine has halted. This means that the input has been accepted.

Suppose next we start the machine with an input of three $\TMstroke$source's. The first few configurations are similar, as the same instructions are carried out, with only a small difference of the tape input:

The machine has now traversed past all the $\TMstroke$source's, and is reading a $\TMblank$source in state $q_1$source. As shown in the diagram, there is an instruction of the form $\delta(q_1, \TMblank) =\tuple{q_1, \TMblank, \TMright}$source. Since the tape is filled with $\TMblank$source indefinitely to the right, the machine will continue to execute this instruction forever, staying in state $q_1$source and moving ever further to the right. The machine will never halt, and does not accept the input.

Explain

It is important to note that not all machines will halt. If halting means that the machine runs out of instructions to execute, then we can create a machine that never halts simply by ensuring that there is an outgoing arrow for each symbol at each state. The even machine can be modified to run indefinitely by adding an instruction for scanning a $\TMblank$source at $q_0$source.

Turing machine example

Explain

Machine tables are another way of representing Turing machines. Machine tables have the tape alphabet displayed on the $x$source-axis, and the set of machine states across the $y$source-axis. Inside the table, at the intersection of each state and symbol, is written the rest of the instruction---the new state, new symbol, and direction of movement. Machine tables make it easy to determine in what state, and for what symbol, the machine halts. Whenever there is a gap in the table is a possible point for the machine to halt. Unlike state diagrams and instruction sets, where the points at which the machine halts are not always immediately obvious, any halting points are quickly identified by finding the gaps in the machine table.

Turing machine example

The machine table for the even machine is:

As we can see, the machine halts when scanning a $\TMblank$source in state $q_0$source.

Explain

So far we have only considered machines that read and accept input. However, Turing machines have the capacity to both read and write. An example of such a machine (although there are many, many examples) is a doubler. A doubler, when started with a block of $n$source $\TMstroke$source's on the tape, outputs a block of $2n$source $\TMstroke$source's.

Turing machine example

Before building a doubler machine, it is important to come up with a strategy for solving the problem. Since the machine (as we have formulated it) cannot remember how many $\TMstroke$source's it has read, we need to come up with a way to keep track of all the $\TMstroke$source's on the tape. One such way is to separate the output from the input with a $\TMblank$source. The machine can then erase the first $\TMstroke$source from the input, traverse over the rest of the input, leave a $\TMblank$source, and write two new $\TMstroke$source's. The machine will then go back and find the second $\TMstroke$source in the input, and double that one as well. For each one $\TMstroke$source of input, it will write two $\TMstroke$source's of output. By erasing the input as the machine goes, we can guarantee that no $\TMstroke$source is missed or doubled twice. When the entire input is erased, there will be $2n$source $\TMstroke$source's left on the tape. The state diagram of the resulting Turing machine is depicted in link to figure A doubler machine.

Unsolved Turing machine exercise

Choose an arbitrary input and trace through the configurations of the doubler machine in link to example Doubler machine.

Unsolved Turing machine exercise

Design a Turing-machine with alphabet $\{\TMendtape,\TMblank, A, B\}$source that accepts, i.e., halts on, any string of $A$source's and $B$source's where the number of $A$source's is the same as the number of $B$source's and all the $A$source's precede all the $B$source's, and rejects, i.e., does not halt on, any string where the number of $A$source's is not equal to the number of $B$source's or the $A$source's do not precede all the $B$source's. (E.g., the machine should accept $AABB$source, and $AAABBB$source, but reject both $AAB$source and $AABBAABB$source.)

Unsolved Turing machine exercise

Design a Turing-machine with alphabet $\{\TMendtape,\TMblank, A, B\}$source that takes as input any string $\alpha$source of $A$source's and $B$source's and duplicates them to produce an output of the form $\alpha\alpha$source. (E.g. input $ABBA$source should result in output $ABBAABBA$source).

Unsolved Turing machine exercise

Alphabetical?: Design a Turing-machine with alphabet $\{\TMendtape,\TMblank, A, B\}$source that when given as input a finite sequence of $A$source's and $B$source's checks to see if all the $A$source's appear to the left of all the $B$source's or not. The machine should leave the input string on the tape, and either halt if the string is “alphabetical”, or loop forever if the string is not.

Unsolved Turing machine exercise

Alphabetizer: Design a Turing-machine with alphabet $\{\TMendtape,\TMblank, A, B\}$source that takes as input a finite sequence of $A$source's and $B$source's rearranges them so that all the $A$source's are to the left of all the $B$source's. (e.g., the sequence $BABAA$source should become the sequence $AAABB$source, and the sequence $ABBABB$source should become the sequence $AABBBB$source).

Explain

The formal definition of what constitutes a Turing machine looks abstract, but is actually simple: it merely packs into one mathematical structure all the information needed to specify the workings of a Turing machine. This includes (1) which states the machine can be in, (2) which symbols are allowed to be on the tape, (3) which state the machine should start in, and (4) what the instruction set of the machine is.

Turing machine definition

[Turing machine] A Turing machine $M$source is a tuple $\langle Q, \Sigma, q_0, \delta\rangle$source consisting of

1. a finite set of states $Q$source,

2. a finite alphabet $\Sigma$source which includes $\TMendtape$source and $\TMblank$source,

3. an initial state $q_0 \in Q$source,

4. a finite instruction set $\delta\colon Q \times \Sigma \pto Q \times \Sigma \times \{\TMleft, \TMright, \TMstay\}$source.

The partial function $\delta$source is also called the transition function of $M$source.

Explain

We assume that the tape is infinite in one direction only. For this reason it is useful to designate a special symbol $\TMendtape$source as a marker for the left end of the tape. This makes it easier for Turing machine programs to tell when they're “in danger” of running off the tape. We could assume that this symbol is never overwritten, i.e., that $\delta(q,\TMendtape) = \tuple{q', \TMendtape, x}$source if $\delta(q,\TMendtape)$source is defined. Some textbooks do this, we do not. You can simply be careful when constructing your Turing machine that it never overwrites $\TMendtape$source. Moreover, there are cases where allowing such overwriting provides some convenient flexibility.

Turing machine example

Even Machine: The even machine is formally the quadruple $\tuple{Q, \Sigma, q_0, \delta}$source where

Explain

Recall tracing through the configurations of the even machine earlier. The imaginary mechanism consisting of tape, read/write head, and Turing machine program is really just an intuitive way of visualizing what a Turing machine computation is. Formally, we can define the computation of a Turing machine on a given input as a sequence of configurations---and a configuration in turn is a sequence of symbols (corresponding to the contents of the tape at a given point in the computation), a number indicating the position of the read/write head, and a state. Using these, we can define what the Turing machine $M$source computes on a given input.

Turing machine definition

[Configuration] A configuration of Turing machine $M = \tuple{Q, \Sigma, q_0, \delta}$source is a triple $\tuple{C, m, q}$source where

1. $C \in \Sigma^*$source is a finite sequence of symbols from $\Sigma$source,

2. $m \in \Nat$source is a number $< \len{C}$source, and

3. $q \in Q$source

Intuitively, the sequence $C$source is the content of the tape (symbols of all squares from the leftmost square to the last non-blank or previously visited square), $m$source is the number of the square the read/write head is scanning (beginning with $0$source being the number of the leftmost square), and $q$source is the current state of the machine.

Explain

The potential input for a Turing machine is a sequence of symbols, usually a sequence that encodes a number in some form. The initial configuration of the Turing machine is that configuration in which we start the Turing machine to work on that input: the tape contains the tape end marker immediately followed by the input written on the squares to the right, the read/write head is scanning the leftmost square of the input (i.e., the square to the right of the left end marker), and the mechanism is in the designated start state $q_0$source.

Turing machine definition

[Initial configuration] The initial configuration of $M$source for input $I \in \Sigma^*$source is

Explain

The $\frown$source symbol is for concatenation---the input string begins immediately to the left end marker.

Turing machine definition

We say that a configuration $\tuple{C, m, q}$source yields the configuration $\tuple{C', m', q'}$source in one step (according to $M$source), iff

1. the $m$source-th symbol of $C$source is $\sigma$source,

2. the instruction set of $M$source specifies $\delta(q, \sigma) = \tuple{q', \sigma', D}$source,

3. the $m$source-th symbol of $C'$source is $\sigma'$source, and

4. 1. $D = L$source and $m' = m - 1$source if $m>0$source, otherwise $m'=0$source, or

   2. $D = R$source and $m' = m + 1$source, or

   3. $D = N$source and $m' = m$source,

5. if $m' = \len{C}$source, then $\len{C'} = \len{C} + 1$source and the $m'$source-th symbol of $C'$source is $\TMblank$source. Otherwise $\len{C'}=\len{C}$source.

6. for all $i$source such that $i < \len{C}$source and $i \neq m$source, $C'(i) = C(i)$source,

Turing machine definition

A run of $M$source on input $I$source is a sequence $C_i$source of configurations of $M$source, where $C_0$source is the initial configuration of $M$source for input $I$source, and each $C_i$source yields $C_{i+1}$source in one step.

We say that $M$source halts on input $I$source after $k$source steps if $C_k = \tuple{C, m, q}$source, the $m$sourceth symbol of $C$source is $\sigma$source, and $\delta(q, \sigma)$source is undefined. In that case, the output of $M$source for input $I$source is $O$source, where $O$source is a string of symbols not ending in $\TMblank$source such that $C = \TMendtape \concat O \concat \TMblank^j$source for some $j \in \Nat$source. ($\TMblank^j$source is a sequence of $j$source $\TMblank$source's.)

Explain

According to this definition, the output $O$source of $M$source always ends in a symbol other than $\TMblank$source, or, if at time $k$source the entire tape is filled with $\TMblank$source (except for the leftmost $\TMendtape$source), $O$source is the empty string.

Explain

Turing machines work on sequences of symbols written on their tape. Depending on the alphabet a Turing machine uses, these sequences of symbols can represent various inputs and outputs. Of particular interest, of course, are Turing machines which compute arithmetical functions, i.e., functions of natural numbers. A simple way to represent positive integers is by coding them as sequences of a single symbol $\TMstroke$source. If $n \in \Nat$source, let $\TMstroke^n$source be the empty sequence if $n = 0$source, and otherwise the sequence consisting of exactly $n$source $\TMstroke$source's.

Turing machine definition

[Computation] A Turing machine $M$source computes the function $f\colon \Nat^k \to \Nat$source iff $M$source halts on input

with output $\TMstroke^{f(n_1, \dots, n_k)}$source.

Unsolved Turing machine exercise

Give a definition for when a Turing machine $M$source computes the function $f\colon \Nat^k \to \Nat^m$source.

Turing machine example

Addition: Let's build a machine that computes the function $f(n,m) = n + m$source. This requires a machine that starts with two blocks of $\TMstroke$source's of length $n$source and $m$source on the tape, and halts with one block consisting of $n+m$source $\TMstroke$source's. The two input blocks of $\TMstroke$source's are separated by a $\TMblank$source, so one method would be to write a stroke on the square containing the $\TMblank$source, and erase the last $\TMstroke$source.

Unsolved Turing machine exercise

Trace through the configurations of the machine from link to example Addition machine for input $\tuple{3,2}$source. What happens if the machine computes $0+0$source?

Explain

In link to example Doubler machine, we gave an example of a Turing machine that takes as input a sequence of $\TMstroke$source's and halts with a sequence of twice as many $\TMstroke$source's on the tape---the doubler machine. However, because the output contains $\TMblank$source's to the left of the doubled block of $\TMstroke$source's, it does not actually compute the function $f(x) = 2x$source, as you might have assumed. We'll describe two ways of fixing that.

Turing machine example

The machine in link to figure Machine computing doubling computes the function $f(x) = 2x$source. Instead of erasing the input and writing two $\TMstroke$source's at the far right for every $\TMstroke$source in the input as the machine from link to example Doubler machine does, this machine adds a single $\TMstroke$source to the right for every $\TMstroke$source in the input. It has to keep track of where the input ends, so it leaves a $\TMblank$source between the input and the added strokes, which it fills with a $\TMstroke$source at the very end. And we have to “remember” where we are in the input, so we temporarily replace a $\TMstroke$source in the input block by a $\TMblank$source.

Turing machine example

A second possibility for computing $f(x) = 2x$source is to keep the original doubler machine, but add states and instructions at the end which move the doubled block of strokes to the far left of the tape. The machine in link to figure Moving a block of strokes to the left does just this last part: started on a tape consisting of a block of $\TMblank$source's followed by a block of $\TMstroke$source's (and the head positioned anywhere in the block of $\TMblank$source's), it erases the $\TMstroke$source's one at a time and writes them at the beginning of the tape. In order to be able to tell when it is done, it first marks the end of the block of $\TMstroke$source's with a $\TMendtape$source symbol, which gets deleted at the end. We've started numbering the states at $q_6$source, so they can be added to the doubler machine. All you'll need is an additional instruction $\delta(q_0, \TMblank) = \tuple{q_6,\TMblank,\TMstay}$source, i.e., an arrow from $q_0$source to $q_6$source labelled $\TMtrans{\TMblank}{\TMblank}{\TMstay}$source. (There is one subtle problem: the resulting machine does not work for input $x=0$source. We'll leave this as an exercise.)

Unsolved Turing machine exercise

In link to example Mover machine we described a machine consisting of a combination of the doubler machine from link to figure Machine computing doubling and the mover machine from link to figure Moving a block of strokes to the left. What happens if you start this combined machine on input $x=0$source, i.e., on an empty tape? How would you fix the machine so that in this case the machine halts with output $2x=0$source? (You should be able to do this by adding one state and one transition.)

Unsolved Turing machine exercise

Subtraction: Design a Turing machine that when given an input of two non-empty strings of strokes of length $n$source and $m$source, where $n > m$source, computes the function $f(n,m) = n - m$source.

Unsolved Turing machine exercise

Equality: Design a Turing machine to compute the following function:

where $n$source and $m \in \PosInt$source.

Unsolved Turing machine exercise

Design a Turing machine to compute the function $\min(x,y)$source where $x$source and $y$source are positive integers represented on the tape by strings of $\TMstroke$source's separated by a $\TMblank$source. You may use additional symbols in the alphabet of the machine.

The function $\min$source selects the smallest value from its arguments, so $\min(3,5)=3$source, $\min(20,16)=16$source, and $\min(4,4)=4$source, and so on.

Turing machine definition

A Turing machine $M$source computes the partial function $f\colon \Nat^k \pto \Nat$source iff,

1. $M$source halts on input $\TMstroke^{n_1}\concat\TMblank\concat \dots \concat\TMblank\concat\TMstroke^{n_k}$source with output $\TMstroke^{m}$source if $f(n_1, \dots, n_k) = m$source.

2. $M$source does not halt at all, or with an output that is not a single block of $\TMstroke$source's if $f(n_1, \dots, n_k)$source is undefined.

Explain

Although we have defined our machines to halt only when there is no instruction to carry out, common representations of Turing machines have a dedicated halting state $h$source, such that $h \in Q$source.

The idea behind a halting state is simple: when the machine has finished operation (it is ready to accept input, or has finished writing the output), it goes into a state $h$source where it halts. Some machines have two halting states, one that accepts input and one that rejects input.

Turing machine example

Halting States. To elucidate this concept, let us begin with an alteration of the even machine. Instead of having the machine halt in state $q_0$source if the input is even, we can add an instruction to send the machine into a halting state.

Let us further expand the example. When the machine determines that the input is odd, it never halts. We can alter the machine to include a reject state by replacing the looping instruction with an instruction to go to a reject state $r$source.

Explain

Adding a dedicated halting state can be advantageous in cases like this, where it makes explicit when the machine accepts/rejects certain inputs. However, it is important to note that no computing power is gained by adding a dedicated halting state. Similarly, a less formal notion of halting has its own advantages. The definition of halting used so far in this chapter makes the proof of the Halting Problem intuitive and easy to demonstrate. For this reason, we continue with our original definition.

Explain

In section link to section Halting States, we considered Turing machines that have a single, designated halting state $h$source---such machines are guaranteed to halt, if they halt at all, in state $h$source. In this way, machines with a single halting state are more “disciplined” than we allow Turing machines in general to be. There are other restrictions we might impose on the behavior of Turing machines. For instance, we also have not prohibited Turing machines from ever erasing the tape-end marker on square $0$source, or to attempt to move left from square $0$source. (Our definition states that the head simply stays on square $0$source in this case; other definitions have the machine halt.) It is likewise sometimes desirable to be able to assume that a Turing machine, if it halts at all, halts on square $1$source.

Turing machine definition

A Turing machine $M$source is disciplined iff

1. it has a designated single halting state $h$source,

2. it halts, if it halts at all, while scanning square $1$source,

3. it never erases the $\TMendtape$source symbol on square $0$source, and

4. it never attempts to move left from square $0$source.

Explain

We have already discussed that any Turing machine can be changed into one with the same behavior but with a designated halting state. This is done simply by adding a new state $h$source, and adding an instruction $\delta(q, \sigma) = \tuple{h, \sigma, N}$source for any pair $\tuple{q,\sigma}$source where the original $\delta$source is undefined. It is true, although tedious to prove, that any Turing machine $M$source can be turned into a disciplined Turing machine $M'$source which halts on the same inputs and produces the same output. For instance, if the Turing machine halts and is not on square $1$source, we can add some instructions to make the head move left until it finds the tape-end marker, then move one square to the right, then halt. We'll leave you to think about how the other conditions can be dealt with.

Turing machine example

In link to figure Disciplined addition machine, we turn the addition machine from link to example Addition machine into a disciplined machine.

Turing machine proposition

For every Turing machine $M$source, there is a disciplined Turing machine $M'$source which halts with output $O$source if $M$source halts with output $O$source, and does not halt if $M$source does not halt. In particular, any function $f\colon\Nat^n \to \Nat$source computable by a Turing machine is also computable by a disciplined Turing machine.

Unsolved Turing machine exercise

Give a disciplined machine that computes $f(x) = x+1$source.

Unsolved Turing machine exercise

Find a disciplined machine which, when started on input $\TMstroke^n$source produces output $\TMstroke^n \concat \TMblank \concat \TMstroke^n$source.

Explain

The examples of Turing machines we have seen so far have been fairly simple in nature. But in fact, any problem that can be solved with any modern programming language can also be solved with Turing machines. To build more complex Turing machines, it is important to convince ourselves that we can combine them, so we can build machines to solve more complex problems by breaking the procedure into simpler parts. If we can find a natural way to break a complex problem down into constituent parts, we can tackle the problem in several stages, creating several simple Turing machines and combining them into one machine that can solve the problem. This point is especially important when tackling the Halting Problem in the next section.

How do we combine Turing machines $M = \tuple{Q, \Sigma, q_0, \delta}$source and $M' = \tuple{Q', \Sigma', q_0', \delta'}$source? We now use the configuration of the tape after $M$source has halted as the input configuration of a run of machine $M'$source. To get a single Turing machine $M \frown M'$source that does this, do the following:

1. Renumber (or relabel) all the states $Q'$source of $M'$source so that $M$source and $M'$source have no states in common ($Q \cap Q' = \emptyset$source).

2. The states of $M \frown M'$source are $Q \cup Q'$source.

3. The tape alphabet is $\Sigma \cup \Sigma'$source.

4. The start state is $q_0$source.

5. The transition function is the function $\delta''$source given by:

   $$\delta''(q,\sigma) = \begin{cases} \delta(q,\sigma) & \text{if $q \in Q$ and $\delta(q,\sigma)$ is defined}\\ \delta'(q,\sigma) & \text{if $q \in Q'$}\\ \tuple{q_0', \sigma, \TMstay} & \text{if $q \in Q$ and $\delta(q,\sigma)$ is undefined} \end{cases}$$source

The resulting machine uses the instructions of $M$source when it is in a state $q \in Q$source, the instructions of $M'$source when it is in a state $q \in Q'$source. When it is in a state $q \in Q$source and is scanning a symbol $\sigma$source for which $M$source has no transition (i.e., $M$source would have halted), it enters the start state of $M'$source (and leaves the tape contents and head position as it is).

Note that unless the machine $M$source is disciplined, we don't know where the tape head is when $M$source halts, so the halting configuration of $M$source need not have the head scanning square $1$source. When combining machines, it's important to keep this in mind.

Turing machine example

Combining Machines: We'll design a machine which, when started on input consisting of two blocks of $\TMstroke$source's of length $n$source and $m$source, halts with a single block of $2(m+n)$source $\TMstroke$source's on the tape. In order to build this machine, we can combine two machines we are already familiar with: the addition machine, and the doubler. We begin by drawing a state diagram for the addition machine.

Instead of halting in state $q_2$source, we want to continue operation in order to double the output. Recall that the doubler machine erases the first stroke in the input and writes two strokes in a separate output. Let's add an instruction to make sure the tape head is reading the first stroke of the output of the addition machine.

It is now easy to double the input---all we have to do is connect the doubler machine onto state $q_4$source. This requires renaming the states of the doubler machine so that they start at $q_4$source instead of $q_0$source---this way we don't end up with two starting states. The final diagram should look as in link to figure Combining adder and doubler machines.

Turing machine proposition

If $M$source and $M'$source are disciplined and compute the functions $f\colon \Nat^k \to \Nat$source and $f'\colon \Nat \to \Nat$source, respectively, then $M \frown M'$source is disciplined and computes $\comp{f}{f'}$source.

Proof

Since $M$source is disciplined, when it halts with output $f(n_1,\dots,n_k) = m$source, the head is scanning square $1$source. If we now enter the start state of $M'$source, the machine will halt with output $f'(m)$source, again scanning square $1$source. The other conditions of link to definition Disciplined Turing machine are also satisfied.

Unsolved Turing machine exercise

Give a disciplined Turing machine computing $f(x) = x+2$source by taking the machine $M$source from link to exercise Disciplined successor machine and construct $M \frown M$source.

Turing machine definition

[Church--Turing thesis] The Church--Turing Thesis states that anything computable via an effective procedure is Turing computable.