Berekenbaarheid

Principes

Complexiteitstheorie

Modellen

Algoritme

Turingmachine

Lambdacalculus

Theorieën

Berekenbaarheid

Complexiteitsgraad

NP-compleet

Berekenbaarheid is een deelprobleem van de complexiteitstheorie. Het vraagstuk van berekenbaarheid gaat over het bepalen van de grens tussen wat berekenbaar is en wat niet.

Inhoud

1 Basis van het probleem
- 1.1 Historische context
- 1.2 Definitie van "berekenbaarheid"
2 Grens van het berekenbare
- 2.1 Het beslissingsprobleem: het onbeslisbare probleem van Turing
  - 2.1.1 Aftelbaarheid van het aantal berekenbare problemen
  - 2.1.2 Bewijs van onbeslisbaarheid
- 2.2 Niet alles is herkenbaar
3 Reduceerbaarheid
4 Bronnen

[bewerk] Basis van het probleem

Het probleem van berekenbaarheid behandelt de vraag of er voor een gegeven, wiskundig probleem wel een oplossing kan bestaan.

Het mechanisme dat de berekenbaarheidsstudie gebruikt om deze vraag te beantwoorden, is de Turingmachine. De Turingmachine is een model van berekening en geeft (waarschijnlijk) aan waar de grens ligt van het berekenbare.

Om deze grens af te bakenen, maakt de berekenbaarheid gebruik van een aantal eigenschappen van wiskundige problemen, waaronder reduceerbaarheid.

[bewerk] Historische context

Sinds de tijd dat mensen begonnen zijn dingen op te schrijven, hebben mensen zich al afgevraagd of ze bepaalde zaken zouden kunnen voorspellen uit wat ze eerder gezien hadden. De Egyptenaren wilden de overstromingen van de Nijl kunnen voorspellen aan de hand van hun observaties van eerder gedrag van de rivier. In Babylonië moest de productie van graan bijgehouden worden en moesten verwachtingen uitgesproken worden over de benodigde opslagruimte. De noodzaak om zaken te modelleren en vanuit het model antwoorden te kunnen bepalen op de vraag van toekomstige ontwikkelingen was het begin van de wiskunde.

Vanaf 1870 raakte de wiskunde in een stroomversnelling. De abstracte logica deed zijn intrede, abstractiemechanismen werden steeds beter begrepen. De mogelijkheden van de wiskunde leken eindeloos en voor alles kon een oplossing gevonden worden. De enige beperking was het vinden van de manier om een oplossing op te stellen. In 1900 publiceerde David Hilbert zijn 23 problemen, een hoopvolle uitdaging aan de wiskundige wereld om binnen de volgende 100 jaar toch eindelijk die 23 rottige probleempjes op te ruimen.

In 1931 werd de droom van de onbeperkte wiskunde wreed verstoord: Kurt Gödel bewees dat, in een voldoende expressief systeem van wiskunde, er altijd zaken moeten zijn die niet bewezen of ontkracht kunnen worden. En de rekenkunde was een dergelijke, expressieve wiskunde. Met de ontdekking van Gödel rees de vraag of zelfs wel voor ieder rekenprobleem een oplossing bestond.

Het antwoord op deze vraag kwam in 1935 en 1936, toen de eerste modellen van berekeningen gepubliceerd werden. Deze modellen demonstreerden hoe een berekening eigenlijk uitgevoerd wordt. Met een berekeningsmodel in de hand kon precies uitgelegd worden hoe een gegeven probleem opgelost moest worden, stap voor stap. En er kon ook gekeken worden of er iets was dat niet berekend kon worden: was er een probleem waarbij het berekeningsmodel vastliep?

In 1936 publiceerde Alan Turing een – inmiddels wereldberoemd – artikel getiteld "On computable numbers, with an application to the Entscheidungsproblem". In dit artikel introduceerde hij het bekendste berekeningsmodel dat de wiskunde kent, de Turingmachine. En hij deed dat om aan te kunnen tonen dat hij een probleem had gevonden dat onoplosbaar, onberekenbaar was: het beslissingsprobleem.

[bewerk] Definitie van "berekenbaarheid"

