Direkt zum Inhalt

Lexikon der Mathematik: Churchsche These

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).

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos