Why is “decidable” included in “Turing-recognizable”

computabilitydecidabilityturing-machines

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?

Best Answer

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.