6.2. Simulation of nondeterministic Turing machines

It is a quite natural question what relation can be stated between the models of deterministic and nondeterministic Turing machines. Is the new approach provide extra power for computation?

Similarly as in the deterministic case, one can define the concept of simulation for nondeterministic Turing machines, too.

Definition 6.10.

Let  and  be two nondeterminstic Turing machines. We say that  
 simulates  if  and  we have . 

However, this definition of simulation may describe relations between nondeterministic Turing machines only. With a little modification one can extend it to deterministic Turing machines.

Definition 6.11.

Let  be a deterministic and let   be a nondeterministic Turing machine. 
We say that  simulates , if   and  we have . 

As a first observation, one can state the following theorem.

Theorem 6.12.

For all deterministic Truing machine  there exists a nondeterministic
Turing machine , which simulates .

Proof

Let be the Turing machine we want to simulate. We define as follows:

and the transition function is such that for all and we have .

By its definition, may go to only one new configuration from every configuration.

Clearly, simulates since has only a unique computation on any input and it is completely identical wit the computation of , thus their output is the same, too. (If has an output, its cardinality is one.) ✓

Remark 6.13.

By the proof of Theorem 6.12., there exists a unique nondeterministic
Turing machine corresponding to any deterministic one, which can be
regarded identic to it. 
This correspondence defines an embedding of the deterministic
Turing machines to the set of nondeterministic Turing machines. 
By this embedding, any deterministic Turing machine can be regarded 
to be a nondeterministic one in the same time. 

Theorem 6.12. states that every problem, which can be solved by a deterministic Turing machine, can be solved by a nondeterministic one, too. This means that the model of nondeterministic Turing machines are at least as strong as the model of deterministic Turing machines. However, at the moment it is not clear, if it is really stronger, i.e. whether there exists any problem, which can be solved by a nondeterministic Turing machine but not by a deterministic one. For simplicity, we will discuss simulation only for accepting Turing machines.

Definition 6.14.

Let  be a nondeterministic and let  be a deterministic acceptor
Turing machine. 
Wesay that  simulates  if .

The equivalence of the two models of Turing machines can be stated in the following way.

Theorem 6.15.

For all nondeterministic acceptor Turing machine  there exists a 
deterministic , which simulates .

Proof

The proof is constructive, but here we give the sketch of it only.

Let be the Turing machine, we want to simulate.

The basic idea is that the simulator Turing machine traverses the complete computation tree of by width first method. More precisely, it searches in the computation tree until either

a.) it finds a configuration with accepting state or

b.) there are no more configuration to observe.

have two tapes. The first tape contains the actual configuration of the simulated Turing machine, from which the possible steps are computed, while the second tape contains a FIFO data structure for storing the configuration to process.

A somewhat more precise description of its operation is the following:

1. By the content of tape it writes the initial configuration of to tape and writes a proper separation sign after it (e.g. ).

2. It observes, whether tape is empty. If yes, then it terminates in a nonaccepting state, otherwise it continues the computation in phase 3.

3. It copies the first configuration from tape to tape and deletes it from there.

4. It observes, whether the configuration on tape is in accepting state or not. If yes, then it terminates in an accepting state, otherwise it continues in phase 5.

5. It observes, whether the configuration on tape is in nonaccepting state. If yes, then it erases tape and continues with phase 2, otherwise it continues with phase 6.

6. It enumerates the possible transitions of in a fixed order, however, it does not execute them, but it copies to the end of tape , separating them by the separation sign. When all is copied, it continues in phase 2.

The above given deterministic Turing machine visits all configuration of with width first traversal, until it reaches an accepting configuration. If it finds one, the input is accepted. If no more configuration to visit (i.e. the computation tree is finite) then it terminates in a nonaccepting state. If the computation tree is not finite but no accepting configuration in it, then it continues computation in an infinite loop.

Clearly, accepts a word if and only if accepts it, i.e. .✓

Remark 6.16.

1. By Theorem 6.15. we can state that the model of nondeterministic 
Turing machines is not stronger than the model of deterministic 
Turing machines, i.e. if a problem can be solved by a nondeterministic 
Turing machine, then it can be solved by a deterministic one, too.
2. If  is a language and there exists a nondeterministic Turing machine
 such that , then .