On Computable Numbers

Pełny tytuł: On Computable Numbers, with an Application to the Entscheidungsproblem. Turing miał 23 lata, złożył tekst w maju 1936 roku, a ukazał się w Proceedings of the London Mathematical Society. Zadanie dotyczyło problemu rozstrzygalności Hilberta: czy istnieje mechaniczna procedura ustalająca, czy dowolne twierdzenie matematyczne wynika z aksjomatów? Odpowiedź wymagała najpierw zdefiniowania, czym w ogóle jest „procedura mechaniczna” — Turing zrobił to, opisując wyimaginowaną maszynę z nieskończoną taśmą, głowicą odczytu i tablicą stanów.

Wszystko inne wynika z tej definicji: maszyna uniwersalna, która symuluje dowolną inną maszynę na podstawie jej opisu zapisanego na taśmie; dowód, że żadna maszyna nie rozstrzygnie, czy dowolna maszyna kiedykolwiek się zatrzyma; a więc „nie” dla Hilberta. Alonzo Church doszedł do tego samego wniosku kilka miesięcy wcześniej przez rachunek lambda, co omal nie zablokowało publikacji — Turing musiał dodać dodatek wykazujący równoważność obu ujęć. Prawdziwym dziedzictwem artykułu nie jest dowód, lecz uwaga na marginesie o maszynie uniwersalnej: maszynie, której program jest danymi.