Diskussion:Church-Turing-These

"In ihrer verallgemeinerten Form vermutet sie, dass sämtliche formalen Algorithmenbegriffe, auch alle zukünftigen, maximal zu diesen beiden äquivalent sind (oder einen geringeren Geltungsanspruch besitzen)."

Wieso denn "oder"? "geringerer Geltungsanspruch" steckt doch in "_maximal_ äquivalent" schon mit drin.

--129.13.64.201 02:54, 29. Okt 2003 (CET)

Ich kenne die Church'sche These noch in einer anderen Formulierung/Bedeutung: Die Chursche These sagt dabei aus, dass sich alle heute gebräuchlichen Rechnermodelle (also keine Quantenrechner) gegenseitig mit polynomiellem Zeitverlust simulieren können!

IMO geht es um Berechenbarkeit, nicht um Komplexität. Beispiel: NP kann wahrscheinlich nicht "mit polynomialem Zeitverlust" mit P simuliert werden." --JensMueller 15:09, 12. Mär 2004 (CET)

Sollte das ebenfalls noch aufgenommen werden?? Falls ja, bitte Mail an tommy_vossy*AT*web.de.

Ich kenne folgende Definition der "Churchschen These": "Alle intuitiv von einem Menschen lösbaren Algorithmen kann auch eine Turingmaschine lösen." Ich bin mir nicht ganz sicher bei der Formulierung. Ein Experte kann sie gerne validieren und ggf. einbauen. 82.82.125.76 23:08, 2. Feb 2004 (CET)

---

"aber wie alle mathematischen Beweise eine ahistorische Gültigkeit für alle Zeiten beansprucht"

Was bedeutet "ahistorische"? Oder ist das ein Schreibfehler? --brunft 14:54, 12. Mär 2004 (CET)

Habe ", aber wie alle mathematischen Beweise eine ahistorische Gültigkeit für alle Zeiten beansprucht, also den Algorithmenbegriff zu eng fasst" herausgenommen, weil im Satz vorher steht, dass es keinen Beweis gibt. --Dirk Beyer 12:49, 11. Okt 2004 (CEST)

Das unter These von Church Gespeicherte bezog sich auf die in diesem Artikel behandelte Church-Turing-These. Lasse deshalb jenen Artikel auf diesen hier zeigen. Habe die besseren Saetze des anderen Artikels in diesen hier uebernommen und dafuer nicht so gute Formulierungen hier herausgenommen. --Dirk Beyer 20:44, 11. Okt 2004 (CEST)

---

Simulierbarkeit

Was soll der Verweis zu Quantencomputern? In dem zugehörigen Artikel steht klar, dass diese prinzipiell auch nichts bisher unberechenbares berechnen können, weil sie (sehr langsam) mit klassischen Computern simulierbar sind. --Tian 17:55, 19. Okt 2004 (CEST)

WEnn ich das richtig verstanden habe, können Quantencomputer nicht simuliert werden, weil sie in der Lage sind, abzählbar unendlich viele möglichkeiten gleichzeitig zu "probieren". Wenn das so ist, dann sollte das unter Quantencomputer erwähnt werden. Wenn nicht, dann hast du recht, und der Hinweis sollte raus. Ich bin da leider kein Experte... -- D. Düsentrieb ⇌ 19:43, 19. Okt 2004 (CEST)

Ich weiß nicht, ob so das Entscheidende an Quantencomputern charakterisiert werden kann. Aber auf jeden Fall kann ein konventioneller Computer das simulieren. Mache einen Schritt der ersten Berechnung, zwei Schritte der ersten beiden Berechnungen, drei Schritte der ersten drei Brechnungen usw. --Tian 17:59, 20. Okt 2004 (CEST)

Und das ist meiner Meinung nach quatsch. Sie können es nicht. Du kannst Q-Computer nicht durch einen Computer (Turing-Maschine) simulieren.

Wieso nicht? Abzählbar unendlich viele Berechnungen sind jedenfalls kein Problem. --Tian

Für einen Turing-Rechner sollten sie tatsächlich kein Problem sein, für jeden realen Rechner allerdings. Wie kommen bei einem Quantenrechner die abzählbar unendlich vielen Werte zustande? Ist eventuell bei dem Vergleich mit der Turingmaschine gemeint, dass die Zeitdauer problematisch sei, weil der Turing-Rechner sehr sehr lange braucht, während beim Quantenrechner nach einem Schritt (oder so ähnlich) alle Varianten vorhanden sind? --Hutschi 17:41, 16. Dez 2005 (CET)

15:40, 16. Dez 2005 (CET)

