| Onbeslisbare talen zijn talen waarvoor geen algoritme (Turing-machine) kan bestaan dat voor elke invoerstring correct beslist of die string lid is van de taal. Beslisbare talen daarentegen *hebben* zo'n algoritme. Het belangrijkste verschil ligt in het bestaan van een gegarandeerd stopalgoritme.
Hier zijn enkele voorbeelden van onbeslisbare talen, die verschillende manieren illustreren waarop onbeslisbaarheid ontstaat:
1. Het stopprobleem (H):
* Taalbeschrijving: H ={⟨M, w⟩ | Turingmachine M stopt bij invoer w}. Deze taal bestaat uit alle paren van de codering van een Turing-machine (⟨M⟩) en een invoerreeks (w), zodat de machine M stopt wanneer invoer wordt gegeven.
* Onbeslisbaarheid: Het is bewezen dat er geen algoritme kan bestaan dat voor elke ⟨M, w⟩ correct bepaalt of M stopt op w. Dit is een fundamenteel resultaat in de berekenbaarheidstheorie. Elke poging om een dergelijk algoritme te bouwen leidt tot een tegenstrijdigheid (meestal door middel van diagonalisatie).
* Waarom het onbeslisbaar is: De onbeslisbaarheid van het stopprobleem komt voort uit het inherente zelfreferentiële karakter van Turing-machines. Een hypothetisch algoritme dat het stopprobleem oplost, zou kunnen worden gebruikt om een paradoxale machine te creëren die zijn eigen voorspelde gedrag tegenspreekt.
2. Het acceptatieprobleem (A):
* Taalbeschrijving: A ={⟨M, w⟩ | Turingmachine M accepteert w}. Dit is vergelijkbaar met het stopprobleem, maar richt zich specifiek op acceptatie (de machine stopt in een accepterende toestand).
* Onbeslisbaarheid: Ook dit is onbeslisbaar. Als we A zouden kunnen beslissen, zouden we ook H kunnen beslissen (want als M w accepteert, stopt het duidelijk op w). Omdat H onbeslisbaar is, moet A ook onbeslisbaar zijn.
3. Het leegteprobleem voor Turingmachines (E):
* Taalbeschrijving: E ={⟨M⟩ | L(M) =∅} waarbij L(M) de taal is die wordt geaccepteerd door Turingmachine M. Deze taal bevat de coderingen van alle Turingmachines die helemaal geen strings accepteren (hun taal is leeg).
* Onbeslisbaarheid: Er is geen algoritme dat voor elke Turingmachine M kan bepalen of L(M) leeg is. Dit houdt verband met het stopprobleem; als we E zouden kunnen oplossen, zouden we het stopprobleem kunnen oplossen door een machine M' te construeren die stopt als en slechts dan als M stopt en w accepteert.
4. Postcorrespondentieprobleem (PCP):
* Taalbeschrijving: Dit is een complexer voorbeeld waarbij paren van strings betrokken zijn. Het is onbeslisbaar om te bepalen of een gegeven set stringparen een oplossing heeft (een aaneenschakeling van strings uit de paren die overeenkomen).
* Onbeslisbaarheid: De onbeslisbaarheid van PCP wordt bewezen met behulp van reducties (waaruit blijkt dat als PCP beslisbaar zou zijn, het stopprobleem ook beslisbaar zou zijn – een tegenstrijdigheid).
Beslisbare talen – Contrast:
Beslisbare talen daarentegen *hebben* algoritmen die strings altijd stoppen en correct classificeren als behorend tot de taal of niet. Voorbeelden zijn onder meer:
* De taal van palindromen: Een algoritme kan eenvoudig controleren of een gegeven string zowel voorwaarts als achterwaarts hetzelfde is.
* De taal van tekenreeksen die "abc" bevatten: Een eenvoudig algoritme kan een string scannen en controleren op de substring "abc".
* De taal van binaire tekenreeksen met even lengte: Een algoritme kan de lengte van de string controleren.
In essentie komt het verschil neer op de vraag of een algoritme kan worden ontworpen om *altijd* binnen een beperkte tijd een correct ja/nee-antwoord te geven. Voor onbeslisbare talen is een dergelijk algoritme aantoonbaar onmogelijk te creëren. Het bestaan van een dergelijk algoritme is het bepalende kenmerk dat beslisbare van onbeslisbare talen onderscheidt. |
