Alan Turing je zakladatelem informatiky a jedním z nejvýznamnějších matematiků všech dob. Je známý díky tomu, že se za 2. světové války podílel na prolomení německého šifrovacího systému Enigma. Do vědecké historie se ale zapsal už dřív. Ve 30. letech navrhl Turingův stroj (Turing mashine), který se používá dodnes.
Pokud si Turingův stroj představujete jako nějaké zařízení ve stylu parního nebo jiného stroje, bohužel vás zklamu. Jedná se pouze o teoretický model, který ale má stejnou výpočetní sílu jako moderní počítače.
Skládá se z jednostranně nekonečné pásky, jež tvoří paměť stroje. Páska je rozdělena na pole, v každém z nich je vždy zapsán jeden symbol. Dále je součástí stroje čtecí hlava, která se pohybuje po pásce. Hlava vždy čte některé z polí pásky, a navíc má ještě svůj vlastní vnitřní stav.
Na začátku výpočtu je na prvním poli symbol začátku pásky a za ním je několik dalších polí popsáno dalšími symboly, které představují vstup výpočtu. Zbytek pásky je prázdný (respektive obsahuje symbol, který říká, že dané pole je prázdné). Čtecí hlava začíná na prvním poli a je v tzv. počátečním vnitřním stavu.
Výpočet provádí čtecí hlava. V jednom kroku se na základě přečteného symbolu z pásky a svého stavu rozhodne, co udělá. Nejprve může přepsat symbol na pásce jiným symbolem, poté může změnit svůj vnitřní stav a nakonec se pohne o jedno pole dopředu, nebo dozadu. Na začátku se musí pohnout dopředu, protože je na prvním poli.
Výpočet skončí, když se hlava dostane do jednoho ze dvou speciálních stavů, jimž se říká akceptující a zamítající stav. Tím nám stroj „odpoví“ na otázku, kterou jsme mu položili.
Tento model se vám může zdát v některých záležitostech zbytečně limitující. Proč se například může hlava pohnout vždy jen o jedno pole? Ve skutečnosti platí, že pokud bychom umožnili, aby se hlava posouvala o libovolné množství polí, stroj by měl stále stejnou výpočetní sílu! Totéž platí i o dalších rozšířeních nebo omezeních, které si můžeme vymyslet. I kdyby měl stroj 5000 pásek s 5000 hlavami, stále by byl stejně silný! Právě proto se používá jako model počítače. Mimozemšťané mohou používat počítače na zcela odlišném fyzikálním principu než my, ale pokud jejich stroj zvládne spočítat totéž, co Turingův stroj, můžeme jej s klidným svědomím nazývat počítačem.