Models of Computation

Lecture 9: Nondeterministic Turing Machines [Fa’16]

Caveat lector: This is a first draft; some topics still need to be written. Please send bug
reports and suggestions to jeffe@illinois.edu.
If first you don’t succeed, then try and try again.
And if you don’t succeed again, just try and try and try.
— Marc Blitzstein, “Useless Song”, The Three Penny Opera (1954)
Adaptation of Bertold Brecht, “Das Lied von der Unzulänglichkeit
menschlichen Strebens” Die Dreigroschenoper (1928)
Children need encouragement.
If a kid gets an answer right, tell him it was a lucky guess.
That way he develops a good, lucky feeling.
— Jack Handey, “Deep Thoughts”, Saturday Night Live (March 21, 1992)

9Nondeterministic Turing Machines

9.1

Definitions

In his seminal 1936 paper, Turing also defined an extension of his “automatic machines” that
he called choice machines, which are now more commonly known as nondeterministic Turingmachines. The execution of a nondeterministic Turing machine is not determined entirely by its
input and its transition function; rather, at each step of its execution, the machine can choose
from a set of possible transitions. The distinction between deterministic and nondeterministic
Turing machines exactly parallels the distinction between deterministic and nondeterministic
finite-state automata.
Formally, a nondeterministic Turing machine has all the components of a standard deterministic Turing machine—a finite tape alphabet Γ that contains the input alphabet Σ and a blanksymbol ; a finite set Q of internal states with special start, accept, and reject states; and atransition function δ. However, the transition function now has the signatureδ : Q × Γ → 2Q×Γ ×{−1,+1} .
That is, for each state p and tape symbol a, the output δ(p, a) of the transition function is a setof triples of the form (q, b, ∆) ∈ Q × Γ × {−1, +1}. Whenever the machine finds itself in state preading symbol a, the machine chooses an arbitrary triple (q, b, ∆) ∈ δ(p, a), and then changes
its state to q, writes b to the tape, and moves the head by ∆. If the set δ(p, a) is empty, themachine moves to the reject state and halts.
The set of all possible transition sequences of a nondeterministic Turing machine N on agiven input string w define a rooted tree, called a computation tree. The initial configuration(start, w, 0) is the root of the computation tree, and the children of any configuration (q, x, i)are the configurations that can be reached from (q, x, i) in one transition. In particular, anyconfiguration whose state is accept or reject is a leaf. For deterministic Turing machines, thiscomputation tree is just a single path, since there is at most one valid transition from every
configuration.
© Copyright 2016 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

9.2

Lecture 9: Nondeterministic Turing Machines [Fa’16]

Acceptance and Rejection

Unlike deterministic Turing machines, there is a fundamental asymmetry between the acceptanceand rejection criteria for nondeterministic Turing machines. Let N be any nondeterministic
Turing machine, and let w be any string.
• N accepts w if and only if there is at least one sequence of valid transitions from the initialconfiguration (start, w, 0) that leads to the accept state. Equivalently, N accepts w if thecomputation tree contains at least one accept leaf.
• N rejects w if and only if every sequence of valid transitions from the initial configuration(start, w, 0) leads to the reject state. Equivalently, N rejects w if every path through thecomputation tree ends with a reject leaf.
In particular, N can accept w even when there are choices that allow the machine to run forever,
but rejection requires N to halt after only a finite number of transitions, no matter what choices
it makes along the way. Just as for deterministic Turing machines, it is possible that N neither
accepts nor rejects w.
Acceptance and rejection of languages are defined exactly as they are for deterministic
machines. A non-deterministic Turing machine N accepts a language L ⊆ Σ∗ if M accepts allstrings in L and nothing else; N rejects L if M rejects every string in L and nothing else; andfinally, N decides L if M accepts L and rejects Σ∗ \ L.

9.3

ÆÆÆ

