Onvolledigheid

Een tweede belangrijke wending in het 'mechaniseren' van het rekenen werd geïnitieerd door een grondslagenstrijd in de wiskunde in het begin van deze eeuw. Voorafgaande aan deze strijd werden wiskundigen in hun streven een solide 'objectieve' basis voor correcte wiskunde te geven geteisterd door streeds terugkerende paradoxen. Een van de belangrijkste stromingen die zich in deze strijd mengde waren de formalisten onder leiding van de toendertijd belangrijkste wiskundige: David Hilbert.

Deze formalisten wouden de wiskunde funderen op puur symbolische/axiomatische afspraken. Alle wiskunde moest volgens hen terug te brengen zijn tot puur symbolische manipulaties, uitgaande van een aantal vaststaande axioma's. Dit idee bracht ook de mechanisering van de wiskunde op tafel. Als alle wiskunde activiteit tot puur symbolische manipulatie terug te brengen is, dan hoef je het eigenlijk niet meer te begrijpen om toch wiskundig werk te doen. En, in zekere zin is dat ook wat veel van de schoolwiskunde beoogt. Begrijpt men bijvoorbeeld waarom een staartdeling een steeds correct antwoord geeft? Zelfs je oude schooljuf of meester zou je het niet hebben kunnen uitleggen.

Dit inzicht bracht David Hilbert tot de vraag of zo'n axiomatisering te samen met een aantal regels de volledige wiskunde zouden kunnen dekken. Is er zo'n puur symbolisch deductiesysteem te geven zodat elke wiskundige waarheid er mee af te leiden zou kunnen zijn? En, zoja, zouden we die afleidingen kunnen mechaniseren in termen van algoritmen, zodat zelfs vindingrijkheid overbodig zou zijn, en in feite, alle wiskundige activiteit door aardse machines overgenomen kon worden? De belangrijkste waarheid die dan met puur symbolische middelen te achterhalen zou moeten zijn is de consistentie van het systeem zelf. Daarmee zou voor eens en voor altijd met paradoxen afgerekend kunnen worden.

Hilbert voorzag dat de antwoorden op deze vragen niet gemakkelijk te verkrijgen waren, en plaatste dit probleeem op een lijst van de tien belangrijkste problemen voor de wiskunde in de 20ste eeuw. Helaas, of achteraf gelukkig, werd het antwoord hierop slecht enkele jaren nadat Hilbert het probleem had geformuleerd een negatief antwoord bewezen door Kurt Gödel. Een van die niet-afleidbare vragen was de juist zo fel begeerde consistentie van de toen moderne axiomatisering van de verzamelingentheorie.

Turing Machines

Natuurlijk vervloog ook de hoop op een mechanisering van de wiskunde. Ondanks dit inzicht bleef er toch een belangrijke vraag over. Iedereen was na enige tijd doordrongen van Gödel's gelijk, maar toch bleef onvolledigheid ontastbaar. Gödel's bewijs was tamelijk cryptisch, en gaf maar weining houwvast. Wat betekende het dat er problemen waren die niet in algoritmes op te lossen, of nog korter, "Wat is een algoritme?". De meest elegante definitie werd in de dertiger jaren gegeven door Alan Turing, en lijkt het meest op wat wij vandaag de dag onder een computerprogramma verstaan.

Turing gebruikte Hilbert's idee van symbolische manipulatie letterlijk, en beschreef zijn definitie als een pure aan regels (denk aan een programma) gehoorzame pen-en-papier operatie (in zijn eerste benadering dacht hij nog niet aan machines). Het papier, of ook wel de tape, bestond uit een oneindige rij van vakjes al dan niet gevuld met een symbool. Het potlood, ofwel de read/write head, staat op een van deze vakjes geplaatst. De genummerde regels, een eindig aantal, definieerde hij als bestaande uit drie elementen: een conditie in de vorm van een symbool, een potloodinstructie en een regelinstructie. Als nu degene die het algoritme uitvoert zo'n regel moet uitvoeren, beginnende bij de bovenste regel, dan moet hij als het symbool in de conditie overeenkomt met het symbool in het vakje waar zijn potlood opdat moment staat de instructies uitvoeren. De potloodinstructie kan een symbool bevatten of een richting: rechts of links. Indien de potloodinstructie een symbool bevat dan moet hij het huidige symbool in het door het potlood aangewezen vakje vervangen door het symbool van de instructie. Als een richting wordt aangegeven dan moet hij het potlood een vakje in die richting opschuiven. De regelinstructie geeft het nummer van de regel die hij vervolgens moet gaan uitvoeren. Als het symbool in de conditie niet overeenkomt moet de uitvoerder naar de volgende regel van het programma.

David Hilbert, 1862-1943 Kurt Gödel, 1906-1978 Alan Turing, 1912-1954
Een concreet voorbeeld als (A,rechts,8) betekent dus dat als het symbool A op dat moment gelezen wordt het potlood naar rechts geschoven moet worden, en vervolgens regel 8 uitgevoerd moet worden.

Als geen enkele conditie vervuld wordt en men bij het einde van de regels is aangekomen dan termineert het algoritme. Dat hoeft niet altijd te gebeuren: bijvoorbeeld het 1-regelige programma 1. (A,A,1) termineert nooit als het potlood op een vakje staat wat het symbool A bevat.

Turing machines worden gemakkelijker als we een grafische representatie gebruiken. Hiervan is een voorbeeld gegeven op de volgende pagina. Turing's veronderstelling was nu dat elk denkbaar algoritme op deze manier te beschrijven was. Natuurlijk is deze veronderstelling niet hard te maken omdat het om een definitie gaat, maar tot op de dag van vandaag heeft nog niemand een algoritme bedacht waar niet een equivalente Turing machine voor te verzinnen is. Bovendien toonde hij aan dat een bekend Amerikaans model voor algoritme, ingebracht door Alonso Church, equivalent was aan zijn formalisering. Turing toonde vervolgens aan dat er makkelijk te formuleren problemen zijn waarvoor geen Turingmachine voor te verzinnen is. Deze problemen zijn dus onberekenbaar, ook wel onbeslisbaar genoemd, volgens Turing's these.

Het meest bekende onbeslisbare probleem is het zogenaamde halting probleem. Turing's resultaat was dat er geen Turing machine (algoritme,programma) bestaat wat voor een willekeurig Turing machine en willekeurige tape bepaalt of het stopt of niet. Zo'n programma zou natuurlijk voor de informatica bijzonder welkom zijn, maar Turing's these aannemende, was al voor dat de eerste computers bestonden bewezen dat zo'n programma niet bestaat.