title: Understanding recognizers and deciders in Theory of Computation
body: <p>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.</p>
  
  <p>When one says that a Turing Machine <code>T</code> recognizes language <code>L</code> where</p>
  
  <pre><code>L = { &lt;A&gt; | A is a DFA }
  </code></pre>
  
  <p><em>where DFA = deterministic finite automaton</em></p>
  
  <p>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.</p>
  
  <p>That is, if that input is a member of <code>L</code>. 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?</p>
  
  <p>On the other hand, a <code>decider</code> over a language seems to be a Turing Machine that never <code>loops</code>, 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?</p>
  
  <p>Thanks</p>