Diskussion:Halteproblem

Mich interessiert eine genauere Unterscheidung zwischen dem speziellen und allgemeinen Halteproblem. Lohnen sich da zwei Artikel? Stern 21:43, 21. Feb 2004 (CET)

Bei mir wird die Anzeige der Unterschiede in der Versionsgeschichte bei den letzten Versionen dieses Artikels unansehnlich auseinandergezogen (Browser: Mozilla Firebird 0.6.1). Hat das Problem noch jemand? Liegt das vielleicht an den von mir eingebauten div's? :( --brunft 15:03, 12. Mär 2004 (CET)

"Bereits ein Spezialfall des Halteproblems, die Frage, ob eine Turingmaschine auf der leeren Eingabe hält, genannt H0, ist nicht entscheidbar."

Warum? --brunft 15:49, 12. Mär 2004 (CET)

Du kannst aus Programm P + Eingabe für H stattdessen ein Programm P_0 für H0 machen, daß am Anfang die Eingabe per Zuweisung enthält, und ansonsten genauso rechnet wie P. --Starblue 22:09, 29. Mär 2004 (CEST)

Wie verbreitet ist denn Jana? hab noch nie davon gehört. Starblue 10:39, 29. Mär 2004 (CEST)

Hmm, weiss nicht, ich bin das erste Mal beim Informatik-Studium in Linz damit in Berührung gekommen. Kennst du noch andere allg. Sprachen zur Beschreibung von Algorithmen? --brunft 21:24, 29. Mär 2004 (CEST)

Hab mal mit Google gesucht, Jana scheint auf Linz beschränkt zu sein. Normalerweise macht jeder Professor seine Privatsprache, ist jedenfalls meine Erfahrung. Starblue 22:01, 29. Mär 2004 (CEST)

Spezifikation vs. Interpretation -- Fehler?

Die Spezifikation von haltetest(p,e) besagt, dass die Ausgabe genau dann TRUE ist, wenn p bei Bearbeitung von e hält. In der Interpretation ist das aber genau vertauscht, dort steht nämlich, dass bei der Ausgabe FALSE bedeutete, dass programm(p,p) terminiert. Müsste es nicht heißen:

liefert haltetest(p,p) TRUE, so hieße dies, dass programm(p,p) terminiert -- aber die Bedingung haltetest(p,p) innerhalb von programm ist dann immer wahr, und damit kann programm nicht terminieren => falsch!
liefert haltetest(p,p) FALSE, so müsste programm(p,p) endlos weiterlaufen. Dann trifft aber die Bedingung in der while-Schleife niemals zu, und programm(p,p) terminiert => auch falsch!

--Pinguin.tk 22:45, 12. Apr 2004 (CEST)

Nachdem niemand Einspruch erhoben hat, hab ich den die "Terminierungserklärungen" wie oben beschrieben im Artikel eingefügt. --Pinguin.tk 16:02, 29. Apr 2004 (CEST)

Philosophisch-weltanschaulicher Teil

Letzter Kommentar: vor 21 Jahren4 Kommentare3 Personen sind an der Diskussion beteiligt

Ich habe den Teil nun zum wiederholten Mal wieder reingenommen und finde es blöd, dass er ständig gelöscht wird. Wenn dem einen oder anderen die Formulierungen nicht gefallen, dann kann er sie ja korrigieren. Aber Volltextlöschung sollten doch eher diskutiert werden! Stern 22:28, 1. Mai 2004 (CEST)Beantworten

Der Teil passt meines Er8ens überhaupt nicht zu dem Artikel. Er ist spekulativ, der Stil ist in großen Passagen un-enzyklopädisch.

Das geht schon mit dem ersten Satz los: Geht man von der Existenz einer Gottheit aus und unterstellt man ihr ... - das ist Spekulation, kein Wissen. Die Wikipedia dient nicht zur Theoriebildung, sondern zur Wissens-Darstellung, hab ich an anderer Stelle in einer Diskussion gelesen.

Am Ende beweist diese These aber weder die Existenz noch die Nichtexistenz von Gott. So ist es. Es ist auch nicht ihre Intention, das eine oder andere zu leisten.

Eigentlich bin ich auch dafür, den Abschnitt zu löschen. --Mussklprozz 01:04, 3. Mai 2004 (CEST)Beantworten

Natürlich wird die Church-Turing-These unterstellt und auch wird unterstellt, dass Gott alles können muss. Aber beides liegt meines Erachtens gar nicht so fern. Daher ist der Abschnitt durchaus interessant. Auch passt er in den Artikel, da man ja durch das Halteproblem auf ein philosophisches Problem Rückschlüsse ziehen kann. Vielleicht ist die Formulierung nicht perfekt. Dann wäre es super, wenn Du die Passage entsprechend überarbeitest. Ich halte die von Dir zitierte Passage auch nicht für Spekulation, sondern für die Voraussetzung einer Vermutung. Man geht ja auch von der Existenz von Atomen aus, wenn man von Molekülen redet. Das ist eine Art Axiom. Stern 01:16, 3. Mai 2004 (CEST)Beantworten

