Olyckliga språk är språk för vilka ingen algoritm (Turing Machine) kan existera som korrekt bestämmer för varje ingångssträng, oavsett om den strängen är medlem i språket. Avgörbara språk, däremot, * har * en sådan algoritm. Den viktigaste skillnaden ligger i förekomsten av en garanterad stoppalgoritm.
Här är några exempel på obeslutbara språk, som illustrerar olika sätt som obeslutbarhet uppstår:
1. Stoppproblemet (h):
* Språkbeskrivning: H ={⟨m, w⟩ | Turing Machine M stoppar på ingången W}. Detta språk består av alla par av en Turing Machine -kodning (⟨m⟩) och en ingångssträng (W) så att maskinen M stannar när den ges W som ingång.
* odecidability: Det har bevisats att ingen algoritm kan existera som korrekt bestämmer, för varje ⟨m, W⟩, huruvida m stoppar på w. Detta är ett grundläggande resultat i beräkningsteori. Varje försök att bygga en sådan algoritm leder till en motsägelse (vanligtvis genom diagonalisering).
* Varför är det obeslutbart: Stoppningsproblemets obeslutbarhet härrör från den inneboende självreferensiella karaktären hos Turing-maskiner. En hypotetisk algoritm som löser stoppproblemet kan användas för att skapa en paradoxisk maskin som strider mot sitt eget förutsagda beteende.
2. Acceptansproblemet (a):
* Språkbeskrivning: A ={⟨m, w⟩ | Turing Machine M accepterar W}. Detta liknar stoppproblemet, men fokuserar specifikt på acceptans (maskinen stoppar i ett accepterande tillstånd).
* odecidability: Detta är också obeslutbart. Om vi kunde bestämma a, kan vi också bestämma H (för om M accepterar W, stoppar det tydligt på W). Eftersom H är obeslutbar måste ett också vara obeslutbart.
3. Tomhetsproblemet för Turing Machines (E):
* Språkbeskrivning: E ={⟨m⟩ | L (m) =∅} där l (m) är det språk som accepteras av Turing Machine M. Detta språk innehåller kodningarna för alla Turing -maskiner som inte accepterar inga strängar alls (deras språk är tomt).
* odecidability: Det finns ingen algoritm som kan bestämma för varje Turing -maskin M, om L (M) är tom. Detta är relaterat till stoppproblemet; Om vi kunde lösa E, kunde vi lösa stoppproblemet genom att konstruera en maskin M 'som stannar om och bara om M stoppar och accepterar w.
4. Post Correspondensproblem (PCP):
* Språkbeskrivning: Detta är ett mer komplext exempel som involverar par av strängar. Det är obeslutbart att avgöra om en given uppsättning strängpar har en lösning (en sammankoppling av strängar från paren som matchar).
* odecidability: PCP:s obeslutbarhet bevisas med hjälp av reduktioner (som visar att om PCP var avgörande, skulle stoppproblemet också vara avgörande - en motsägelse).
Avgörbara språk - Kontrast:
Avgörande språk har å andra sidan * algoritmer som alltid stoppar och klassificerar strängar som tillhör språket eller inte. Exempel inkluderar:
* Palindromes språk: En algoritm kan enkelt kontrollera om en given sträng är samma framåt och bakåt.
* Språket för strängar som innehåller "ABC": En enkel algoritm kan skanna en sträng och kontrollera för underlaget "ABC".
* Språket för jämnt längdbinära strängar: En algoritm kan kontrollera strängens längd.
I huvudsak beror skillnaden till om en algoritm kan utformas för att * alltid * ge ett korrekt ja/nej svar i begränsad tid. För obeslutbara språk är en sådan algoritm bevisligt omöjlig att skapa. Förekomsten av en sådan algoritm är den definierande funktionen som skiljer sig från oavbrutna språk.
