Alan Turing: nadenken over wat computers kunnen
Alan Turing (1912–1954) was een wiskundige wiens werk de informatica mede vormgaf. In 1936 ontwikkelde hij een wiskundige beschrijving van berekeningen. Tijdens de Tweede Wereldoorlog werkte hij met het team van codebrekers in Bletchley Park; daarna werkte hij aan computers bij het National Physical Laboratory en in Manchester. Hij onderzocht ook patronen in levende wezens. Lees de biografie van King’s College (Engels).
Een computer op papier
Een turingmachine is een wiskundig model met een band van vakjes, een lees- en schrijfkop en een eindige verzameling regels. Een regel gebruikt de huidige toestand en het gelezen teken om te bepalen wat er wordt geschreven, waarheen de kop beweegt en welke toestand volgt. De band heeft geen vaste opslaggrens. Turing beschreef ook een universele machine die andere zulke machines kan nabootsen aan de hand van hun gecodeerde beschrijving. Zie Turings oorspronkelijke artikel, paragrafen 1 en 6 (Engels).
Speel zelf de machine
Teken een rij vakjes met 1 1 1 _. Het teken _ betekent een leeg vakje. Leg een potlood onder het eerste vakje: dat is de kop.
Gebruik deze kleine regeltabel. De begintoestand is zoeken.
| Toestand | Lees | Schrijf | Beweeg | Volgende toestand |
|---|---|---|---|---|
| zoeken | 1 | 1 | Rechts | zoeken |
| zoeken | Leeg | 1 | Blijf staan | stop |
Voer steeds één regel uit. Je eindigt met vier enen. Als de enen een aantal voorstellen, heeft je machine er één bij opgeteld.
Probeer het opnieuw met vijf enen en een leeg vakje. Zijn er andere regels nodig? Wat gebeurt er als het potlood op het lege vakje begint?
Dit is één kleine machine met één taak. Het is zelf geen universele machine.
Het verband met Pliro
Als je een Pliro-programma stap voor stap volgt, voer je ook opdrachten uit en houd je veranderende waarden bij. Met een turingmachine kun je zulke stappen in een heel eenvoudige vorm onderzoeken. Je hoeft er geen te bouwen voordat je een spel schrijft.
Het volgende artikel legt turingvolledigheid uit: wat het betekent dat een taal of model algemene berekeningen kan uitdrukken.
En de turingtest?
De turingtest gaat over de vraag of een machine een menselijk gesprek kan nabootsen. De test komt voort uit Turings bespreking van een imitatiespel in 1950. Dat is een andere vraag dan welke berekeningen een taal kan beschrijven. Zie Computing Machinery and Intelligence (Engels).