Suppose we have a decidable language B (there exists some TM that decides it). Suppose we have another TM M which only recognizes B but does not decide it - there are words not in B that M doesn't halt on (for words not in B M might either reject or not halt).

Let A = {w | M does not halt on the word w}.

Which of the following has to be true:

1) A must be decidable

2) A might not be decidable but it has to be recognizable

3) A might not be recognizable but its complement has to be recognizable.

4) It might be that A and its complement are both not recognizable.

I was asked this question and i think that the answer is 3.

What i don't understand is why give the extra information about some decidable language B that M recognizes if the complement of A will always be recognizable regardless of whether it recognizes some decidable language B -> for any TM, the set of all the words it does halt on will always be recognizable. The recognizer for A complement will be - run M on w and accept if it halts).

What am i missing ? Is the info about B redundant ?


The question is designed to test your understanding, so it's legitimate regardless of whether the details of $B$ are actually relevant. Maybe you're supposed to understand why they're relevant; maybe you're supposed to understand why they're not.

You've said that "recognize" is defined to mean that the Turing machine accepts all words in the language, and either rejects or loops on words not in the language. This means that $A$ is some subset of $\overline{B}$ (the complement of $B$). Since $B$ is decidable, we know that $\overline{B}$ is also decidable. So, $A$ is a subset of some decidable language. Well, $\Sigma^*$ is a decidable language, so $A$ could be any subset of $\Sigma^*$. So it looks like $A$ could be any language at all! However, we have a little more information: $\overline{A} = \{w\mid M(w)\text{ halts}\}$, so $\overline{A}$ is recognizable.

  • $\begingroup$ I figured out the fact that A is a subset of B's complement in the start but still - why can't we always recognize A's complement ? $\endgroup$ – caffein Jan 12 at 0:09
  • $\begingroup$ If A is the words that M does not halt on then the complement is words M halts on meaning we can run M on w and accept when it halts and that's how we recognize A's complement so its recognizable right ? $\endgroup$ – caffein Jan 12 at 0:10
  • $\begingroup$ Am i correct ? ? $\endgroup$ – caffein Jan 12 at 0:40
  • $\begingroup$ I disagree with "$A$ could be any language". Since A = {w | M does not halt on the word w} this limits the possible languages $A$ to coRE ones. $\endgroup$ – chi Jan 12 at 11:27
  • $\begingroup$ @caffein You're correct. I've corrected my answer. (By the way, you probably shouldn't have accepted my answer while you weren't sure that it was correct.) $\endgroup$ – David Richerby Jan 13 at 9:53

By definition, $\bar A = \{w \ |\ M \mbox{ halts on } w \}$, which is recognizable: we run $M$ on $w$, accepting if it ever halts (and diverging otherwise).

So, the complement of $A$ must be recognizable. We now need to understand what class $A$ might belong to.

Take the trivial case where $B=\emptyset$ (which is decidable). This can be recognized by a TM $M$ which does the following: on input $w$, it semi-decides the halting problem on $w$, rejecting when $w\in HALT$, and diverging otherwise. Since this never accepts, it indeed recognizes $B=\emptyset$.

In this case, $A$ becomes the set of those $w$s making $M$ diverge, i.e. those $w \notin HALT$. Hence $A$ is the complement of the halting problem, which is not recognizable.

So, the answer is 3, as you pointed out.

The information about $B$ being decidable may appear a bit redundant at first, but actually it constraints our choice of $B$ when we wanted to prove that $A$ might be non recognizable. We could not pick $B=HALT$, for instance.

  • $\begingroup$ Yes, but even if M didn't recognize any decidable language - we could still say that the complement of A is recognizable simply by its definition - "all words M does halt on". right ? I mean A-complement will always be decidable, for such an A. $\endgroup$ – caffein Jan 12 at 14:33
  • $\begingroup$ And "A" itself will always be un-recognizable $\endgroup$ – caffein Jan 12 at 14:34
  • $\begingroup$ @caffein Note that $A$ can actually be decidable in some cases. E.g. Take $B$ to be the set of strings starting with 0. As a semidecider $M$ for $B$, make it diverge on the string $1$, accept any string in $B$ and reject the rest. In this case $A=\{1\}$, which is decidable. $\endgroup$ – chi Jan 12 at 14:39
  • $\begingroup$ Yes, sorry, i meant that A-complement will always be recognizable. Regardless of whether M decides any language at all, right ? Constructing a TM that accepts when M halts is always possible and this will always yield the complement of A, recognizing A-complement $\endgroup$ – caffein Jan 12 at 15:20
  • $\begingroup$ @caffein Yes, that looks correct. $\endgroup$ – chi Jan 12 at 17:16

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.