Maszyna Turinga
Matematyczna zabawka z nieskończoną papierową taśmą i głowicą odczytu, wymyślona w 1936 roku, by udowodnić, czego komputery nie potrafią.
Model ma cztery części: taśmę podzieloną na komórki, głowicę, która odczytuje i zapisuje jeden symbol naraz, skończony zbiór stanów oraz tablicę mówiącą, co robić przy danym stanie i symbolu pod głowicą. To cały aparat. Żadnej arytmetyki, rejestrów ani adresowania — a mimo to oblicza wszystko, co potrafi jakikolwiek inny model obliczeń.
Zbudowanie takiej maszyny nigdy nie było celem. Alan Turing potrzebował definicji „procedury mechanicznej" na tyle ubogiej, by dało się rozumować o tym, czego żadna procedura nie osiągnie, a odpowiedź na Entscheidungsproblem Hilberta wyszła negatywna: istnieją pytania, których żaden algorytm nie rozstrzyga, m.in. czy dowolny program się zatrzyma. Alonzo Church doszedł do tego samego wniosku w tym samym roku za pomocą rachunku lambda, a równoważność obu modeli to treść tezy Churcha–Turinga.
Uniwersalna maszyna Turinga bierze opis innej maszyny na swoją taśmę i ją naśladuje. To idea programu przechowywanego w pamięci, sformułowana dekadę przed tym, zanim ktokolwiek zbudował sprzęt zdolny ją zrealizować. Nazwanie języka kompletnym w sensie Turinga oznacza, że potrafi taką maszynę symulować — do tego klubu należy CSS z kilkoma rozszerzeniami i prawdopodobnie coś, czego wcale nie planowałeś.