Student wint prijs met bewijs

Het was een probleem voor de fijnproevers onder de informatici: wat is de kleinste universele Turing-machine? Een student gaf antwoord, in 44 pagina’s.

Alex Smith, een twintigjarige student informatica en elektronica uit Birmingham, heeft een openstaand probleem uit de informatica opgelost. Hij won daarmee vorige week 25.000 dollar. Smith bewees dat een zeer eenvoudige machine elke mogelijke berekening kan uitvoeren.

De prijs werd in mei dit jaar uitgeloofd door Stephen Wolfram, een vooraanstaande Amerikaanse wiskundige. Hij loofde het geldbedrag uit aan degene die een vermoeden kon bewijzen dat hij in 2002 onder woorden bracht in zijn lijvige boek A new kind of science.

Wolframs vermoeden betrof Turing-machines. Deze denkbeeldige machines werden in 1936 bedacht door Alan Turing als model voor computers. Ze bestaan uit een kop die kan lezen of schrijven en een onbegrensd lange strook papier. De machine kan verschillende tekens op het papier schrijven en kan daarnaast in een beperkt aantal mogelijke toestanden verkeren: hoog of laag bijvoorbeeld. Deze toestanden zijn te vergelijken met gemoedstoestanden, ze bepalen samen met de symbolen op de strook de stappen die de machine maakt.

Een Turing-machine wordt universeel genoemd als hij net zo krachtig is als elke andere mogelijke Turing-machine. Anders gezegd als hij elk algoritme – een berekening die op een gegeven moment weer stopt – kan uitvoeren.

Het vermoeden van Wolfram betrof een zogeheten 2,3 Turing machine: een apparaat met twee verschillende toestanden en drie tekens.

Zo’n machine, schreef Wolfram in 2002, zou de kleinst mogelijk universele Turing-machine zijn. En in een ruim veertig pagina’s tellend bewijs toont student Smith nu, tot zijn eigen verrassing, aan dat die bewering inderdaad juist is. In eerste instantie geloofde Smith juist dat hij kon bewijzen dat de machine niet universeel is, zo zei hij in een telefoongesprek met Wolfram.

Aan de informaticapraktijk verandert dit bewijs niet zoveel, denkt Peter van Emde Boas, lector in de mathematische informatica aan het Institute for Logic, Language en Computation van de Universiteit van Amsterdam. „Mooi dat die jongen dit probleem heeft opgelost, maar het zal niet bijdragen tot de ontwikkeling van betrouwbaarder computerprogramma’s.”

Maar aan de andere kant: „Als Wolfram het geld ervoor over had: waarom niet? Het is een serieus en lastig probleem.”

Met het nieuwe bewijs komt er nu wél een einde aan de jarenlange jacht naar steeds kleinere universele Turing-machines, want een machine met twee toestanden en twee tekens kan niet universeel zijn. In 1962 bewees Marvin Minsky dat een machine met zeven toestanden en vier symbolen universeel is. Dat record bleef lang ongebroken, de afgelopen tien jaar volgden verbeteringen met universele 4,6 en 2,5 machines. En nu is dus met een 2,3 Turing-machine de grens bereikt.