2
$\begingroup$

Forming a language that is recognizable but not co-recognizable. I'm having trouble coming up with a language with these properties. A recognizable language is a language $A \subseteq \Sigma^*$ iff $A = L(M)$ for some Turing machine $M$.

Co-recognizable is the exact same except the complement of $A$ has to be recognizable.

My question is how do I come up with a language that I know will be recognizable but not co-recognizable?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Remember that there are three things a Turing machine can do, given an input. It can:

  • Accept
  • Reject
  • Diverge (infinite-loop)

"Recognizable" means "we can accept on strings in our language, and reject-or-diverge on anything else". "Co-recognizable" means "we can reject-or-diverge on strings in our language, and accept on anything else". Or, equivalently, "we can accept-or-diverge on strings in our language, and reject on anything else".

So the key is, intuitively, to find a language so that a TM always diverges on (some) strings not in the language.

A classic example is the Halting Problem. (To be more specific, the set of encoded Turing machines that halt on empty input, for a given encoding.) You can recognize this language by simulating the machine, then accepting. But you can't recognize its opposite.

(Formally, you have to do a bit more work. You have to prove that the language is undecidable: that no Turing machine can always say "no" correctly, even if it can always say "yes" correctly. Usually this means reduction to the Halting Problem or Rice's Theorem.)

Improve this answer
$\endgroup$
6
  • $\begingroup$ I think it's important to say that your last two paragraphs are only providing intuition. While it's true to say that you can't recognize the complement of the halting language just by simulating the machine in question to see what it does, that doesn't rule out the possibility that you could recognize that language some other way. Formally, you need to prove that no Turing machine recognizes the complement of HALT, e.g., by showing that a language and its complement being recognizable means that they're both decidable, which contradicts the undecidability of HALT. $\endgroup$
    – David Richerby
    Jun 4, 2019 at 14:09
  • $\begingroup$ @DavidRicherby True. I'll note that. $\endgroup$
    – Draconis
    Jun 4, 2019 at 16:07
  • $\begingroup$ Is there some obvious language that is recognizable but not co-recognizable? Only one I can think of is the HALT $\endgroup$
    – bob
    Jun 4, 2019 at 22:32
  • $\begingroup$ @bob Pretty much any language of encoded Turing machines, due to Rice's Theorem. "The set of encoded Turing machines that accept even numbers", for example, is recognizable but not co-recognizable. $\endgroup$
    – Draconis
    Jun 4, 2019 at 22:54
  • $\begingroup$ So intuitively this would mean for recognizable it just needs to find 1 set of even number of strings out of infinity number of strings to accept to make it recognizable. But the compliment is it wont accept any set of even number of strings which is hard to say because theres infinity possibilities so it cant be co-recognizable. is that correct? $\endgroup$
    – bob
    Jun 4, 2019 at 23:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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