Alan Turing beschrijft een machine die elke berekening kan uitvoeren

LONDEN, NOVEMBER 1936 - Bij de London Mathematical Society is op 12 november een opvallend artikel behandeld van de 24-jarige wiskundige Alan Turing uit Cambridge. De titel, On Computable Numbers, klinkt droog, maar de inhoud is dat niet. Turing wil weten wat rekenen eigenlijk is, en bedenkt daarvoor een machine die niet bestaat.

De rekenaar aan zijn bureau

Wie aan een rekenaar denkt, denkt aan een mens. Sterrenwachten, verzekeraars en ministeries hebben hele kamers vol mensen die de hele dag tabellen uitrekenen, vaak zonder de wiskunde erachter te kennen. Ze krijgen een werkvoorschrift en volgen dat stap voor stap.

Dat brengt Turing op zijn vraag. Als iemand zonder enig inzicht een voorschrift kan volgen, wat doet die persoon dan eigenlijk? Hij kijkt naar wat er op het papier staat, houdt in zijn hoofd bij waar hij is in het voorschrift, schrijft iets op en kijkt naar het volgende stukje. Meer niet.

Een strook papier en een paar regels

Turing brengt dat terug tot het allereenvoudigste. Zijn machine heeft een strook papier verdeeld in vakjes. Ze ziet steeds één vakje. Ze kan er een teken in schrijven of uitvegen, en de strook een vakje opschuiven. Ook heeft ze een klein aantal standen, zoals de rekenaar onthoudt waar hij is. Een tabel zegt voor elke stand en elk teken wat de machine moet doen.

Een voorbeeld: stand 1 en het teken 0 betekent "schrijf een 1, schuif naar rechts en ga naar stand 2". Het lijkt speelgoed. Toch is Turing ervan overtuigd dat zo'n machine elke berekening kan uitvoeren die een mens met potlood en papier volgens vaste regels kan doen.

Eén machine voor alles

Dan volgt zijn belangrijkste stap. Voor elke rekenklus is er een andere tabel, en dus lijkt er een andere machine nodig. Maar de tabel van een machine is ook gewoon een rijtje tekens, en dat kun je op de strook schrijven. Turing beschrijft een machine die zo'n tabel leest en daarna precies doet wat de beschreven machine zou doen. Eén enkele machine kan dus het werk van alle andere overnemen. Hij noemt dat de universele machine.

Wat niet kan

Turing gebruikt zijn idee om een beroemde vraag van de Duitse wiskundige David Hilbert te beantwoorden: bestaat er een vaste methode om van elke wiskundige bewering te bepalen of ze te bewijzen is? Hij laat zien dat er getallen en vragen zijn die geen enkele machine kan afhandelen, dus het antwoord is nee. De Amerikaan Alonzo Church kwam dit jaar langs een andere weg tot dezelfde uitkomst.

Teruggeblikt vanuit 2026

Turings universele machine is het idee achter elke computer: één apparaat dat alles kan, zolang je het de juiste regels geeft. Die regels noemen we nu software, en het woord computer ging over van de mens aan het bureau op de machine. Veertien jaar later stelde Turing de volgende vraag: kunnen machines denken?

Alles wat vandaag op een chip draait, ook een groot taalmodel, is in principe uit te voeren door Turings strook papier. Het zou alleen onvoorstelbaar lang duren.