Je leest:

Student vindt eenvoudigste universele Turingmachine

Student vindt eenvoudigste universele Turingmachine

Auteur: | 26 oktober 2007

Een prijsvraag die in mei van dit jaar werd uitgeschreven is gewonnen door de twintigjarige student Alex Smith. Hij bewees dat de zogeheten ‘2,3-Turingmachine’ universeel is.

Vijf jaar geleden verscheen het boek A New Kind of Science van Stephen Wolfram. Aan dit 1200 pagina’s tellende boek had hij twee decennia gewerkt. Hij beschrijft hierin de relatie tussen computers, wiskunde en het universum. Het staat vol met alle mogelijke formele systemen met interessante eigenschappen, zoals recursieve functies, registermachines, substitutiesystemen en Diophantische vergelijkingen. Vergelijkingen zoals 2x3 + 3y2 = 17, waarbij de oplossingen alleen gehele getallen mogen zijn, heten Diophantische vergelijkingen, naar de Griekse geleerde Diophantus (ca. 250 na Chr.) die ze systematisch bestudeerde. Ook de beroemde Laatste Stelling van Fermat gaat over zulke vergelijkingen.

Over zijn Turingmachine, de ‘Wolfram 2,3 Turingmachine’ genaamd, schrijft hij op pagina 709: “And although it will no doubt be very difficult to prove, it seems likely that this Turing machine will in the end turn out to be universal.” (En hoewel het ongetwijfeld zeer moeilijk te bewijzen zal zijn, is het waarschijnlijk dat deze Turing machine universeel zal blijken te zijn.)

Universele Turingmachines

Een Turingmachine, in 1936 door Alan Turing voorgesteld, is een abstract model van wat een computer (én een mens) kan berekenen. Turings bevindingen waren extreem belangrijk voor de theoretische informatica, de logica en de taalkunde, en vormden in feite een Big Bang in de ontwikkeling van computertechnologie. Meestal wordt een Turingmachine voorgesteld als een oneindig lange band papier en een lees/schrijfkop die over de band beweegt. De papierband is onderverdeeld in cellen, waarop symbolen (kleuren) staan die door de kop gelezen en beschreven kunnen worden. In een tabel staat wat de Turingmachine moet doen bij het lezen van een bepaald symbool. Zo kan de kop bij een bepaalde invoer een symbool op de band schrijven, naar links of rechts bewegen en naar een andere toestand gaan.

De grootste openbaring van Turing was wat de universele Turingmachine wordt genoemd. In deze theorie blikte de wiskundige vooruit naar een denkende machine die in principe bij alle denkbare logische processen kon worden ingezet – een apparaat dat kon schaken, cryptografische coderingen kraken en algebrasommen maken.

In de loop der jaren begonnen onderzoekers zo klein mogelijke universele Turingmachines te ontwikkelen. ‘Zo klein mogelijk’ betekent met zo weinig mogelijk toestanden en zo weinig mogelijk verschillende symbolen in het alfabet. Marvin Minksy vond in 1962 een universele Turingmachine met 7 toestanden en 4 kleuren. Stephen Wolfram ontdekte in de jaren 1990 een Turingmachine met 2 toestanden en 5 kleuren waarvan hij vermoedde dat ze universeel is, en Matthew Cook bewees dit bij het voorbereiden van Wolframs boek A New Kind of Science. Tot voor kort was dit de kleinst bekende universele Turingmachine. Alex Smith heeft nu bewezen dat een Turingmachine met 2 toestanden en 3 kleuren universeel is. Dit is niet alleen de kleinst bekende universele Turingmachine, het is ook de kleinst mogelijke universele Turingmachine: al langer was bekend dat een Turingmachine met 2 toestanden en 2 kleuren niet universeel kan zijn.

Prijsvraag

Naar aanleiding van de vijfde verjaardag van zijn boek schreef Wolfram in mei van dit jaar de Wolfram 2,3 Turing Machine Research Prize uit. Hij vermoedde dat een bepaalde Turingmachine met 2 toestanden en 3 kleuren universeel is, maar kon het niet bewijzen. Wie hier wel in zou slagen, kan prijzengeld van 25000 dollar tegemoet zien. Als de machine universeel is, zou het de kleinst mogelijke universele Turingmachine zijn. Het is namelijk bewezen dat een Turingmachine met 2 toestanden en 2 kleuren niet universeel kan zijn.

Wolfram wist niet hoe lang het zou duren voor iemand de prijs zou winnen: dat kon na een maand al zijn, maar ook na een eeuw. Misschien was de vraag of deze Turingmachine universeel is zelfs formeel onbeslisbaar. Vijf maanden na de aankondiging hebben we echter al resultaat: Alex Smith, een twintig jaar oude student Electronic, Electrical and Computer Engineering aan de universiteit van Birmingham, heeft een bewijs dat de Turingmachine van Wolfram universeel is. Op 30 juni stuurde hij al een bewijs op, dat hij na enkele opmerkingen van de prijscommissie bewerkte. De uiteindelijke versie telt veertig pagina’s en is hieronder te downloaden.

In zijn bewijs construeerde Smith een ‘compiler’ die elke mogelijke code uit een bepaalde klasse van universele machines kan compileren. Dit is dus een manier om de Turingmachine te programmeren om elke mogelijke berekening uit te voeren. Zijn compiler is niet heel efficiënt, want ze genereert enorm grote code. Maar ze bewijst wél dat de 2,3 Turingmachine universeel is, en daar ging het om. We weten nu dat dit de kleinste universele Turingmachine is die bestaat.

Een Turingmachine met 2 toestanden en 3 kleuren geeft 2 × 3 = 6 regels. Deze Turingmachine is hier gevisualiseerd.

Waarschijnlijk zullen er de komende jaren wel bewijzen opduiken die de constructie van Smith aanpassen om een efficiëntere compiler te construeren. Zoals Erdös zei: “Nobody gets blamed if his first proof is messy.” (Niemand wordt beschuldigd als zijn eerste bewijs slordig is.) Wolfram droomt al van praktische toepassingen hiervan: “And that’ll be interesting. Perhaps one day there’ll even be practical molecular computers built from this very 2,3 Turing machine. With tapes a bit like RNA strands, and heads moving up and down like ribosomes.”

Wolfram telefoneerde met Smith en vroeg hem waarom hij aan het probleem gewerkt had. De student antwoordde dat hij het eerst een leuke puzzel vond en dat hij er zeker van was dat de Turingmachine te eenvoudig was voor universeel gedrag. Toen hij er echter dieper indook, ontdekte hij echter gedrag dat ingewikkelder was, en toen begon hij aan zijn bewijs van universaliteit. Binnen enkele weken komt er een officiële prijsceremonie in Bletchley Park, waar Alan Turing tijdens de oorlog werkte.

Alex Smith werd geboren op 15 april 1987 in Birmingham. Op de middelbare school deed hij twee keer mee aan de Internationale Wiskunde Olympiade. Nu studeert hij Electronic, Electrical and Computer Engineering aan de universiteit van Birmingham.

In Bletchley Park, zie de foto onder, zal hij binnenkort zijn prijs van 25000 dollar in ontvangst nemen.

Bronnen en verder lezen:

Dit artikel is een publicatie van NEMO Kennislink.
© NEMO Kennislink, sommige rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 26 oktober 2007

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

NEMO Kennislink nieuwsbrief
Ontvang elke week onze nieuwsbrief met het laatste nieuws uit de wetenschap.