„Church-Turing-These“ – Versionsunterschied

Versionsgeschichte interaktiv durchsuchen

[ungesichtete Version]

[gesichtete Version]

Inhalt gelöscht Inhalt hinzugefügt

Inline

Aktuelle Version vom 1. Dezember 2025, 17:07 Uhr

Die Church-Turing-These (benannt nach Alonzo Church und Alan Turing, auch Churchsche These genannt) trifft Aussagen über die Fähigkeiten einer Rechenmaschine. Sie lautet:

„Die Klasse der Turing-berechenbaren Funktionen stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein.“^[1]

Diese These ist nicht beweisbar, da der Begriff „intuitiv berechenbare Funktion“ nicht exakt formalisiert werden kann. Man versteht darunter alle Funktionen, die prinzipiell auf irgendeine Weise berechnet werden könnten. Damit setzt man insbesondere keine Vorstellung voraus, welche Funktionen auf den natürlichen Zahlen berechenbar sind. Es wird in der Informatik üblicherweise angenommen, dass die These stimmt. Dadurch wird es möglich, für eine Funktion nachzuweisen, dass sie nicht berechenbar ist.

Entstehung

Turing empfand die Gedankenprozesse eines Menschen beim Zahlenrechnen durch die von ihm entwickelte Turingmaschine nach (in der Funktionsweise ähnlich den heutigen Computern) und analysierte deren Fähigkeiten. Er stellte fest, dass viele Funktionen, die von einem Menschen ausgedacht werden können, erst gar nicht durch die Turingmaschine berechenbar sind, wie z. B. die Funktion des Halteproblems.

Zum anderen zeigte sich, dass auch andere Herangehensweisen, die menschliche Denkweise beim Rechnen zu formalisieren, nicht erfolgreicher waren: So wurde von Turing historisch zuerst die Äquivalenz von Churchs Lambda-Kalkül zur Turingmaschine bewiesen. Es folgten darauf viele weitere vorgeschlagene Algorithmenbegriffe (Rechenmodelle), die alle in ihrer Berechnungsfähigkeit nicht mehr leisteten als die Turingmaschine. Man bezeichnet diese Algorithmenbegriffe demzufolge als Turing-vollständig.

Dies ließ vermuten, dass es keinen mächtigeren Formalismus als den der Turingmaschine hinsichtlich der Berechenbarkeit gäbe und der Mensch – ebenfalls algorithmisch arbeitend – auch nicht mehr Funktionen ausrechnen könne. Damit entstand die Church-Turing-These.

Implikationen

Falls die These wahr ist, kann es kein Rechnermodell geben, das mehr als die bisherigen Modelle berechnen kann. Insbesondere ist ein Computer ein solches Rechnermodell, somit kann auf ihm theoretisch jeder Algorithmus ausgeführt werden, vorausgesetzt genügend Speicherplatz ist vorhanden. Es ist dann nicht möglich, eine Rechenmaschine zu bauen, die mehr berechnen kann, als ein Computer bereits kann. Da viele Programmiersprachen ebenfalls Turing-vollständig sind, kann man jeglichen Algorithmus mittels eines Quelltexts dieser Sprachen ausdrücken. Insbesondere können sich verschiedene Rechenmodelle (z. B. Registermaschinen, Turingmaschinen, GOTO-Programme, WHILE-Programme, µ-rekursive Funktionen) gegenseitig simulieren.

Falls die These falsch ist, gelten die genannten Implikationen nicht. Eine Widerlegung der These wäre mit der Konstruktion eines Hypercomputers möglich, der Berechnungen ausführen kann, die auf einer Turingmaschine nicht möglich sind.

Erweiterte Churchsche These

Die erweiterte Churchsche These geht noch einen Schritt weiter. Sie lautet:

„Für je zwei Rechnermodelle $R_{1}$ und $R_{2}$ gibt es ein Polynom $p$ , sodass $t$ Rechenschritte auf Modell $R_{1}$ bei Eingaben der Länge $n$ durch $p(t,n)$ Rechenschritte auf Modell $R_{2}$ simuliert werden können.“

Im Angesicht von Quantencomputern wird heute angenommen, dass diese stärkere These nicht stimmt. So ist beispielsweise Shors Algorithmus in der Lage, Zahlen in polynomieller Zeit zu faktorisieren, während die besten bekannten Algorithmen für reguläre Turingmaschinen super-polynomiellen Aufwand verursachen.

Weitere Algorithmenbegriffe

