Okej, låt oss utforska området för icke-Turing-igenkännbara språk och hur de skiljer sig från turing-igenkännande (rekursivt faktiskt) och turing-avgörande (rekursiva) språk. Det är ett landskap av vad datorer * inte kan göra, och det är ganska intressant!
Förstå landskapet först
Innan vi dyker in i exempel, låt oss klargöra kategorierna:
* turing-deciderbara (rekursiva) språk: Det här är språk för vilka en Turing -maskin kan * alltid * stoppa och korrekt svara på "Ja" (acceptera) om ingångssträngen finns på språket eller "nej" (avvisa) om ingångssträngen inte finns på språket. Turing -maskinen ger alltid ett definitivt svar.
* turing-igenkännande (rekursivt faktiskt) språk: Dessa är språk för vilka en Turing -maskin kommer att stoppa och acceptera om ingångssträngen * är * på språket. Men om ingångssträngen är * inte * på språket, kan Turing -maskinen antingen stoppa och avvisa, eller så kan den gå för evigt (slinga). Nyckeln är att den * så småningom * säger "ja" för strängar på språket.
* Icke-Turing Erkännande (icke-återkänsligt faktiskt) språk: Detta är språk för vilka * ingen * Turing -maskin kan till och med utformas för att på ett tillförlitligt sätt känna igen strängar på språket. Oavsett hur smart du är, kan du inte bygga en Turing -maskin som accepterar alla strängar på språket (och potentiellt stoppar när det inte är det). Komplementet av ett Turing-igenkännligt språk är icke-turing igenkännbart.
Exempel på icke-Turing igenkännbara språk
De vanligaste exemplen på icke-Turing igenkännbara språk involverar ofta komplement av välkända obeslutbara problem.
1. Komplementet för stoppproblemet (¬halt):
* Stoppproblemet (stopp): Detta är språket som innehåller alla Turing Machine -kodningar `⟨m, w⟩` där Turing Machine` m` stannar på ingångssträngen `w`. (Detta är Turing-igenkännande men * inte * turing-avkoppbart).
* ¬halt: Detta är språket som innehåller alla Turing Machine -kodningar `⟨m, w⟩` där Turing Machine` m` gör * inte * på ingångssträngen `w`.
* Varför är det icke-Turing igenkännbart: Om ¬halt var turing-igenkännande, skulle stopp vara turing-avgörande (vi kunde simulera "m" på "w" och om vår igenkänning för ¬halt accepterar, vet vi att "m" inte stoppar; om det avvisar, vet vi att "m" stannar). Men stopp är * bevisat * obeslutbart. Eftersom stoppet är Turing-igenkännande men inte turing-avkoppbart, måste dess komplement, ¬halt, vara icke-turing igenkännande. Om stopp var avgörande skulle både det och det är kompliment att vara igenkännligt.
2. Komplementet för acceptansproblemet (¬a tm ):
* Acceptansproblemet (A tm ): Detta är språket som innehåller alla Turing Machine -kodningar `⟨m, w⟩` där Turing Machine` m` accepterar inmatningssträng `w`. (Detta är Turing-igenkännande men inte turing-avkoppbart).
* ¬a tm : Detta är språket som innehåller alla Turing Machine -kodningar `⟨m, w⟩` där Turing Machine` m` inte * accepterar ingångssträng `w`. `M` kan antingen avvisa eller slinga.
* Varför är det icke-Turing igenkännbart: Liknande resonemang som med ¬halt. Om ¬a tm var turing-igenkännbara, sedan en tm skulle vara turing-avgörande och motsäga den kända obeslutbarheten hos en tm .
3. Komplementet av tomhetsproblemet för Turing -maskiner (¬E tm ):
* Tomhetsproblemet (E tm ): Detta är språket som innehåller alla Turing Machine -kodningar `⟨m⟩ 'där språket som erkänns av Turing Machine` m` är tom (dvs `l (m) =∅`). (Detta är * inte * Turing-igenkännande).
* ¬E tm : Detta är språket som innehåller alla Turing Machine -kodningar `⟨m⟩ 'där språket som erkänns av Turing Machine` m` är * inte * tom (dvs `l (m) ≠ ∅`).
* Varför det är Turing-igenkännbart: En Turing -maskin kan känna igen detta språk genom att simulera maskinen "m" på alla möjliga ingångar tills "m" accepterar.
4. Språket för Turing -maskiner som inte stoppar på * någon * ingång:
* Tänk på språket för Turing -maskiner som, när den startas på * någon * inmatningssträng, aldrig kommer att stoppa. Det finns ingen allmän algoritm för att bestämma detta.
* Du kan försöka köra maskinen på många olika ingångar, men du kommer aldrig att vara säker på att den inte kommer att stoppa på någon annan, otestad ingång.
Hur icke-Turing igenkännbara språk skiljer sig
Den viktigaste skillnaden ligger i förmågan att skapa en Turing -maskin som * pålitligt * känner igen strängar på språket:
* turing-decidabla: En Turing -maskin * ger alltid * ett korrekt svar ("ja" eller "nej") och stoppar.
* turing-igenkännande: En Turing -maskin ger ett "ja" -svar om strängen är på språket, men kan slinga för alltid om strängen är * inte * på språket.
* icke-Turing igenkännbart: * Ingen* Turing -maskin kan konstrueras för att till och med pålitligt känna igen strängar på språket. Varje Turing -maskin du försöker kommer antingen att acceptera några strängar som * inte * på språket, slinga för alltid på strängar som * är * på språket eller misslyckas på något annat grundläggande sätt.
intuition
Tänk på det så här:
* Avgörbar: Du har ett perfekt pålitligt test som alltid ger dig rätt svar.
* igenkänd: Du har ett test som * definitivt kommer att säga "ja" om det är rätt svar, men det kanske inte kan berätta om svaret är "nej."
* icke-igenkännande: Du kan inte ens skapa ett test som pålitligt identifierar "ja" -fallen. Varje test du kommer med kommer att vara felaktiga och kan ge dig felaktiga resultat.
Viktiga konsekvenser
Förekomsten av icke-Turing igenkännbara språk har djupa konsekvenser för datavetenskap och matematik:
* beräkningsgränser: Det visar att det finns inneboende begränsningar för vad datorer kan göra, oavsett hur kraftfulla de blir.
* odecidability: Det belyser förekomsten av problem som i grunden är obeslutbara - det finns ingen algoritm som kan lösa dem i alla fall.
* Bevisstekniker: Det kräver användning av sofistikerade bevistekniker (som diagonalisering och reduktioner) för att visa obeslutbarhet eller icke-igenkännande av vissa problem.
Kort sagt definierar icke-Turing igenkännbara språk gränsen för vad som är grundläggande okomputerbart. De är en avgörande del av att förstå de teoretiska beräkningsgränserna.
