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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Look at the definitions. $\endgroup$ Commented Feb 19, 2018 at 10:38

1 Answer 1

Reset to default
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.

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.