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

Question

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?

Answer 1

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.