Sipser's Theory of Computation, Third edition, chapter three asks me to prove this.

I see three languages in this problem:

  1. The original recognized language
  2. The set of strings in which the original recognizer halts in the reject state
  3. 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.

  • $\begingroup$ I guess we could exclude all strings that have, for example, make it halt on all strings that are prefixes of strings for which the original recognizer loops. However, that might exclude the entire language $\endgroup$
    – Anna Naden
    Commented Nov 11, 2021 at 7:29
  • $\begingroup$ I'm thinking about the properties of language three. If language one is undecidable then language three would have to be infinite, right? And what about the lengths of the strings in language three? If they are bounded then perhaps we can construct a finite superset from its prefixes and we would be done $\endgroup$
    – Anna Naden
    Commented Nov 11, 2021 at 7:52
  • $\begingroup$ We could reject strings whose length-n prefix is the length of the shortest string on which the recognizer loops. It seems that would produce a decidable subset, but how do we know that the subset so defined in infinite? $\endgroup$
    – Anna Naden
    Commented Nov 11, 2021 at 21:51

1 Answer 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .