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
  • 1
    $\begingroup$ Look at the definitions. $\endgroup$
    – Raphael
    Feb 19, 2018 at 10:38

1 Answer 1

3
$\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$
16
  • $\begingroup$ Is there any subset relation between undecidable language and Turing recognizable language? $\endgroup$
    – Robur_131
    Feb 19, 2018 at 6:52
  • 1
    $\begingroup$ No set is a subset of the other. $\endgroup$ Feb 19, 2018 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, 2018 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, 2018 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$ Mar 21, 2018 at 15:14

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.