Time and Space Complexity• Define “time” and “space”.
• TIME( f (n)) is the class of languages that can be decided by a deterministic multi-tapeTuring machine in O( f (n)) time.

• NTIME( f (n)) is the class of languages that can be decided by a nondeterministic multitape Turing machine in O( f (n)) time.

• SPACE( f (n)) is the class of languages that can be decided by deterministic multi-tapeTuring machine in O( f (n)) space.

• NSPACE( f (n)) is the class of languages that can be decided by a nondeterministic
multi-tape Turing machine in O( f (n)) space.

• Why multi-tape TMs? Because t steps on any k-tape Turing machine can be simulated inO(t log t) steps on a two-tape machine [Hennie and Stearns 1966, essentially using lazy
counters and amortization], and in O(t 2 ) steps on a single-tape machine [Hartmanisand Stearns 1965; realign multiple tracks at every simulation step]. Moreover, the latter
quadratic bound is tight [Hennie 1965 (palindromes, via communication complexity)].

9.4

Deterministic Simulation via Dovetailing

Theorem 1. For any nondeterministic Turing machine N , there is a deterministic Turing machine
M that accepts exactly the same strings and N and rejects exactly the same strings as N . Moreover,
if every computation path of N on input x halts after at most t steps, then M halts on input x after
at most O(t 2 r 2t ) steps, where r is the maximum size of any transition set in N .
Proof: I’ll describe a deterministic machine M that performs a breadth-first search of thecomputation tree of N . (The depth-first search performed by a standard recursive backtracking
algorithm won’t work here. If N ’s computation tree contains an infinite path, a depth-first searchwould get stuck in that path without exploring the rest of the tree.)2Models of Computation

Lecture 9: Nondeterministic Turing Machines [Fa’16]

At the beginning of each simulation round, M ’s tape contains a string of the form · · · •• y1 q1 z1 • y2 q2 z2 • · · · • yk qk zk ••where each substring yi qi zi encodes a configuration (qi , yi zi , | yi |) of some computation pathof N , and • is a new symbol not in the tape alphabet of N . The machine M interprets thissequence of encoded configurations as a queue, with new configurations inserted on the rightand old configurations removed from the left. The double-separators •• uniquely identify thestart and end of this queue; outside this queue, the tape is entirely blank.
Specifically, in each round, first M appends the encodings of all configurations than N canreach in one transition from the first encoded configuration (q1 , y1 z1 , | y1 |); then M erases thefirst encoded configuration.
· · · •• y1 q1 z1 • y2 q2 z2 • · · · • y r q r z r •• · · ·ww· · ·  · · · •• y2 q2 z2 • · · · • yk qk zk • ỹ1 q̃1 z̃1 • ỹ2 q̃2 z̃2 • · · · • ỹ r q̃ r z̃ r •• · · ·Suppose each transition set δN (q, a) has size at most r. Then after simulating t steps of N ,the tape string of M encoding O(r t ) different configurations of N and therefore has length
L = O(t r t ) (not counting the initial blanks). If M begins each simulation phase by moving
the initial configuration from the beginning to the end of the tape string, which takes O(t 2 r t )time, the time for the rest of the the simulation phase is negligible. Altogether, simulating all r t
possibilities for the the tth step of N requires O(t 2 r 2t ) time. We conclude that M can simulate
the first t steps of every computation path of N in O(t 2 r 2t ) time, as claimed.
The running time of this simulation is dominated by the time spent reading from one end of
the tape string and writing to the other. It is fairly easy to reduce the running time to O(t r t ) byusing either two tapes (a “read tape” containing N -configurations at time t and a “write tape”
containing N -configurations at time t + 1) or two independent heads on the same tape (one ateach end of the queue).

9.5

Nondeterminism as Advice

