This presentation examines various extensions to the standard Turing machine model and establishes their equivalence to the standard model. These extensions include the multi-tape, nondeterministic, and oracle Turing machines. Before we get into those extensions, let's review the basic concept of Turing machine.

In 1936 Alan Turing, a British Mathematician, came up with an idea for an imaginary machine that could carry out all kinds of computations on numbers and symbols. A Turing machine is an abstract representation of a computing device. The Turing Machine consists of

• an Input/Output Tape,
• the Turing Machine itself,
• and a Rule List

The Input/Output Tape is divided into cells. The cells contain the input and output symbols and change frequently as a program is running. The standard TM usually contains only a single tape.

The Turing Machine consists of a read/write head that scans the Input/Output Tape. Computation begins with the machine, in a given "state", scanning a cell. If a binary machine is considered, it erases what it finds there, prints a 0 or 1, moves to an adjacent cell, and goes into a new state. This behavior is completely determined by three parameters:

• the state the machine is in,
• the number on the cell it is scanning, and
• a table of instructions.

The table of instructions specifies, for each state and binary input, what the machine should write, which direction it should move in, and which state it should go into. (E.g., "If in State 1 scanning a 0: print 1, move left, and go into State 3".) The table can list only finitely many states, each of which becomes implicitly defined by the role it plays in the table of instructions. These states are often referred to as the "functional states" of the machine.

A Turing machine, therefore, is more like a computer program (software) than a computer (hardware). Any given Turing machine can be realized or implemented on an infinite number of different physical computing devices. Computer scientists and logicians have shown that Turing machines -- given enough time and tape -- can compute any function that any conventional digital computers can compute.

A k-tape (deterministic) Turing machine has k tapes rather than 1 as in the standard model mentioned above. A multi-tape Turing machine has a finite number of tapes, each with it's own independently controlled tape head. See Figure 5.4 on text p214.

Theorem 5.2.1 (below) shows that every multi-tape Turing machine Mk has an equivalent single-tape Turing machine, M1.

Theorem 5.2.1 For each k-tape TM Mk there is a one-tape TM M1 such that a terminating T-step computation by Mk can be simulated in O(T^2) steps by M1.

This theorem is proved by simulation. See test on page 213.

In the proof, the tape alphabet of M1 is larger than that of Mk. A natural question is whether this is necessary. In fact, a Turing machine with tape alphabet equal to {0,1,blank} can simulate M1: since the tape alphabet of M1 is finite, say of size k, then one can uniquely represent each symbol in Mk's tape alphabet using log k bits (rounded up to the next integer). Therefore, by using log k tape cells rather than one tape cell, one can represent each symbol on (M1)'s tape.

In fact, even if the tape alphabet of M1 contains only one symbol, say a, other than the blank symbol, one can represent each tape symbol of M1 uniquely by a sequence of a's. In this case, approximately k tape cells may be needed to represent a single tape symbol of M1.

The conclusion is that multi-tape Turing machines are equivalent to standard Turing machines.

It's defined as:

Definition 5.2.1 A Nondeterministic Turing machine (NTM) is a 7-tuple M=(S, T, B, Q, d, s, h) where S is the choice input alphabet, T is the tape alphabet not containing the blank symbol B, Q is the set if states, d is the next state function (explained later), s is the initial state, and h not in Q is the accepting halt state. A TM cannot exit from h.

In a nondeterministic Turing machine (NTM), there may be several possible transitions corresponding to a given state and input symbol. Nondeterministic Turing machines can be considered to be language-recognizers or language-deciders, just like deterministic Turing machines. We say a NTM N decides language L if

(i) for all strings x in L, there is a sequence of configurations C1, C2, ..., Ck where C1 is the initial configuration of N on input x, Ci yields C(i+1) for each i between 1 and k-1, and Ck is an accepting configuration, and

(ii) for all strings x not in L, all possible computations of N are finite, that is, there does not exist an infinite sequence C1, C2, ..., Ck such that C1 is the initial configuration of N on x and for all i, Ci yields C(i+1).

In contrast, a NTM can recognize a language L without halting on all computation paths.

It turns out that every nondeterministic Turing machine can be simulated by a deterministic Turing machine (DTM):

We can prove that for every NTM N there is a DTM D such that

(i) if L is recognized by N then L is also recognized by D,

(ii) if L is decided by N then L is decided by D.

Or more formal:

Theorem 5.2.2 Any language accepted by a nondeterministic standard TM can be accepted by a standard deterministic one.

This provides more evidence that the determinstic Turing machine is a powerful model of computation.

The oracle Turing machine (OTM) is a multi-tape DTM or NDTM with a special oracle tape and an associated oracle function h, which need not be computable.

One of the most fascinating of Turing's lesser-known constructs is that of the "o-machine". An o-machine, wrote Turing in his doctoral thesis, had a black box that could compute the uncomputable. Positing the o (for oracle) box, Turing could show that theoretically, o machines could solve the unsolvable problems that Turing machines could not.

In short, if o machines are possible, then things that are currently thought to be impossible, are doable. Computing, and the world, could quickly be turned on their respective heads.