De Turingmachine is een zeer simpel, mechanisch model van berekening. De machine verdeelt een berekening in een groot aantal zeer kleine stappen. Deze stappen worden een voor een uitgevoerd, totdat bepaald wordt dat de machine klaar is met het zetten van stappen. Op dat punt heeft de machine een van twee toestanden bereikt: de accepterende toestand (met de betekenis het is goed, of oplossing gevonden) of de afwijzende toestand (met als betekenis geen oplossing gevonden en de berekening kan ook niet verder).

Bij de vraag of een probleem P berekenbaar is, gaat het eigenlijk om de volgende vraag:

Stel, we hebben een algemeen probleem P, met alle mogelijke instanties I_P van P. Bestaat er een Turingmachine TM_P zodanig dat we iedere I_P op de band van TM_P kunnen zetten als invoer, TM_P aan kunnen zetten en dat TM_P dan na een eindige hoeveelheid tijd de accepterende of afwijzende toestand bereikt?

Een instantie I_P van een probleem P is overigens een specifiek voorbeeld van dat probleem P. Bijvoorbeeld, het vermenigvuldigen van twee getallen A en B is een probleem; het vermingvuldigen van 3 en 7 is een instantie van dat probleem.

De bovenstaande probleemstelling geeft een belangrijke beperking aan in de soort van Turingmachine die we zoeken als we naar een oplossing zoeken: het moet een Turingmachine zijn die altijd een antwoord oplevert (ja of nee). Het mag niet een machine zijn die ja op kan leveren of nee of ook gewoon eeuwig door kan blijven lopen. Dergelijke machines bestaan wel (we noemen dat herkenners), maar die leveren niet gegarandeerd voor iedere instantie een oplossing op – voor sommige instanties kunnen ze eeuwig blijven lopen. We zijn echt op zoek naar machines die altijd een antwoord opleveren (dit zijn de zogeheten beslissers).

Als we zeggen dat een probleem berekenbaar is, dan is er dus een belisser voor dat probleem – er is een Turingmachine TM die iedere instantie van het probleem beslist.

[bewerk] Grens van het berekenbare

In dit hoofdstuk zullen ingaan op de vragen of er wiskundige problemen zijn die niet beslisbaar zijn, of zelfs herkenbaar zijn. Die vragen zullen we positief beantwoorden: er zijn problemen die niet berekenbaar zijn en zelfs problemen die niet herkenbaar zijn.

We zullen beginnen met aan te tonen dat er een onbeslisbaar probleem is. Hiervoor zullen we een aantal technische details overnemen uit het bewijs van Alan Turing. Vervolgens komen we op een onherkenbaar probleem.

[bewerk] Het beslissingsprobleem: het onbeslisbare probleem van Turing

In het vorige hoofdstuk hebben we gesproken over een probleem P en een instantie van P. Dit is eigenlijk alweer een abstractieniveau hoger dan het niveau waarop de Turingmachine werkt. De Turingmachine kent helemaal geen problemen en instanties. Een Turingmachine kent alleen zijn regels voor het zetten van stappen (de transitiefunctie) en de rij symbolen op zijn band. Dat wij mensen daar problemen en instanties in zien, doet er niet toe. Het gaat om toestanden, transities en symbolen, meer niet.

In plaats van te praten over problemen en instanties, kun je het dus ook heel algemeen hebben over een gegeven Turingmachine TM en een rij symbolen s: het paar <TM, s>. En TM kan s beslissen, of niet. Vergeet problemen en instanties, we praten er alleen over of TM een beslisser is voor de rij symbolen s.

Als we het over een dergelijk paar <TM, s> kunnen hebben, dan kunnen we het ook over verzamelingen van paren hebben. Bijvoorbeeld over alle paren <TM, s> waarvoor TM een beslisser is voor s:

{ < T M, s > | TM beslist s}

Mensen die bekend zijn met formele talen, zullen op dit moment wellicht opmerken dat de bovenstaande verzameling op een formele taal lijkt. En dat klopt ook, het is de taal van paren van symboolrijen en Turingmachines die die symboolrijen beslissen.

Op dit moment zou je je af kunnen vragen of deze taal zelf beslisbaar is: kun je een Turingmachine bouwen die een paar <TM, s> als invoer heeft en bepaalt of dat paar ja of nee tot de bovenstaande verzameling behoort? Dit probleem heet het beslissingsprobleem. En nee, bewees Turing, hij is niet beslisbaar.