Beweisbarkeit

Der Artikel behauptet, das die Church'sche These nicht formal beweisbar ist. Ich habe das auch schon häufiger in Büchern und Skripten zur Theoretischen Informatik gelesen, aber nie einen Beweis oder wenigstens eine Begründung dafür bekommen. Es wäre schön, wenn dazu etwas gesagt werden würde. --Coma 22:20, 1. Jan 2005 (CET)

Das Problem besteht darin, dass der Terminus "intuitiv berechenbar" nicht formal fassbar ist: die allgemeinste Art von Berechenbarkeit, die wir formal beschreiben können, ist die Turing-Berechenbarkeit. Der Berechenbarkeitsbegriff ist darüberhinaus einfach undefiniert, desshalb können Aussagen darüber nicht getroffen werden. Wird jedoch eine "stärkere" Berechenbarkeitsklasse gefunden (z.B. due Quantencomputing, etc), so wäre die These widerlegt, bzw. "intuitiv berechenbar" müsste genauer eingeschränkt werden. -- D. Dÿsentrieb ⇌ 03:02, 2. Jan 2005 (CET)

Naja, das stimmt schon, d.h. aber nicht, dass man es nicht formal beweisen könnte. Es reicht ja aus eine stärkere Aussage zu beweisen, die das formal nicht fassbare "intuitiv" mit einschließt und damit nicht benötigt. Zum Beispiel könnte es ja sein, dass die Nichtberechbarkeit jedes nicht-turing-berechenbaren Problems auf die nicht-turing-Berechbarkeit des speziellen Halteproblems zurückgeführt werden kann (mir sind keine Beispiele bekannt, wo dies nicht möglich ist). Insofern wäre eine Erweiterbarkeit also prinzipiell schon unmöglich. --Coma 04:01, 2. Jan 2005 (CET)

Den Ansatz verstehe ich nicht. Es spricht doch z.B. nichts dagegen, dass jemand ein Verfahren angibt, mit dem man das spezielle Halteproblem für TM lösen kann. Es ist eben ausschließlich bewiesen, dass dies nicht mit einer TM geht. Der Formalismus, in dem dieses Verfahren beschrieben ist, wird sein eigenes Halteproblem haben, aber das steht auf einem ganz anderen Blatt. --Tian 17:51, 2. Mär 2005 (CET)

Prinzipiell nicht, aber wenn man sich den Beweis für die Unentscheidbarkeit des Halteproblems genau ansieht, wird man feststellen, das der relativ unabhängig vom Algorithmusbegriff funktioniert. Man kann sicher axiomatisch sinnvolle Anforderungen an intuitiv berechenbare Funktionen stellen, so dass der Beweis immer klappt, also auch jeder stärkere Berechenbarkeitsbegriff weder das Halteproblem für TMs noch das Halteproblem für den stärkeren Berechenbarkeitsbegriff löst. --Coma 00:04, 3. Mär 2005 (CET)

Du bräuchtest die nicht beweisbare Coma-These, dass deine Axiomatik alle intuitiv berechenbaren Funktionen umfasst... Der Beweis dürfte aber immer nur die Nichtberechenbarkeit des Halteproblems für den benutzten Berechenbarkeitsbegriff liefern. Betrachtet man z.B. TM mit Orakel für das (gewöhnliche) Halteproblem, so ist der Beweis anwendbar und zeigt, dass diese Maschinen ihr Halteproblem nicht lösen können, obwohl sie das gewöhnliche Halteproblem in einem Schritt lösen.

Ähm, da muss ich nochmal drüber nachdenken, aber ich glaube da hast du Recht. --Coma 20:59, 4. Mär 2005 (CET)

Zur Frage, ob sich alle nichtberechenbaren Sprachen auf das Halteproblem zurückführen lassen: ich glaube nicht. Betrachte für jede reelle Zahl q die Sprache {(m,n)|m und n sind nat. Zahlen mit m/n<q}. Jede positive Zahl q ergibt eine andere Sprache, es sind also überabzählbar viele. Andrerseits gibt es nur abzählbar viele Algorithmen, also müssen nichtentscheidbare Sprachen unter diesen langweiligen, gar nicht halteproblemäquivalent aussehenden Sprachen sein. (Chaitins Omega könnte einem da noch einfallen, aber das ist algorithmisch approximierbar, die abzählbar vielen approximierbaren Zahlen können wir als q noch ausschließen, da bleiben genug.) -- Tian 17:57, 4. Mär 2005 (CET)

