A useless state in a Turing machine is one that is never ent

A useless state in a Turing machine is one that is never entered on any input string. Let L be the language consisting of Turing machines M with no useless state.

HINT: The use of nondeterministic Turing machines may simplify the proof

3. A useless state in a Turing machine is one that is never entered on any input string. Let L be the language consisting of Turing machines M with no useless state. a) Prove that L is recursively enumerable. b) Prove that L is not recursive.

Solution

By definition, if L is recursive enumerable, but not recursive, it means that for any Turing Machine T that recognize L, there exists at least one input ¯x 6 L such that T on input ¯x loops forever. We want to show that there actually are infinitely many such ¯x’s. Let us proceed by contradiction, assuming that the set S of all the strings ¯x 6 L that make T loop forever is finite. We can construct another Turing Machine T such that, on input x: • if x S, T halts and accepts; • if x 6 S, T halts and rejects. Then, we can build a Turing Machine T that decides L as follows. On input x, T first runs T with input x. If T accepts, then T halts and rejects. If T rejects, then T runs T on x. It is clear that adding the above preprocessing step, eliminates the possibility that T loops forever. In fact: • if x S, then T will halt and reject as soon as T stops executing; • if x 6 S, then T will get to run T which, by our assumption, will stop executing accepting or rejecting according to whether x L or x 6 L. By definition, the existence of such Turing Machine T implies that L is recursive. Since we reached a contradiction, the set S of input ¯x 6 L that make T loop forever must be infinite.