Question

Modify the proof of Theorem 3.16 to obtain Corollary 3.19, showing that a language is decidable if some nondeterministic Turing machine decides it. (You may assume the following theorem about trees. If every node in a tree has finitely many children and every branch of the tree has finitely many nodes, the tree itself has finitely many nodes.)

Short answer

This theorem is proved

Step-by-step solution

NONDETERMINISTIC TURING MACHINES.

A nondeterministic Turing machine is defined in the expected way. At any point in a computation, the machine may proceed according to several possibilities. The transition function for a nondeterministic Turing machine has the form

$\delta :Q\times \Gamma \to P\left(Q\times \Gamma \times \left\{L,R\right\}\right).$

The computation of a nondeterministic Turing machine is a tree whose branches correspond to different possibilities for the machine. If some branch of the computation leads to the accept state.

Nondeterministic Turing machine theorem.

Here the both directions of the if and only if the language follows the property of Turing machine or the grammar, language L or string must be passes from its machine called as Turing machine.

Firstly, if a language L is decidable, it can be decided by a deterministic Turing machine, and that is automatically a nondeterministic Turing machine.

Second, if a language L is decided by a nondeterministic Turing machine N, we modify the deterministic Turing machine$D_0$that was given in the proof of theorem as follows.

Move stage 4 to be stage 5. Add new stage 4: Reject if all branches of N’s non determinism have rejected. We argue that this new Turing machine$D_0$is a decider for language L.

If N accepts its input,$D_0$will eventually find an accepting branch and accept, too. If N rejects its input, all of its branches halt and reject because it is a decider.

Hence each of the branches has finitely many nodes, where each node represents one step of N’s computation along that branch.

Therefore,N ’s entire computation tree on this input is finite, by virtue of the theorem about trees given in the statement of the exercise. Consequently, $D_0$will halt and reject when this entire tree has been explored.