QED

Terwijl ik in mijn recentste artikel in PC-Active nog uitgebreid de strategieën besprak om de Wolfram 2,3 Turing Machine Research Prize ter waarde van 25 000 $ te winnen, schrijft Stephen Wolfram vandaag in zijn blog dat de prijs is gewonnen: zijn Turingmachine is universeel.

Vijf jaar geleden schreef hij op p. 709 van A New Kind of Science:

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.

Op 14 mei van dit jaar kondigde Wolfram de prijs aan en hij 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 20 jaar oude student Electronic, Electrical and Computer Engineering aan de universiteit van Birmingham, heeft een bewijs van 40 pagina’s dat de Turingmachine van Wolfram universeel is. Op 30 juni al stuurde hij een bewijs op, dat hij na opmerkingen van de prijscommissie herwerkte.

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 wel het punt dat de 2,3 Turingmachine universeel is, waardoor we nu weten dat dit de kleinste universele Turingmachine is.

Waarschijnlijk zullen er de komende jaren dus 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.” 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.

Update: Kathryn Cramer, consultant voor Wolfram Research, e-mailt mij zonet dat er meer informatie over het bewijs van Smith is gepubliceerd op de website van de prijs. Je vindt er zijn bewijs, dat zal gepubliceerd worden in Complex Systems, en een technische uitleg over de algemene strategie van het bewijs. Cramer wijst ook op artikelen met meer achtergrond over Smith in New Scientist en Nature.
Update 26 oktober: Kijk ook op Kennislink voor een uitgebreider artikel op basis van mijn blogposts over Wolframs universele Turingmachine.