Partiell-rekursive Funktion
Markow-Algorithmus
LOOP-Programm (nicht Turing-vollständig)

Siehe auch

Literatur

Douglas R. Hofstadter: Gödel, Escher, Bach – ein Endloses Geflochtenes Band. Kapitel 17.
Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. In: Proceedings of the London Mathematical Society. Series 2, Bd. 42, 1936, ISSN 0024-6115, S. 230–265.
Hans Hermes: Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit. 2. Auflage. Springer Berlin, Heidelberg, New York, 1971, ISBN 3-540-05334-4.

Einzelnachweise

↑ Dirk W. Hoffmann: Theoretische Informatik. 2., aktualisierte Auflage. Carl Hanser Fachbuchverlag, München 2011, ISBN 978-3-446-42639-9, S. 308.

[1] Dirk W. Hoffmann: Theoretische Informatik. 2., aktualisierte Auflage. Carl Hanser Fachbuchverlag, München 2011, ISBN 978-3-446-42639-9, S. 308.

[1]

@@ Zeile 1: / Zeile 1: @@
-Die '''Church-Turing-These''' (auch '''Churche These''', benannt nach [[Alonzo Church]] und [[Alan Turing]]) ist eine These der [[Berechenbarkeitstheorie]]. Sie geht davon aus, dass eine gewisse Vorstellung davon existiert, welche Funktionen auf den natürlichen Zahlen berechenbar sind. Allerdings ist es schwierig bis unmöglich auf Basis dieser Intuition den Nachweis zu führen, dass eine Funktion nicht berechenbar ist.
+Die '''Church-Turing-These''' (benannt nach [[Alonzo Church]] und [[Alan Turing]], auch '''Churchsche These''' genannt) trifft Aussagen über die Fähigkeiten einer Rechenmaschine. Sie lautet:
+{{Zitat
-Der intuitive Begriff der Berechenbarkeit muss daher mittels einer Definition in eine mathematische Form gebracht werden. Dadurch kann es ermöglicht werden, von einer Funktion nachzuweisen, dass sie nicht berechenbar ist. Allerdings muss begründet werden, dass die formale Definition den intuitiven Begriff der Berechenbarkeit erfasst. Diese Begründung mündet dann in der '''Church-Turing-These''':
+ |Text=Die [[Klasse (Mengenlehre)|Klasse]] der [[Turingmaschine|Turing-berechenbaren]] [[Funktion (Mathematik)|Funktionen]] stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein.
+ |ref=<ref>[[Dirk W. Hoffmann]]: ''Theoretische Informatik.'' 2.,&nbsp;aktualisierte Auflage. Carl Hanser Fachbuchverlag, München 2011, ISBN 978-3-446-42639-9, S.&nbsp;308.</ref>}}
+Diese [[These]] ist nicht beweisbar, da der Begriff „intuitiv berechenbare Funktion“ nicht exakt formalisiert werden kann. Man versteht darunter alle Funktionen, die prinzipiell auf irgendeine Weise berechnet werden könnten. Damit setzt man insbesondere keine Vorstellung voraus, welche Funktionen auf den natürlichen Zahlen berechenbar sind. Es wird in der [[Informatik]] üblicherweise angenommen, dass die These stimmt. Dadurch wird es möglich, für eine Funktion nachzuweisen, dass sie nicht berechenbar ist.
-:''Die [[Klasse (Mengenlehre)|Klasse]] der [[Turingmaschine|Turing-berechenbaren]] [[Funktion (Mathematik)|Funktionen]] ist genau die Klasse der intuitiv berechenbaren Funktionen.''
-Diese [[These]] ist nicht beweisbar, da der Begriff ''intuitiv berechenbare Funktion'' nicht exakt formalisiert werden kann. Man versteht darunter alle Funktionen, die prinzipiell auch von einem Menschen ''ausgerechnet'' werden könnten. Es wird in der [[Informatik]] üblicherweise angenommen, dass die These stimmt.
 == Entstehung ==
