Deterministic Turing Machine
Observation: If N accepts w in n steps, then there is a sequence of n nondeterministic choices, i1,i2,...,in, that cause N to accept w.
The DTM M will search for such a sequence of nondeterministic choices:
- Given the sequence of choices that N makes, M can simulate N
- Don’t know what the right choices are. So simulate N for each possible choice!
- Don’t know how many steps N takes to accept w. Simulate N on sequences of all possible lengths!
- Essentially, do breadth first search on NTM’s “computation tree”
Deterministic Simulation: Details
DTM M uses 3 tapes to simulate NTM N
- Tape 1 always holds input w
- Tape 2 is used as N’s tape when simulating N on a sequence of nondeterministic choices
- Tape 3 stores the current sequence of nondeterministic choices.
M uses a subroutine that generates the “next” sequence of choices, after a simulation of N is complete 1. Subroutine generates sequences in {1,2,...r}∗ in lexicographic order, i.e., 1,2,...,r,11,12,...,1r,111,112,...
- Given a sequence (say 111) on Tape 3, the subroutine will write the next sequence (112) on Tape 3
Deterministic Simulation: Implementation
- Initialize: Tape 3 to the string 1
- Copy contents of Tape 1 onto Tape 2
- Simulate N using Tape 2 as its tape
(a) At the next step of N, if state is q, Tape 2 and 3 contain X and i respectively, then simulate the ith possibility in δ(q,X). (b) After changing state, Tape 2 contents, and head position on Tape 2, move Tape 3’s head to the right. If Tape 3 is now scanning B, then goto step 4 (c) If N accepts, then accept and halt. Otherwise, goto step 3(a) to simulate the next step of N
- Write the next sequence on Tape 3, erase everything on Tape 2 and goto step 2.
Deterministic Simulation: Correctness
- M simulates N over and over again, for different sequences, and for different number of steps
- If N accepts w, then there is a sequence of choices that will lead to acceptance. M will eventually have this sequence on Tape 3, and then its simulation N will accept
- If N does not accept w then no sequence of choices leads to acceptance. M will therefore never halt!
Seong-lae Cho