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

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 nondeterministicis a nonempty finite set; set of states finite set with at least elements and ;Turing machine, if nemdeterminisztikusTuring-gépnektape 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.