The o machine works this way. Say you want to know if a given computer program will run forever or halt, a problem that is intractable on modern computers given the current state of the art.

A computer program consists of a long string of ones and zeroes, and can be viewed as a number. Any string of ones and zeroes is a binary number, and can be represented as an integer.

Now, imagine a memory device of some type that is storing a certain special number. This number is irrational, that is to say, it can be written as an infinite string of digits, and it is binary. It might be written as 0.1010010110... A very important property of this number is that each individual number represents which programs will terminate, and which will not.

So, if a program were represented by the number 7,687,684,959, one would only have to look at the 7,687,684,959th digit of the special number, and the problem would be solved. A zero might stand for "does not terminate", and a one might mean "terminates".

The "oracle" would simply be the device that performs this task of finding the proper digit. Obviously, if the special number doesn't exist, the oracle wouldn't be able to do its job, and it's far from clear if such a number does or could exist.

It should be noted that Turing never specified the workings of the oracle box, but, neither did he ever specify the workings of the Turing machine. He concentrated on the theoretical plain, leaving later generations to work out the details. In fact, many software Turing machines have been created, including Java applets that run in browsers. The oracle comparator would be a relatively simple software construct.

That computers are ubiquitous, shows that the details of building practical Turing machines were relatively straightforward. One begins to wonder if the o machine might be an attainable goal as well.

O machines could perform tasks that Turing called hypercomputing, for machines that could go far beyond the capabilities of extant computers. That the human brain routinely goes far beyond the capabilities of even the most advanced computers, is, in the mind of some, an indications that o machines, and hypercomputing are possible.

Modern computers, no matter how powerful, have great difficulty doing tasks, like recognizing a face, that even a small child can do easily. One could take the view that, if a human brain is a naturally occurring instance of an o machine, given its great power, then Turing's special number must exist. If that's all true, then, like the Turing machine, the only trick remaining is to work out the details.

Two automata are said to be equivalent if they accept the same language. Let's use a somewhat more general definition: two transducers are equivalent if they compute the same function.

A class of automata (e.g. standard Turing machines) is equivalent to another class of automata (e.g. nondeterministic Turing machines) if, for each transducer in one class, an equivalent transducer can be found in the other class.

Then we have the following equivalents:

(1) At each move of a Turing machine, the tape head may move either left or right. We may augment this with a stay option: we will add "don't move" to the set {L, R}.

Theorem. Turing machines with a stay option are equivalent to standard Turing machines.

 (2) An n-track Turing machine is one in which each square of the tape holds an ordered n-tuple of symbols from the tape alphabet. You can think of this as a Turing machine with multiple tape heads, all of which move in lock-step mode.

Theorem. N-track Turing machines are equivalent to standard Turing machines.

(3) A Turing machine may have a semi-infinite tape; the nonblank input is at the extreme left end of the tape.

Theorem. Turing machines with semi-infinite tape are equivalent to standard Turing machines.

(4) An off-line Turing machine has two tapes. One tape is read-only and contains the input; the other is read-write and is initially blank.

Theorem. Off-line Turing machines are equivalent to standard Turing machines.

(5) A multidimensional Turing machine has a multidimensional "tape;" for example, a two-dimensional Turing machine would read and write on an infinite plane divided into squares, like a checkerboard. Possible directions that the tape head could move might be labeled {N, E, S, W}. A three-dimensional Turing machine might have possible directions {N, E, S, W, U, D}, and so on.

Theorem. Multidimensional Turing machines are equivalent to standard Turing machines.

(6) A binary Turing machine is one whose tape alphabet consists of exactly two symbols.

Theorem. Binary Turing machines are equivalent to standard Turing machines.

(7) A two-state Turing machine is one that has only two states. (It makes up for this by having a large, albeit finite, alphabet.)

Theorem. Two-state Turing machines are equivalent to standard Turing machines.

This Turing machine model is more powerful in several ways than FA's and PDA's.

First, the input head can move both forwards and backwards on the tape of the machine. Second, symbols can be written to the tape as well as read from the tape. Thus, a Turing machine has random access memory. Third, the tape has an infinite number of blank tape cells following the initial input, providing the machine with unlimited storage.

A Turing machine has a special accept state and a special reject state. Once the machine enters one of these states, the decision of whether to accept or reject the input is irreversible. Also, when a transition requires that the input head be moved left when the head happens to be on the leftmost character of the input, the convention is that the head just stays where it is.

The finite-state machine can be viewed as a Turing machine with two tapes, the first a read-only tape and the second a write-only output tape.

A Turing machine is a lot like a pushdown automaton. Both have a finite-state machine as a central component; both have additional storage. But where a pushdown automaton uses a stack for storage, a Turing machine uses a tape, which is considered to be infinite in both directions. The tape consists of a series of squares, each of which can hold a single symbol. The tape head, or read-write head, can read a symbol from the tape, write a symbol to the tape, and move one square in either direction.

The PAD can be viewed as a Turing machine with two tapes, a read-only input tape and a pushdown tape.