## [Church-Turing-These](/de/node/58845) Definition Eine informelle grundlegende Behauptung, dass jede Funktion, die durch ein endliches mechanisches Verfahren (einen effektiven Algorithmus) berechnet werden kann, von einer Turing-Maschine berechnet werden kann; sie identifiziert Turing-Berechenbarkeit mit der intuitiven Vorstellung algorithmischer Berechenbarkeit. ## Prinzip Prinzip Dass ein einzelnes formales Modell (Turing-Maschinen, äquivalent Lambda-Kalkül, rekursive Funktionen usw.) das informelle Konzept effektiven Rechnens erfasst. ## Demonstration Demonstration Konkretes Beispiel: Jeder Algorithmus in einer modernen Programmiersprache lässt sich in eine äquivalente Turing-Maschinen-Prozedur übersetzen, die für eine Kodierung der Eingaben das gleiche Ausgabe-Verhalten reproduziert; die Äquivalenz wird durch Konstruktion eines Simulators für die Sprachsemantik auf einer universellen Turing-Maschine gezeigt. ## Fehlanwendung Fehlanwendung Die Behauptung, die Church-Turing-These sei ein mathematischer Satz über alle physikalischen Prozesse, oder ihre Verwendung zur Festlegung von Laufzeit- oder Platzgrenzen (Komplexität) statt von Berechenbarkeit; oder die vorschnelle Ablehnung möglicher Formen von Hyperberechnung ohne empirische Grundlage. ## Konsequenz Konsequenz Bietet eine als gültig angenommene Grundlage für die Berechenbarkeitstheorie und für die Klassifikation von Problemen als entscheidbar oder unentscheidbar; rechtfertigt die Verwendung von Turing-Maschinen (oder äquivalenten Modellen) als kanonisch für Diskussionen darüber, was prinzipiell berechenbar ist. ## Umkehrung Umkehrung Die Umkehrung würde die Existenz eines intuitiv beschreibbaren effektiven Verfahrens behaupten, das keine Turing-Maschine implementieren kann — also einen praktikablen Algorithmus außerhalb der Turing-Berechenbarkeit. ## Abgrenzung Abgrenzung Eine These, kein formaler Beweis: Sie betrifft, was als effektiver Algorithmus zählt, und behandelt nicht Ressourcenbegrenzungen (Zeit/Platz), probabilistisches oder approximatives Rechnen oder physikalische Realisierbarkeit; physikalische Varianten der These sind gesondert und empirisch zu prüfen. ## Semantische Spannung Semantische Spannung Spannung zwischen ‚prinzipiell berechenbar‘ (theoretische Äquivalenz zu Turing-Maschinen) und ‚praktisch berechenbar‘ (ressourcenbeschränktes, physikalisches oder approximatives Rechnen) sowie zwischen beschreibender These und empirisch/normativer Behauptung über physikalische Systeme. ## Synthese Synthese Die Church-Turing-These besagt, dass das informelle Konzept eines effektiven Algorithmus durch Turing-Berechenbarkeit erfasst wird: sie ordnet die Berechenbarkeitstheorie, indem sie intuitive algorithmische Verfahren dem formalen Modell der Turing-Maschine gleichsetzt, während Fragen zu Ressourcen und physikalischer Realisierung offenbleiben.