Models of Computation

Lecture 6: Turing Machines [Fa’16]

Think globally, act locally.
— Attributed to Patrick Geddes (c.1915), among many others.
We can only see a short distance ahead,but we can see plenty there that needs to be done.
— Alan Turing, “Computing Machinery and Intelligence” (1950)
Never worry about theory
as long as the machinery does what it’s supposed to do.
— Robert Anson Heinlein, Waldo & Magic, Inc. (1950)
It is a sobering thought that when Mozart was my age,he had been dead for two years.
— Tom Lehrer, introduction to “Alma”, That Was the Year That Was (1965)

6

Turing Machines

In 1936, a few months before his 24th birthday, Alan Turing launched computer science as amodern intellectual discipline. In a single remarkable paper, Turing provided the following
results:• A simple formal model of mechanical computation now known as Turing machines.
• A description of a single universal machine that can be used to compute any function
computable by any other Turing machine.
• A proof that no Turing machine can solve the halting problem—Given the formal descriptionof an arbitrary Turing machine M , does M halt or run forever?
• A proof that no Turing machine can determine whether an arbitrary given proposition
is provable from the axioms of first-order logic. This is Hilbert and Ackermann’s famous
Entscheidungsproblem (“decision problem”).
• Compelling arguments1 that his machines can execute arbitrary “calculation by finite
means”.
Although Turing did not know it at the time, he was not the first to prove that the Entscheidungsproblem had no algorithmic solution. The first such proof is implicit in the work of Kurt
Gödel; in lectures on his incompleteness theorems2 at Princeton in 1934, Gödel described amodel of general recursive functions, which he largely credited to Jacques Herbrand.3 Gödel’s
incompleteness theorem can be viewed as a proof that some propositions cannot be proved using
general recursive functions. However, Gödel viewed his definition as a “heuristic principle” rather
than an accurate model of effective computation, or even a complete definition of recursion.
The first published proof was written by Alonzo Church and published just a new months
before Turing’s paper, using another different model of computation, now called the untyped
λ-calculus. Turing and Church developed their results independently; indeed, Turing rushed
1As Turing put it, “All arguments which can be given are bound to be, fundamentally, appeals to intuition, and forthis reason rather unsatisfactory mathematically.” The claim that anything that can be computed can be computing
using Turing machines is now known as the Church-Turing thesis.
2which he published at the ripe old age of 25
3Herbrand was a brilliant French mathematician who was killed in a mountain-climbing accident at the age of 23.
© Copyright 2018 Jeff Erickson.
This work is licensed under a Creative Commons License (http://creativecommons.org/licenses/by-nc-sa/4.0/).
Free distribution is strongly encouraged; commercial distribution is expressly forbidden.
See http://jeffe.cs.illinois.edu/teaching/algorithms/ for the most recent revision.

1Models of Computation

Lecture 6: Turing Machines [Fa’16]

the submission of his own paper immediately after receiving a copy of Church’s paper, pausing
only long enough to prove that any function computable via λ-calculus can also be computedby a Turing machine and vice versa.⁴ Church was the referee for Turing’s paper; between thepaper’s submission and its acceptance, Turing was admitted to Princeton as a PhD student, where
Church became his advisor. He finished his PhD two years later.
Informally, Turing described an abstract machine with a finite number of internal states thathas access to “memory” in the form of a tape. The tape consists of a semi-infinite sequence ofcells, each containing a single symbol from some arbitrary finite alphabet. The Turing machine
can access the tape only through its head, which is positioned over a single cell. Initially, the tapecontains an arbitrary finite input string followed by an infinite sequence of blanks, and the headis positioned over the first cell on the tape. In a single iteration, the machine reads the symbol inthat cell, possibly write a new symbol into that cell, possibly changes its internal state, possibly
moves the head to a neighboring cell, and possibly halts. The precise behavior of the machine ateach iteration is entirely determined by its internal state and the symbol that it reads. When themachine halts, it indicates whether it has accepted or rejected the original input string.
Write O
Move left

T O R T U R I N G M A C H I N E
Write N
Move rightT O R T U R I N G M A C H I N E
Write U
Move rightN O R T U R I N G M A C H I N E
Halt and
accept!

N U R T U R I N G M A C H I N E
A few iterations of a six-state Turing machine.

6.1

Why Bother?

Students used to thinking of computation in terms of higher-level operations like random memory
accesses, function calls, and recursion may wonder why we should even consider a model as
simple and constrained as Turing machines. Admittedly, Turing machines are a terrible modelfor thinking about fast computation; simple operations that take constant time in the standard
⁴At roughly the same time as Turing’s paper, Church and his more recent PhD graduate Steven Kleene independently
proved that all general recursive functions are definable in the λ-calculus and vice versa. At the time, Kleene was 27,
and Church was 33.

2Models of Computation

Lecture 6: Turing Machines [Fa’16]

random-access model can require arbitrarily many steps on a Turing machine. Worse, seemingly
minor variations in the precise definition of “Turing machine” can have significant impact on
problem complexity. As a simple example (which will make more sense later), we can reversea string of n bits in O(n) time using a two-tape Turing machine, but the same task provably
requires Ω(n2 ) time on a single-tape machine.
But here we are not interested in finding fast algorithms, or indeed in finding algorithms
at all, but rather in proving that some problems cannot be solved by any computational means.
Such a bold claim requires a formal definition of “computation” that is simple enough to support
formal argument, but still powerful enough to describe arbitrary algorithms. Turing machines
are ideal for this purpose. In particular, Turing machines are powerful enough to simulate other
Turing machines, while still simple enough to let us build up this self-simulation from scratch,
unlike more complex but efficient models like the standard random-access machine(Arguably, self-simulation is even simpler in Church’s λ-calculus, or in Schönfinkel andCurry’s combinator calculus, which is one of many reasons those models are more common in thedesign and analysis of programming languages than Turing machines. Those models are much
more abstract; in particular, they are harder to show equivalent to standard iterative models ofcomputation.)

6.2

Formal Definitions

Formally, a Turing machine consists of the following components. (Hang on; it’s a long list.)• An arbitrary finite set Γ with at least two elements, called the tape alphabet.
• An arbitrary symbol  ∈ Γ , called the blank symbol or just the blank.
• An arbitrary nonempty subset Σ ⊆ (Γ \ {}), called the input alphabet.
• Another arbitrary finite set Q whose elements are called states.
• Three distinct special states start, accept, reject ∈ Q.
• A transition function δ : (Q \ {accept, reject}) × Γ → Q × Γ × {−1, +1}.
A configuration or global state of a Turing machine is represented by a triple (q, x, i) ∈Q ×Γ ∗ ×N, indicating that the machine’s internal state is q, the tape contains the string x followedby an infinite sequence of blanks, and the head is located at position i. Trailing blanks in thetape string are ignored; the triples (q, x, i) and (q, x, i) describe exactly the same configuration.
The transition function δ describes the evolution of the machine. For example, δ(q, a) =(p, b, −1) means that when the machine reads symbol a in state q, it changes its internal state
to p, writes symbol b onto the tape at its current location (replacing a), and then decreases its
position by 1 (or more intuitively, moves one step to the left). If the position of the head becomes
negative, no further transitions are possible, and the machine crashes.
We write (p, x , i) ⇒ M (q , y, j ) to indicate that Turing machine M transitions from the first
configuration to the second in one step. (The symbol ⇒ is often pronounced “yields”; I will omit
the subscript M if the machine is clear from context.) For example, δ(p, a) = (q, b, ±1) meansthat(p, x a y, i) ⇒ (q, x b y, i ± 1)
for any non-negative integer i, any string x of length i, and any string y. The evolution of any
Turing machine is deterministic; each configuration C yields a unique configuration C 0 . We write
C ⇒∗ C 0 to indicate that there is a (possibly empty) sequence of transitions from configuration C
to configuration C 0 . (The symbol ⇒∗ can be pronounced “eventually yields”.)
3Models of Computation

Lecture 6: Turing Machines [Fa’16]

The initial configuration is (start, w, 0) for some arbitrary (and possibly empty) input stringw ∈ Σ∗ . If M eventually reaches the accept state—more formally, if (start, w, 0) ⇒∗ (accept, x, i)for some string x ∈ Γ ∗ and some integer i—we say that M accepts the original input string w.
Similarly, if M eventually reaches the reject state, we say that M rejects w. We must emphasizethat “rejects” and “does not accept” are not synonyms; if M crashes or runs forever, then M
neither accepts nor rejects w.
We distinguish between two different senses in which a Turing machine can “accept” alanguage. Let M be a Turing machine with input alphabet Σ, and let L ⊆ Σ∗ be an arbitrary
language over Σ.
• M recognizes or accepts L if and only if M accepts every string in L but nothing else. A
language is recognizable (or semi-computable or recursively enumerable) if it is recognizedby some Turing machine.
• M decides L if and only if M accepts every string in L and rejects every string in Σ∗ \ L.
Equivalently, M decides L if and only if M recognizes L and halts (without crashing) on all
inputs. A language is decidable (or computable or recursive) if it is decided by some Turingmachine.
Trivially, every decidable language is recognizable, but (as we will see later), not every recognizable
language is decidable.

6.3

A First Example

Consider the language L = {0n 1n 0n | n ≥ 0}. This language is neither regular nor context-free,
but it can be decided by the following six-state Turing machine. The alphabets and states of themachine are defined as follows:Γ = {0, 1, $, x,}
Σ = {0, 1}
Q = {start, seek1, seek0, reset, verify, accept, reject}
The transition function is described in the table on the next page; all unspecified transitions leadto the reject state. The figure below shows a graphical representation of the same machine,which resembles a drawing of a DFA, but with output symbols and actions specified on each edge.
For example, we indicate the transition δ(p, 0) = (q, 1, +1) by writing 0/1, +1 next to the arrowfrom state p to state q.
$/$,+1

0/$,+1start

1/x,+1

0/0,+1x/x,+1x/$,+1x/$,+1

seek1

verify□/□,−1seek0

1/1,+1x/x,+10/x,−1reset

0/0,−1
1/1,−1x/x,−1

acceptA graphical representation of the example Turing machine4Models of Computationδ(p, a) = (Lecture 6: Turing Machines [Fa’16]q, b, ∆ )δ( start , 0) = ( seek1 , $, +1)
δ( start , x) = ( verify , $, +1)

explanation
mark first 0 and scan rightlooks like we’re done, but let’s make sureδ(seek1, 0) = ( seek1 , 0, +1)δ(seek1, x) = ( seek1 , x, +1)δ(seek1, 1) = ( seek0 , x, +1)

scan rightward for 1
mark 1 and continue rightδ(seek0, 1) = ( seek0 , 1, +1)δ(seek0, x) = ( seek0 , x, +1)δ(seek0, 0) = ( reset , x, +1)

mark 0 and scan left

δ( reset , 0) = ( reset , 0, −1)

scan leftward for $δ( reset , 1) = ( reset , 1, −1)δ( reset , x) = ( reset , x, −1)δ( reset , $) = ( start , $, +1)

step right and start overδ( verify , x) = ( verify , $, +1)δ( verify , ) = (accept, , −1)

scan rightward for 0

scan right for any unmarked symbol
success!

The transition function for a Turing machine that decides the language {0n 1n 0n | n ≥ 0}.

Finally, we trace the execution of this machine on two input strings: 001100 ∈ L and
00100 6∈ L. In each configuration, we indicate the position of the head using a small triangle
instead of listing the position explicitly. Notice that we automatically add blanks to the tapestring as necessary. Proving that this machine actually decides L—and in particular, that it nevercrashes or infinite-loops—is a straightforward but tedious exercise in induction.

6.4

Variations

There are actually several formal models that all fall under the name “Turing machine”, eachwith small variations on the definition we’ve given. Although we do need to be explicit about
which variant we want to use for any particular problem, the differences between the variants are
relatively unimportant. For any machine defined in one model, there is an equivalent machine ineach of the other models; in particular, all of these variants recognize the same languages anddecide the same languages. For example:• Halting conditions. Some models allow multiple accept and reject states, which (depending on the precise model) trigger acceptance or rejection either when the machine enters
the state, or when the machine has no valid transitions out of such a state. Others include
only explicit accept states, and either equate crashing with rejection or do not define arejection mechanism at all. Still other models include halting as one of the possible actionsof the machine, in addition to moving left or moving right; in these models, the machine
accepts/rejects its input if and only if it halts in an accepting/non-accepting state.
• Actions. Some Turing machine models allow transitions that do not move the head, orthat move the head by more than one cell in a single step. Others insist that a single step of
the machine either writes a new symbol onto the tape or moves the head one step. Finally,
as mentioned above, some models include halting as one of the available actions.
• Transition function. Some models of Turing machines, including Turing’s original
definition, allow the transition function to be undefined on some state-symbol pairs. In this5Models of Computation

Lecture 6: Turing Machines [Fa’16](start, 001100)
Î⇒ (seek1, $01100)
Î⇒ (seek1, $01100)
Î⇒ (seek0, $0x100)Î⇒ (seek0, $0x100)Î⇒ (reset, $0x1x0)Î⇒ (reset, $0x1x0)Î⇒ (reset, $0x1x0)Î⇒ (reset, $0x1x0)Î⇒ (start, $0x1x0)Î⇒ (seek1, $$x1x0)Î⇒ (seek1, $$x1x0)Î⇒ (seek0, $$xxx0)Î⇒ (seek0, $$xxx0)Î⇒ (reset, $$xxxx)Î⇒ (reset, $$xxxx)Î⇒ (reset, $$xxxx)Î⇒ (reset, $$xxxx)Î⇒ (start, $$xxxx)Î⇒ (verify, $$$xxx)Î⇒ (verify, $$$$xx)
Î⇒ (verify, $$$$$x)
Î⇒ (verify, $$$$$$)Î⇒ (accept, $$$$$$) ⇒ accept!
ÎThe evolution of the example Turing machine on the input string 001100 ∈ L(start, 00100)
Î⇒ (seek1, $0100)
Î⇒ (seek1, $0100)
Î⇒ (seek0, $0x00)
Î⇒ (reset, $0xx0)Î⇒ (reset, $0xx0)Î⇒ (reset, $0xx0)Î⇒ (start, $0xx0)Î⇒ (seek1, $$xx0)Î⇒ (seek1, $$xx0)Î⇒ (seek1, $$xx0) ⇒ reject!
ÎThe evolution of the example Turing machine on the input string 00100 6∈ L

6Models of Computation

Lecture 6: Turing Machines [Fa’16]

formulation, the transition function is given by a set δ ⊂ Q × Γ × Q × Γ × {+1, −1}, suchthat for each state q and symbol a, there is at most one transition (q, a, · , · , · ) ∈ δ. If themachine enters a configuration from which there is no transition, it halts and (dependingon the precise model) either crashes or rejects. Others define the transition function asδ : Q × Γ → Q × (Γ ∪ {−1, +1}), allowing the machine to either write a symbol to the tapeor move the head in each step.
• Beginning of the tape. Some models forbid the head to move past the beginning of thetape, either by starting the tape with a special symbol that cannot be overwritten andthat forces a rightward transition, or by declaring that a leftward transition at position 0
leaves the head in position 0, or even by pure fiat—declaring any machine that performs aleftward move at position 0 to be invalid.
To prove that any two of these variant “species” of Turing machine are equivalent, we mustshow how to transform a machine of one species into a machine of the other species that accepts
and rejects the same strings. For example, let M = (Γ ,, Σ, Q, s, accept, reject, δ) be a Turingmachine with explicit accept and reject states. We can define an equivalent Turing machine
M 0 that halts only when it moves left from position 0, and accepts only by halting while in an
accepting state, as follows. We define the set of accepting states for M 0 as A = {accept} anddefine a new transition function(accept, a, −1) if q = accept0δ (q, a) := (reject, a, −1) if q = rejectδ(q, a)otherwise
Similarly, suppose someone gives us a Turing machine M = (Γ ,, Σ, Q, s, accept, reject, δ)whose transition function δ : Q ×Γ → Q ×Γ ×{−1, 0, +1} allows the machine to transition without
moving its head. Then we can construct an equivalent Turing machine M 0 = (Γ ,, Σ, Q0 , s,accept, reject, δ0 ) that moves its head at every transition by defining Q0 := Q × {0, 1} and¨((q, 1), b, +1) if δ(p, a) = (q, b, 0),δ0 ((p, 0), a) :=((q, 0), b, ∆) if δ(p, a) = (q, b, ∆) and ∆ 6= 0,δ0 ((p, 1), a) := ((p, 0), a, −1).

6.5

Computing Functions

Turing machines can also be used to compute functions from strings to strings, instead of justaccepting or rejecting strings. Since we don’t care about acceptance or rejection, we replace
the explicit accept and reject states with a single halt state, and we define the output of theTuring machine to be the contents of the tape when the machine halts, after removing theinfinite sequence of trailing blanks. More formally, for any Turing machine M , any string w ∈ Σ∗ ,and any string x ∈ Γ ∗ that does not end with a blank, we write M(w ) = x if and only if(w, s, 0) ⇒∗M (x, halt, i) for some integer i. If M does not halt on input w, then we write M(w ) %,which can be read either “M diverges on w” or “M (w) is undefined.” We say that M computes
the function f : Σ∗ → Σ∗ if and only if M (w) = f (w) for every string w.
6.5.1

Shifting

One basic operation that is used in many Turing machine constructions is shifting the input
string a constant number of steps to the right or to the left. For example, given any input
7Models of Computation

Lecture 6: Turing Machines [Fa’16]

string w ∈ {0, 1}∗ , we can compute the string 0w using a Turing machine with tape alphabet
Γ = {0, 1,}, state set Q = {0, 1, halt}, start state 0, and the following transition function:
δ(p, a) = ( q , b, ∆ )δ(0, 0) = ( 0 , 0, +1)δ(0, 1) = ( 1 , 0, +1)δ(0, ) = (halt, 0, +1)δ(1, 0) = ( 0 , 1, +1)δ(1, 1) = ( 1 , 1, +1)δ(1, ) = (halt, 1, +1)
By increasing the number of states, we can build a Turing machine that shifts the input string any
fixed number of steps in either direction. For example, a machine that shifts its input to the leftby five steps might read the string from right to left, storing the five most recently read symbols in
its internal state. A typical transition for such a machine would be δ(12345, 0) = (01234, 5, −1).
6.5.2

Binary Addition

With a more complex Turing machine, we can implement binary addition. The input is a string of
the form w+ x, where w, x ∈ {0, 1}n , representing two numbers in binary; the output is the binary
representation of w+ x. To simplify our presentation, we assume that |w| = |x| > 0; however, thisrestrictions can be removed with the addition of a few more states. The following figure showsthe entire Turing machine at a glance. The machine uses the tape alphabet Γ = {, 0, 1, +, 0, 1};
the start state is shift0. All missing transitions go to a fail state, indicating that the input wasbadly formed.
Execution of this Turing machine proceeds in several phases, each with its own subset ofstates, as indicated in the figure. The initialization phase scans the entire input, shifting it to
the right to make room for the output string, marking the rightmost bit of w, and reading anderasing the last bit of x.
δ( p , a) = ( q , b, ∆ )δ( shift0 , 0) = ( shift0 , 0, +1)
δ( shift0 , 1) = ( shift1 , 0, +1)
δ( shift0 , +) = (shift+, 0, +1)
δ( shift0 , ) = ( add0 , , −1)δ( shift1 , 0) = ( shift0 , 1, +1)
δ( shift1 , 1) = ( shift1 , 1, +1)
δ( shift1 , +) = (shift+, 1, +1)
δ( shift1 , ) = ( add1 , , −1)δ(shift+, 0) = ( shift0 , +, +1)
δ(shift+, 1) = ( shift1 , +, +1)

The first part of the main loop scans left to the marked bit of w, adds the bit of x that was
just erased plus the carry bit from the previous iteration, and records the carry bit for the next
iteration in the machines internal state.

8Models of Computation

Lecture 6: Turing Machines [Fa’16]

shift++/0,+10/+,+1

initialization+/1,+1

1/+,+1

1/0,+1
shift00/0,+1

0/1,+1□/□,−10/0,−1
1/1,−1+/+,−1

shift1

1/1,+10/0,−1
1/1,−1+/+,−1

add0
0/0,−1
1/1,−1add1
1/0,−10/1,−1

next1□/□,−1

last0

0/0,+1
1/1,+1+/+,+1□/□,−1

1/□,−10/□,−1+/□,−10/0,−1
1/1,−1

scan rightand read

1/1,+1

next0

get0

scan left
and add0/0,−1
1/1,−1

back1

1/0,+10/□,−10/0,−1
1/1,−1+/+,−1

add2

back0

0/0,+1
1/1,+1+/+,+1

main loop□/□,−1get1

1/□,−1+/□,−10/0,−1halt

0/0,−1

last1

0/0,−1
1/1,−1termination

A Turing machine that adds two binary numbers of the same length.

δ( p , a) = ( q , b, ∆ )δ(add0, 0) = ( add0 , 0, −1)δ(add0, 1) = ( add0 , 0, −1)δ(add0, +) = ( add0 , 0, −1)δ(add0, 0) = (back0, 0, −1)δ(add0, 1) = (back0, 1, −1)δ( p , a) = ( q , b, ∆ )δ(add1, 0) = ( add1 , 0, −1)δ(add1, 1) = ( add1 , 0, −1)δ(add1, +) = ( add1 , 0, −1)δ(add1, 0) = (back0, 1, −1)δ(add1, 1) = (back1, 0, −1)δ( p , a) = ( q , b, ∆ )δ(add2, 0) = ( add2 , 0, −1)δ(add2, 1) = ( add2 , 0, −1)δ(add2, +) = ( add2 , 0, −1)δ(add2, 0) = (back1, 0, −1)δ(add2, 1) = (back1, 1, −1)

The second part of the main loop marks the previous bit of w, scans right to the end of x, andthen reads and erases the last bit of x, all while maintaining the carry bit.
δ( p , a) = ( q , b, ∆ )δ(back0, 0) = (next0, 0, +1)
δ(back0, 1) = (next0, 1, +1)
δ( next0 , 0) = (next0, 0, +1)
δ( next0 , 1) = (next0, 0, +1)
δ( next0 , +) = (next0, 0, +1)
δ( next0 , ) = ( get0 , , −1)δ( get0 , 0) = ( add0 , , −1)δ( get0 , 1) = ( add1 , , −1)δ( get0 , +) = ( last0 , , −1)δ( p , a) = ( q , b, ∆ )δ(back1, 0) = (next1, 0, +1)
δ(back1, 1) = (next1, 1, +1)
δ( next1 , 0) = (next1, 0, +1)
δ( next1 , 1) = (next1, 0, +1)
δ( next1 , +) = (next1, 0, +1)
δ( next1 , ) = ( get1 , , −1)δ( get1 , 0) = ( add1 , , −1)δ( get1 , 1) = ( add2 , , −1)δ( get1 , +) = ( last1 , , −1)

Finally, after erasing the + in the last iteration of the main loop, the termination phase adds thelast carry bit to the leftmost output bit and halts.

9Models of Computation

Lecture 6: Turing Machines [Fa’16]

δ( p , a) = ( q , b, ∆ )δ(last0, 0) = (last0, 0, −1)δ(last0, 1) = (last0, 0, −1)δ(last0, 0) = ( halt , 0,)δ(last1, 0) = (last1, 0, −1)δ(last1, 1) = (last1, 0, −1)δ(last1, 0) = ( halt , 1,)

6.6

Variations on Tracks, Heads, and Tapes

Multiple Tracks
It is sometimes convenient to endow the Turing machine tape with multiple tracks, each with its
own tape alphabet, and allow the machine to read from and write to the same position on all
tracks simultaneously. For example, to define a Turing machine with three tracks, we need threetape alphabets Γ1 , Γ2 , and Γ3 , each with its own blank symbol, where (say) Γ1 contains the input
alphabet Σ as a subset; we also need a transition function of the form
δ : Q × Γ1 × Γ2 × Γ3 → Q × Γ1 × Γ2 × Γ3 × {−1, +1}
Describing a configuration of this machine requires a quintuple (q, x 1 , x 2 , x 3 , i), indicating thateach track i contains the string x i followed by an infinite sequence of blanks. The initialconfiguration is (start, w, ", ", 0), with the input string written on the first track, and the othertwo tracks completely blank.
But any such machine is equivalent (if not identical) to a single-track Turing machine withthe (still finite!) tape alphabet Γ := Γ1 × Γ2 × Γ3 . Instead of thinking of the tape as three infinite
sequences of symbols, we think of it as a single infinite sequence of “records”, each containing
three symbols. Moreover, there’s nothing special about the number 3 in this construction; aTuring machine with any constant number of tracks is equivalent to a single-track machine.
Doubly-Infinite Tape
It is also sometimes convenient to allow the tape to be infinite in both directions, for example,
to avoid boundary conditions. There are several ways to simulate a doubly-infinite tape on amachine with only a semi-infinite tape. Perhaps the simplest method is to use a semi-infinite tapewith two tracks, one containing the cells with positive index and the other containing the cellswith negative index in reverse order, with a special marker symbol at position zero to indicate
the transition.
0 +1 +2 +3 +4 · · ·É −1 −2 −3 −4 · · ·Another method is to shuffle the positive-index and negative-index cells onto a single track,and add additional states to allow the Turing machine to move two steps in a single transition.
Again, we need a special symbol at the left end of the tape to indicate the transition:
É

0

−1

+1

−2

+2

−3

+3

···

A third method maintains two sentinel symbols É and Ê that surround all other non-blanksymbols on the tape. Whenever the machine reads the right sentinel Ê, we write a blank, moveright, write Ê, move left, and then proceed as if we had just read a blank. On the other hand,when the machine reads the left sentinel É, we shift the entire contents of the tape (up to and10Models of Computation

Lecture 6: Turing Machines [Fa’16]

including the right sentinel) one step to the right, then move back to the left sentinel, move right,
write a blank, and finally proceed as if we had just read a blank. Since the Turing machine does
not actually have access to the position of the head as an integer, shifting the head and the tapecontents one step right has no effect on its future evolution.
É

−3

−2

−1

0

+1

+2

+3

+4

+5

Ê

···

Using either of the first two methods, we can simulate t steps of an arbitrary Turing machinewith a doubly-infinite tape using only O(t) steps on a standard Turing machine. The third
method, unfortunately, requires Θ(t 2 ) steps in the worst case.
Insertion and Deletion
We can also allow Turing machines to insert and delete cells on the tape, in addition to simply
overwriting existing symbols. We’ve already seen how to insert a new cell: Leave a special markon the tape (perhaps in a second track), shift everything to the right of this mark one cell to theright, scan left to the mark, erase the mark, and finally write the correct character into the newcell. Deletion is similar: Mark the cell to be deleted, shift everything to the right of the mark one
step to the left, scan left to the mark, and erase the mark. We may also need to maintain a markin some cell to the right every non-blank symbol, indicating that all cells further to the right areblank, so that we know when to stop shifting left or right.
Multiple Heads
Another convenient extension is to allow machines simultaneous access to more than one positionon the tape. For example, to define a Turing machine with three heads, we need a transition
function of the form
δ : Q × Γ 3 → Q × Γ 3 × {−1, +1}3 .
Describing a configuration of such a machine requires a quintuple (q, x, i, j, k), indicating that themachine is in state q, the tape contains string x, and the three heads are at positions i, j, k. The
transition function tells us, given q and the three symbols x[i], x[ j], x[k], which three symbols
to write on the tape and which direction to move each of the heads.
We can simulate this behavior with a single head by adding additional tracks to the tapethat record the positions of each head. To simulate a machine M with three heads, we use atape with four tracks: track 0 is the actual work tape; each of the remaining tracks has a single
non-blank symbol recording the position of one of the heads. We also insert a special marker
symbols at the left end of the tape.
É
É
É
É

M

Y

W O R

K

T A

P
Î

Î
Î

E ···
···
···
···

We can simulate any single transition of M , starting with our single head at the left end of
the tape, as follows. Throughout the simulation, we maintain the internal state of M as one of
the components of our current state. First, for each i, we read the symbol under the ith head of
M as follows:
Scan to the right to find the mark on track i, read the corresponding symbol fromtrack 0 into our internal state, and then return to the left end of the tape.
11Models of Computation

Lecture 6: Turing Machines [Fa’16]

At this point, our internal state records M ’s current internal state and the three symbols under
M ’s heads. After one more transition (using M ’s transition function), our internal state records
M ’s next state, the symbol to be written by each head, and the direction to move each head.
Then, for each i, we write with and move the ith head of M as follows:
Scan to the right to find the mark on track i, write the correct symbol onto on track
0, move the mark on track i one step left or right, and then return to the left end of
the tape.
Again, there is nothing special about the number 3 here; we can simulate machines with any
fixed number of heads.
Careful analysis of this technique implies that for any integer k, we can simulate t stepsof an arbitrary Turing machine with k independent heads in Θ(t 2 ) time on a standard Turingmachine with only one head. Unfortunately, this quadratic blowup is unavoidable. It is relatively
easy to recognize the language of marked palindromes {w•wR | w ∈ {0, 1}∗ } in O(n) time usinga Turing machine with two heads, but recognizing this language provably requires Ω(n2 ) time
on a standard machine with only one head. On the other hand, with much more sophisticatedtechniques, it is possible to simulate t steps of a Turing machine with k head, for any fixed
integer k, using only O(t log t) steps on a Turing machine with just two heads.
Multiple Tapes
We can also allow machines with multiple independent tapes, each with its own head. To
simulate such a machine with a single tape, we simply maintain each tape as an independent
track with its own head. Equivalently, we can simulate a machine with k tapes using a single
tape with 2k tracks, half storing the contents of the k tapes and half storing the positions of the kheads.
É T A P E # O N E
···
É
Î
···
É T A P E # T W O
···
É
Î
···
É T A P E # T H R E E ···ÉÎ···
Just as for multiple tracks, for any constant k, we can simulate t steps of an arbitrary Turingmachine with k independent tapes in Θ(t 2 ) steps on a standard Turing machine with one tape,and this quadratic blowup is unavoidable. Moreover, it is possible to simulate t steps on a
k-tape Turing machine using only O(t log t) steps on a two-tape Turing machine using moresophisticated techniques. (This faster simulation is easier to obtain for multiple independenttapes than for multiple heads on the same tape.)
By combining these tricks, we can simulate a Turing machine with any fixed number of tapes,
each of which may be infinite in one or both directions, each with any fixed number of heads andany fixed number of tracks, with at most a quadratic blowup in the running time.

12Models of Computation

Lecture 6: Turing Machines [Fa’16]

6.7

Simulating a Real Computer

6.7.1

Subroutines and Recursion

ÆÆÆUse a second tape/track as a “call stack”. Add save and restore actions. In the simplest
formulation, subroutines do not have local memory. To call a subroutine, save the current
state onto the call stack and jump to the first state of the subroutine. To return, restore (andremove) the return state from the call stack. We can simulate t steps of any recursive Turingmachine with O(t) steps on a multitape standard Turing machine, or in O(t 2 ) steps on astandard Turing machine.
More complex versions of this simulation can adapt to

6.7.2

ÆÆÆ

Random-Access Memory

Keep [address•data] pairs on a separate “memory” tape. Write address to an “address”
tape; read data from or write data to a “data” tape. Add new or changed [address•data]
pairs at the end of the memory tape. (Semantics of reading from an address that has neverbeen written to?)
Suppose all memory accesses require at most ` address and data bits. Then we cansimulate the kth memory access in O(k`) steps on a multitape Turing machine or in O(k2 `2 )steps on a single-tape machine. Thus, simulating t memory accesses in a random-accessmachine with `-bit words requires O(t 2 `) time on a multitape Turing machine, or O(t 3 `2 ) time
on a single-tape machine.

6.8

Universal Turing Machines

With all these tools in hand, we can now describe the pinnacle of Turing machine constructions:the universal Turing machine. For modern computer scientists, it’s useful to think of a universal
Turing machine as a "Turing machine interpreter written in Turing machine". Just as the input
to a Python interpreter is a string of Python source code, the input to our universal Turingmachine U is a string 〈M , w〉 that encodes both an arbitrary Turing machine M and a string w in
the input alphabet of M . Given these encodings, U simulates the execution of M on input w; inparticular,• U accepts 〈M , w〉 if and only if M accepts w.
• U rejects 〈M , w〉 if and only if M rejects w.
The next few pages, I will sketch a universal Turing machine U that uses the input alphabet{0, 1, [, ], •, |} and a somewhat larger tape alphabet (via marks on additional tracks). However,I will not require that the Turing machines that U simulates have similarly small alphabets, so
we first need a method to encode arbitrary input and tape alphabets.
Encodings
Let M = (Γ , , Σ, Q, start, accept, reject, δ) be an arbitrary Turing machine, with a single halfinfinite tape and a single read-write head. (I will consistently indicate the states and tape symbolsof M in slanted green to distinguish them from the upright red states and tape symbols of U.)
We encode each symbol a ∈ Γ as a unique string |a| of dlg(|Γ |)e bits. Thus, if Γ = {0, 1, $, x, },
we might use the following encoding:〈0〉 = 001,〈1〉 = 010,〈$〉 = 011,
13〈x〉 = 100,〈〉 = 000.

Models of Computation

Lecture 6: Turing Machines [Fa’16]

The input string w is encoded by its sequence of symbol encodings, with separators • between
every pair of symbols and with brackets [ and ] around the whole string. For example, with thisencoding, the input string 001100 would be encoded on the input tape as〈001100〉 = [001•001•010•010•001•001]
Similarly, we encode each state q ∈ Q as a distinct string 〈q〉 of dlg|Q|e bits. Without loss ofgenerality, we encode the start state with all 1s and the reject state with all 0s. For example, if
Q = {start, seek1, seek0, reset, verify, accept, reject}, we might use the following encoding:〈start〉 = 111〈seek1〉 = 010〈seek0〉 = 011〈verify〉 = 101〈accept〉 = 110〈reject〉 = 000〈reset〉 = 100

We encode the machine M itself as the string 〈M 〉 = [〈reject〉•〈〉]〈δ〉, where 〈δ〉 is theconcatenation of substrings [〈p〉•〈a〉|〈q〉•〈b〉•〈∆〉] encoding each transition δ(p, a) = (q, b, ∆)such that q 6= reject. We encode the actions ∆ = ±1 by defining 〈−1〉 := 0 and 〈+1〉 := 1.
Conveniently, every transition string has exactly the same length. For example, with the symboland state encodings described above, the transition δ(reset, $) = (start, $, +1) would be encodedas[100•011|001•011•1].
Our first example Turing machine for recognizing {0n 1n 0n | n ≥ 0} would be represented by
the following string (here broken into multiple lines for readability):[000•000][[001•001|010•011•1][001•100|101•011•1][010•001|010•001•1][010•100|010•100•1][010•010|011•100•1][011•010|011•010•1][011•100|011•100•1][011•001|100•100•1][100•001|100•001•0][100•010|100•010•0][100•100|100•100•0][100•011|001•011•1][101•100|101•011•1][101•000|110•000•0]]
Finally, we encode any configuration of M on U’s work tape by alternating between encodingsof states and encodings of tape symbols. Thus, each tape cell is represented by the string[〈q〉•〈a〉] indicating that (1) the cell contains symbol a; (2) if q 6= reject, then M ’s head islocated at this cell, and M is in state q; and (3) if q = reject, then M ’s head is located somewhere
else. Conveniently, each cell encoding uses exactly the same number of bits. We also surroundthe entire tape encoding with brackets [ and ].
For example, with the encodings described above, the initial configuration (start, 001100, 0)
Î
for our first example Turing machine would be encoded on U’s tape as follows.

[[111•001][000•001][000•010][000•010][000•001][000•001]]
|
{z
}|
{z
}|
{z
}|
{z
}|
{z
}|
{z
}
start 0reject 0

reject 1

reject 1

reject 0

reject 0

Similarly, the intermediate configuration (reset, $0x1x0, 3) would be encoded as follows:Î[[000•011][000•011][000•100][010•010][000•100][000•001]]
|
{z
}|
{z
}|
{z
}|
{z
}|
{z
}|
{z
}
reject $reject 0

reset 1

reject x

14

reject x

reject 0

Models of Computation

Lecture 6: Turing Machines [Fa’16]

Input and Execution
Without loss of generality, we assume that the input to our universal Turing machine U is given
on a separate read-only input tape, as the encoding of an arbitrary Turing machine M followedby an encoding of its input string x. Notice the substrings [[ and ]] each appear only only once
on the input tape, immediately before and after the encoded transition table, respectively. U also
has a read-write work tape, which is initially blank.
We start by initializing the work tape with the encoding 〈start, x, 0〉 of the initial configurationof M with input x. First, we write [[〈start〉•. Then we copy the encoded input string 〈x〉 onto
the work tape, but we change the punctuation as follows:• Instead of copying the left bracket [, write [[〈start〉•.
• Instead of copying each separator •, write ][〈reject〉•• Instead of copying the right bracket ], write two right brackets ]].
The state encodings 〈start〉 and 〈reject〉 can be copied directly from the beginning of 〈M 〉(replacing 0s for 1s for 〈start〉). Finally, we move the head back to the start of U’s tape.
At the start of each step of the simulation, U’s head is located at the start of the work tape.
We scan through the work tape to the unique encoded cell [〈p〉•〈a〉] such that p 6= reject.
Then we scan through the encoded transition function 〈δ〉 to find the unique encoded tuple[〈p〉•〈a〉|〈q〉•〈b〉•〈∆〉] whose left half matches our the encoded tape cell. If there is no suchtuple, then U immediately halts and rejects. Otherwise, we copy the right half 〈q〉•〈b〉 of thetuple to the work tape. Now if q = accept, then U immediately halts and accepts. (We don’t
bother to encode reject transformations, so we know that q 6= reject.) Otherwise, we transfer
the state encoding to either the next or previous encoded cell, as indicated by M ’s transition
function, and then continue with the next step of the simulation.
During the final state-copying phase, we ever read two right brackets ]], indicating that
we have reached the right end of the tape encoding, we replace the second right bracket with[〈reject〉•〈〉]] (mostly copied from the beginning of the machine encoding 〈M 〉) and thenscan back to the left bracket we just wrote. This trick allows our universal machine to pretendthat its tape contains an infinite sequence of encoded blanks [〈reject〉•〈〉] instead of actual
blanks .
ExampleAs an illustrative example, suppose U is simulating our first example Turing machine M on
the input string 001100. The execution of M on input w eventually reaches the configuration(seek1, $$x1x0, 3). At the start of the corresponding step in U’s simulation, U is in the followingÎ
configuration:[[000•011][000•011][000•100][010•010][000•100][000•001]]
ÎFirst U scans for the first encoded tape cell whose state is not reject. That is, U repeatedly
compares the first half of each encoded state cell on the work tape with the prefix [〈reject〉• of
the machine encoding 〈M 〉 on the input tape. U finds a match in the fourth encoded cell.

[[000•011][000•011][000•100][010•010][000•100][000•001]]
Î
Next, U scans the machine encoding 〈M 〉 for the substring [010•010 matching the current encoded cell. U eventually finds a match in the left size of the the encoded transition15

Models of Computation

Lecture 6: Turing Machines [Fa’16][010•010|011•100•1]. U copies the state-symbol pair 011•100 from the right half of thisencoded transition into the current encoded cell. (The underline indicates which symbols arechanged.)[[000•011][000•011][000•100][011•100][000•100][000•001]]
Î
The encoded transition instructs U to move the current state encoding one cell to the right. (Theunderline indicates which symbols are changed.)[[000•011][000•011][000•100][000•100][011•100][000•001]]
ÎFinally, U scans left until it reads two left brackets [[; this returns the head to the left end of
the work tape to start the next step in the simulation. U’s tape now holds the encoding of M ’s
configuration (seek0, $$xxx0, 4), as required.
Î

[[000•011][000•011][000•100][000•100][011•100][000•001]]
Î

Exercises
In the following problems, a standard Turing machine has a single semi-infinite tape, one
read-write head, and the input alphabet Σ = {0, 1}. For problems that ask you to construct a
standard Turing machine, you may assume without loss of generality that the initial tape contains
a special symbol É just to the left of the input string, indicating the left end of the tape; theread-write head starts just to the right of this symbol. For problems that ask you to simulate astandard Turing machine, you may assume without loss of generality that the tape alphabet is{0, 1,}.

Turing Machine Programming
1. Describe standard Turing machines that decide each of the following languages:(a) Palindromes over the alphabet {0, 1}(b) {ww | w ∈ {0, 1}∗ }(c) 0a 1 b 0a b | a, b ∈ N
2. Let 〈n〉2 denote the binary representation of the non-negative integer n. For example,〈17〉2 = 10001 and 〈42〉2 = 101010. Describe standard Turing machines that computethe following functions from {0, 1}∗ to {0, 1}∗ :(a) w 7→ www(b) 1n 01m 7→ 1mn(c) 1n 7→ 12n(d) 1n 7→ 〈n〉2(e) 0∗ 〈n〉2 7→ 1n(f) 〈n〉2 7→ 〈n2 〉216Models of Computation

Lecture 6: Turing Machines [Fa’16]

3. Describe standard Turing machines that write each of the following infinite streams of bits
onto their tape. Specifically, for each integer n, there must be a finite time after which thefirst n symbols on the tape always match the first n symbols in the target stream.
(a) An infinite stream of 1s(b) 0101101110111101111101111110 . . . , where the nth block of 1s has length n.
(c) The stream of bits whose nth bit is 1 if and only if n is prime.
(d) The Thue-Morse sequence T0 • T1 • T2 • T3 · · · , where
if n = 0
0
Tn := 1
if n = 1T•Totherwisen−1

n−1

where w indicates the binary string obtained from w by flipping every bit. Equivalently,
the nth bit of the Thue Morse sequence if 0 if the binary representation of n has aneven number of 1s and 1 otherwise.

0110100110010110100101100110100110010110011010010110 . . .
(e) The Fibonacci sequence F0 • F1 • F2 • F3 · · · , where
if n = 0
0
Fn := 1
if n = 1F•Fotherwisen−2

n−1

01011010110110101101011011010110110101101011011010101 . . .

Simulation by “Weaker” Machines
4. A two-stack machine is a Turing machine with two tapes with the following restrictedbehavior. At all times, on each tape, every cell to the right of the head is blank, and every
cell at or to the left of the head is non-blank. Thus, a head can only move right by writinga non-blank symbol into a blank cell; symmetrically, a head can only move left by erasing
the rightmost non-blank cell. Thus, each tape behaves like a stack. To avoid underflow,
there is a special symbol at the start of each tape that cannot be overwritten. Initially, onetape contains the input string, with the head at its last symbol, and the other tape is empty(except for the start-of-tape symbol).
Prove that any standard Turing machine can be simulated by a two-stack machine.
That is, given any standard Turing machine M , describe a two-stack machine M 0 that
accepts and rejects exactly the same input strings as M .
5. A k-register machine is a finite-state automaton with k non-negative integer registers.
Formally, a k-register machine consists of a finite set Q of states (which include start,
accept, and reject) and a transition function
δ : Q × {0, 1}k → Q × {halve, nop, double, double+1}k17Models of Computation

Lecture 6: Turing Machines [Fa’16]that takes the internal state and the signs of the registers as input, and produces a newinternal state and changes to the registers as output. The instructions halve, nop, double,
and double+1 change any register with value n to n/2, n, 2n, and 2n + 1, respectively.
For example, if δ(p, 0, 1, 0, 1) = (q, halve, nop, halve, double+1), then from the configuration (p, 0, 2, 3, 1), the machine would transition to (q, 1, 2, 1, 3).
Prove that any standard Turing machine (with suitably encoded input and output) canbe simulated by a two-register machine. The input to the register machine is encoded inreversed binary in one of the registers, so the parity of the register value is the first input
bit; the other register is initially zero.
6. A k-counter machine (also known as a Minksy machine) is a finite-state automaton withk non-negative integer registers. Formally, a k-counter machine consists of a finite set Q ofstates (which include start, accept, and reject) and a transition function
δ : Q × {0, +}k → Q × {inc, nop, dec}kthat takes the internal state and the signs of the registers as input, and produces a newinternal state and changes to the registers as output. The instructions inc, nop, and decchange any register with value n to n + 1, n, and n − 1, respectively. The transition function
must forbid decrementing a register whose value is already zero.
For example, if δ(p, 0, +, +, +) = (q, inc, dec, nop, dec), then from the configuration(p, 0, 2, 3, 1), the machine would transition to (q, 1, 1, 3, 0).
(a) Prove that any standard Turing machine (with suitably encoded input and output) canbe simulated by a three-counter machine. [Hint: Simulate a two-register machine,using the third counter for scratch work.](b) Prove that any three-counter machine (with suitably encoded input and output) canbe simulated by a two-counter machine. [Hint: Store all three counters in a single
integer of the form 2a 3 b 5c , and use the other counter for scratch work.]
? (c)

Æ

Prove that a three-counter machine can compute a suitable encoding of any computablefunction. Specifically, for any computable function f : N → N, prove there is a threecounter machine M that transforms any input (n, 0, 0) into ( f (n), 0, 0). [Hint: Firsttransform (n, 0, 0) to (2n , 0, 0) using all three counters; then run a two- (or three)counter TM simulation to obtain (2 f (n) , 0, 0); and finally transform (2 f (n) , 0, 0) to( f (n), 0, 0) using all three counters.](d) Prove that not two-counter machine can transform (n, 0) to (2n , 0). This impossiblity
result was independently proved by Bārzdin, š in 1963, Yao in 1971, and Schroeppel in1972. ⁵

7. A hole-punch Turing machine is a standard Turing machine with two restrictions. First, thetape alphabet has only two symbols  and , and thus the input alphabet is the singleton
⁵Ja. M. Barzdin0 [Jānis Bārzdin, š]. Ob odnom klasse mašin T0 ûringa (mašiny Minskogo) [On a class of Turingmachines (Minsky machines)]. Algebra i Logika 1(6):42–51, 1963. In Russian. Sorry.
Oscar H. Ibarra, Nicholas Q. Trân. A note on simple programs with two variables. Theoretical Computer Science
112(2): 391–397, 1993.
Rich Schroeppel. A two counter machine cannot calculate 2N . Artificial Intelligence Memo 257, MIT AI Lab, May
1972. [Schroeppel claims that the same result was independently proved by Frances Yao in 1971.

18

Models of Computation

Lecture 6: Turing Machines [Fa’16]

set {}. Second, the machine can never write a blank () over a non-blank (); intuitively,
the machine can punch new holes (s) into the tape, but it cannot erase holes.
Prove that any standard Turing machine (with a unary input alphabet) can be simulated
by a hole-punch Turing machine.
8. A tag-Turing machine has two heads: one can only read, the other can only write. Initially,
the read head is located at the left end of the tape, and the write head is located at the first
blank after the input string. At each transition, the read head can either move one cell tothe right or stay put, but the write head must write a symbol to its current cell and move
one cell to the right. Neither head can ever move to the left.
Prove that any standard Turing machine can be simulated by a tag-Turing machine.
That is, given any standard Turing machine M , describe a tag-Turing machine M 0 that
accepts and rejects exactly the same input strings as M .
9. ? (a) Prove that any standard Turing machine can be simulated by a standard Turingmachine with only three states. [Hint: Keep an encoding of the state of the simulated
machine on the tape of the simulating machine.]Æ(b) Prove that any standard Turing machine can be simulated by a standard Turingmachine with only two states.

Simulating “Stronger” Machines
10. A two-dimensional Turing machine uses an infinite two-dimensional grid of cells as
the tape; at each transition, the head can move from its current cell to any of its
four neighbors on the grid. The transition function of such a machine has the form
δ : Q × Γ → Q × Γ × {↑, ←, ↓, →}, where the arrows indicate which direction the head should
move.
(a) Prove that any two-dimensional Turing machine can be simulated by a standard
Turing machine.
(b) Suppose further that we endow our two-dimensional Turing machine with thefollowing additional actions, in addition to moving the head:• Insert row: Move all symbols on or above the row containing the head up one
row, leaving the head’s row blank.
• Insert column: Move all symbols on or to the right of the column containing thehead one column to the right, leaving the head’s column blank.
• Delete row: Move all symbols above the row containing the head down one row,deleting the head’s row of symbols.
• Delete column: Move all symbols the right of the column containing the head
one column to the right, deleting the head’s column of symbols.
Show that any two-dimensional Turing machine that can add an delete rows can be
simulated by a standard Turing machine.
11. A binary-tree Turing machine uses an infinite binary tree as its tape; that is, every cell inthe tape has a left child and a right child. At each step, the head moves from its current
19Models of Computation

Lecture 6: Turing Machines [Fa’16]

cell to its Parent, its Left child, or to its Right child. Thus, the transition function of such amachine has the form δ : Q × Γ → Q × Γ × {P, L, R}. The input string is initially given along
the left spine of the tape.
Show that any binary-tree Turing machine can be simulated by a standard Turingmachine.
12. A stack-tape Turing machine uses an semi-infinite tape, where every cell is actually the
top of an independent stack. The behavior of the machine at each iteration is governed by
its internal state and the symbol at the top of the current cell’s stack. At each transition,
the head can optionally push a new symbol onto the stack, or pop the top symbol off thestack. (If a stack is empty, its “top symbol” is a blank and popping has no effect.)Show that any stack-tape Turing machine can be simulated by a standard Turingmachine. (Compare with Problem 4!)
13. A tape-stack Turing machine has two actions that modify its work tape, in addition tosimply writing individual cells: it can save the entire tape by pushing in onto a stack, and it
can restore the entire tape by popping it off the stack. Restoring a tape returns the content
of every cell to its content when the tape was saved. Saving and restoring the tape do notchange the machine’s state or the position of its head. If the machine attempts to “restore”
the tape when the stack is empty, the machine crashes.
Show that any tape-stack Turing machine can be simulated by a standard Turingmachine.

© Copyright 2018 Jeff Erickson.
This work is licensed under a Creative Commons License (http://creativecommons.org/licenses/by-nc-sa/4.0/).
Free distribution is strongly encouraged; commercial distribution is expressly forbidden.
See http://jeffe.cs.illinois.edu/teaching/algorithms/ for the most recent revision.

20