# What is the difference between undecidable language and Turing Recognizable language?

I was wondering what is the difference difference undecidable language and Turing recognizable language. I've seen in some cases where they ask:

1. Prove that the language $A_{TM} = \{ \ <M,w> | \ M \mbox{ is a Turing Machine accepting } w\}$ is undecidable.
2. Prove that the language $A_{TM} = \{ \ <M,w> | \ M \mbox{ is a Turing Machine accepting } w\}$ is Turing Recognizable.

Are they the same thing? Can someone elaborate on this issue?

Another one, is the question at hand is known as the halting problem? Or is it different from halting problem?

• Look at the definitions.
– Raphael
Feb 19, 2018 at 10:38

A language $L$ is decidable if there exists a Turing machine $M$ such that:

• If $x \in L$ and $M$ is run with input $x$, then $M$ halts at an accepting state.

• If $x \notin L$ and $M$ is run with input $x$, then $M$ halts at a rejecting state.

(In particular, $M$ always halts.) If no such Turing machine exists, $L$ is undecidable.

A language $L$ is recognizable (or, recursively enumerable, abbreviated r.e.) if there exists a Turing machine $M$ such that:

• If $x \in L$ and $M$ is run with input $x$, then $M$ halts.
• If $x \notin L$ and $M$ is run with input $x$, then $M$ doesn't halt.

If no such Turing machine exists, $L$ is unrecognizable.

A basic fact about these definitions is:

A language $L$ is decidable if and only both $L$ and $\overline{L}$ are recognizable.

Your language $A_{TM}$ is one way of stating the halting problem (there are many equivalent ways). It is recognizable but not decidable.

• Is there any subset relation between undecidable language and Turing recognizable language? Feb 19, 2018 at 6:52
• No set is a subset of the other. Feb 19, 2018 at 9:24
• @Robur_131 There is no inclusion between them. However, we have that decidable implies recognizable. (Hence, unrecognizable implies undecidable)
– chi
Feb 19, 2018 at 12:11
• @YuvalFilmus you wrote If x∉L and M is run with input x, then M doesn't halt. I suppose it should be it may or may not halt. Cause if it does not halt then we would not have recursive languages a subset of recursively enumerable languages would we? Mar 21, 2018 at 8:04
• @SumeetSingh Under your proposed definition, every language is recognizable. Just take the machine that always halts. In order to show that every decidable language is recognizable, you take the Turing machine deciding the language and modify it to recognize the language (exercise). Mar 21, 2018 at 15:14