Turing-machine na 65 jaar nog niet met pensioen

Stelt u zich een pc voor die nooit kapot gaat en een onbeperkte opslagcapaciteit heeft. Wat zou zo’n pc in principe wel en niet kunnen berekenen? Het antwoord op deze vraag is al heel lang bekend. De zojuist beschreven pc is namelijk niets anders dan een Turing-machine, een apparaat waarvan de mogelijkheden en beperkingen al in 1936 door de Engelse wiskundige Alan Turing in kaart werden gebracht. Turing zag zijn machine als een model voor de verrichtingen van een menselijke rekenaar die zich braaf aan de regels houdt en geen gebruik maakt van zoiets als intuïtie. Hij liet zien dat dergelijke rekenaars principiële beperkingen hebben, zelfs als ze het eeuwige leven hebben, geen fouten maken en een onbeperkte hoeveelheid kladpapier tot hun beschikking hebben: er zijn getallen en wiskundige functies die ze niet kunnen berekenen en er bestaan problemen die ze nooit kunnen oplossen. Onze tegenwoordige pc’s kunnen niet meer dan dergelijke rekenaars en hebben dus dezelfde tekortkomingen (en meer, omdat ze immers maar een beperkte opslagcapaciteit en levensduur hebben). Alle verbeteringen aan de digitale computer die tegenwoordig worden overwogen zullen deze beperkingen niet opheffen. Massief parallellisme brengt geen wezenlijke verandering in de situatie: digitale computers met miljarden parallel werkende processors zullen stellig sneller werken dan een oude Pentium met maar één processor, maar kunnen in feite niet méér dan zo’n oud model. Hetzelfde geldt voor de quantumcomputers die tegenwoordig geregeld in het nieuws zijn: ze zullen sneller werken dan een oude Pentium, maar zullen toch dezelfde principiële beperkingen hebben. De Turing-machine heeft dit jaar de pensioengerechtigde leeftijd bereikt. Zou de tijd zo langzamerhand niet gekomen zijn om eens over krachtiger rekenmachines na te denken? Ja, zeggen de zogenaamde ‘hypercomputationalisten’, een groeiend internationaal gezelschap van onderzoekers dat zich bezighoudt met ‘hypercomputers’ (ook wel ‘super Turing-machines’ genoemd), computers die fundamenteel krachtiger zijn dan de Turing-machine. Deze onderzoekers laten steeds meer van zich horen: vorig jaar vond de eerste internationale conferentie over hypercomputation plaats op University College in Londen, het aantal publicaties in de wetenschappelijke literatuur neemt toe, Scientific American heeft het onderwerp opgepikt (april 1999), en er is inmiddels een speciale website aan dit thema gewijd (www.hypercomputation.net). Zoals te verwachten valt, zijn vooral niet-informatici (met name natuurkundigen, filosofen, logici en wiskundigen) met dit onderwerp bezig; de informatica is nog steeds volledig in de ban van Turing. De resultaten zijn op dit moment alleen nog maar van theoretisch belang; men is nog druk bezig om zich te bevrijden van het dominante Turing-machinemodel en andere wegen te verkennen. De eerste toepassingen zijn echter al aangekondigd: Mike Stannett van The Noise Factory (Verenigd Koninkrijk) is van plan de eerste hypercomputer over een paar jaar op de markt te brengen. Orakels Hoe zouden we de Turing-machine kunnen overtreffen? Het oudste idee stamt van Turing zelf. Zoals gezegd, is de Turing-machine een model van een rekenaar die geen gebruik maakt van zoiets als intuïtie. Wat zou er gebeuren als we een Turing-machine zouden begiftigen met intuïtie? Om dit te onderzoeken bedacht Turing in 1939 de zogenaamde ‘O-machine’. De ‘O’ staat voor ‘orakel’. Een O-machine is een Turing-machine die ja/nee-vragen mag stellen aan een zogenaamd orakel, dat dan vervolgens het juiste antwoord geeft, waarna de machine weer verder gaat. Het zal duidelijk zijn dat een machine die af en toe de hulp van een orakel kan inroepen krachtiger is dan een gewone Turing- machine. Een voorbeeld: een Turing-machine kan het zogenaamde stop-probleem (stopt Turing-machine nr. X wel of niet gegeven input nr. Y?) niet oplossen. Een O-machine kan dat wel: hij kan de vraag immers gewoon voorleggen aan het orakel. Dat wil overigens niet zeggen dat O-machines absoluut alles kunnen: ze hebben weer hun eigen beperkingen. Turing verloor al snel zijn belangstelling voor orakels. Toen de eerste elektronische computers ten tonele verschenen raakte hij zó onder de indruk van hun vermogens dat hij meende dat we voor het modelleren van menselijk gedrag nooit een beroep zouden behoeven te doen op een niet-mechanisch orakel. Het blijft echter een interessante vraag of er misschien orakels in de natuur zouden kunnen bestaan. Eén ding waaraan we kunnen denken zijn de constanten in de fysica, zoals de zwaartekrachtconstante of het getal van Planck. Het is niet gezegd dat deze door een of ander computerprogramma kunnen worden gegenereerd. Als we een apparaatje hadden dat ze op een geschikte manier zou kunnen decoderen, zou dat misschien als orakel kunnen fungeren. Een simpel voorbeeld: stel dat de zwaartekrachtconstante binair uitgeschreven er zo uitziet: 0,010101111000... Het zou kunnen zijn dat het Xste getal achter de komma precies het antwoord bevat op de vraag of de Xste Turing-machine stopt gegeven de Xste input. Een apparaatje dat het Xste getal achter de komma uit kan lezen zou een prima orakel zijn. Iets anders waaraan wel wordt gedacht is ruis. De natuur is vergeven van bronnen van ruis: kosmische straling, radioactief verval et cetera. Ook hieruit valt misschien onberekenbare informatie te distilleren, die als extra bron van informatie voor een Turing-machine kan fungeren. De aangekondigde hypercomputer van The Noise Factory is op dit idee gebaseerd. Neurale netwerken Een ander gebied waarop we orakels tegenkomen is het neurale netwerken-onderzoek. Neurale netwerken zijn geïdealiseerde modellen van stukjes zenuwweefsel. Ze bestaan uit talloze componenten die via verbindingen met een bepaald ‘gewicht’ met elkaar verbonden zijn. In de meeste netwerken mogen de gewichten iedere reële waarde tussen 0 en 1 aannemen. Ze kunnen in principe dus ook waarden aannemen die door geen enkele Turing- machine kunnen worden berekend (zoals het getal 0,010101111000... dat we al noemden). Als we nu een module inbouwen die dergelijke waarden op een geschikte manier kan uitlezen, kan die module als een soort orakel fungeren, en krijgen we een netwerk dat in principe meer vermag dan welke Turing-machine ook. Deze constructie wordt in detail beschreven in het boek Neural Networks and Analog Computation: Beyond the Turing Limit (1998) van de Israëlische onderzoekster Hava Siegelmann. Interessant genoeg zijn de biologisch meest realistische modellen van het menselijke zenuwstelsel equivalent met de netwerken van Siegelmann. Dit suggereert dat onze eigen hersenen hypercomputers zijn. Helaas is er een factor die roet in het eten gooit: ruis. Als je realistische soorten ruis aan het model toevoegt kunnen de waarden van de gewichten niet meer met de benodigde precisie worden uitgelezen, en krijg je netwerken die veel minder krachtig zijn dan de Turing-machine. Dit lijkt een belangrijke beperking te zijn: ik weet niet hoe het met andermans hersenen zit, maar ik weet wel zeker dat er in de mijne nogal wat ruis zit. Siegelmann werpt hier tegenin dat deze resultaten misschien te pessimistisch zijn. Haar netwerken zijn wel degelijk bestand tegen een matige portie ruis, misschien alle ruis waar we in de praktijk mee te maken krijgen. Het laatste woord is hierover nog niet gezegd. Het wachten is op het hersenonderzoek van de toekomst. Tegelijkertijd zeggen sommige natuurkundigen wel dat ruis eigenlijk helemaal niet bestaat. Volgens hen is ruis alleen maar een ander woord voor ‘onwetendheid’. Als dat zo is, hoeven we er misschien helemaal geen rekening mee te houden. Orakels zijn niet de enige manier om tot hypercomputation te komen. Historisch gezien was de eerste hypercomputer na Turings O-machine de zogenaamde geaccelereerde Turing-machine. Deze machine zet zijn eerste rekenstapje in een halve seconde, de tweede stap in een kwart seconde, de derde in een achtste enzovoort. We lezen hem af na een seconde, en laten wat we dan zien gelden als resultaat van het rekenwerk. Een dergelijke machine kan meer dan een Turing-machine. Neem bijvoorbeeld het stop-probleem. Zoals we al hebben gezien, is de vraag of een bepaalde Turing-machine gegeven een bepaalde input al dan niet stopt in het algemeen niet te beantwoorden. Maar als we Turing-machines onbeperkt kunnen versnellen hebben we geen last van dit probleem: we zetten gewoon de versnelde versie van de machine aan en kijken of hij na een seconde nog werkt. Zo ja, dan luidt het antwoord ‘nee’, zo niet, dan is het ‘ja’. Helaas zijn geaccelereerde Turing-machines waarschijnlijk onmogelijk in ons universum, waarin we rekening moeten houden met maximumsnelheden (de lichtsnelheid) en minimumafstanden (de Planck-lengte). Deze machines zijn praktisch gezien dus niet zo interessant. Gefascineerd Met het bovenstaande zijn de mogelijkheden op het gebied van de hypercomputation nog lang niet uitgeput. De hypercomputationalisten worden ook gefascineerd door analoge automaten. Turing-machines zijn in alle opzichten discreet, net zoals onze tegenwoordige digitale computers: ze werken in duidelijk van elkaar onderscheiden rekenstapjes en gaan met duidelijk van elkaar afgebakende symbolen om (bijvoorbeeld enen en nullen). Natuurkundige systemen zijn doorgaans echter analoog: ze worden beschreven met continue waarden (reële getallen, zoals de wortel van twee) en gemodelleerd met differentiaalvergelijkingen, integralen en wat dies meer zij. Dit opent perspectieven. In het analoge domein is er namelijk veel meer mogelijk dan in het digitale domein. Dit zagen we al bij de analoge neurale netwerken van Siegelmann, die immers super Turing-vermogens hadden. Maar haar modellen hadden nog de beperking dat ze in discrete rekenstapjes werken en alleen maar enen en nullen als input accepteren en als output produceren. Als we ook de tijd en de input-output continu maken is er stellig nog meer mogelijk. Helaas valt er over dit gebied verder weinig te zeggen, omdat het nog onvoldoende onderzocht is. Er zijn analoge modellen die in continue tijd werken en krachtiger zijn dan Turing-machines, maar deze lijken niet erg realistisch te zijn vanuit fysisch oogpunt. Al met al kunnen we concluderen dat het vakgebied van de hypercomputation nog in de kinderschoenen staat. Theoretisch is er al veel bereikt, maar het staat nog maar te bezien of de verzonnen modellen ook fysisch mogelijk zijn. Veel hangt af van de natuurkunde: welk soort berekeningen kunnen er in principe nu wel en niet worden uitgevoerd door fysische systemen? Fysici hebben hier nog lang niet genoeg over nagedacht. Hoe het ook zij, hypercomputation is in ieder geval een belangwekkend terrein omdat het ons perspectief verruimt en ons verlost van het juk van de Turing-machine. De Turing-machine is een geïdealiseerd model van een fantasieloze menselijke boekhouder die braaf zijn sommetjes maakt. De huidige digitale elektronische computer is niet meer dan een andere belichaming van ditzelfde beeld. Het is niets anders dan bekrompen antropomorfisme om dit beeld zomaar op de natuur te projecteren en om er voetstoots van uit te gaan dat de natuur geen enkele boekhouder in rekenkracht overtreft. Wie weet wat zij allemaal in petto heeft. Dr Gert-Jan Lokhorst is verbonden aan het Centrum voor de Filosofie van de Informatie- en Communicatietechnologie (FICT) van de Faculteit der Wijsbegeerte van de Erasmus Universiteit te Rotterdam, waar hij zowel logica als filosofie van de informatica doceert.Turing-machine Een Turing-machine bestaat uit een controle-eenheid die in een eindig aantal toestanden kan verkeren, een lees/schrijfkop die één symbool tegelijk kan lezen of schrijven en een oneindige band die in vakjes is verdeeld en met symbolen uit een eindig alfabet is beschreven. Het gedrag van de controle-eenheid wordt bepaald door een eindig aantal rijtjes van de vorm ‘huidige toestand, gelezen symbool, volgende toestand, te schrijven symbool, actie’, waarbij ‘actie’ staat voor ‘één plaats naar links gaan’ of ‘één plaats naar rechts gaan’. De machine stopt als de controle-eenheid in een speciale stop-toestand belandt of een teken tegenkomt waar zij in haar huidige toestand niets mee kan doen. Analoge automaat Een eenvoudig analoog apparaat dat iets kan wat geen enkele Turing-machine kan. De cirkel stelt een aan de binnenkant reflecterende ronde spiegel voor met een gaatje bij A. Bij A bevindt zich tevens een detector die binnenkomend licht doorlaat en uit A komend licht registreert. Volgens de wetten van de optica kan een lichtstraal die bij A onder een hoek a binnenkomt alleen weer bij A naar buiten gaan als er een rationeel getal (breuk) q bestaat zodanig dat a=q.1800. Het apparaat bepaalt dus of a een rationeel veelvoud is van 1800. (Bij de afgebeelde lichtstraal is dit inderdaad het geval omdat a=360.) Turing-machines kunnen deze berekening niet uitvoeren omdat ze alleen maar met eindige reeksen van gehele getallen kunnen omgaan.