Wie ist denn das mit den Orakel-Turingmaschinen, die können ja zumindest nichtdeterministische Fragestellungen fehlerfrei beantworten (was normale TMs nicht tun) -- wie weit sind die von Deiner "Gottheit" entfernt in ihrer Mächtigkeit? Kennt sich da jemand aus?? Ich versuche mal, es nachzulesen... --Pinguin.tk 08:22, 3. Mai 2004 (CEST)Beantworten

Dieser ganze philosophische Teil erscheint mir überflüssig und unenzyklopädisch. Wenn überhaupt, gehört diese Betrachtung zur Church-Turing-These, da sie nur mit dieser sinnvoll sein kann. Sie ist nicht spezifisch für das Halteproblem - genauso gut könnte man sie dann zum Äquivalenzproblem schreiben.

Beispiel in Java

Ich glaube nicht, dass das Beispiel in JAVA von einem Nicht-Kenner dieser Sprache soleicht verstanden wird. Ich würde da eine etwas klarere Sprache nehmen? Oder?

Die Beispiele sind in Jana (Informatik), nicht Java (Programmiersprache). Aber du hast recht, ich werd's mal auf etwas verständlicheren Pseudocode umschreiben. -- D. Düsentrieb (?!) 15:55, 17. Aug 2004 (CEST)

Turingmaschine => physikalisch realisierbarer Rechner => Mensch

Die letzten zwei Drittel des Artikels sind ziemlich weit her geholt. Alle Schlussfolgerungen zu Turingmaschinen basieren auf der Analyse eines ziemlich simplen Models. Schon die Church Hypothese, die letztlich ausdrückt, dass das einfache mathematische Model der Turing maschine für alle physikalisch realisierbaren Rechner adequat ist, ist schon starker Tobak. Hier wird nämlich ein Schluss von der Mathematik zur Physik gezogen, obwohl wir letztere nur in Teilen verstehen. Ich weise mal auf die Überraschungen hin, die Quantencomputer so liefern. Von diese Stufe nochmal auf die Grenzen des menschlichen Gehirns zu schliessen, von dem wir auch nur sehr wenig wissen,ist schon ziemlich verwegen. Wir sollten klarer nette Spekulation und gesicherte Erkenntnis im Artikel trennen. --Marc van Woerkom 16:29, 24. Sep 2004 (CEST)

da hast Du recht, aber ich fände es falsch, die Spekulationen ganz rauszuwerfen -- schon, weil sie nach einer Weile wahrscheinlich von allein wieder auftauchen, von Gesichertem schwer zu unterschieden (siehe auch Diskussion oben). --Pinguin.tk 16:59, 24. Sep 2004 (CEST)

Naja, der Schluss von der Turingmaschine auf physikalische Rechner ist eigentlich nicht so weit hergeholt: die Aussage bezieht sich ja nicht darauf, was phyikalisch Machbar ist, sondern darauf, was formale Systeme (und damit auch ihre mechanische oder elektronische Umsetzung) überhaupt leisten können. Zudem ist es ja eine dem wesen nach unbeweisbare These (weil wir nicht wissen, was wir noch nicht wissen). Die analogie zum Gehirn ist da schon etwas schwieriger, da es sich dabei ja nicht um ein formales System handelt. Oder doch, aber nur auf der untersten, unübersichtlichsten ebene: Energie-Quanten interagieren auf eine fest vorgegebene Weise miteinander. Ob es physikalische prozesse gibt, die sich durch ein formales System nicht ausdrücken lassen, wissen wir nicht - aber es gibt viele, die sich nur sehr sehr aufwendig formal fassen lassen (z.B. das Drei-Körper-Problem). Quantenkomputer sind übrigens soweit ich weiss nicht mächtiger als Turingmaschinen - aber sie hebeln einige Gesetze der Komplexitätstheorie aus, sind also effizienter. -- D. Düsentrieb ⇌ 18:54, 24. Sep 2004 (CEST)

bei einem formalen System werden aus einer Handvoll Axiome und Schlußregeln in endlich vielen Schritten Sätze konstruiert. Der Quantencomputer scheint jedoch die Möglichkeit zu bieten, in einem einzigen Schritt (abzählbar) unendlich viele Schritte des formalen Systems in einen einzigen Rechenschritt zusammenzuziehen. Sollte dies stimmen, ist er nicht an das Halteproblem gebunden! Deshalb halte ich es ebenfalls für sehr gewagt, um nicht zu sagen "naiv", aus der (formalen) Turing-Maschine Rückschlüsse auf die physikalische Welt, insbesondere auf den Menschen zu ziehen. Ein formales System ist nur ein formales System. Nicht umsonst zählt die Mathematik NICHT zu den NATUR-Wissenschaften!