[bewerk] Aftelbaarheid van het aantal berekenbare problemen

Turings argumentatie begint met de vaststelling dat er weliswaar oneindig veel wiskundige problemen zijn, maar dat het aantal berekenbare problemen gelijk is aan het aantal natuurlijke getallen: aftelbaar veel. Dat wil zeggen, de verzameling die het beslissingsprobleem voorstelt is isomorf met $(\N \times S^*)$ , waarbij S de verzameling van alle symbolen is.

Stel, $M$ is een Turing-machine. Uiteraard bestaat de volledige machine $M$ uit een tupel van zeven elementen (toestanden, bandalfabet, begintoestand, accepterende toestand, afwijzende toestand en transitiefunctie). Maar stel nu dat we $M$ licht aanpassen tot $M +$ :

$M +$ bevat alle toestanden van $M$ – maar dan wel hernoemd tot de vorm $q_0, q_1, q_2, \ldots$
$M +$ bevat alle symbolen die $M$ bevat in zijn alfabet – maar dan wel hernoemd tot $k_0, k_1, k_2, \ldots$
In de transitiefunctie van $M +$ zijn alle toestanden en symolen correct vervangen
De begintoestand van $M$ is in $M +$ hernoemd tot $q 0$
De accepterende toestand van $M$ is in $M +$ hernoemd tot $q 1$
De afwijzende toestand van $M$ is in $M +$ hernoemd tot $q 2$

De hele machine $M +$ kan nu worden samengevat door zijn transitiefunctie $\delta_{M^+}$ . Immers:

$q 0$ is per definitie de begintoestand; $q 1$ en $q 2$ per definitie de accepterende en afwijzende toestanden
Het totaal aantal toestanden kan gevonden worden door in de transitiefunctie te zoeken naar de toestand $q i$ met de hoogste waarde van i – alle toestanden $q 0$ t/m $q i$ horen per definitie tot de verzameling toestanden van $M +$
Voor de symbolen geldt iets soortgelijks
De transitiefunctie blijft de transitiefunctie

Alle elementen van $\delta_{M^+}$ zijn afbeeldingen. Het domein van $\delta_{M^+}$ is een tuple van toestand en symbool, het bereik een triple van toestand, symbool en L of R – dat is de definitie van de transitiefunctie van een Turing-machine. Het domein en bereik van ieder element van $\delta_{M^+}$ kunnen we echter ook opschrijven als een tupel van vijf elementen:

$\{q_i, k_m\} \rightarrow \{q_j, k_n, D\}$

wordt dan

(q i, k m, q j, k n, D)

Ook deze vorm kunnen we weer omschrijven. In plaats van een tupel schrijven we alles dan aan elkaar als een "woord":

q i k m q j k n D

In deze vorm kunnen we de hele transitiefunctie $\delta_{M^+}$ aan elkaar schrijven, gescheiden door spaties of puntkomma's of iets dergelijks. Tenslotte kunnen we de hele transitiefunctie nog eens omschrijven, volgens de volgende regels:

$q i$ wordt 2 gevolgd door i 1'en
$k i$ wordt 3 gevolgd door i 1'en
$L$ wordt 4
$R$ wordt 5
het scheidingsteken tussen de elementen van de transitiefunctie wordt 6

Stel dat we in het voorbeeld hierboven i, j, m, n en D als volgt invullen:

q 3 k 3 q 4 k 7 R

Dan wordt de omgeschreven vorm

21113111211113111111156

Op deze manier kunnen we de hele transitiefunctie omschrijven naar een natuurlijk getal.

Deze omschrijving kan toegepast worden op iedere Turing-machine. Op deze manier correspondeert iedere Turing-machine een-op-een met een natuurlijk getal. De mogelijke Turing-machines zijn dus isomorf met een deelverzameling van de natuurlijke getallen. En omdat iedere oneindige deelverzameling van de natuurlijke getallen (net als de natuurlijke getallen zelf) aftelbaar is, is het aantal berekenbare problemen ook aftelbaar.

Tenminste, als de Turing-machines werkelijk alle berekenbare problemen kunnen beschrijven.

[bewerk] Bewijs van onbeslisbaarheid

