Understanding recognizers and deciders in Theory of Computation

Question

I am having some trouble grasping what it means for a machine to recognize and decide a language. I think I'm close to the definitions but not right.

When one says that a Turing Machine T recognizes language L where

L = { <A> | A is a DFA }

where DFA = deterministic finite automaton

my understanding is that it means that it is possible to build a Turing Machine that given any kind of input (strings, cars, persons, whatever!) will be able to tell you whether that thing you gave it as input is a DFA or not. With this I mean, will always accept a DFA and will always reject a non-DFA input.

That is, if that input is a member of L. Other example would be saying that guy X is a recognizer of his father, as whatever is the thing you put in front of him, he will be able to tell you if what is in front of him is his father or not. Is this correct? Which part is not correct?

On the other hand, a decider over a language seems to be a Turing Machine that never loops, that is, it will always halt in either an accept or reject state for any input. Isn't this going to be similar, or the same, as what I explained above about recognizers?

Thanks

Answer 1

After some studying, I think I got the difference between the two.

As always, the devil is in the details.

To start off, a decidable language is always a recognizable language.

A recognizable language is a language for which there is at least one machine that has it as its language. At first this may seem like one more of those circular definitions, but..

In lay terms, a language is recognizable if you can think of a machine that'd be able to accept all its strings.

An example

Let's devise some really simple language:

L = { abc }

this language is composed only by the word abc. This means that to prove that this language is recognizable, one must build one machine that accepts it. We'll informally do it:

M is the machine that when given abc as input accepts, otherwise loops infinitely.

This machine accepts all the members of the language L, so it is a recognizer for L. Yet, for all other inputs it will just hang on forever. Would a machine exist that for every input accepts / rejects, this language could also be part of the class of decidable languages. Can you build one?

(spoiler alert!!!11@#$!1)

M' is the machine that when given abc as input accepts, otherwise rejects.

That is, as there is a machine that recognizes L and that whatever the input you give it, will always either accept / reject, the language is considered decidable.

Moreover, were you interest in one day building a machine that recognizes L, you'd know that you have at least one machine that's able to always do it without incurring in the problem of being able to accept abc but failing miserably in the other cases, hanging on forever!

Answer 2

Turing decidable means that there is a Turing Machine that accepts all strings in the language and rejects all strings not in the language, note that this machine is not allowed to loop on a string forever if it was a decider, it must halt at one stage and accept or reject the input string.

Turing Recognizable means there is a Turing Machine that accepts all strings in that language. Note that the machine does not have to reject strings which are not in the language, in other words, this machine is allowed to loop forever on strings which are not in the language.

To put it in high-level English, a decider machine must answer "Yes" or "No" to the question "is the string x in the language A" A recognizer must answer "Yes" to the same question if the string is in the language BUT if the string is not, it is allowed to say "No" or "No comment i.e. loop forever"