Aber mE beschreibt das Kapitel "weltanschauliche Konsequenzen" sowieso nur, daß eine Gottheit genau dann keine Turing-Maschine ist, wenn sie keine Turing-Maschine ist. Also zirkelschlüssiger Humbug, oder? Die Nichtbeweisbarkeit und Nichtwiderlegbarkeit der Existenz eines Gottes war auch schon vor Gödel und Turing bekannt...

Erschreckend finde ich, daß unter "Siehe auch" nur ein Link zu "Gottesbeweis" existiert - bei einem rein zahlentheoretischen Lemma! --Modran 19:10, 24. Sep 2004 (CEST)

Ich lagere mal den Gottesbeweis hierer aus und schreib das neu. Dauert aber einen Moment... -- D. Düsentrieb ⇌ 19:44, 24. Sep 2004 (CEST)

Philosophisch-weltanschauliche Konsequenz

Geht man von der Existenz einer Gottheit aus und unterstellt man ihr, sie sei allwissend und stehe nicht im Widerspruch zu allem Vorhandenen, so hieße das, dass sie prinzipiell auch das Halteproblem entscheiden können müsse. So muss diese Gottheit also die Fähigkeiten von Menschen und Maschinen im Sinn von Berechenbarkeit übersteigen.

Geht man davon aus, dass eine Gottheit keiner Turingmaschine im oben angenommenen Sinn entspricht, also übersinnliche Fähigkeiten hätte, so wäre ihre Nichtexistenz nicht bewiesen.

Geht man aber davon aus, dass die Existenz einer Gottheit in Widerspruch zu Bekanntem steht, also unlogisch ist, weil niemand ein bewiesenermaßen unlösbares Problem lösen kann, so gäbe es keine Gottheit! Dies gilt insbesondere unter Voraussetzung der Vorstellung mancher Gläubiger, nach der Menschen, deren mathematischen Fähigkeiten das Halteproblem nicht zu lösen vermögen, Ebenbilder einer Gottheit sind. Dann könnte eine Gottheit nicht existieren! Die Nichtexistenz Gottes wäre bewiesen. Zumindest aber wäre bewiesen, dass eine Gottheit keine Maschine ist.

Diese philosophisch-weltanschauliche Konsequenz setzt allerdings die Korrektheit der churchschen These voraus.

Am Ende beweist diese These aber weder die Existenz noch die Nichtexistenz von Gott, denn Gott wäre kein abzählbar potentiell unendlicher Automat, wie die Turingmaschine.

Man muss beachten, dass die Turingmaschine streng determiniert ist, nur abzählbare Mengen bearbeitet und keinen Zufall kennt. Sie ist eine theoretische Maschine. Jede praktische Maschine hält, zumindest, wenn der Strom ausfällt (allgemeiner, wenn ein zufallsbedingter Zustand eintritt).

Gott könnte die Reset-Taste drücken. Die Frage, ob dann die Welt hält, ist nicht entscheidbar.

Siehe auch: Gottesbeweis

So, ich hoffe, das gefällt euch besser -- D. Düsentrieb ⇌ 20:04, 24. Sep 2004 (CEST)

So ists wesentlich besser. Aber eine Sache stört mich noch: Einstein hat zwar noch die Konsequenzen der Quantentheorie kategorisch abgelehnt (Fernwirkung), aber heutzutage können wir sie nicht mehr ignorieren, sie sind x-fach experimentell bestätigt.

In dem Artikel sieht es im Moment so aus, als wäre der Determinismus die vorherrschende physikalische Weltanschauung, und dies ist seit mindestens 30 jahren nicht mehr wahr! Heutzutage leugnet kein ernsthafter Physiker mehr den nicht-deterministischen Charakter der Welt. --Modran 20:14, 24. Sep 2004 (CEST)

Ja, mitterweile ist der Indeterminismus lehrmeinung (und ich stimme dem zu), aber weder die verborgene Variable noch die Viele-Welten-Theorie ist wiederlegt. Der Grund dafür, dass ich hier die deterministische Sichtweise in den Vordergrund gehoben habe ist die, dass auf sie das Halteproblem zutrifft. Andernfalls wäre das ein Beitrag geworden, der besser in den (dürftigen) Artikel zu Indeterminismus passt. Es ging ja um die Philosophische konsequenz des Halteproblems. Du kannst das ganze aber gerne so anpassen, dass es etwas ausgewogener daherkommt. -- D. Düsentrieb ⇌ 20:23, 24. Sep 2004 (CEST)