# Recognizable vs co-recognizable languages

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?

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".