Chapter 28 of 34

Variants of Turing Machines

When we met finite automata, adding nondeterminism changed nothing (NFA = DFA in power). With pushdown automata, it mattered (DPDAs are weaker than PDAs). So it is natural to ask about Turing machines: if we give a TM extra features (more tapes, several heads, a two-dimensional tape, nondeterministic choices), does it become able to accept new languages?

The surprising and very important answer is no. Every reasonable extension can be simulated by the plain single-tape TM of Turing Machines; it may be slower, but it accepts the same languages. Even some restrictions (a tape infinite in only one direction, or just two stacks, or just two counters) keep the full power.

Two kinds of machines are equivalent if they accept the same class of languages. All the standard variants of Turing machines (stay option, one-way or two-way infinite tape, multiple tracks, multiple tapes, multiple heads, multidimensional tape, nondeterminism, two-stack machines, two-counter machines, enumerators) are equivalent to the standard TM: they all accept exactly the recursively enumerable languages.

This robustness is the main evidence for the Church–Turing thesis, discussed at the end. The two-tape machine in this chapter was simulated and tested on all strings up to length 12, and the TM encoding was generated by a program.


How Equivalence Is Proved

To show variant V is equivalent to the standard TM we prove two directions:

  1. Standard TM → V. Usually trivial, because the standard TM is a special case of V (a multitape TM that ignores its extra tapes is a single-tape TM).

  2. V → standard TM. The real work: show that a standard TM can simulate every move of V, by storing V's whole configuration on its own tape in some encoded form.

Equivalence is about which languages can be accepted, not about speed. Simulation often costs extra time, and we will track how much.


1. TM with a Stay Option

Allow δ(q, X) = (p, Y, S), where S means "do not move".

Simulation: replace each stay move δ(q, X) = (p, Y, S) by δ(q, X) = (r, Y, R), where r is a new state, and add δ(r, Z) = (p, Z, L) for every tape symbol Z. The head goes right and comes straight back. Time at most doubles.


2. Multi-Track TM

The tape is divided into k tracks; each cell holds a k-tuple of symbols, and the single head reads all k symbols of a cell at once.

track 1:  | a | b | b | a | B |
track 2:  | B | X | B | B | B |        one head reads a whole column,
track 3:  | 1 | 0 | 0 | 1 | B |        e.g. (b, X, 0)
                ▲

This is not even a real extension: a k-tuple is just one symbol of a bigger alphabet Γ' = Γ1 × Γ2 × ... × Γk. So a multi-track TM is a standard TM with a cleverly chosen alphabet. Tracks are a design convenience: one track keeps the input, another holds marks or a work area.


3. Semi-Infinite vs Two-Way Infinite Tape

Some books use a tape infinite in both directions, others a tape with a left end (the head simply cannot move left of cell 0). Both are equivalent.

  • Semi-infinite → two-way: put a special end marker just left of the input and never move past it.

  • Two-way → semi-infinite: fold the tape in half using two tracks. The upper track holds cells 0, 1, 2, ...; the lower track holds cells −1, −2, −3, ...; cell 0 of the lower track holds a marker *. The finite control remembers which track the head is on; on the lower track, the meaning of L and R is swapped.

Two-way tape:    ... c-3 c-2 c-1 | c0 c1 c2 c3 ...

Folded:   upper:  c0   c1   c2   c3  ...
          lower:  *    c-1  c-2  c-3 ...

4. Multitape TM

A k-tape TM has k tapes, each with its own independently moving head. The input starts on tape 1; the other tapes start blank. One move depends on the state and all k scanned symbols:

δ : Q × Γ^k → Q × Γ^k × {L, R, S}^k

Example: a 2-tape TM for {anbn : n ≥ 1} in linear time

Idea: copy each a onto tape 2 as an X (tape 2 works like a stack), then for each b move back over one X. Accept if both run out together.

State

(tape 1, tape 2) read

Write

Moves

Next

→ s

(a, B)

(a, X)

(R, R)

p

p

(a, B)

(a, X)

(R, R)

p

p

(b, B)

(b, B)

(S, L)

m

m

(b, X)

(b, X)

(R, L)

m

m

(B, B)

(B, B)

(S, S)

f (accept)

Trace on aabb (head positions counted from the first input cell = 0):

Step

State

Tape 1 head

Tape 2 contents

Tape 2 head

0

s

0 (a)

empty

0 (B)

1

p

1 (a)

X

1 (B)

2

p

2 (b)

XX

2 (B)

3

m

2 (b)

XX

1 (X)

4

m

3 (b)

XX

0 (X)

5

m

4 (B)

XX

−1 (B)

6

f

accept

XX

-