Any nondeterministic Turing machine N can also be simulated by a deterministic machine M
with two inputs: the user input string w ∈ Σ∗ , and a so-called advice string x ∈ Ω∗ , where Ω isanother finite alphabet. Only the first input string w is actually given by the user. At least for
now, we assume that the advice string x is given on a separate read-only tape.
The deterministic machine M simulates N step-by-step, but whenever N has a choice of
how to transition, M reads a new symbol from the advice string, and that symbol determines
the choice. In fact, without loss of generality, we can assume that M reads a new symbol fromthe advice string and moves the advice-tape’s head to the right on every transition. Thus, M ’stransition function has the form δ M : Q × Γ × Ω → Q × Γ × {−1, +1}, and we require thatδN (q, a) = {δ M (q, a, ω) | ω ∈ Ω}
For example, if N has a binary choiceδN (branch, ?) = (left, L, −1), (right, R, +1) ,3

Models of Computation

Lecture 9: Nondeterministic Turing Machines [Fa’16]

then M might determine this choice by definingδ M (branch, ?, 0) = (left, L, −1)andδ M (branch, ?, 1) = (right, R, +1)

More generally, if every set δN (p, a) has size r, then we let Ω = {1, 2, . . . , r} and define δ M (q, a, i)to be the ith element of δN (q, a) in some canonical order.
Now observe that N accepts a string w if and only if M accepts the pair (w, x) for some stringx ∈ Ω∗ , and N rejects w if and only if M rejects the pair (w, x) for all strings x ∈ Ω∗ .
The “advice” formulation of nondeterminism allows a different strategy for simulation by astandard deterministic Turing machine, which is often called dovetailing. Consider all possible
advice strings x, in increasing order of length; listing these advice strings is equivalent torepeatedly incrementing a base-r counter. For each advice string x, simulate M on input (w, x)
for exactly |x| transitions.
Dovetail M (w):for t ← 1 to ∞done ← True
for all strings x ∈ Ω t
if M accepts (w, x) in at most t steps
acceptif M (w, x) does not halt in at most t steps
done ← False
if donereject

The most straightforward Turing-machine implementation of this algorithm requires three tapes:
A read-only input tape containing w, an advice tape containing x (which is also used as a timer
for the simulation), and the work tape. This simulation requires O(t r t ) time to simulate all
possibilities for t steps of the original non-deterministic machine N .
If we insist on using a standard Turing machine with a single tape and a single head, thesimulation becomes slightly more complex, but (unlike our earlier queue-based strategy) notsignificantly slower. This standard machine S maintains a string of the form •w• x •z, where z
is the current work-tape string of M (or equivalently, of N ), with marks (on a second track)indicating the current positions of the heads on M ’s work tape and M ’s advice tape. Simulating
a single transition of M now requires O(|x|) steps, because S needs to shuttle its single head
between these two marks. Thus, S requires O(t 2 r t ) time to simulate all possibilities for t
steps of the original non-deterministic machine N . This is significantly faster than the queuebased simulation, because we don’t record (and therefore don’t have to repeatedly scan over)intermediate configurations; recomputing everything from scratch is actually cheaper!

9.6ÆÆÆThe Cook-Levin Theorem
Define Sat and CircuitSat. Non-determinism is fundamentally different from other Turingmachine extensions, in that it seems to provide an exponential speedup for some problems,
just like NFAs can use exponentially fewer states than DFAs for the same language.

The Cook-Levin Theorem. If SAT ∈ P, then P=NP.
Proof: Let L ⊆ Σ∗ be an arbitrary language in NP, over some fixed alphabet Σ. There must bean integer k and Turing machine M that satisfies the following conditions:4Models of Computation

