* Beslisbare taal (recursieve taal): Een taal L is beslisbaar als er een Turingmachine bestaat die, voor *elke* invoerreeks w, stopt en correct "ja" antwoordt als w ∈ L en "nee" als w ∉ L. Dit betekent dat de TM altijd stopt, ongeacht of de invoer in de taal is of niet.

* Herkenbare taal (recursief opsombare taal): Een taal L is herkenbaar als er een Turingmachine bestaat die, voor *elke* invoerreeks w, stopt en "ja" antwoordt als w ∈ L. Als w ∉ L kan het TM echter stoppen en "nee" antwoorden, of het kan voor altijd doorgaan (voor onbepaalde tijd herhalen). De sleutel is dat het *altijd* het juiste antwoord geeft ("ja") als de string in de taal staat; het is alleen toegestaan ​​om niet-deterministisch te zijn of geen antwoord te geven als de string *niet* in de taal is.

In eenvoudiger bewoordingen:

* Beslisbaar: De TM geeft altijd binnen een beperkte tijd een definitief antwoord (ja of nee).

* Herkenbaar: De TM geeft binnen een beperkte tijd een "ja" antwoord als de invoer in de taal is, maar geeft mogelijk geen antwoord (door voor altijd te herhalen) als de invoer niet in de taal is.

Elke beslisbare taal is ook herkenbaar. Het omgekeerde is echter niet waar; er zijn herkenbare talen die niet beslisbaar zijn. Het stopprobleem is een klassiek voorbeeld van een taal die herkenbaar maar niet beslisbaar is. Er kan een TM worden gebouwd die strings herkent die stoppende Turing-machines vertegenwoordigen (het simuleert de machine en antwoordt "ja" als deze stopt), maar geen enkele TM kan beslissen of een willekeurige Turing-machine zal stoppen bij een bepaalde invoer (omdat dat het stopprobleem zelf zou oplossen).

Het verschil komt neer op de vraag of het TM beëindiging garandeert voor alle invoer (beslisbaar) of alleen een "ja" antwoord in een beperkte tijd garandeert voor invoer in de taal (herkenbaar). Het verschil is fundamenteel in de berekenbaarheidstheorie.