1
$\begingroup$

enter image description here

(pic from "introduction to the theory of computation" - Michael Sipser)

According to my understanding:

  • Turing-recognizable languages are languages whice are accepted by a Turing machine;

  • decidable languages are languages for which a Turing machines halts, i.e. either accepts or rejects, but never loops.

This would make me think that decidable languages include Turing-recognizable languages, and not viceversa.

So why does Sipser depicts decidable languages as a subset of the recognizable ones?

$\endgroup$
3
  • 1
    $\begingroup$ Decidable languages are rarer, because when you don't accept, you must additionally reject. But with Turing recognizable languages, you don't care whether you reject or not. $\endgroup$
    – Trebor
    Commented Aug 21, 2021 at 14:26
  • 1
    $\begingroup$ For example, the set of mathematical statements which are provable is Turing-recognizable, but not decidable. $\endgroup$ Commented Aug 21, 2021 at 14:31
  • $\begingroup$ I quote the definition of Turing recognizable :"call a language Turing-recognizable if some Turing machine recognises it". That means if a Turing machine accepts all strings in that language, right? Accepting all strings means also to halt, so to decide. That's why I would be tempted to think that Turing-recognizable is included in decidable and not viceversa... That's what I don't understand $\endgroup$ Commented Aug 22, 2021 at 11:18

1 Answer 1

3
$\begingroup$

Recognizable means there is a Turing-machine that accepts all and only instances of that language. So that does not mean that if the input is not of that language, the machine rejects, because the machine could also go into some infinite loop if the input is otherwise.

Decidable means there is a Turing-machine that accepts all and only instances of that language, but also explicitly rejects when input is not that language. So, this Turing-machine will always halt, either accepting or rejecting.

So note that deciding is harder than merely recognizing. So, there are languages that are recognizable, but not decidable. But clearly, anything is decidable, is recognizable. So decidable is subset of recognizable.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .