3
$\begingroup$

I understand following about recognizable (aka recursively enumerable) and co-recognizable languages:

  1. Definition 1: Recognizable language is one which have one-to-one correspondence with the natural number with the additional property that we could specify an algorithm to enumerate the language elements.

  2. For recognizable language, we can specify Turing machine which can enumerate the language elements.

  3. Given the string in the recognizable language, Turing machine can eventually confirm that the string indeed belongs to the language.

  4. Language L is called co-Turing-recognizable, if L’ is Turing-recognizable.

  5. Given the string not in the co-recognizable language, Turing machine can eventually confirm that the string indeed does not belong to the language.

Doubt

Q1. What is definition 1 equivalent of co-recognizable languages?

Q2. Do they also have one-to-one correspondence to natural numbers?

Q3. Do they also have Turing machine associated with them which can enumerate their elements?

Q4. If answer to Q2 and Q3 is true, then doesnt it make them same as recognizable?

$\endgroup$

1 Answer 1

2
$\begingroup$

A language is recognizable if there is a Turing machine that enumerates all words in the language. It is co-recognizable if there is a Turing machine that enumerates all words not in the language.

Every language has a one-to-one correspondence to the natural numbers, simply because the number of possible words is countable.

To see the difference between recognizable and co-recognizable, let's take the prototypical example of a recognizable language: it is the language of Turing machines which halt on the empty input. It is easy to enumerate this language: run in parallel all Turing machines on the empty input, and whenever one of them halts, print its index. There is provably no similar way to enumerate the complement of this language.

If a language is both recognizable and co-recognizable, then it is decidable, meaning that there is a Turing machine that always halts and tells you whether the input belongs to the language or not. Indeed, if $L$ is recognizable and co-recognizable, then there is a Turing machine $T_1$ which enumerates all words in $L$, and other Turing machine $T_0$ which enumerates all words not in $L$. Using these, we construct a decider $T$: on input $w$, run $T_1$ and $T_0$ in parallel, until one of them prints $w$. If it were $T_1$, answer "Yes", and if it were $T_0$, answer "No".

$\endgroup$
1
  • $\begingroup$ Second sentence resolved all doubts. But last paragraph was a fresh take on decidability, especially decider as two TMs. $\endgroup$
    – RajS
    Commented Nov 12, 2019 at 8:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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