Simulation of Nondeterministic Turing Machines-Again
A better better simulation of nondeterministic Turing machines
Bart de Keijzer just sent me a great comment. A great one. I was working on a continuation of my last post on the simulation of nondeterministic Turing machines (NTM). I have a additional insight into the simulation technology that was sketched there. For example, I now can prove,
Theorem: For a two-tape binary alphabet NTM with running time , there is a deterministic simulation with running time,
for any .
In the previous post, the constant was . But while I was preparing that post I got a great comment from de Keijzer that proves a much better result that I missed:
Theorem: For a -tape NTM with alphabet of size and running time , there is a deterministic simulation with running time,
Let be a -tape NTM running in time with tape alphabet of size . A configuration is a description of the non-blank contents of the tapes, the position of the tape heads, and a state. The length of each tape can be assumed to be , therefore a configuration for can be encoded as a string of length of symbols from an alphabet of size and at most additional bits. Thus, the total number of configurations is at most,
Let . The deterministic machine will construct a series of sets of configurations, for . Inductively, is the set of all configurations that can be in after steps. Clearly, we only accept if some accepting configuration is in some . Call the construction of the stage.
The set consists only of the initial configuration of . We will show how to go from to efficiently, and that will complete his proof. The machine can scan each configuration in and output all the configurations that can be reached in one step. Call this set .
We cannot use as since some configurations may occur more than once. So the machine sorts the set and removes any duplicate configurations to form .
That is how simulates . The remaining issue is how much time do the stages take in total? Clearly, there are stages, so the question is what is the cost of each stage. The first contribution to the cost is the pass over each configuration in and outputting the next configurations to form . This clearly takes at most
time since can simulate a configuration for one step in linear time. The remaining is the time to sort to remove duplicates. This takes at most
Note, the machine has to sort objects of size . Thus, the total time for a stage is
Hence, the total time for the simulation is
The main question remains, can we prove the conjecture of the last post?
Conjecture: For any ,
By the way this is, in my opinion, what this blog is all about. I am thrilled that some of the questions I have raised are getting solved. I think what Bart noticed, may seem simple now, but was missed by all of us for years. Great job Bart.