Computerpioniers: Alan Turing

Alan Turing en het beslissingsprobleem
Alan Mathison Turing werd in Londen op 23 juni 1912 geboren. Alan Turing bezocht de Universiteit van Cambridge (Verenigd Koninkrijk) waar hij kwantummechanica ging studeren. Tijdens, maar ook ná de studie hield Turing zich met allerlei wiskundige problemen bezig. Bijvoorbeeld met logische vraagstukken. Hij maakte kennis met het Entscheidungsproblem (Duits: beslissingsprobleem). Na bestudering hiervan publiceerde Turing zijn beroemde artikel On Computable Numbers, with an Application to the Entscheidungsproblem. Het beslissingsprobleem draait in essentie om de vraag of er een algoritme (hier: reeks instructies) is om te beslissen of een wiskundige formule een bewijs heeft of niet.Turing Machine
Dit artikel zou de basis zijn van de beroemde Turingmachine, feitelijk als een soort gedachte-experiment onder de naam Logical Computing Machine geïntroduceerd. De Turingmachine is geen echte machine, het is een model van berekening en berekenbaarheid. In de basis is een Turingmachine een erg eenvoudig mechanisme waarmee in kleine stapjes symbolen gemanipuleerd worden. De Turingmachine kan in één stap twee verschillende waarden aanpassen. Niet meer. Met dit mechanisme kun je alle mogelijke berekeningen uitvoeren, hoewel je misschien wel héél veel kleine stapjes moet zetten. De hoeveelheid kleine stapjes is dus niet belangrijk. Wat de Turingmachine aantoont is dat iets kán of juist niet. Als je het goed bekijkt, leverde Turing met zijn werk een op dat moment nog onbekende blauwdruk van de moderne computer.Princeton
Na zijn periode in Cambridge vertrok Alan Turing naar de Verenigde Staten, waar hij ging werken aan de universiteit van Princeton. Hier maakt hij kennis met John von Neumann, die de grondlegger was van de 'von Neumann-architectuur'. Von Neumann had deze ontworpen voor elektronische rekenmachines, maar deze architectuur bleek later ook uitstekend toepasbaar op computers. De Von Neumann-architectuur voorziet erin dat je in computers verschillende onderdelen aantreft: een processor, een controle-eenheid, een geheugen, een input- en outputeenheid. Alles wordt hierin binair opgeslagen.Met de kennis die het werk van Von Neumann leverde kon Turing zijn Turing Machine vervolmaken.
Turing-compleet

Alle moderne computers zijn dat wél.