Der Umweg über die reellen Zahlen ist hier überflüssig. Es gibt überabzählbar viele Sprachen. Im Prinzip folgt damit auch schon, dass es tat. nicht so geht, wie von mir vorgeschlagen. Denn es gibt nur abzählbar viele Alg. wie du schon angemerkt hast. Also auch nur abzählbar viele Reduktionen auf andere Probleme. Also kann das Halteproblem auch nur auf abzählbar viele Probleme reduziert werden. Da es aber überabzählbar viele unentscheidbare Sprachen gibt reicht das also nicht. --Coma 20:59, 4. Mär 2005 (CET)

Die Idee hatte ich auch, aber ganz so einfach ist es nicht. Eine Reduktion kann das Halteproblem durchaus auf verschiedene Probleme reduzieren, solange die sich nur in Fällen unterscheiden, auf die die Reduktion nicht abbildet. Ich kann mir allerdings gut vorstellen, dass sich der Gedanke retten läßt. -- Tian 23:54, 4. Mär 2005 (CET)

Stimmt auch wieder. Aber im Prinzip ist das auch nicht so wichtig. Das Beispiel sollte ja eigentlich nur zeigen, dass man nicht ganz so leichtfertig behaupten kann, die Church-Turing-Theses ließe sich nicht beweisen. Leider konnte mir bisher noch niemand beweisen oder plausibel machen, dass sie nicht beweisbar ist. --Coma 13:14, 5. Mär 2005 (CET)

Bewiesene Äquivalenz

Aus dem Artikel wurde gelöscht, dass Turings und Churchs Algorithmenbegriff beweisbar äquivalent sind. Das stimmt aber und ist nicht etwa Teil der These. Ich baue das wieder ein. --Tian 17:51, 2. Mär 2005 (CET)

von Menschen ausgedacht

wobei das Halteproblem natürlich auch man-made ist. wers besser beschreiben kann soll sich versuchen... --141.35.10.186 19:23, 3. Jun 2005 (CEST)

Was ist: "Intuitiv berechenbar"?

Schließt es Intuition mit ein? Z.B. bei Entscheidungsproblemen, die aus dem Bauch entschieden werden, sind diese Turing-berechenbar? Oder anders gesagt: Könnte ein Turing-Automat erzeugt werden, der das gleiche Ergebnis liefert? --Hutschi 10:10, 22. Jun 2005 (CEST)

Siehe dazu die neue Einleitung... --Coma 13:45, 22. Jun 2005 (CEST)

Stochastische Computer

Wenn man einen determinierten Computer verwendet, der eine abzählbar unendliche Menge an Zuständen hat, ist mir das klar, dass er Turing-kompatibel sein kann. Gilt die These aber auch für einen Computer, der an mindestens einer wesentlichen Stelle stetig ist, oder für einen, der an einer wesentlichen Stelle echt stochastisch ist, zum Beispiel, indem er den radioaktiven Zerfall nutzt, also echte Zufallszahlen liefert? Mit einer Turingmaschine sind echte Zufallszahlen nicht berechenbar, soviel ich weiß. So ein Computer braucht ja dann nicht mal ein Supercomputer zu sein. --Hutschi 14:51, 16. Sep 2005 (CEST)

Dein Text enthält viele vage Begriffe. Was ist ein determinierter Computer mit einer abzählbar unendlichen Menge von Zuständen? Wozu hift es uns, wenn wir wissen, dass solche Monstren Turing-kompatibel sein können?

Was ist ein Computer, der an mindestens einer wesentlichen Stelle stetig ist?

Ein Computer, der echt stochastisch arbeitet, muss aus einem Raum von vorgegebenen Ereignissen ein Ereignis auswählen. Dieses Experiment können wir stets deterministisch nachbilden. Daher sind die stochastischen Turingmaschinen nicht mächtiger als die "normalen". Wie der Zufall entsteht ist belanglos, seine Verteilung muss bekannt sein. Wenn die Verteilungsfkt. nicht berechenbar ist, erhalten wir eine Klasse der Berechenbarkeit, die relativ zu der Berechenbarkeit der Verteilungsfunktion ist. Das hat mit Stochastik nichts zu tun. Dieser Prozess wird in der Arithmetischen Hierarchie behandelt. (Der Artikel Arithmetische Hierarchie fehlt in der Wikipedia leider noch!)

Viele Grüße --Gerhard Buntrock 08:29, 17. Sep 2005 (CEST)

Erweiterte Church'sche These

Ich finde, die reine Definition ist hier noch nicht aussagekräftig genug. Es stellen sich Fragen, warum die Simulation in polynomieller Zeit so sinnreich ist etc... M. Seysen 14:55, 25. Sep. 2007 (CEST)