Eerst het landschap begrijpen

Laten we, voordat we in de voorbeelden duiken, de categorieën verduidelijken:

* Turing-beslisbare (recursieve) talen: Dit zijn talen waarvoor een Turingmachine *altijd* kan stoppen en correct kan antwoorden met "ja" (accepteren) als de invoerreeks in de taal staat, of "nee" (afwijzen) als de invoerreeks niet in de taal staat. De Turingmachine geeft altijd het definitieve antwoord.

* Turing-herkenbare (recursief opsombare) talen: Dit zijn talen waarvoor een Turingmachine stopt en accepteert als de invoertekenreeks *is* in de taal. Als de invoertekenreeks echter *niet* in de taal is, kan de Turingmachine stoppen en weigeren, of kan deze voor altijd blijven draaien (lus). De sleutel is dat er *uiteindelijk* "ja" staat voor tekenreeksen in de taal.

* Niet-Turing herkenbare (niet-recursief opsombare) talen: Dit zijn talen waarvoor *geen* Turing Machine zelfs maar kan worden ontworpen om op betrouwbare wijze tekenreeksen in de taal te herkennen. Hoe slim je ook bent, je kunt geen Turingmachine bouwen die alle strings in de taal accepteert (en mogelijk stopt als dat niet het geval is). Het complement van een Turing-herkenbare taal is niet-Turing-herkenbaar.

Voorbeelden van niet-Turing herkenbare talen

De meest voorkomende voorbeelden van niet-Turing-herkenbare talen omvatten vaak de complementen van bekende onbeslisbare problemen.

1. Het complement van het stopprobleem (¬HALT):

* Het stopprobleem (HALT): Dit is de taal die alle Turing Machine-coderingen `⟨M, w⟩` bevat, waarbij Turing Machine `M` stopt bij invoerstring `w`. (Dit is Turing-herkenbaar maar *niet* Turing-beslisbaar).

* ¬HALT: Dit is de taal die alle Turing Machine-coderingen `⟨M, w⟩` bevat, waarbij Turing Machine `M` *niet* stopt bij invoerstring `w`.

* Waarom het niet-Turing herkenbaar is: Als ¬HALT Turing-herkenbaar zou zijn, dan zou HALT Turing-beslisbaar zijn (we zouden `M` op `w` kunnen simuleren en als onze herkenner voor ¬HALT accepteert, weten we dat `M` niet stopt; als het afwijst, weten we dat `M` stopt). Maar HALT is *bewezen* onbeslisbaar. Omdat HALT Turing-herkenbaar is, maar niet Turing-beslisbaar, moet het complement ervan, ¬HALT, niet-Turing-herkenbaar zijn. Als HALT beslisbaar zou zijn, zouden zowel het compliment als het compliment herkenbaar zijn.

2. Het complement van het acceptatieprobleem (¬A_TM ):

* Het acceptatieprobleem (A_TM ): Dit is de taal die alle Turing Machine-coderingen `⟨M, w⟩` bevat, waarbij Turing Machine `M` invoertekenreeks `w` accepteert. (Dit is Turing-herkenbaar, maar niet Turing-beslisbaar).

* ¬A_TM : Dit is de taal die alle Turing Machine-coderingen `⟨M, w⟩` bevat, waarbij Turing Machine `M` de invoertekenreeks `w` *niet* accepteert. `M` kan weigeren of herhalen.

* Waarom het niet-Turing herkenbaar is: Soortgelijke redenering als bij ¬HALT. Als ¬A_TM Turing-herkenbaar waren, daarna A_TM zou Turing-beslisbaar zijn, wat in tegenspraak is met de bekende onbeslisbaarheid van A_TM .

3. De aanvulling op het leegteprobleem voor Turingmachines (¬E_TM ):

* Het leegteprobleem (E_TM ): Dit is de taal die alle Turing Machine-coderingen `⟨M⟩` bevat, waarbij de taal die wordt herkend door Turing Machine `M` leeg is (d.w.z. `L(M) =∅`). (Dit is *niet* Turing-herkenbaar).

* ¬E_TM : Dit is de taal die alle Turing Machine-coderingen `⟨M⟩` bevat, waarbij de taal die door Turing Machine `M` wordt herkend *niet* leeg is (d.w.z. `L(M) ≠ ∅`).

* Waarom het Turing-herkenbaar is: Een Turingmachine kan deze taal herkennen door machine 'M' op alle mogelijke invoer te simuleren totdat 'M' accepteert.

4. De taal van Turing-machines die niet stoppen bij *enige* invoer:

* Denk eens aan de taal van Turing Machines die, wanneer ze op *elke* invoerreeks worden gestart, nooit zullen stoppen. Er is geen algemeen algoritme om dit te bepalen.

* Je zou kunnen proberen de machine op veel verschillende ingangen te laten draaien, maar je zult er nooit zeker van zijn dat hij niet stopt op een andere, niet-geteste ingang.

Hoe niet-Turing herkenbare talen verschillen

Het belangrijkste verschil ligt in de mogelijkheid om een ​​Turing-machine te maken die *betrouwbaar* tekenreeksen in de taal herkent:

* Turing-beslisbaar: Een Turingmachine geeft *altijd* een juist antwoord ("ja" of "nee") en stopt.

* Turing-herkenbaar: Een Turingmachine geeft een "ja" antwoord als de string in de taal staat, maar kan voor altijd in een lus blijven als de string *niet* in de taal is.

* Niet-Turing herkenbaar: *Nee* Turing Machine kan worden geconstrueerd om zelfs op betrouwbare wijze tekenreeksen in de taal te herkennen. Elke Turing-machine die je probeert, accepteert een aantal tekenreeksen die *niet* in de taal voorkomen, loopt voor altijd door op tekenreeksen die *wel* in de taal voorkomen, of faalt op een andere fundamentele manier.

Intuïtie

Zie het als volgt:

* Beslisbaar: U beschikt over een volkomen betrouwbare test die u altijd het juiste antwoord geeft.

* Herkenbaar: Je hebt een test die *zeker* "ja" zegt als het het juiste antwoord is, maar die je misschien niet kan vertellen of het antwoord "nee" is.

* Onherkenbaar: Je kunt niet eens een test maken die de 'ja'-gevallen op betrouwbare wijze identificeert. Elke test die u bedenkt, zal gebrekkig zijn en u mogelijk onjuiste resultaten opleveren.

Belangrijke implicaties

Het bestaan ​​van niet-Turing herkenbare talen heeft grote gevolgen voor de informatica en wiskunde:

* Beperkingslimieten: Het laat zien dat er inherente beperkingen zijn aan wat computers kunnen doen, hoe krachtig ze ook worden.

* Onbeslisbaarheid: Het benadrukt het bestaan ​​van problemen die fundamenteel onbeslisbaar zijn; er bestaat geen algoritme dat ze in alle gevallen kan oplossen.

* Bewijstechnieken: Het vereist het gebruik van geavanceerde bewijstechnieken (zoals diagonalisatie en reducties) om de onbeslisbaarheid of niet-herkenbaarheid van bepaalde problemen aan te tonen.

Kortom, niet-Turing herkenbare talen definiëren de grens van wat fundamenteel onberekenbaar is. Ze zijn een cruciaal onderdeel van het begrijpen van de theoretische grenzen van berekeningen.