Understanding recognizers and deciders in Theory of Computation
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
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!