On anbn this machine makes 2n + 2 moves (4, 6, 8, 10, ... for n = 1, 2, 3, 4). The single-tape zig-zag machine from Turing Machines needed 2n2 + 2n + 1 moves (5, 13, 25, 41, ...). Rejections also work: on aabbb tape 2 runs out while tape 1 still shows b; on abab, after one b the machine sees (a, B) in state m and has no move.

Simulating k tapes with one tape

Theorem: every multitape TM has an equivalent single-tape TM. If the multitape TM makes t moves, the single-tape simulation makes O(t2) moves.

Construction: use a single tape with 2k tracks. For each tape i, one track holds tape i's contents and the track below it holds a single marker ↑ showing where head i is.

track 1 (tape 1):   a   a   b   b
track 2 (head 1):           ↑
track 3 (tape 2):   X   X
track 4 (head 2):       ↑

To simulate one move of the k-tape machine:

  1. Sweep from left to right, visiting all head markers, and remember the k scanned symbols in the finite control (k symbols is a finite amount of information).

  2. Now δ of the multitape TM is known. Sweep again, and at each marker write the new symbol and move the marker one cell left or right.

  3. Update the state stored in the finite control.

Why O(t2): after t moves no head is more than t cells from its start, so the markers lie within a region of about 2t cells. Each simulated move needs a constant number of sweeps over that region: O(t) moves. t simulated moves cost O(t) · t = O(t2). The slowdown is only polynomial, which is why multitape TMs are used to define complexity classes like P.


5. Nondeterministic TM (NTM)

In an NTM, δ gives a finite set of possible moves:

δ : Q × Γ → finite subsets of  Q × Γ × {L, R}

The NTM accepts w if at least one sequence of choices leads to a final state. Branches that reject or loop forever do not matter if some branch accepts.

Example (guess and check): L = {1n : n is composite}. An NTM can nondeterministically write two numbers p ≥ 2 and q ≥ 2 on a work area, multiply them (deterministically), and compare the product with n. If n is composite, some branch guesses the right factors and accepts. A deterministic machine would have to try factors one by one.

Simulating an NTM by a DTM

Theorem: for every NTM N there is a DTM D with L(D) = L(N).

The computations of N on w form a tree: the root is the start ID, and each ID has at most r children, where r is the largest number of choices in any δ entry. N accepts iff some node of the tree is an accepting ID.

                   q0 w                     depth 0
              /      |       \
           ID1      ID2      ID3            depth 1   (at most r children each)
          /   \      |      /  |  \
       ...    ...   ...   ...  ACCEPT ...   depth 2

D searches this tree breadth-first (level by level), never depth-first. Depth-first search could follow an infinite rejecting branch forever and never reach an accepting node on another branch. Breadth-first search reaches every node at depth d after finitely many steps, so if an accepting ID exists at any depth, D finds it.

A standard way to organise this is a 3-tape DTM: tape 1 keeps the input untouched; tape 2 holds an address, a string over {1, ..., r} such as 2 3 1 meaning "take choice 2, then 3, then 1"; tape 3 is a scratch copy of N's tape. For each address in the order ε, 1, 2, ..., r, 11, 12, ... (shorter first), D copies the input to tape 3 and runs N following those choices. Then the 3-tape DTM is converted to a single-tape DTM as above.

Cost: if N accepts in t steps, the tree up to depth t has at most 1 + r + r2 + ... + rt nodes, so D needs time 2O(t). Nobody knows a simulation with only polynomial slowdown; whether polynomial-time NTMs can be simulated by polynomial-time DTMs is the famous P vs NP question (see Complexity Classes: P, NP & NP-Complete).


6. Other Extensions

  • Multi-head TM: one tape, several heads. Simulate by marking each head position on extra tracks, just like the multitape simulation.

  • Multidimensional TM: a 2-D grid tape with moves up, down, left, right. Simulate by writing the used rectangle of the grid row by row on a 1-D tape with row separators (rows can be padded as the rectangle grows).

  • Offline TM: a read-only input tape plus a work tape. Copy the input to a work tape and it becomes an ordinary multitape TM.

None adds power; each costs at most a polynomial slowdown.


7. Restricted Machines That Are Still Universal

Two-stack machines

A PDA has one stack and accepts only CFLs. Give it a second stack and it becomes as powerful as a TM.

Simulating a TM tape with two stacks: stack L holds everything to the left of the head (nearest cell on top); stack R holds the scanned cell and everything to its right (scanned cell on top).

TM ID:   a b  q  c d                       head on c

stack L (top at right):   a b              stack R (top at left):   c d

Move δ(q, c) = (p, Y, R):  pop c from R, push Y on L       L: a b Y      R: d
Move δ(q, c) = (p, Y, L):  pop c from R, push Y on R,
                           pop b from L, push b on R       L: a          R: b Y d
(If R becomes empty, treat its top as B: the tape is blank there.)

