Hier zijn enkele voorbeelden van Turing-herkenbare talen, in tegenstelling tot andere taalklassen:

Voorbeelden van Turing-herkenbare talen:

* De taal van alle Turing-machines die stoppen op de lege string: We kunnen een Turing-machine bouwen die een gegeven Turing-machine op de lege string simuleert. Als de gesimuleerde machine stopt, accepteert onze machine. Als het voor altijd in een lus blijft, blijft onze machine voor altijd in een lus. Dit is herkenbaar; er is geen manier om definitief te zeggen dat een machine *niet* stopt.

* De taal van alle ware uitspraken in de eerste-orde rekenkunde: De volledigheidsstelling van Gödel laat zien dat elke ware bewering bewezen kan worden. Een Turingmachine kan systematisch alle mogelijke bewijzen opsommen en een verklaring accepteren als er een bewijs wordt gevonden. Als een bewering echter onwaar is, zal de machine nooit stoppen.

* De taal van alle contextvrije grammatica's die ten minste één reeks met een lengte van 10 genereren: Een Turingmachine kan systematisch alle snaren van een bepaalde CFG genereren en hun lengte controleren. Als het er een vindt met lengte 10, accepteert het. Als de CFG zo'n tekenreeks niet genereert, kan de machine voor onbepaalde tijd blijven draaien om er een te vinden.

* De taal van alle paren Turing-machines (M1, M2) zodat M1 stopt wanneer de codering van M2 als invoer wordt gegeven: Dit illustreert de complexiteit. We kunnen een machine bouwen die M1 simuleert op basis van de codering van M2. Als M1 stopt, accepteert onze machine. Anders loopt het in een lus. Dit benadrukt de onbeslisbaarheid die inherent is aan veel Turing-herkenbare problemen.

Hoe ze verschillen van andere soorten talen:

Het belangrijkste verschil ligt in het stopgedrag:

* Turing-beslisbare (recursieve) talen: Dit zijn talen waarvoor er een Turing-machine bestaat die altijd stopt en correct beslist of een bepaalde invoerreeks in de taal aanwezig is of niet. Elke string krijgt een duidelijk "ja" of "nee" antwoord. Voorbeelden hiervan zijn reguliere talen, contextvrije talen (met enkele beperkingen) en vele andere talen die kunnen worden bepaald door algoritmen met gegarandeerde beëindiging.

* Turing-herkenbare (recursief opsombare) talen: Zoals hierboven besproken, worden deze talen herkend door Turing-machines die voor altijd in een lus kunnen blijven hangen op strings die niet in de taal voorkomen. Ze zijn een *superset* van door Turing beslisbare talen; elke beslisbare taal is ook herkenbaar.

* Niet-Turing-herkenbare talen: Deze talen kunnen niet eens door een Turingmachine worden herkend. Er is geen algoritme, hoe inefficiënt ook, dat alle strings in de taal correct kan identificeren. Een voorbeeld is het complement van het Halting-probleem (de taal van alle Turing-machines die *niet* stoppen op de lege string).

Samengevat:

| Taalles | Gedrag stoppen | Voorbeeld |

|-----------------------|-------------------------------------------- ---|-----------------------------------------------------------------|

| Turing-beslisbaar | Stopt altijd, besluit correct over het lidmaatschap | Reguliere talen, contextvrije talen (met beperkingen) |

| Turing-herkenbaar | Stopt en accepteert strings in de taal, kan anders in een lus voorkomen | Taal van Turing-machines die stoppen op de lege string |

| Niet-Turing-herkenbaar | Geen enkele Turing-machine kan het herkennen | Aanvulling van het stopprobleem |

De hiërarchie is:Turing-beslisbaar ⊂ Turing-herkenbaar ⊂ Alle talen. De opname is strikt; er zijn herkenbare talen die niet beslisbaar zijn. En er zijn veel talen die zelfs verder gaan dan de herkenbare talen.