Die Church-Turing-These

Die Church-Turing-These besagt, dass jede Funktion, die durch ein effektives Verfahren berechenbar ist, auch von einer Turingmaschine berechenbar ist, wodurch die informelle Vorstellung eines Algorithmus mit einem präzisen mathematischen Modell gleichgesetzt wird.

Definition

Die Church-Turing-These ist die Behauptung, dass die intuitiv berechenbaren Funktionen genau die Funktionen sind, die von einer Turingmaschine, äquivalent vom Lambda-Kalkül oder den allgemeinen rekursiven Funktionen, berechenbar sind; es handelt sich um eine These und nicht um einen Satz, da der intuitive Begriff nicht formal definiert ist.

Scope

Dieses Thema behandelt die Aussage der These, die konvergierenden Beweise aus unabhängig voneinander vorgeschlagenen Modellen, die Unterscheidung zwischen der ursprünglichen These über die effektive Berechenbarkeit und stärkeren physikalischen oder komplexitätstheoretischen Varianten sowie die Rolle der These als Brücke zwischen Intuition und formalem Beweis in der Berechenbarkeitstheorie.

Core questions

• Was bedeutet es, den informellen Algorithmusbegriff mit einem formalen Modell gleichzusetzen?
• Warum wird die Konvergenz unabhängiger Modelle als starker Beweis für die These angesehen?
• Ist die These ein mathematischer Satz, eine Definition oder eine empirische Behauptung?
• Wie gehen physikalische und komplexitätstheoretische Versionen über die ursprüngliche Aussage hinaus?

Key theories

Konvergenz von Berechnungsmodellen

Turingmaschinen, Churchs Lambda-Kalkül und Gödels und Herbrands rekursive Funktionen definieren nachweislich genau dieselbe Klasse von Funktionen, und diese unabhängige Übereinstimmung ist der Hauptbeweis, der für die These angeführt wird.

Status als These, nicht als Satz

Da der intuitive Begriff eines effektiven Verfahrens nicht formalisiert ist, kann die Behauptung nicht bewiesen werden; sie wird als grundlegende Identifikation akzeptiert, die informelle algorithmische Argumente anstelle formaler Turingmaschinen-Konstruktionen zulässt.

Clinical relevance

Die These legitimiert die alltägliche Praxis, Algorithmen in hochrangigem Pseudocode statt als Turingmaschinen zu beschreiben, da jede vernünftige Vorstellung eines effektiven Verfahrens als Turing-äquivalent angenommen wird; sie rahmt auch Debatten darüber ein, ob physikalische oder Quantengeräte jemals über das Turing-Berechenbare hinaus berechnen könnten.

History

1936 schlug Church vor, die effektive Berechenbarkeit mit der Lambda-Definierbarkeit gleichzusetzen, und Turing argumentierte unabhängig für sein Maschinenmodell, woraufhin Turing, Kleene und andere bewiesen, dass diese und die rekursiven Funktionen äquivalent sind. Gödel, der zunächst skeptisch war, betrachtete Turings Analyse als schlüssig, und die kombinierte Behauptung wurde als Church-Turing-These bekannt.

Debates

Kann physikalische Berechnung die Turing-Grenze überschreiten?

Die ursprüngliche These betrifft effektive Verfahren, aber stärkere physikalische Versionen behaupten, dass kein physikalisch realisierbares Gerät nicht-Turing-berechenbare Funktionen berechnen kann. Vorschläge zur Hyperberechnung und die Implikationen der Quantenmechanik halten diese erweiterte Behauptung umstritten, auch wenn die klassische These im Wesentlichen unangefochten bleibt.

Key figures

• Alonzo Church
• Alan Turing
• Kurt Gödel
• Stephen Kleene

Seminal works

• church1936
• turing1937

Frequently asked questions

Warum wird sie als These und nicht als Satz bezeichnet?

Sie verbindet ein formales Modell mit der informellen Vorstellung eines effektiven Verfahrens, und diese informelle Vorstellung hat keine mathematische Definition, über die man Dinge beweisen könnte. Der starke Beweis ist, dass jeder unabhängige Versuch, die Berechnung zu formalisieren, dieselbe Klasse von Funktionen hervorgebracht hat, aber diese Unterstützung ist eher konzeptionell als ein Beweis.

Widerlegen Quantencomputer die Church-Turing-These?

Nein. Quantencomputer können einige Probleme schneller lösen, aber sie berechnen genau dieselbe Klasse von Funktionen wie Turingmaschinen, sodass die ursprüngliche These darüber, was berechenbar ist, Bestand hat. Sie beziehen sich stattdessen auf die stärkere komplexitätstheoretische Version, die sich eher mit Effizienz als mit Berechenbarkeit befasst.