Met de bovenstaande kennis in de hand is er een simpel bewijs te geven dat het beslissingsprobleem onbeslisbaar is.

Ten eerste heb je een Turingmachine nodig, die iedere transitiefunctie uit kan voeren (een Universele Turingmachine). En een dergelijke machine bestaat. Turing geeft er in zijn artikel een complete beschrijving van, maar om het overzichtelijk te houden laten wij die beschrijving hier achterwege. Zij simpelweg gezegd dat het idee dit is: je neemt een Turingmachine die gecodeeerd is tot een getal zoals hierboven beschreven. Die zet je op de band. Op de band reserveer je ook ruimte voor een natuurlijk getal – hiermee wordt de toestand van de gecodeerde machine bijgehouden. De rest van de band is voor de invoer van de gecodeerde machine en om als kladruimte te gebruiken. De universele Turingmachine speelt nu de gecodeerde Turingmachine na op de gegeven invoer. Er is ruimte om de toestand bij te houden, de invoer staat op de band en de transities zijn uit de codering op te zoeken.

Stel nu dat het mogelijk was om een machine B te maken, die het beslissingsprobleem beslist. Deze machine zou natuurlijk lijken op de bovenstaande, universele machine – hij zou een paar <TM, s> als invoer meekrijgen, een gecodeerde Turingmachine en diens invoer. B zou dan TM naspelen op s en als volgt resultaat opleveren (we noteren even B(<TM, s>) in de betekenis "het resultaat van het uitvoeren van B met invoer <TM, s>"):