-Turing empfand die Gedankenprozesse eines Menschen beim Zahlenrechnen durch die von ihm entwickelte [[Turingmaschine]] nach (in der Funktionsweise ähnlich den heutigen [[Computer|Computern]]) und analysierte deren Fähigkeiten [1]. Er stellte fest, dass viele Funktionen, die von einem Menschen ''ausgedacht'' werden können, erst gar nicht durch die Turingmaschine berechenbar sind, wie z.B. die Funktion des [[Halteproblem|Halteproblems]].
+Turing empfand die Gedankenprozesse eines Menschen beim Zahlenrechnen durch die von ihm entwickelte [[Turingmaschine]] nach (in der Funktionsweise ähnlich den heutigen [[Computer]]n) und analysierte deren Fähigkeiten. Er stellte fest, dass viele Funktionen, die von einem Menschen ''ausgedacht'' werden können, erst gar nicht durch die Turingmaschine berechenbar sind, wie z.&nbsp;B. die Funktion des [[Halteproblem]]s.
-Zum anderen zeigte sich, dass auch andere Herangehensweisen, die menschliche Denkweise beim Rechnen zu formalisieren nicht erfolgreicher waren: So wurde von Turing historisch zuerst die Äquivalenz von Churchs [[Lambdakalkül]] zur Turingmaschine bewiesen. Es folgten darauf viele weitere vorgeschlagene [[Algorithmus|Algorithmenbegriffe]], die alle in ihrer Berechnungsfähigkeit nicht mehr leisteten als die Turingmaschine. Man bezeichnet sie demzufolge als [[Turing-Vollständigkeit|turing-vollständig]].
+Zum anderen zeigte sich, dass auch andere Herangehensweisen, die menschliche Denkweise beim Rechnen zu formalisieren, nicht erfolgreicher waren: So wurde von Turing historisch zuerst die Äquivalenz von Churchs [[Lambda-Kalkül]] zur Turingmaschine bewiesen. Es folgten darauf viele weitere vorgeschlagene [[Algorithmus|Algorithmenbegriffe]] (Rechenmodelle), die alle in ihrer Berechnungsfähigkeit nicht mehr leisteten als die Turingmaschine. Man bezeichnet diese Algorithmenbegriffe demzufolge als [[Turing-Vollständigkeit|Turing-vollständig]].
-Dies ließ vermuten, dass es keinen mächtigeren Formalismus als den der Turingmaschine hinsichtlich der [[Berechenbarkeit]] gäbe und der Mensch - ebenfalls algorithmisch arbeitend - auch nicht mehr Funktionen ''ausrechnen'' könne. Damit entstand die Church-Turing-These.
+Dies ließ vermuten, dass es keinen mächtigeren Formalismus als den der Turingmaschine hinsichtlich der [[Berechenbarkeit]] gäbe und der Mensch –&nbsp;ebenfalls algorithmisch arbeitend&nbsp;– auch nicht mehr Funktionen ''ausrechnen'' könne. Damit entstand die Church-Turing-These.
 == Implikationen ==
