Church-Turing-These, von Church 1936 aufgestellte These, die besagt, daß der intuitive Berechenbarkeitsbegriff adäquat durch den Begriff der Turing-Berechenbarkeit (Turing- Maschine, berechenbare Funktion) erfaßt wird.

Wenn eine Funktion also nachweislich nicht mittels einer Turing-Maschine berechenbar ist, dann ist sie aufgrund der Churchschen These überhaupt nicht berechenbar, egal mit welchem ausgeklügelten Berechnungsformalismus.

Die (nicht im strengen Sinne beweisbare) Churchsche These wird deshalb allgemein akzeptiert, da sich bis heute jeder Formalisierungsvorschlag für den Begriff „berechenbar“ zu dem Begriff der Turing-Berechenbarkeit als äquivalent herausgestellt hat, z. B. die allgemein-rekursiven Funktionen, die μ-rekursiven Funktionen, die λ-definierbaren Funktionen (λ-Kalkül), die durch WHILE- oder GOTO-Programme, Markow-Algorithmen oder Registermaschinen berechenbaren Funktionen (Berechnungstheorie).