Lecture 9: Nondeterministic Turing Machines [Fa’16]• For all strings w ∈ L, there is at least one string x ∈ Σ∗ such that M accepts the string w x.
• For all strings w 6∈ L and x ∈ Σ∗ , M rejects the string w x.
• For all strings w, x ∈ Σ∗ , M halts on input w x after at most max{1, |w|k } steps.
Now suppose we are given a string w ∈ Σ∗ . Let n = |w| and let N = max{1, |w|k }. Weconstruct a boolean formula Φw that is satisfiable if and only if w ∈ L, by following the executionof M on input w x for some unknown advice string x. Without loss of generality, we can assume
that |x| = N − n − 1 (since we can extend any shorter string x with blanks.) Our formula Φw uses
the following boolean variables for all symbols a ∈ Γ , all states q ∈ Q, and all integers 0 ≤ t ≤ N
and 0 ≤ i ≤ N + 1.
• Q t,i,q — M is in state q with its head at position i after t transitions.
• Tt,i,a — The kth cell of M ’s work tape contains a after t transitions.
The formula Φw is the conjunction of the following constraints:• Boundaries: To simplify later constraints, we include artificial boundary variables justpast both ends of the tape:
Q t,i,q = Q t,N +1,q = False

for all 0 ≤ t ≤ N and q ∈ Q

Tt,0,a = Tt,N +1,a = False

for all 0 ≤ t ≤ N and a ∈ Γ• Initialization: We have the following values for variables with t = 0:
Q 0,1,start = True
Q 0,1,q = False

for all q 6= start

H0,i,q = False

for all i 6= 1 and q ∈ Q

T0,i,w i = True

for all 1 ≤ i ≤ n

T0,i,a = False

for all 1 ≤ i ≤ n and a 6= w i

T0,n+1, = True
T0,n+1,a = False

for all a 6= 

• Uniqueness: The variables T0,i,a with n+2 ≤ i ≤ N represent the unknown advice string x;
these are the “inputs” to Φw . We need some additional constraints ensure that for each i,exactly one of these variables is True:_^T0, j,a ∧T0, j,a ∨ T0, j,ba6= ba∈Γ

• Transitions: For all 1 ≤ t ≤ N and 1 ≤ i ≤ N , the following constraints simulate thetransition from time t − 1 to time t.
__
Q t,i,q =Q t−1,i−1,p ∧ Tt,i−1,a ∨Q t−i,i+1,p ∧ Tt,i+1,aδ(p,a)=(q,·,+1)

δ(p,a)=(q,·,−1)Tt,i,b =_Q t−1,i,p ∧ Tt−1,i,aδ(p,a)=(·,b,·)

∨
^
q∈Q

5Q t−1,i,q ∧ Tt−1,i,b

Models of Computation

Lecture 9: Nondeterministic Turing Machines [Fa’16]• Output: We have one final constraint that indicates acceptance.
z=N
N__

Q t,i,accept

t=0 i=1

By definition, Φw is satisfiable if and only if some input values T0,i,a , all constraints aresatisfied, including acceptance. A straightforward induction argument implies that even without
the acceptance constraint, any assignment of values to the unknown variables T0,i,a that satisfies theuniqueness constraints determines unique values for the other variables in Φw , which consistently
describe the execution of M . To satisfy the acceptance constraint, this execution of M must leadto the accept state. Thus, Φw is satisfiable if and only if there is a string x ∈ Γ ∗ such that M
accepts the input w x. We conclude that Φw is satisfiable if and only if w ∈ L.
It remains only to argue that the reduction requires only polynomial time. For any input
string w of length n, the formula Φw has O(N 2 ) variables and O(N 2 ) constraints (where thehidden constants depend on the machine M ). Every constraint except acceptance has constantlength, so altogether Φw has length O(N 2 ). Moreover, we can construct Φw in O(N 2 ) = O(n2k )time.
In conclusion, if we could decide SAT for formulas of size M in O(M c ) time, then we could
decide membership in L in O(n2kc ) time, which implies that L ∈ P.
Exercises
1. Prove that the following problem is NP-hard, without using the Cook-Levin Theorem. Givena string 〈M , w〉 that encodes a non-deterministic Turing machine M and a string w, does M
accept w in at most |w| transitions?

ÆÆÆMore excerises!

© Copyright 2016 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.

6