-Falls die These wahr ist, kann es kein Rechenmodell geben, das mehr als die bisherigen Modelle berechnen kann. Insbesondere ist ein [[Computer]] ein solches Rechenmodell, somit kann auf ihm theoretisch jeder Algorithmus ausgeführt werden, vorausgesetzt genügend [[Speicher|Speicherplatz]] ist vorhanden. Es ist dann nicht möglich eine Rechenmaschine zu bauen, die mehr berechnen kann als ein Computer bereits kann. Da viele [[Programmiersprachen]] ebenfalls turing-vollständig sind, kann man jeglichen Algorithmus mittels eines [[Quelltext|Quelltexts]] dieser Sprachen ausdrücken.
+Falls die These wahr ist, kann es kein [[Rechnermodell]] geben, das mehr als die bisherigen Modelle berechnen kann. Insbesondere ist ein [[Computer]] ein solches Rechnermodell, somit kann auf ihm theoretisch jeder Algorithmus ausgeführt werden, vorausgesetzt genügend [[Speicherkapazität|Speicherplatz]] ist vorhanden. Es ist dann nicht möglich, eine Rechenmaschine zu bauen, die mehr berechnen kann, als ein Computer bereits kann. Da viele [[Programmiersprache]]n ebenfalls Turing-vollständig sind, kann man jeglichen Algorithmus mittels eines [[Quelltext]]s dieser Sprachen ausdrücken. Insbesondere können sich verschiedene Rechenmodelle (z.&nbsp;B. [[Registermaschine]]n, [[Turingmaschine]]n, [[GOTO-Programm]]e, [[WHILE-Programm]]e, [[Μ-Rekursion|µ-rekursive Funktionen]]) gegenseitig simulieren.
+Falls die These falsch ist, gelten die genannten Implikationen nicht. Eine [[Falsifikation|Widerlegung]] der These wäre mit der Konstruktion eines [[Hypercomputer]]s möglich, der Berechnungen ausführen kann, die auf einer Turingmaschine nicht möglich sind.
+== Erweiterte Churchsche These ==
+Die '''erweiterte Churchsche These''' geht noch einen Schritt weiter. Sie lautet:
+{{Zitat
-Falls die These falsch ist, gelten die genannten Implikationen nicht. Eine [[Falsifikation|Widerlegung der These]] wäre mit der Konstruktion eines [[Hypercomputer|Hypercomputers]] möglich, der Berechnungen ausführen kann, die auf einer Turingmaschine nicht möglich sind.
+ |Text=Für je zwei Rechnermodelle <math>R_1</math> und <math>R_2</math> gibt es ein [[Polynom#Verallgemeinerungen|Polynom]] <math>p</math>, sodass <math>t</math> Rechenschritte auf Modell <math>R_1</math> bei Eingaben der Länge <math>n</math> durch <math>p(t,n)</math> Rechenschritte auf Modell <math>R_2</math> simuliert werden können.}}
+Im Angesicht von [[Quantencomputer]]n wird heute angenommen, dass diese stärkere These nicht stimmt. So ist beispielsweise [[Shor-Algorithmus|Shors Algorithmus]] in der Lage, Zahlen in polynomieller Zeit zu [[Faktorisierungsproblem|faktorisieren]], während die besten bekannten Algorithmen für reguläre Turingmaschinen super-polynomiellen Aufwand verursachen.
-==Weitere Algorithmenbegriffe==
-*[[Μ-Rekursion|partiell-rekursive Funktion]]
-*[[Registermaschine]]
-*[[Markow-Algorithmus]]
-*[[GOTO-Programm]]
-*[[LOOP-Programm]] (nicht turing-vollständig)
-*[[WHILE-Programm]]
+== Weitere Algorithmenbegriffe ==
-== Referenzen und Literatur ==
+* [[Μ-Rekursion|Partiell-rekursive Funktion]]
-* [1] [[Alan Turing|Turing, A.M.]]: [http://www.abelard.org/turpap2/tp2-ie.asp "On Computable Numbers, with an Application to the Entscheidungsproblem"], 1936.
+* [[Markow-Algorithmus]]
-* [[Douglas_R._Hofstadter|Hofstadter, Douglas R.]]: [[Gödel, Escher, Bach|''Gödel, Escher, Bach: Gödel, Escher, Bach: ein Endloses Geflochtenes Band'']], Kapitel 17.
+* [[LOOP-Programm]] (nicht Turing-vollständig)
+== Siehe auch ==
+* [[Gödelscher Unvollständigkeitssatz]]
+* [[Philosophie des Geistes]]
+== Literatur ==
-''Siehe auch:'' [[Gödelscher Unvollständigkeitssatz]], [[Philosophie des Geistes]]
+* {{Literatur |Autor=[[Douglas R. Hofstadter]] |Titel=[[Gödel, Escher, Bach|Gödel, Escher, Bach – ein Endloses Geflochtenes Band]] |Datum= |Kapitel=Kapitel 17}}
+* {{Literatur |Autor=[[Alan Turing]] |Titel=On Computable Numbers, with an Application to the Entscheidungsproblem |Sammelwerk=Proceedings of the London Mathematical Society |Band=Series 2, Bd. 42 |Datum=1936 |ISSN=0024-6115 |Seiten=230–265}}
+* {{Literatur |Autor=[[Hans Hermes]] |Titel=Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit |Auflage=2. |Verlag=Springer Berlin, Heidelberg, New York |Datum=1971 |ISBN=3-540-05334-4}}
+== Einzelnachweise ==
-[[Kategorie:Theoretische Informatik]]
+<references />
+[[Kategorie:Berechenbarkeitstheorie]]
-[[en:Church-Turing thesis]]
+[[Kategorie:Automatentheorie]]
-[[es:Tesis de Church-Turing]]
+[[Kategorie:Komplexitätstheorie]]
-[[fr:Thèse de Church-Turing]]
+[[Kategorie:Alan Turing als Namensgeber]]
-[[ko:처치-튜링 명제]]
-[[lt:Tiuringo tezė]]
+[[lt:Tiuringo mašina#Tiuringo tezė]]
-[[pt:Tese de Church-Turing]]
-[[ru:Тезис Чёрча-Тьюринга]]
-[[zh:邱奇-图灵论题]]

~2025-37651-59 (Diskussion | Beiträge)