Turing-igenkännbara språk (även kallad rekursivt obegränsade språk) är språk för vilka det finns en Turing-maskin som stannar och accepterar strängar på språket, men kan slinga för evigt på strängar som inte är på språket. Detta står i kontrast till andra typer av språk på ett avgörande sätt:de bestämmer inte nödvändigtvis * medlemskap; De känner bara * igen * det.
Här är några exempel på Turing-igenkännbara språk, i kontrast till andra språkklasser:
Exempel på turing-igenkännbara språk:
* Språket för alla Turing -maskiner som stannar på den tomma strängen: Vi kan bygga en Turing -maskin som simulerar en given Turing -maskin på den tomma strängen. Om den simulerade maskinen stoppar accepterar vår maskin. Om det slingrar för evigt, slingrar våra maskiner för alltid. Detta är igenkännligt; Det finns inget sätt att definitivt säga att en maskin * inte * stoppar.
* Språket för alla sanna uttalanden i första ordningens aritmetik: Gödels fullständighetsteorem visar att varje sant uttalande kan bevisas. En Turing -maskin kan systematiskt räkna upp alla möjliga bevis och acceptera ett uttalande om ett bevis hittas. Men om ett uttalande är falskt kommer maskinen aldrig att stoppa.
* Språket för alla kontextfria grammatik som genererar minst en sträng längd 10: En Turing -maskin kan systematiskt generera alla strängar av en given CFG och kontrollera deras längd. Om den hittar en av längd 10 accepterar den. Om CFG inte genererar någon sådan sträng, kan maskinen köra på obestämd tid försöka hitta en.
* Språket för alla par av Turing -maskiner (M1, M2) så att M1 stoppar när den ges kodning av M2 som ingång: Detta illustrerar komplexiteten. Vi kan bygga en maskin som simulerar M1 vid kodningen av M2. Om M1 stoppar accepterar vår maskin. Annars slingrar det. Detta belyser den obeslutbarhet som är inneboende i många Turing-igenkännliga problem.
Hur de skiljer sig från andra typer av språk:
Den viktigaste skillnaden ligger i stoppbeteendet:
* turing-deciderbara (rekursiva) språk: Detta är språk för vilka det finns en Turing -maskin som alltid stoppar och avgör korrekt om en given ingångssträng finns på språket eller inte. Varje sträng får ett definitivt "ja" eller "nej" svar. Exempel inkluderar vanliga språk, kontextfria språk (med vissa begränsningar) och många andra som kan beslutas av algoritmer med garanterad uppsägning.
* turing-igenkännande (rekursivt faktiskt) språk: Som diskuterats ovan erkänns dessa språk av Turing -maskiner som kan slinga för evigt på strängar som inte är på språket. De är en * superset * av turing-avgörande språk; Varje avgörande språk är också igenkänd.
* icke-Turing-igenkännbara språk: Dessa språk kan inte ens erkännas av en Turing -maskin. Det finns ingen algoritm, dock ineffektiv, som korrekt kan identifiera alla strängar på språket. Ett exempel är komplementet till stoppproblemet (språket för alla Turing -maskiner som * inte * stoppar på den tomma strängen).
Sammanfattningsvis:
| Språkklass | Stoppande beteende | Exempel |
| --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
| Turing-avgörande | Stoppar alltid, beslutar korrekt medlemskap | Regelbundna språk, kontextfria språk (med begränsningar) |
| Turing-igenkännande | Haltar och accepterar strängar på språket, kan slinga annars | Språk för Turing -maskiner som stannar på den tomma strängen |
| Icke-Turing-igenkännande | Ingen Turing -maskin kan känna igen den | Komplement av stoppproblemet |
Hierarkin är:Turing-deciderbar ⊂ Turing-igenkännande ⊂ alla språk. Inkluderingen är strikt; Det finns igenkännliga språk som inte är avgörande. Och det finns många språk utöver även de igenkännliga.
