Computational Complexity and Computability
Lecture 5 – NTMs & Enumerators
Koushik Pal
University of Toronto
January 25, 2021
Nondeterministic TM
Transition function: δ : Q × Γ → P(Q × Γ × {L, R}) (P(S) denotes the power set of S)
q
q
⊔
a
be
t
⊔
q Nondeterministic Choice
Time 6 Choice 1
Time 5
… …
q
… … … …
Choice 2
⊔
a
bd
t
⊔
⊔
a
b
gt
⊔
q q
e → g, R Choice 2
e → d, L Choice 1
Nondeterministic TM
Computation of a nondeterministic TM on an input can be viewed as a tree.
Each node of the tree represents a configuration.
The root node represents the initial configuration.
Each branch corresponds to a different possibility for the machine.
If some branch of the computation leads to the accept state, the machine accepts its input.
Nondeterministic TM
123
12 123
11112 .
Nondeterministic TM
Theorem
The class of nondeterministic TMs has the same power as the class of standard TMs.
Proof.
A standard (deterministic) TM is trivially a nondeterministic TM that has exactly one branch at each node.
To simulate a nondeterministic TM N on a standard TM, we need to evaluate each branch of the computation tree and accept the input when one of the branches accepts the input.
But we need to be careful with the order in which we choose the branches to evaluate. DFS does not work! Use BFS!
Nondeterministic TM
Define a 3-tape deterministic TM D as follows:
⊔
⊔
Input Tape Simulation Tape Address Tape
… …
… …
… …
⊔
x
x
$
y
⊔
⊔
⊔
Input tape contains only the input and is never altered.
Simulation tape maintains a copy of N’s tape on some branch
of its nondeterministic computation.
Address tape keeps track of D’s location in N’s computation tree by generating strings in the lexicographic ordering from the language Σ+, where Σ = {,,…,b} with b being the maximum number of choices at any given node.
Nondeterministic TM
Exercise. Design a TM that generates strings in the lexicographic ordering from the language Σ+, where Σ = {, , . . . , b}.
Example: Lexicographic ordering on Σ = {, , } is as follows:
{1, 2, 3, 11, 12, 13, 21, 22, 23, 31, 32, 33, 111, 112, 113, 121, 122, 123, . . .}
Exercise. Convince yourself that lexicographically ordered strings from the language Σ+ is equivalent to a BFS search on N’s nondeterministic computation tree.
Nondeterministic TM
Actual description of D:
1. Initialize the input tape with the input w, the address tape with the empty string ε (aka, root configuration), and leave the simulation tape empty.
2. Copy the input w from the input tape to the simulation tape.
3. Simulate N with input w on one branch of its computation on the simulation tape. Before each step of N, consult the next symbol on the address tape to determine which choice to make among those allowed by N’s transition function.
4. If no more symbols remain on the address tape or this choice is invalid or a rejecting configuration is encountered, abort this branch by going to stage . If an accepting configuration is encountered, accept the input and halt.
5. Replace the string on the address tape with the next string in the lexicographic ordering. Simulate the next branch of N’s computation by erasing the simulation tape and going to stage .
Turing-recognizable and Turing-decidable
Definition
A language is called Turing-recognizable / semi-decidable / recursively enumerable if some TM recognizes it.
Three outcomes are possible when a TM runs on an input: 1. Accept
2. Reject
3. Loop (aka, the machine doesn’t halt).
Definition
A TM is called a decider if it halts on all inputs x ∈ Σ∗.
A language is called Turing-decidable / decidable / recursive if some TM decides it.
Examples
Example (Decidable languages)
1. PAL = {yyreverse | y ∈ {,}∗} 2. L={anbncn |n∈N}
3. L={aibjck |i+j=k}
4. Any finite language L
Notation
D={A⊆Σ∗ |Aisdecidable}
SD = {A ⊆ Σ∗ | A is semi-decidable}
P ={A⊆Σ∗ |A=L(M)forsomeM whichhaltsin polynomial time}.
Theorem
P D SD.
Enumerator
Definition
An enumerator E is a -tape TM with an input tape and an output tape and a transition function
δ : Q × Γ → Q × Γ × {L, R} × {print, don’t print}.
E has an initial state, but no accept/reject states – it runs forever.
Note: The language L(E) enumerated by E is the set of strings it prints. E may print strings in any order and multiple times.
Semi-decidable iff enumerated by enumerator
Theorem
A language A ⊆ Σ∗ is semi-decidable iff some enumerator enumerates it.
Proof.
(←−)
Suppose E enumerates A. We define a TM M as follows:
On input w:
Run E.
Every time E computes a string, compare it with w;
if they match, halt and accept.
Clearly M recognizes A, and hence A is semi-decidable.
Semi-decidable iff enumerated by enumerator
(−→)
Conversely, suppose A is semi-decidable. Then A = L(M) for some TM M.
Let s, s, . . . ∈ Σ∗ be all possible strings in lexicographic order. Define E as follows:
Repeat the following for i = , , . . .:
Generate string si
Append it to the existing strings with a delimiter
Execute M’s next move on the inputs s,…,si
If any of the computations result in an accept state,
print out the corresponding sj.
Semi-decidable iff enumerated by enumerator
M executes
first step on s; then
first step on s, followed by second step on s; then
first step on s, followed by second step on s, followed by
third step on s; and so on …
s s s s …
.
Clearly, if M accepts s, then s eventually appears in L(E).
Remark.
This technique is called DOVETAILING. It gives the effect of running M in parallel on all possible input strings.
Decidable iff enumerated by enumerator lexicographically
Theorem
A language A ⊆ Σ∗ is decidable iff some enumerator enumerates it in lexicographic order.
Proof.
Exercise.