Subtile misunderstanding about Recognizable vs Decidable

94 Views Asked by At

Recognizable vs Decidable

I think I understand the definition of Turing-recognizable and Turing-decidable, but still there's few subtle details I did not catch so far.

Can you explain in details why all decidable languages are also Turing-acceptable languages? Why in details the he reverse is not true?

EDIT

For a language decidable, if $x \in T^c$, does it have to terminate in a finite number of step? Is that the major difference between a Turing-recognizable and Turing-decidable? In other word, the language is decidable iff there a Turing-Machine which accepts a word of $L$ in finite number of steps and reject a word of $L^c$ in a finite number of steps.

1

There are 1 best solutions below

5
On

Edit: Let me clarify the definition. We say that a Turing machine $T$ decides language $L$ if, and only if, for every $x$, $T$ halts, and $T$ halts with "true" if $x \in L$ and "false" otherwise.

We say that a Turing machine $T$ recognises language $L$ if, and only if, for all $x$, $T$ halts with value "true" iff $x \in L$.

If $T$ decides a language, it halts on every input and tells you whether that input is in $L$. In other words, $T$ is required to "always tell the truth" about whether $x \in L$.

If $T$ recognises a language, it is obligated to halt whenever $x \in L$. It is also obligated "never to lie" - if $T$ halts on $x$, then it must report accurately whether $x \in L$. On the other hand, if $x \notin L$, $T$ has no obligation to halt.