Each TM move becomes a constant number of stack operations, so two stacks = one tape. Conversely a TM easily simulates two stacks on two tracks. This is why a "PDA with two stacks" accepts all recursively enumerable languages.

Counter machines

A counter is a stack with only one symbol above the bottom marker: it holds a natural number and the machine can add 1, subtract 1 and test for zero.

Number of counters

Power

1 counter

strictly weaker than a PDA (it accepts anbn, but not, for example, even palindromes)

2 counters

equivalent to a TM (Minsky)

3 or more

equivalent to a TM

Idea: a stack over an alphabet of size m − 1 can be stored as a single number in base m, and pushing or popping becomes multiplying or dividing by m. Two stacks need two such numbers plus one scratch counter to do the multiplication and division, giving three counters. A further trick packs the three counter values i, j, k into one number 2i3j5k (incrementing j means multiplying by 3, testing k = 0 means checking divisibility by 5, and so on), with one more counter as scratch space, giving two counters.


8. Enumerators

An enumerator is a TM with an attached printer (an output tape). It starts with a blank tape, runs (possibly forever) and occasionally prints a string. The language it enumerates is the set of all strings it ever prints, in any order, possibly with repetitions.

Theorem: a language is recursively enumerable (accepted by some TM) if and only if some enumerator enumerates it. This is where the name "recursively enumerable" comes from.

  • Enumerator E → TM M: on input w, run E; whenever E prints a string, compare it with w; accept if they are equal. (If w is never printed, M runs forever, which is allowed.)

  • TM M → enumerator E: we cannot simply run M on s1, then s2, ..., because M might loop forever on s1. Instead use dovetailing: for i = 1, 2, 3, ..., run M for i steps on each of s1, ..., si, and print every sj that is accepted. Each accepted string is accepted within some number k of steps, so it gets printed in round max(j, k).


9. The Universal Turing Machine

So far each TM has done one fixed job. Turing's great insight was that one machine can run any machine, given its description as input, exactly like a computer that runs any program.

Encoding a TM as a binary string

Using the convention from Hopcroft–Motwani–Ullman: number the states q1, q2, ..., with q1 the start state and q2 the only final state; number the tape symbols X1 = 0, X2 = 1, X3 = B; number the directions D1 = L, D2 = R. A transition δ(qi, Xj) = (qk, Xl, Dm) is encoded as

0^i 1 0^j 1 0^k 1 0^l 1 0^m

Each part is non-empty, so a single 1 separates the parts and never two 1s appear in a row. The whole TM is the list of its transition codes separated by 11.

Worked example. A TM with four transitions:

Transition

i, j, k, l, m

Code

δ(q1, 0) = (q3, 1, R)

1, 1, 3, 2, 2

0 1 0 1 000 1 00 1 00

δ(q3, 1) = (q2, 1, L)

3, 2, 2, 2, 1

000 1 00 1 00 1 00 1 0

δ(q3, B) = (q1, 0, L)

3, 3, 1, 1, 1

000 1 000 1 0 1 0 1 0

δ(q1, 1) = (q1, 1, R)

1, 2, 1, 2, 2

0 1 00 1 0 1 00 1 00

Code of M = 0101000100100 11 00010010010010 11 0001000101010 11 010010100100
          = 0101000100100110001001001001011000100010101011010010100100

A pair (M, w) is encoded as the code of M, then 111, then w. Many different strings encode the same TM (the transitions can be listed in any order), and not every binary string is a valid code; by convention an invalid code stands for a TM with no moves, which accepts nothing.

How the UTM works

The universal Turing machine U takes ⟨M, w⟩ and accepts exactly when M accepts w. Conveniently it uses several tapes (then converted to one):

  1. Tape 1 holds ⟨M, w⟩ (the "program").

  2. Tape 2 holds M's simulated tape, with each symbol Xj written as 0j and cells separated by 1.

  3. Tape 3 holds M's current state qi as 0i.

  4. For each step: read the state on tape 3 and the symbol under head 2, search tape 1 for the transition starting 0i1 0j1, then rewrite the cell, move head 2 and update tape 3. If no transition matches, M halts and U halts too; U accepts if the state is q2.

U accepts the universal language Lu = {⟨M, w⟩ : M accepts w}. It is recursively enumerable, and in Halting Problem & Undecidability we will show it is not recursive. The UTM is the theoretical blueprint of the stored-program computer: one fixed machine whose behaviour is set by the program in its memory.


10. The Church–Turing Thesis

Church–Turing thesis: every function that can be computed by an algorithm (an effective, step-by-step mechanical procedure) can be computed by a Turing machine.