$B(<TM, s>) = \{ \begin{matrix} \mbox{Als TM s accepteert} \rightarrow \mbox{accepteer} \\ \mbox{Als TM s niet accepteert} \rightarrow \mbox{wijs af} \end{matrix}$

Merk op dat B afwijst als TM afwijst, maar ook als TM gewoon niet eindigt (hier zit overigens de kneep van het probleem).

Stel dat we een dergelijk apparaat B hebben. Dan kunnen we B ook gebruiken om andere Turingmachines te maken – we spelen gewoon na hoe B andere machines naspeelt. Op een dergelijke manier kunnen we bijvoorbeeld een specialistische machine $B +$ bouwen, die als symboolrij s alleen maar beschrijvingen heeft van Turingmachines:

Zij M de codering van een Turingmachine als hierboven. Dan

$B^+(<TM, M>) = \{ \begin{matrix} \mbox{Als TM M accepteert} \rightarrow \mbox{accepteer} \\ \mbox{Als TM M niet accepteert} \rightarrow \mbox{wijs af} \end{matrix}$

Of nog iets anders: machine $B *$ , die precies het tegenovergestelde van $B +$ doet:

Zij M de codering van een Turingmachine als hierboven. Dan

$B^*(<TM, M>) = \{ \begin{matrix} \mbox{Als TM M accepteert} \rightarrow \mbox{wijs af} \\ \mbox{Als TM M niet accepteert} \rightarrow \mbox{accepteer} \end{matrix}$

Op dit punt is het even belangrijk om goed door te hebben wat machine $B *$ eigenlijk doet: deze machine geeft aan dat een Turingmachine TM niet een beslisser is voor de codering van Turingmachine M.

Wat gebeurt er nu als we het resultaat $B * ( < B *, B * > )$ laten uitrekenen? We krijgen dan:

$B^*(<B^*, B^*>) = \{ \begin{matrix} \mbox{Als } B^* \mbox{ } B^* \mbox{ accepteert} \rightarrow \mbox{wijs af} \\ \mbox{Als } B^* \mbox{ } B^* \mbox{ niet accepteert} \rightarrow \mbox{accepteer} \end{matrix}$

Maar hierboven staat feitelijk: als $B *$ een beslisser is voor de codering van $B *$ , geef dan aan dat $B *$ niet een beslisser is voor $B *$ . En als $B *$ niet een beslisser is voor $B *$ , geef dan aan van wel. Oftewel: als $B *$ een beslisser is voor $B *$ , dan is $B *$ niet een beslisser voor $B *$ . En andersom.

Dat is een tegenspraak. We hebben dus een machine $B *$ ontdekt die tegelijkertijd wel en niet een beslisser moet zijn. En die machine konden we bouwen, omdat we aangenomen hadden dat we het beslissingsprobleem konden beslissen. Die aanname is dus verkeerd.

Conclusie: het beslissingsprobleem is onbeslisbaar.

[bewerk] Niet alles is herkenbaar

Een herkenner is een Turingmachine die, gegeven een instantie van het probleem van die Turingmachine, accepteert, afwijst of eeuwig door blijft lopen. De herkenners zijn een krachtigere (meer expressieve) klasse van Turingmachines dan de beslissers – er zijn formele talen (bijvoorbeeld die van het beslissingsprobleem) die niet beslisbaar zijn, maar wel herkenbaar. De reden hiervoor is uiteraard dat het acceptabel is dat een herkenner niet altijd een antwoord oplevert.

Het klinkt dus alsof de herkenners alle problemen moeten omvatten die er ooit kunnen zijn. Toch zijn er talen die niet herkenbaar zijn. En dat is vrij eenvoudig aan te tonen.

Stel, T is een formele taal. Dan bestaat er ook co-T (het compliment van T, notatie $\bar{T}$ ), de taal die bestaat uit alle symboolrijen die niet in T zitten.

Stel nu dat we voor T en co-T een herkenner hebben. Dan kunnen we als volgt een Turingmachine bouwen:

Laat de herkenners voor T en voor co-T gelijktijdig lopen op een eigen kopie van dezelfde invoer. Accepteer als de herkenner voor T accepteert, wijs af als de herkenner voor co-T accepteert.

Iedere symboolrij moet in T of in co-T zitten. Dus voor iedere symboolrij moet een van beide machines accepteren. Dus wat hebben we hierboven gebouwd? Een beslisser voor T. Voor iedere taal T geldt: als T herkenbaar is en co-T ook, dan is T beslisbaar.

Van de taal van het beslissingsprobleem (taal B) weten we dat hij herkenbaar is, maar niet beslisbaar. B is niet beslisbaar, maar B is wel herkenbaar. Als co-B herkenbaar was, dan was B beslisbaar. Conclusie: co-B kan niet herkenbaar zijn.

[bewerk] Reduceerbaarheid

Een belangrijk hulpmiddel bij het bepalen of een gegeven probleem beslisbaar is of niet, is de techniek van reductie.

Het reduceren van een probleem wil zeggen P: zoek een manier om een probleem P uit te drukken in termen van een ander probleem Q. Als dat lukt, kun je de bekende eigenschappen van Q gebruiken om iets te zeggen over probleem P.

Als voorbeeld beschouwen we het halting problem, het probleem van het bepalen of een gegeven Turingmachine al dan niet stopt voor een gegeven invoer. De bijbehorende taal is

H A L T = { < T M, s > | TM is een Turingmachine en stopt in eindige tijd bij invoer s}

Stel dat we een Turingmachine H hebben, die dit probleem beslist.

Dan kunnen we een Turingmachine H' bouwen, als volgt:

Laat H lopen op invoer <TM, s>.

Als H afwijst, wijs dan af.

Als H accepteert, simuleer dan TM op invoer s.

Als TM s accepteert, accepteer dan. Zoniet, wijs af.

Met behulp van H hebben we een H' gebouwd die het beslissingsprobleem beslist. Conclusie: de beslisser H kan niet bestaan, HALT is een onbeslisbaar probleem.

Hierboven hebben we, in ons bewijs, gebruikgemaakt van het feit dat we al wisten dat het beslissingsprobleem onbeslisbaar is. Door reductie hebben we laten zien dat HALT onbeslisbaar moet zijn.

Reductie is niet alleen een belangrijk hulpmiddel bij berekenbaarheidsbepaling, maar ook bij het bepalen van de complexiteit van een probleem. De meeste NP-complete problemen worden niet gevonden door een apart bewijs van NP-compleetheid, maar door reductie tot een ander NP-compleet probleem.

[bewerk] Bronnen

Bron(nen):

On computable numbers, with an application to the Entscheidungsproblem
A.M. Turing
Introduction to the theory of computation
Michael Sipser
PWS Publishing Company
ISBN 0-543-94728-X / ISBN 053494728X
An introduction to formal languages and automata, Second edition
Peter Linz
D.C. Heath and Company
ISBN 0-669-35403-1

Categorieën: Theoretische informatica | Wiskunde