Die Turingmaschine (1936)
Der 24-jährige britische Mathematiker Alan Turing veröffentlicht eine grundlegende Arbeit, in der er ein abstraktes Berechnungsmodell definiert: ein unendliches Band, einen Lese-/Schreibkopf und eine endliche Menge von Zuständen. Eine solche Maschine kann jeden Algorithmus simulieren.
Das Entscheidungsproblem
Turing beantwortet Hilberts Entscheidungsproblem negativ: Es gibt mathematische Funktionen beziehungsweise Probleme, die kein mechanisches Verfahren allgemein lösen kann, darunter das Halteproblem. Alonzo Church gelangt unabhängig zu einem äquivalenten Ergebnis.
Bedeutung
Die Church-Turing-These besagt, dass jede effektiv berechenbare Funktion von einer Turingmaschine berechnet werden kann. Dieses Modell bildet die theoretische Grundlage von Compilern, Komplexitätstheorie und künstlicher Intelligenz.