It is a thesis, not a theorem, because "algorithm" is an informal notion and cannot be proved equal to a mathematical one. The evidence is strong:

  • All the variants in this chapter, stronger-looking or weaker-looking, accept the same class.

  • Completely different formalisms invented independently (Church's λ-calculus, Gödel–Kleene recursive functions, Post systems, unrestricted grammars, register machines, and every real programming language) compute exactly the same functions as TMs.

  • No one has found an effective procedure that a TM cannot imitate.

The thesis is about what can be computed, not how fast. (Quantum computers, for example, compute nothing a TM cannot, though they may be faster for some problems.)


All Variants at a Glance

Variant

Power vs standard TM

Simulation cost on standard TM

Stay option (L, R, S)

Same

at most 2× moves

Multi-track

Same (it is a standard TM with a product alphabet)

none

Semi-infinite tape

Same

constant factor

k tapes

Same

O(t2)

Multi-head, 2-D tape

Same

polynomial

Nondeterministic

Same

exponential, 2O(t) (best known)

Two stacks

Same

constant factor

Two counters

Same

exponential

One stack (PDA)

Weaker (CFLs only)

-

One counter

Weaker (a proper subset of the CFLs)

-

Tape restricted to the input length (LBA)

Weaker (context-sensitive languages)

-

Enumerator

Same (enumerates exactly the RE languages)

-

The LBA is the subject of Chomsky Hierarchy & Linear Bounded Automata.


Common Mistakes

  • "A multitape TM can accept more languages." No. It is faster, not more powerful.

  • "Nondeterminism adds power to TMs, as it does to PDAs." No. NTM = DTM in power (as with finite automata). Among the machines in this course, the PDA is the one where nondeterminism is known to add power (for linear bounded automata the question is still open).

  • Simulating an NTM by depth-first search. One infinite branch would trap the search. Breadth-first (or iterative deepening) is required.

  • Thinking a PDA with two stacks is "a better PDA". It is a full Turing machine.

  • Calling the Church–Turing thesis a theorem. It cannot be proved; it relates an informal concept to a formal one.

  • Equating "same power" with "same speed". Equivalence ignores time; the NTM simulation, for instance, is exponentially slower as far as anyone knows.


Practice and GATE-Style Questions

Q1. Which of the following accept exactly the recursively enumerable languages: (a) 2-tape DTM (b) NTM (c) PDA with two stacks (d) PDA with one stack and one counter (e) machine with two counters?

All five. (a), (b), (c) and (e) are covered in this chapter. For (d): a counter is a restricted stack, so a stack plus a counter is a two-stack machine with one stack limited to one symbol. Since two counters alone already reach full TM power and a stack can simulate a counter, a stack plus a counter can simulate two counters, so (d) is also TM-equivalent. All five accept exactly the RE languages.

Q2. A 3-tape TM decides a language in time O(n). What bound does the standard single-tape simulation give?

O(t2) with t = O(n), so O(n2).

Q3. An NTM has at most 3 choices per move and accepts w in 10 steps on some branch. In the worst case, how many IDs does a breadth-first simulation examine up to depth 10?

1 + 3 + 32 + ... + 310 = (311 − 1)/2 = 88,573. This is the source of the exponential slowdown.

Q4. Using the encoding above, write the code for δ(q2, B) = (q4, 0, R).

i = 2, j = 3 (B = X3), k = 4, l = 1 (0 = X1), m = 2 (R): 00 1 000 1 0000 1 0 1 00 = 0010001000010100.

Q5. Why can't the enumerator for an RE language simply run M on s1, s2, s3, ... one after another?

If M loops forever on some si that is not in L, the enumerator never gets to si+1, si+2, ..., and strings of L after si are never printed. Dovetailing runs every string for a bounded number of steps per round, so no single loop blocks progress.

Q6. Interview: if multitape TMs are no more powerful, why do textbooks use them?

They make designs much simpler (separate tapes for input, counters and scratch work), and their running times are polynomially related to single-tape times, so classes like P and NP come out the same whichever model you use.


Summary

  • The Turing machine model is robust: stay option, multiple tracks, semi-infinite tape, multiple tapes, multiple heads, 2-D tapes and nondeterminism all give the same power.

  • k-tape → 1-tape simulation costs O(t2); NTM → DTM by breadth-first search over the computation tree costs 2O(t).

  • A machine with two stacks, or with two counters, is as powerful as a TM; with one stack it is a PDA, with one counter even weaker.

  • A language is RE iff some enumerator lists it; dovetailing turns a TM into an enumerator.

  • A TM can be encoded as a binary string (0i10j10k10l10m per move, separated by 11), and the universal TM runs any encoded TM on any input.

  • The Church–Turing thesis: TMs capture everything that is algorithmically computable.

Extra tapes, heads, dimensions and guesses make Turing machines faster or easier to program, never more powerful. That stubborn sameness is why the Turing machine is accepted as the definition of "computable".