1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Look at the definitions. $\endgroup$ – Raphael Feb 19 '18 at 10:38
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is there any subset relation between undecidable language and Turing recognizable language? $\endgroup$ – Robur_131 Feb 19 '18 at 6:52
  • 1
    $\begingroup$ No set is a subset of the other. $\endgroup$ – Yuval Filmus Feb 19 '18 at 9:24
  • $\begingroup$ @Robur_131 There is no inclusion between them. However, we have that decidable implies recognizable. (Hence, unrecognizable implies undecidable) $\endgroup$ – chi Feb 19 '18 at 12:11
  • $\begingroup$ @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? $\endgroup$ – Sumeet Mar 21 '18 at 8:04
  • $\begingroup$ @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). $\endgroup$ – Yuval Filmus Mar 21 '18 at 15:14

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.