Ondanks de benaming is een Turing-machine eigenlijk geen fysiek apparaat maar een theoretisch model, dat in 1936 door de wiskundige Alan Turing (1912-1954) werd beschreven. Hij gaf het de naam “a(utomatic)-machine”. Bedoeling van het model was om de limieten te onderzoeken van wat berekend kan worden. De Turing-machine vormt de basis voor de computerwetenschap. In een latere publicatie noemde Turing het trouwens een “Logical Computing Machine”.
Lego Turing-machine (© ; licentie: )
Een Turing-machine kun je voorstellen als een oneindige tape onderverdeeld in cellen, die horizontaal van links naar rechts loopt. Elke cel kan een symbool bevatten: ofwel “0”’of “1”. Daarnaast heeft de machine een lees-schrijfkop. Die scant een cel en kan erin schrijven. Op die manier kan men een taak ‘programmeren’.
Jeroen van den Bos en Davy Landman, twee wetenschappers verbonden aan het Centrum Wiskunde & Informatica in Amsterdam, bouwden met Lego een werkend model van een Turing-machine. Ze begonnen met één doos Lego Mindstorms NXT, maar gebruikten ook nog onderdelen van Lego Technic.
De Lego Turing-machine is te bekijken in de tentoonstelling ‘Turings Erfenis‘ die het CWI organiseert ter gelegenheid van de honderdste geboortedag van Alan Turing. Er is trouwens ook een originele Enigma codeermachine uit de Tweede Wereldoorlog te bekijken, waarvan Alan Turing samen met andere codebrekers in Bletchley Park de code wist te breken.
