Sipser's Theory of Computation, Third edition, chapter three asks me to prove this.
I see three languages in this problem:
- The original recognized language
- The set of strings in which the original recognizer halts in the reject state
- The strings on which the recognizer loops
We can combine machines for language one and the complement of language 2 in a single no deterministic Turing machines that is a decider. It will, however accept some strings that are not in language 1 (I think), so its language is not a subset of the original recognized language. So I'm stuck.
Best Answer
Probably you cannot find a decidable subset just by combining the TMs for your three languages. We need a more specific subset of the original language.
For example: for every Turing-recognizable/enumerable language $L$ there exists some enumerator. This TM has as outputs a list of all the words in the language. Denote the words in this list by $w_1,w_2,\dots$ for a given enumerator.
Now we define the index set $I$ as follows: $$\{i: |w_i|>|w_j| \text{ for all } j<i\}$$ We obtain all the indices of words, which are longer than all the words before them in our enumeration. $I$ is infinite, because for any index $i$ one can always find words longer than $w_i$ in $L$, since $L$ is infinite.
The set $\{w_i: i\in I\}$ is also decidable. For an input $v$ we run the enumerator and successively compare $v$ to the words $w$ that are produced. If at some point $w=v$, then the input is accepted. On the other hand, as soon as $|w|>|v|$ we can reject $|v|$. One of the two conditions is always reached after a finite number of steps.
Thus $\{w_i: i\in I\}$ is a subset of $L$, it is decidable and infinite.