Chapter 6. Nondeterministic Turing machines

In the above chapters we discussed about the standard models of Turing machines. Now we turn to a generalization by introducing nondeterminism.

6.1. Definition of nondeterministic Turing machines

For simplicity, we define the single tape nondeterministic Turing machine only, but of course, similarly to the deterministic case, the multi tape model can be precisely given, too. Later we will see, that it is not necessary, but for the better identification we will use the notation instead of .

Definition 6.1.

The five tuple  is called a nondeterministic 
               
Turing machine, if 
nemdeterminisztikus 
               Turing-gÚpnek
            

             is a nonempty finite set; set of states
 finite set with at least  elements and ; tape alphabet

            ; initial state

            , nonempty; set of final states
; transition function

The notation refers to the power set of , i.e. the set which elements are the subsets of : .

By the above definition, the function maps its arguments to not single values, but to sets of values.

To distinguish the former models of Turing machines from the present one, we will call them deterministic Turing machines.

For the proper interpretation, we need similar concepts as in the case of deterministic Turing machines.

Similarly as before, we define the configuration of a nondetreministic Turing machine.

Definition 6.2.

A configuration of the nondeterministic Turing machine
 is  .

Remark 6.3.

The same rule is true here as in the deterministic case, namely
a nondeterministic Turing machine  may have a configuration in 
the form  if and only if  or .
One may notice, that there are no difference between the 
configurations of a deterministic and a nondeterministic Turing machine.

The real difference between the deterministic and nondeterministic Turing machine models is their operation semantics.

Definition 6.4.

We say, that the nondeterministic Turng machine  may go from  
to  in one step (or directly; notation ), if
   
   
            
and exactly one of the following is true:
1) 
   
            
   
            , 
       where ,  and .
   --- overwrite operation
2) 
   
            
   
            , where  ,  and .
   --- right movement operation
3) 
   
            
   
            , where ,  and .
   --- left movement operation

By the definition, one can say, that a nondetreministic Turing machine not steps, but may step to a new configuration. To understand better the difference between the definitions, we should study the concept of computation.

Definition 6.5.

Let  be a nondetreministic Turing machine. A possible computation of  
is a sequence  
                of configurations, such that 
1. , where ; 
2. , if there exists a directly reachable configuration from 
3. , if there are no directly reachable configuration from . 

The word  is called the input of .

We say that the configuration  is reachable from the configuration ,
if the Turing machine has a possible computation in the form  

If  is reachable from  and , then we say that the 
computation corresponding to  is finite and the Turing machine terminates 
in state  on this arm of computation. 
Then the word  is an output of .

The output of a nondeterministic Turing machine is the set:
.

For the proper interpretation one should note that there are no difference between the different transitions to different configurations (e.g. in the case of stochastic models), but the Turing machine regarded as it would continues its computation in all possible direction. (It may fission to several Turing machine in one step.)

Examples

1. Let , where , , and

:

.

The output of the Turing machine on the empty word is: .

The structure of the possible computations of the Turing machine can be described by the following infinite tree:

The green box is the initial configuration and the red boxes are the final configurations.

2. Let , where , , and

:

.

The output of the Turing machine on the empty word is: .

3. Let , where , , and

:

.

The output of the Turing machine on the empty word is: .

Just as in the case of deterministic Turing machines, one can define concept of nondeterministic accepting Turing machines. However, because of their operation properties, this is slightly different.

Definition 6.6.

Let  be a nondeterministic Turing machine,
 and . 
The  is called a nondeterministic acceptor Turing machine 
and the sates from  are called accepting states.

Definition 6.7.

Let  be a nondeterministic acceptor Turing machine and let  be
the set of accepting states of . 
We say that  accepts the word , if  has a finite computation on
the input , which terminates in a state from the set .

Definition 6.8.

Let  be a nondeterministic acceptor Turing machine.
The language  is called the language 
recognized by .

By the above definition, a nondeterministic Turing machine accepts a word , if it has a possible computation which accepts it. However, in the meantime it may have other computations, which reject it, but does not have an effect on the acceptance. A word is not accepted by a nondeterministic Turing machine, if it has no accepting computation at all. In general, it is seems to be much more difficult to analyse the operation of a nondeterministic Turing machine than a deterministic one, since there may infinitely many computations starts from the initial configuration.

Similarly as in the deterministic case, one can define the composition of nondeterministic Turing machines.

Definition (composition of nondeterministic Turing machines) 6.9.

Let  and  be two 
nondeterministic Turing machines and assume that . 
The Turing machine  (or ) is defined by the following
, where 
  , , , 
   and . 
Here 
 
where 
, for all  and
 or .

One may notice that the transition from the first Turing machine to the second is unique, just as in the case of deterministic Turing machines.