حل تمرین نظریه محاسبات/فصل سوم/حل تمرین۳-۲

حل تمرین در کتاب سیپسر

We prove both directions of the "iff." First, 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 TM N, we construct a deterministic TM D2 that decides L. Machine D2 runs the same algorithm that appears in the TM D described in the proof of Theorem 3.10, with an additional Stage 3.5: Reject if all branches of the non determinism of N are exhausted. We argue that D2 is a decider for L. If N accepts its input, D2 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 D2 will halt and reject when this entire tree has been explored.