CWI’ers bouwen Turingmachine van Lego

Het concept van de Turingmachine dateert uit 1936 en is hét theoretische model dat ten grondslag ligt aan alle computers die vandaag de dag in gebruik zijn. Een Turingmachine bestaat uit een oneindige tape (‘geheugen’) waarop symbolen staan, een lees/schrijfkop en een controle-eenheid die het ‘programma’ bevat dat het gedrag van de machine bepaalt. Een Turingmachine - ook deze van Lego - kan in principe ieder mogelijk computerprogramma uitvoeren.

Redactie AG ConnectMeer van deze auteur

Tech & Toekomst — Shutterstock

Shutterstock

Het theoretische model van de Turingmachine heeft de essentie en vooral ook de beperkingen van het begrip ‘berekenbaarheid’ duidelijk gemaakt.

60 uur aan gewerkt

Jeroen van den Bos en Davy Landman, beiden promovendi aan de Software Analysis and Transformation groep van Paul Klint, zijn anderhalve week bezig geweest om de machine te bouwen, verspreid over twee maanden. Jeroen van den Bos: “Om uiteindelijk de Turingmachine te programmeren hebben we zelf een ontwikkelomgeving gebouwd voor de instructies, met behulp van Rascal, een metaprogrammeertaal die op het CWI is ontwikkeld specifiek om zulke omgevingen makkelijk op te kunnen zetten. Dat was dus relatief weinig werk.”

Lego Mindstorms NXT

Van den Bos en Landman begonnen met één doos Lego Mindstorms NXT. “Gaandeweg bleken we echter wat extra onderdelen nodig te hebben waardoor we nog twee dozen Lego Technic hebben aangebroken (een hoogwerker en een oplegger) plus een handvol losse onderdelen die we via internet hebben besteld. Die extra onderdelen waren vooral nodig om de tape (het geheugen van de machine) wat langer te maken dan we standaard met alleen de doos Mindstorms zouden kunnen.”

De machine gebruikt uiteindelijk alleen de elektronische componenten die in één doos Mindstorms te vinden zijn: één sensor, drie motoren en één aansturingseenheid. Dat was ook een doel: een essentiële versie van de machine te bouwen met slechts één doos Lego (Minstorms NXT).

Lego Nederland heeft de Lego beschikbaar gesteld. Het Lego-apparaat is vanaf 14 juni te zien in de tentoonstelling 'Turings Erfenis' in het CWI. De tentoonstelling wordt georganiseerd ter ere van de honderdste geboortedag van Alan Turing op 23 juni 2012, die dit jaar wereldwijd wordt gevierd. Turing is grondlegger van de kunstmatige intelligentie en informatica.

De Lego Turingmachine toont de verschillende onderdelen van het oorspronkelijke theoretische model. Een band met schakelaars is het geheugen van de computer. De computer kan door het geheugen bewegen door de band heen en weer te schuiven. De draaikop kan in het geheugen schrijven door de schakelaars om te zetten en de lichtsensor leest uit het geheugen door de stand van de schakelaar te bepalen.

Nauwkeurige klus

Een uitgangspunt bij de bouw was dat alle taken van de Turingmachine duidelijk zichtbaar zouden zijn. Om dit te bereiken wordt elke afzonderlijke taak - bewegen door het geheugen, lezen en schrijven - uitgevoerd door een bewegend onderdeel. Een uitdaging daarbij was om de verschillende onderdelen ten opzichte van elkaar goed in te stellen: de lees- en schrijfkoppen mogen elkaar niet raken en de band moet tot op de millimeter nauwkeurig bewegen.