Diskussion:Halteproblem/Archiv

Diese Seite ist ein Archiv abgeschlossener Diskussionen. Ihr Inhalt sollte daher nicht mehr verändert werden. Benutze bitte die aktuelle Diskussionsseite, auch um eine archivierte Diskussion weiterzuführen.

Um einen Abschnitt dieser Seite zu verlinken, klicke im Inhaltsverzeichnis auf den Abschnitt und kopiere dann Seitenname und Abschnittsüberschrift aus der Adresszeile deines Browsers, beispielsweise

[[Diskussion:Halteproblem/Archiv#Thema 1]]

oder als Weblink zur Verlinkung außerhalb der Wikipedia

https://de.wikipedia.org/wiki/Diskussion:Halteproblem/Archiv#Thema_1

generelle kritik

Das ganze bezieht sich nicht auf den Einleitungsabschnitt, sondern auf den Rest dadrunter, der die Einleitung eigentlicher deutlicher machen soll.

Wenn ich wissen will, ob das Programm halten wird, dann schau einfach im Sourcecode nach. Darin wird man vermutlich eine Haltebedingung entdecken und aus dem vorigen Programmcode ableiten können, ob diese jemals erreicht wird. Es gibt ja nur zwei Möglichkeiten, entweder das Programm hält oder es hält nicht. Wenn es nicht hält, dann liegt es an einer Endlosschleife(sei es rekursiv oder "normal"). Also geht es nur darum diese Endlosschleife aussfindig zu machen, oder nach Lücken schauen, die eine Endlosschleife zur Programmlaufzeit verursachen können. Wo hier das Problem liegt, das zeigt dieses Beispiel keineswegs.

Das problem mit dem Beispiel ist: es hält sich nicht an die Problemstellung: "In der angewandten Informatik lautet die Frage: Kann man ein Programm entwickeln, das als Eingabe den Quelltext eines zweiten Programms sowie dessen Eingabewerte erhält, welches entscheiden kann, ob das zweite Programm terminiert, d. h. nicht endlos weiterläuft." Hier im Beispiel ist, aber nur ein Programm. Und das "Problem" mit rekursiven Endlosschleife besteht immernoch:

Angenommen: test(test) wurde ausgeführt, wir sind in der Prozedur haltetest(Programm, Eingabe) angekommen, dessen Inhalt nun folgender ist:

haltetest(test, test)

1 wenn test(test) terminiert

2 dann return Ja

3 sonst return Nein

um test(test) nun "irgendwie" zu prüfen, müsste man ja folgendes wieder überprüfen:

test(test)

1 solange haltetest(test, test) == Ja

2 führe aus keine Aktion

hier sieht man, dass wir wieder mit dem selben Ergebniss in der Prozedur haltetest sind, und immer so weiter... das Programm muss sich verschachteln.

Fragt die Informatik falsch, hat jemand die Frage falsch verstanden, oder stehen im Artikel falsche Antworten: geht es darum zu entscheiden, ob ein zweites Programm etwas über ein anderes rausfindet, oder ein Programm etwas über sich selbst? (hier ist mit "etwas" das Halteproblem gemeint)

Je öfter ich mir diesen Artikel durchlese, desto weniger versteh ich ihn:

Zitat/ "liefert haltetest(test,test) JA, so hieße dies, dass test(test) terminiert – aber die Bedingung haltetest(Programm,Programm) innerhalb von test ist gerade dann immer wahr, so dass test(test) eben nicht terminiert, weil die while-Schleife niemals beendet wird. Das ist ein Widerspruch!"

"liefert haltetest(test,test) NEIN, so ist die Bedingung der while-Schleife niemals wahr, und test(test) terminiert sofort. Das ist ebenfalls ein Widerspruch!" \Zietat ende

Was liefert das Programm, denn letztendlich??? Garnichts! Es hält ja nicht an, gesetzt das mit der Rekursivität steht. Ist das nun der Beweis?

Es sollte vielleicht mal jemand, dieses (Pseudo)Programm wirklich schreiben, und ausprobieren.

Gesetzt nun, das Programm gibt keine Antwort, wenn es sich selbst aufruft( das wäre ja dann wohl die gesuchte Unentscheidbarkeit). Wenn es mit der Rekursivität' nun so steht, dann hab ich das ja als Mensch entscheiden können. Mit diesem Wissen nun, kann ich das Programm so schreiben, dass es sich sogar dann entscheidet, wenn es selbst aufgerufen wird:

test(Programm)

1 solange ((Programm != test) AND haltetest(Programm, Programm)) == Ja

2 führe aus keine Aktion

Würde bei der ersten fehlgeschlagenen Bedingung abrechen, ohne die weiteren zu testen. Et voila! Problem gelöst, zumindest bei diesem Pseudobeweis.

Ob ein zweites Programm sagen kann ob ein anderes endigt, ist vielleicht sogar auch möglich. Beruht darauf: da das Ganze eine rein logische angelegenheit ist, und da ein Mensch das ganze selbst nur logisch bestimmen kann, ob ein Programm endigt(wie?: s.o.!), ergo muss es möglich sein ein Programm zu schreiben, dass dies kann, denn das ist selbst ja nur logik; bin mir in diesem Punkt nicht so sicher; denke auch das Turings Beweis hier ansetzt, indem er grad dort die logische Unentscheidbarkeit beweist, (na wenn überhaupt, ich kenne den Beweis ja nicht).

Wenn, der Artikel das alles klären würde, dann fände, zumindest ich, ihn sehr gelungen. Das sollte jemand machen, der sich mit der Materie auskennt, ich besitze da leider zu wenig Kenntnisse.

Hoffe, etwas zur Aufklärung beigetragen zu haben:

--WahrnehmendeMaschine 18:45, 12. Feb 2006 (CET)

@WahrnehmendeMaschine: Es geht hier nicht darum, dass man ein Prog schreiben kann, dass keinen Widerspruch liefert, sondern darum, dass es EIN Programm GIBT (z.B. dieses), welches einen Widerspruch erzeugt ( Die Frage ist ja: Gibt es diese Funktion? Widerspruch -> Nein, es gibt sie NICHT (für alles Programme (denn bei min. einem haben wir den Widerspruch)))!!(Der vorstehende, nicht signierte Beitrag – siehe dazu Hilfe:Signatur – stammt von Poser99 (Diskussion • Beiträge) 03:12, 10. Nov. 2008 (CET))

Halteproblem unentscheidbar

Das Halteproblem ist nicht semi-entscheidbar sondern unentscheidbar. Die Begründung für die semi-Entscheidbarkeit ist falsch, da nur eine feste Eingabe w betrachtet wird.

Allgemein sollte man genauer zwischen nicht entscheidbar und unentscheidbar unterscheiden.

--129.13.72.198 15:22, 28. Jan. 2009 (CET)

Das Halteproblem ist semi-entscheidbar und damit auch unentscheidbar (Semi-Entscheidbarkeit ist eine Unterkategorie von Unentscheidbarkeit), man simuliert einfach das gegebene Programm mit der gegebenen Eingabe (z.B. auf einer universellen Turingmaschine) und falls es terminiert, gibt man die entsprechende Meldung aus. Falls das Programm mit der Eingabe nicht hält, wird dies die Simulation natürlich auch nicht tun, d.h. die Ausgabe wird nicht definiert sein. "Nich entscheidbar" und "unentscheidbar" ist das gleiche, deshalb ist eine Unterscheidung nicht nötig. --Godfatherofpolka 11:45, 30. Jan. 2009 (CET)

>""Nich entscheidbar" und "unentscheidbar" ist das gleiche" das stimmt sicher, trotzdem, ich nehme an, du meintest semi-entscheidbar und unentscheidbar? Darum geht es ja hier. Und da muss ich dir wohl wiedersprechen. Bei unserem Prof klingt es immer so, als wäre semi-entscheidbar schon fast so viel wert wie entscheidbar, was natürlich genau so Käse ist. Kommt es nicht auf die Komplexität an? Wenn ich ein Programm schreibe: while(false) ist wohl mit jedem denkbaren Computer schnell entscheidbar, dass es hält. Während while(true) offensichtlich mit keinem Computer entscheidbar ist. Nur für sehr komplexe Probleme ist Semientscheidbarkeit wohl in der Regel nicht hilfreich.--F GX 10:33, 24. Jul. 2009 (CEST)

Semi-entscheidbar ist nicht das gleiche wie unentscheidbar, eine semi-entscheidbare (bzw. der Genauigkeit halber: semi-entscheidbare, nicht entscheidbare) Menge ist unentscheidbar, eine unentscheidbare Menge hingegegen muss nicht semi-entscheidbar sein (Beispiel: Das Komplement einer semi-entscheidbaren, nicht entscheidbaren Menge). Bei der Semi-Entscheidbarkeit handelt es sich also in einem gewissen Sinne um die einfachste Stufe der Unentscheidbarkeit (bzw. die zweit-einfachste Stufe, wenn man noch die "Entscheidbarkeit" miteinrechnet. Es gibt noch viele weitere Stufen, weitere Infos findet man unter "arithmetische Hierarchie" in der einschlägigen Literatur), d.h. wenn eine Menge nicht entscheidbar ist, dann kann man darauf hoffen, dass sie wenigstens semi-entscheidbar ist. Zudem gibt es viele "schöne" Äquivalenzen zur Semi-Entscheidbarkeit (z.B. rekursive Aufzählbarkeit), die das Arbeiten damit angenehm machen. Mit Komplexitätsklassen hat das ganze relativ wenig zu tun, die Probleme in den gängigsten Komplexitätsklassen (P, NP, PH) sind längst noch entscheidbar. Ein einzelnes Programm ist nicht entscheidbar oder nicht, es geht immer um Mengen (von Programmen, bzw. deren Codes). Gruss --Godfatherofpolka 17:16, 26. Jul. 2009 (CEST)

Sorry, <Ein einzelnes Programm ist nicht entscheidbar oder nicht, es geht immer um Mengen> ich verstehe dich einfach nicht. Ich sage jetzt einfach, dass ich dafür bin, dass Halteproblem als semi-entscheidbar zu deklarieren und damit, den Artikel zu ändern. Wie du selbst schreibst, ist sogar Entscheidbarkeit eine Unterklasse von Unentscheidbarkeit. Es macht also sinn, immer die strengste, mächtigste Kategoriesierung zu verwenden. Es hat keinen Sinn, das Halteproblem als unentscheidbar zu bezeichnen, wenn es semi-entscheidbar ist, selbst wenn beides korrekt ist.--F GX 10:32, 17. Aug. 2009 (CEST)

Im dritten Abschnitt der Einleitung sowie im Beweis wird auf die Semi-Entscheidbarkeit hingewiesen, falls dies aber zu wenig deutlich erscheint, bitte ich Dich natürlich entsprechende Verbesserungen anzubringen, der Artikel ist sicherlich nicht perfekt. Mit der beanstandeten Bemerkung meinte ich, dass Entscheidbarkeit eine Eigenschaft von Mengen, z.B. Mengen von Programmen bzw. deren Gödel-Nummern, ist und nicht die Eigenschaft eines Programmes. Gruss --Godfatherofpolka 21:16, 17. Aug. 2009 (CEST)

OK du hast natürlich Recht, es geht bei Entscheidbarkeit um Sprachen (aka "Mengen"). Solange in der Artikel Einleitung einwandtfrei beides hervorgeht, nämlich dass das Halteproblem unentscheidbar und dabei im Speziellen noch semi-entscheidbar ist, bin ich zufrieden. Insofern möchte ich meinen früheren Beitrag teilweise revidieren. Worüber man eventuell noch nachdenken könnte ist die Erwähnung, dass das Komplement des Halteproblems nicht entscheidbar und auch nicht semientscheidbar ist. Alternativ werde ich das in den Artikel zur Entscheidbarkeit einfügen.--F GX 16:22, 18. Sep. 2009 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: Friedrich Graf (Diskussion) 23:04, 16. Mär. 2012 (CET)

artikel so lassen

Lasst bitte den Text, so wie er ist, bestehen. Der ist nämlich sehr gut. Da hat jemand sein Lebenswerk in wenigen Worten zusammengefasst, punktgenau, wenn man etwas von Mathematik versteht. Denkt drüber nach, statt zu lärmentieren.(Der vorstehende, nicht signierte Beitrag – siehe dazu Hilfe:Signatur – stammt von 212.117.90.66 (Diskussion • Beiträge) 06:07, 14. Jan. 2007 (CET))

Sagt wer? --- ich lärmentiere trotzdem einfach mal:

1. haltetest soll ein (hypothetischer) Algorithmus sein, keine Funktion.
2. Die Haltefunktion H, also die Funktion, die jedem Paar Programm und Eingabe seine Terminierungseigenschaft zuordnet, die gibt es ohne Zweifel. Hier ist ihre Definition: H: Programm x Eingabe -> {nein,ja} definiert durch

H(P,a) = ja, falls P für die Eingabe a hält; H(P,a) = nein sonst.

1. Im Beweis geht es darum zu zeigen, dass die Haltefunktion nicht berechenbar ist, also dass es zur Haltefunktion keinen Algorithmus gibt.
2. Die Annahme muss also lauten: Angenommen, es gibt einen Algorithmus für die Haltefunktion, nennen wir ihn haltetest. Über die Form von haltetest darf nichts vorausgesetzt werden. (Der Dreizeiler ist also unzulässig.)
3. Die Argumentation geht dann so:

haltetest(test, test) ergibt nein => test(test) terminiert => haltetest(test, test) gibt die falsche Antwort.

haltetest(test, test) ergibt ja => test(test) terminiert nicht => haltetest(test, test) gibt die falsche Antwort.

In jedem Fall gibt also haltetest(test, test) die falsche Antwort. Widerspruch.--AlfonsGeser 00:28, 10. Mai 2008 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: Friedrich Graf (Diskussion) 23:05, 16. Mär. 2012 (CET)

Artikel ungenau

Der Artikel ist ungenau. Hier wird vom Halteproblem gesprochen jedoch ist der der Beweis zum einen kein Beweis sondern eine informale Beweisidee. Zum anderen, was viel wichtiger ist, wird hier das SELBSTANWENDBARKEITSPROBLEM behandelt was nur eine echte Teilmenge des Halteproblems ist. Das Halteproblem an sich ist Semi-Entscheidbar.(Der vorstehende, nicht signierte Beitrag – siehe dazu Hilfe:Signatur – stammt von 81.173.238.48 (Diskussion • Beiträge) 15:56, 26. Sep. 2007 (CEST))

Archivierung dieses Abschnittes wurde gewünscht von: Friedrich Graf (Diskussion) 23:05, 16. Mär. 2012 (CET)

Aus der Vogelperspektive

1. Die zentrale Aussage des Artikels ist natürlich die Unentscheidbarkeit des Halteproblems der Turingmaschinen. Daneben sollte aber kurz auf das Halteproblem in anderen Kalkülen eingegangen werden. Insbesondere gibt es ja auch Kalküle mit entscheidbarem Halteproblem.
2. Die Bemerkung über das spezielle Halteproblem und das Halteproblem mit leerem Band sollte in einen eigenen Abschnitt "Verwandte Probleme" wandern. Dorthin gehört auch eine Bemerkung über das Gleichmäßige Halteproblem (englisch: uniform halting problem).
3. Der Abschnitt "Halteproblem und Mächtigkeit von Potenzmengen" gehört thematisch definitiv nicht in diesen Artikel. Eine kurze Bemerkung ist aber angebracht, dass der Beweis der Unentscheidbarkeit des Halteproblems zu den Diagnonalisierungen gehört, und dass die Überabzählbarkeit der reellen Zahlen und die Mächtigkeit der Potenzmengen mit derselben Methode angegangen werden.
4. Im Abschnitt "Konsequenzen" werden Vorkommnisse erwähnt, die zeitlich vor Turings Beweis (1936) stehen, also unmöglich Konsequenzen sein können. Dazu gehört Gödels Unvollständikeitssatz (1931). Wurde nicht Turing von Gödels Unvollständigkeitssatz inspiriert zu seinem Unentscheidbarkeitsresultat? "Vorgeschichte" wäre doch passend als Abschnittsüberschrift.
5. Dass der Satz von Rice eine Konsequenz von Turings Satz sein soll, kann ich nicht nachvollziehen. Es handelt sich einfach um ein sehr allgemeines Unentscheidbarkeitsresultat.
6. Was für Unsinn die Leute glauben, gehört nicht in eine Enzyklopädie.
7. Im Halteproblem-Artikel wird ein Kalkül vorausgesetzt --- ob zu recht oder nicht. Die gesamte Diskussion um Kalküle und ihren Bezug zur Wirklichkeit gehört also anderswohin, zum Beispiel zum Artikel Church-Turing-These.
8. Eine philosophische Betrachtung wäre auch nett, aber bitte mit der gebotenen Präzision und Neutralität. Skizze:

Ein putatives höheres Wesen, das nicht an die Beschränkungen des Kalküls gebunden ist, könnte zum Halteproblem für Turingmaschinen immer eine Antwort parat haben, etwa durch Nachsehen in einer unendlichen Tabelle (einem Orakel). Eine derartige Annahme steht nicht im Widerspruch zur Unentscheidbarkeit, denn das Orakel ist ja kein Algorithmus, also kein Entscheidungsverfahren. Für dieses Wesen stellt sich allerdings ein neues Problem, nämlich das Halteproblem für Orakel-Turingmaschinen, das heißt Turing-Maschinen, die außerdem wie unser höheres Wesen das Orakel befragen dürfen. Auch für Orakel-Turingmaschinen läßt sich Turings Beweis anwenden, mit dem Ergebnis, dass es keine Orakel-Turingmaschine gibt, die das Halteproblem für Orakel-Turingmaschinen löst. Das höhere Wesen hat sich also durch seine erhöhte Fähigkeit auch ein härteres Problem eingehandelt. Man kann diese Argumentation ins Unendliche fortsetzen, wobei man letzten Endes zu jeder Ordinalzahl einen Kalkül bekommt.

Was haltet ihr davon?--AlfonsGeser 14:17, 10. Mai 2008 (CEST)

Also das mit den übermächtigen Orakeln, die eine geheime Tabelle besitzen, möcht ich gerne noch genauer erklärt bekommen. Also es handelt sich dabei um keinen Algorithmus und es kann daher nicht von dem zu überprüfenden Programm aufgerufen werden. Allerdings könnte es andere übermächtige Orakelwesen geben, welche auf unser mächtiges Orakel zugreifen können, d.h. zur Vorhersage verwenden können. Daher kann unser Orakel wieder nicht vorhersehen, da die anderen mächtigen Orakel dies verhindern. Man bräuchte jetzt ein Orkakel noch höhere Ordnung, welches dies alles überblickt usw. Richtig verstanden? --Headbreak 21:41, 3. Sep. 2011 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: Friedrich Graf (Diskussion) 23:06, 16. Mär. 2012 (CET)

formaler fehler

außerdem liegt hier ein formaler fehler vor, x tritt sowohl in der menge X auf also auch in P(X) formal wäre hier richtig zu schreiben x element X und {x} element P(x) (die potenzmenge ist die menge aller teilmengen, dh. die potenzmenge ist eine menge von mengen)(Der vorstehende, nicht signierte Beitrag – siehe dazu Hilfe:Signatur – stammt von 80.108.32.133 (Diskussion • Beiträge) 23:16, 26. Jun. 2008 (CEST))

Archivierung dieses Abschnittes wurde gewünscht von: Friedrich Graf (Diskussion) 23:07, 16. Mär. 2012 (CET)

verständnissfrage

Mal eine Frage, verstehe ich es richtig, dass Y hier die leere Menge ist ? $Y:=\left\{\,x\in X\mid x\notin f(x)\,\right\}$.(Der vorstehende, nicht signierte Beitrag – siehe dazu Hilfe:Signatur – stammt von Poser99 (Diskussion • Beiträge) 03:02, 10. Nov. 2008 (CET))

Tatsächlich fehlt hier noch der Beweis, dass Y nicht leer sein kann: Angenommen Y wäre leer, dann gälte für alle x aus X: f(x) enthält x. Die Potenzmenge über N muss aber alle möglichen Kombinationen der Elemente ihrer Ursprungsmenge enthalten. So z.B. auch {x, 1}. Für ALLE x. Damit wären dann schon alle Zahlen x ausgenutzt und es bliebe keine mehr für z.B. {x,2} übrig - was ja aber auch ein Teil der Potenzmengen ist. Daraus folgt, dass Y nicht leer sein kann. Kann diesen wichtigen(!) Beweis noch jemand formal ergänzen? (nicht signierter Beitrag von 79.255.97.63 (Diskussion) 14:08, 25. Nov. 2010 (CET))

Archivierung dieses Abschnittes wurde gewünscht von: Friedrich Graf (Diskussion) 23:07, 16. Mär. 2012 (CET)

vorschlag

Also aus meiner langjährigen Informatiksicht würde ich Euch folgende,

dem Problem angemessenere und hoffentlich auch verständlichere Programmbeschreibung vorschlagen.

(Das bisherige Beispiel läuft aus technischer Sicht natürlich immer in eine endlose Rekursion und wird daher kein Ergebnis liefert, auch kein falsches!)

haltetest(programm)

' Kommentar: Es folgt das Scannen des Codes des Programms test und seines Unterprogramms haltetest.

' Kommentar: Die Funktion scanneCode wird den Wert 'wird terminieren' oder 'wird nicht terminieren' liefern.

' Kommentar: Das Paradoxon wird sichtbar, wenn man nun versuchen würde eine logisch korrekte Funktion für 'scanneCode' einzusetzen.

' Kommentar: Dies ist schlicht und einfach nicht möglich!

' Kommentar: Allerdings könnte die Funktion noch so etwas wie 'kein Ergebnis möglich' zurückgeben.

' Kommentar: Dann würde schlussendlich das Programm zwar terminieren, hätte es aber eben selbst nicht feststellen können.

ergebnis = scanneCode(programm)

wenn ergebnis = 'wird terminieren' dann

liefere 'ja'

sonst

liefere 'nein'

test()

ergebnis = haltetest(test)

wenn ergebnis = 'ja' dann

terminiere nicht

sonst

terminiere(Der vorstehende, nicht signierte Beitrag – siehe dazu Hilfe:Signatur – stammt von 92.117.89.78 (Diskussion • Beiträge) 11:42, 10. Dez. 2008 (CET))

Ich glaube, es gibt einen Grund, warum das Beispiel nicht (mehr?) im Artikel ist - mit einem offensichtlichen Programmfehler läßt sich nichts beweisen. Nicht alles, was falsch ist, ist ein Paradoxon. Außerdem geht es im Artikel um ZWEI Programme: "Kann man ein Programm entwickeln, das als Eingabe den Quelltext eines zweiten Programms sowie dessen Eingabewerte erhält, welches entscheiden kann, ob das zweite Programm terminiert, d. h. nicht endlos weiterläuft?"--213.221.250.85 14:17, 7. Dez. 2010 (CET)

Ich finde das Beispiel sehr schön. Im Beispiel sind ja auch zwei Programme: haltetest und test --217.251.229.97 21:02, 21. Jul. 2011 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: Friedrich Graf (Diskussion) 23:08, 16. Mär. 2012 (CET)

Konsequenzen

Für den Abschnitt Konsequenzen fehlen die Quellen. Ohne Quellen stellt dieser Abschnitt eine Theoriefindung dar. --Headbreak 17:23, 17. Jul. 2011 (CEST)

Quellen finden sich in verlinkten Artikeln. --Leif Czerny 13:26, 4. Sep. 2011 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: Friedrich Graf (Diskussion) 23:08, 16. Mär. 2012 (CET)

Bezug zur Russellschen Antinomie fehlt

Ich denke in diesem Artikel fehlt der Bezug zur Russellschen Antinomie. Diese beschreibt abstrakt genau, warum das Halteproblem und andere derartige Paradoxien nicht-entscheidbar sind.

• Die Unlösbarkeit des Halteproblems und sein Bezug zu den klassischen Antinomien (Christian Maurer)
• Russell: Mathematical logic as based on the theory of types, in: American Journal of Mathematics 30 (1908), Seite 225.

“Whatever involves all of a collection must not be one of the collection” --Headbreak 10:48, 1. Okt. 2011 (CEST)

Es gibt sehr viele "Verwandtschaften" des Halteproblems. Im Fall der "Russellschen Antinomie" wird die Unlösbarkeit des Halteproblems als Illustration benutzt. Das würde dieses Lemma nicht bereichern und dem Leser keinen Erkenntnisgewinn bringen. --Friedrich Graf (Diskussion) 23:15, 16. Mär. 2012 (CET)

Archivierung dieses Abschnittes wurde gewünscht von: Friedrich Graf (Diskussion) 23:15, 16. Mär. 2012 (CET)

Beispiele

Ich hätte gerne einen Abschnitt mit Beispielen für Programme, die weder halten noch endlos laufen. Hier mein Vorschlag, welcher auch schon früher mal im Artikel war:

test(Programm)
  solange haltetest(Programm, Programm) == Ja
      führe aus keine Aktion
test(test)

--Headbreak 10:05, 2. Okt. 2011 (CEST)

der satz ist sinnlos. ein programm haelt fuer eine bestimmte eingabe oder nicht. --Mario d 18:41, 2. Okt. 2011 (CEST)

Was heißt hier sinnlos? Genau um solche Programme geht es doch beim Halteproblem. Schau mal in der Beweisskizze nach. Da steht das selbe Programm. Sinn hat es in dem Sinn also, dass es zeigt, dass es ein solches Programm haltetest nicht geben kann. --Headbreak 18:56, 4. Okt. 2011 (CEST)

Ächz ... das Code-Beispiel verwirrt eher, als dass es den Sachverhalt erhellt. Falls Du es weiterhin drinhaben willst, hole bitte Dritte Meinung ein. Gruß, --Mussklprozz 22:30, 4. Okt. 2011 (CEST)

Und warum ächzt es? --Headbreak 21:13, 14. Nov. 2011 (CET)

Weil es falsch ist. Das hier beschriebene Pseudocode Programm ruft sich selbst wieder auf, was G nicht tut. Auch prüft G nur einmal H, und nicht endlos oft, wie in deinem Pseudocode. Wie ich Dir schon vor deiner Sperre sagte: Du scheinst die Materie nicht verstanden zu haben. --P.C. ✉ 07:25, 16. Nov. 2011 (CET)

„Das hier beschriebene Pseudocode Programm ruft sich selbst wieder“ Versuch mal den Artikelinhalt anzuschauen und nicht nur den Diff. Dann sollten auch die Einrückungen stimmen. G ruft sich niemals selber auf. Ob H mehrmals oder nur einmal aufgerufen wird, ist gar nicht relevant. Es soll halt nur zu einer Endlosschleife führen. H hätte sicher einen Ergebnispuffer, sodass das Ergebnis zwischengespeichert wird und nicht nochmal gerechnet werden soll. Da es ja ein "Beispiel" ist, muss es nur den Anforderungen im Artikel genügen, kann aber auch noch zusätzliche Merkmale haben. Übrigens ist eine Ausgabe für den Fall, dass G nicht hält hier zu vernachlässigen, weil, wenn G nicht hält, dann braucht es auch nichts ausgeben. Also ist das Beispiel korrekt. --Headbreak 19:01, 21. Nov. 2011 (CET)

Headbreak, ich vermute, das du etwas in der Art der Collatz-Vermutung meinst. Dieses Beispiel ist jetzt im Text. --Friedrich Graf (Diskussion) 23:17, 16. Mär. 2012 (CET)

Archivierung dieses Abschnittes wurde gewünscht von: Friedrich Graf (Diskussion) 23:17, 16. Mär. 2012 (CET)

Sprachgebrauch

Bei dem Begriff „Halteproblem“ werden im allgemeinen Sprachgebrauch und der Definition verschiedene Bedeutungen gemischt.

Wenn vom Halteproblem gesprochen wird, geht es meistens darum, dass es Berechnungsvorschriften gibt, bei denen man die Frage, ob sie bei der Ausführung etwas bestimmtes tun werden, nur mit „vielleicht“ beantworten kann. Diese Berechnungsvorschriften werden als wohldefiniert, aber als unlösbar angesehen. So ist bei manchen Berechnungsvorschriften die Frage, ob sie jemals halten werden, in absehbarer Zeit nicht zu beantworten. Diese Berechnungsvorschriften lassen sich zwar wohldefiniert niederschreiben, aber nicht in absehbarer Zeit zu Ende ausführen. Die unten dargestellte Beweiskizze behandelt allerdings eine gänzlich andere Situation. In diesem Fall geht es darum, ob eine Berechnungsvorschrift bei der Ausführung etwas bestimmtes tun wird, wenn die Berechnungsvorschrift dabei auf die Beantwortung dieser Frage zurückgreifen kann und so handelt, dass sie die Beantwortung widerlegt. Diese Berechnungsvorschrift wird dann ebenfalls als wohldefiniert, aber unlösbar angesehen.

--Headbreak 17:38, 21. Feb. 2012 (CET)

das ist teilweise wischi-waschi, teilweise falsch und ich kann nicht sehen, wie das einem leser weiterhelfen soll. das halteproblem ist genau definiert, da gibt es kein "meistens". der definitionsversuch ist falsch, es geht darum, ob ein algorithmus terminiert, nicht darum, was er tut - das waere die korrektheit, ein anderes problem. die begriffe "loesbar" oder "unloesbar" koennen nicht sinnvoll auf algorithmen angewendet werden. dem langen satz, der den beweis erklaeren soll, kann ich keine sinnvolle aussage entnehmen. s.a. WP:GA#Begriffsdefinition_und_Einleitung. --Mario d 17:49, 21. Feb. 2012 (CET)

"Dem langen Satz kann ich keine sinnvolle Aussage entnehmen". Dann erklär doch mal, wo dein Interpreter stecken bleibt. Sonst wird das schwierig mit der Fehlersuche. --Headbreak 23:11, 21. Feb. 2012 (CET)

aus dem satz geht nicht hervor, welche "Frage" gemeint ist, und es ist unklar, was es bedeuten soll, eine beantwortung zu widerlegen. ich denke es waere sinnvoller, wenn du beschreiben wurdest, wo du die jetzige einleitung unklar findest, anstatt einen neuen absatz einzufuegen, der den gleichen sachverhalt nocheinmal beschreibt. --Mario d 11:40, 22. Feb. 2012 (CET)

Gut. Die einzige mögliche interpretierbare Frage ist die, die nach dem "ob" folgt. Was es bedeutet, eine Beantwortung zu widerlegen, sieht man ja in der Beweiskizze. In der Einleitung fehlt a) der entscheidene Hinweis, dass es zulässig und dann auch immer noch wohldefiniert ist, wenn das zu untersuchende Programm das Ergebnis des Untersuchers verwenden kann und b) dass im allgemeinen Sprachgebrauch etwas anderes mit dem Halteproblem gemeint ist. --Headbreak 21:41, 26. Feb. 2012 (CET)

der abschnitt ist jedenfalls unverstaendlich. bei a) sehe ich nicht, was das mit dem halteproblem zu tun haben soll, fuer b) haette ich gerne eine quelle. --Mario d 13:52, 27. Feb. 2012 (CET)

Wenn man die einzigen in der Beweiskizze vorgehenden Vorgang (Programm schaut, was es in der Zukunft machen wird und wird laut Programmiercode genau das Gegenteil machen, um das zu verhindern) nicht versteht, dann kann man natürlich auch nicht verstehen, was a) ist. Falls doch müsstest du zumindest einen Unterschied zwischen "a" und der Beweiskizze nennen können. Für b) (Berechnung theoretisch möglich, dauert aber zu lange) schau schlag einfach mal ein Buch zum Thema „Fleißiger Biber“ auf. --Headbreak 22:27, 27. Feb. 2012 (CET)

Achso, dann gibt es natürlich auch Bedeutung c) ein Programm wird zwar in absehbarer Zeit halten oder endlos laufen bzw. etwas beliebiges anderes tun, aber es würde kein Programm geben, welche vorhersehen könnte, was in dieser absehbaren Zeit passieren wird. Siehe dazu auch Abschnitt "Politik" --Headbreak 18:45, 28. Feb. 2012 (CET)

Das ist keine Quellenangabe, sondern vages Namedropping. Das Halteproblem ist ein wohldefinierter mathematischer Begriff, der Einleitungsabschnitt erklärt es in diesem Sinne. Stichhaltige Quellen für abweichenden Sprachgebrauch kannst Du offensichtlich nicht nennen. Bitte sieh von Einfügungen ab, die den Sachverhalt verwässern. – Vielen Dank, Gruß aus Freiberg am Neckar --Mussklprozz 07:51, 28. Feb. 2012 (CET)

dem kann ich nur zustimmen. zu a): klar kann ich das. im beweis verwendet "das zu untersuchende Programm" nicht "das Ergebnis des Untersuchers". die disku dient aber nicht dazu, dir den beweis zu erklaeren; dafuer gibt es genug foren im internet. --Mario d 12:09, 28. Feb. 2012 (CET)

«im beweis verwendet "das zu untersuchende Programm" nicht "das Ergebnis des Untersuchers".» Quelle? --Headbreak 16:16, 28. Feb. 2012 (CET)

brauche ich nicht, ich will ja nichts in den artikel einbauen. du willst das, also musst du quellen herbeischaffen, die deine aussagen belegen. --Mario d 17:16, 28. Feb. 2012 (CET)

diskussionsbeitraege nachtraeglich zu veraendern bzw. zwischen bereits bestehende beitraege zu quetschen, macht es sehr schwierig, darauf zu antworten. das ist im moment aber nicht so tragisch, solange du keine belege fuer deine aussagen hast, ist die diskussion fuer mich beendet. --Mario d 19:13, 28. Feb. 2012 (CET)

Da bisher also weder die eine noch die gegenteilige Aussage belegt im Artikel steht, habe ich einen Lückenhaft-Baustein gesetzt. --Headbreak 20:02, 28. Feb. 2012 (CET)

schon die frage ist in dem kontext sinnlos. T darf ueberhaupt nichts machen, weil T gar nicht laeuft. H wird aufgerufen, und nur H macht irgendwas. --Mario d 20:28, 28. Feb. 2012 (CET)

Wenn du mal auf meine Diskussionsseite geschaut hättest, dann wüstest du das das Argument schon mal kam. Und ja, wie kann denn T überhaupt darauf geprüft werden, ob es halten wird, wenn es ja gar nicht läuft? Was nicht startet kann ja auch nicht halten.

wie im artikel bereits erklaert: H bekommt den code von T und kann ihn sich anschauen. du glaubst doch nicht im ernst, dass ich mir deine disku durchlese, um herauszufinden, was du bereits mit wem diskutiert hast? --Mario d 20:48, 28. Feb. 2012 (CET)

Bist du mit „Darf in den Anweisungen von T stehen, dass H aufgerufen werden soll?“ zufrieden? Sprachlich wohldefiniert?

Auch übrigens sehr informativ: mathoverflow: What is the shortest program for which halting is unknown? --Headbreak 21:13, 28. Feb. 2012 (CET)

Ups ich bin schon wieder reingefallen. Natürlich läuft T. So ein Unsinn.^^ Es ist ja eben die Sache, dass sowohl T läuft als auch H(T) (innerhalb von T). --Headbreak 21:17, 28. Feb. 2012 (CET)

Wenn man $F$ mit ihrer eigenen Beschreibung $b(F)$ als Eingabe in Betrieb setzt, dann passiert Folgendes:

1. $F$ ersetzt die Eingabe $b(F)$ durch $b(F)*b(F)$.
2. $F$ ruft $G$ mit der Eingabe $b(F)*b(F)$ auf.
3. $G$ ruft $H$ mit der Eingabe $b(F)*b(F)$ auf.

→ Und wie man hier sieht wird keinesfalls irgendeine Funktion F, welche von H geprüft wird, in Betrieb gesetzt. Nein, doch nicht in Betrieb gesetzt! Und auch nicht mit exakt dem gleichen Eingabewert! Nein, nicht doch! Schließlich ist das eine F ja ein anderes als das andere F, weil es während der Ausführung verändert wird... (Ironie) --Headbreak 21:28, 28. Feb. 2012 (CET)

Archivierung dieses Abschnittes wurde gewünscht von: Friedrich Graf (Diskussion) 23:18, 16. Mär. 2012 (CET)

Abschnitt über Politik

Was soll denn der merkwürdige Abschnitt "Politik"? Nur weil mal irgendein "Politiker" das Wort Halteproblem in den Mund nimmt (und mehr passiert ja im Video nicht), muss da doch kein Verweis drauf in die Wikipedia, denke ich.

Von "Erklären" kann da ja auch kaum die Rede sein. So wie es auf den ersten Blick scheint hat dieser Mann mit Informatik ohnehin eher weniger am Hut. (nicht signierter Beitrag von 188.102.76.92 (Diskussion) 05:03, 29. Feb. 2012 (CET))

Bin fürs Löschen -- Leif Czerny 08:43, 29. Feb. 2012 (CET)

ich denke, da hat es ein tagespolitischer abschnitt mal wieder in die WP geschafft. ausser, dass der abgeordnete das wort ein paarmal in den mund nimmt, hat das auch nicht viel mit dem thema zu tun, schon gar nicht wird das halteproblem, wie im artikel geschrieben, erklaert. --Mario d 11:16, 29. Feb. 2012 (CET)

Du hast es gelöscht – gut so. :-) Gruß aus Freiberg am Neckar, --Mussklprozz 12:10, 29. Feb. 2012 (CET)

Archivierung dieses Abschnittes wurde gewünscht von: Friedrich Graf (Diskussion) 23:19, 16. Mär. 2012 (CET)

Mächtigkeit

Eben erhielt ich folgenden Hinweis: "Mächtigkeit bezieht sich nur auf Mengen und bedeutet nicht dasselbe wie Komplexität. ..." - hierzu habe ich der Diskussion auf dem Lemma "Gödelscher Unvollständigkeitssatz" folgendes entnommen.... --Friedrich Graf (Diskussion) 19:55, 15. Mär. 2012 (CET)

1:0 für Dich. Der Artikel Gödelscher Unvollständigkeitssatz verwendet Mächtigkeit tatsächlich im allgemeineren Sinne, nicht im Sinne der Mengenlehre. Trotzdem gefällt mir die Verwechslungsmöglichkeit nicht, und der Link auf Mächtigkeit (Mathematik) geht ganz und gar nicht. Ich hab mal ins Bücherregal gegriffen, und bin bei Douglas R. Hofstadter fündig geworden: „(...) dass, mag System X auch noch so leistungsstark und flexibel sein, es Wahrheiten gibt, die in seinem Rahmen unerreichbar bleiben, solange es sich nicht in einen Selbstwiderspruch verwickelt“ (Douglas R. Hofstadter: Eine leicht fassliche Darstellung von Gödels Theorem, in: Metamagikum, Klett-Cotta, Stuttgart 1988, ISBN 3-608-93098-2, S. 270.) - Kurz und gut: was hältst Du von leistungsstark statt mächtig? Gruß, --Mussklprozz (Diskussion) 20:48, 15. Mär. 2012 (CET)

Ehrlich gesagt ist mir der einzelne Begriff nicht primär wichtig. Was ich für deutlich wichtiger halten würde, ist eine längere Kausalkette bezüglich des "Gödelschen Unvollständigkeitssatz". Dessen fundamentale Bedeutung für die Mathematik (ab einem bestimmten Grad treten Eigenschaften auf ...) ist durch eine einfache Verlinkung dem Laien nicht verständlich zu machen. Aber genau diese Bedeutung findet im Halteproblem ein wunderbares Beispiel. Meine Kausalkonstruktion folgte dazu ungefähr folgendem Prinzip: es gibt formale Systeme (Erklärung) > wenn diese komplex werden, entstehen neue Eigenschaften > Unentscheidbarkeit entsteht > Halteproblem. Dabei habe ich an dieser Stelle bewußt auf das Wort "Axiom" verzichtet, denn dieses kennt unzählige Sinnzusammenhänge im Sprachgebrauch (und zur Erklärung ist es nicht notwendig).

• Hinweis: Die angestrebte Laienverständlichkeit sollte natürlich nicht "unendlich" im Artikel praktiziert werden. Aber solange wir uns im oberen Teil des Lemmas befinden, dürfte dies ein "muss" sein.

FG --Friedrich Graf (Diskussion) 21:46, 15. Mär. 2012 (CET)

Ich kann zwar keine Gedanken lesen, vermute aber, das oben angedeutete Kausalkette gestern Abend "im Eifer des Gefechts" verschwunden ist ... und jetzt traut sich keiner/kann es keiner/ möchte es keiner/...
Mache wir es doch einfach: heute nachmittag werde ich einen zweiten Anlauf unternehmen und die beschriebene Kausalkette neu formulieren. Hierzu würden mich generelle Hinweise bezüglich der Wortverwendung "Mächtigkeit" interessieren. Falls jemand gegen das Wort "Mächtigkeit" ist, würde ich auch immer um eine Alternative bitten. Danke. --Friedrich Graf (Diskussion) 09:10, 16. Mär. 2012 (CET)

Bitte verwende stattdessen Leistungsfähigkeit. Gruß, --Mussklprozz (Diskussion) 09:31, 16. Mär. 2012 (CET)

der begriff "axiom" hat in diesem kontext eine eindeutige bedeutung, man koennte auch auf Axiom#Formaler_Axiombegriff verlinken, wenn das dadurch klarer wird. fuer eigenschaften wuerde ich eher "auftreten" als "entstehen" sagen, letzteres hat eher etwas prozesshaftes. die kausalkette finde ich noch ein wenig loechrig: der unvollstaendigkeitssatz spricht ueber die unbeweisbarkeit wahrer aussagen, beim halteproblem geht es um die algorithmische unentscheidbarkeit von eigenschaften. vieleicht hilft en:Undecidable_problem#Relationship_with_G.C3.B6del.27s_incompleteness_theorem, en:Halting_problem#Relationship_with_G.C3.B6del.27s_incompleteness_theorem, en:Gödel's_incompleteness_theorems#Relationship_with_computability bei der formulierung. --Mario d 12:22, 16. Mär. 2012 (CET)

Danke für die Anregungen. Was die Löcher betrifft, so werde ich mal mal nachdenken. Ich melde mich dann. --Friedrich Graf (Diskussion) 13:20, 16. Mär. 2012 (CET)

Ich versuche mich mal ... --Friedrich Graf (Diskussion) 16:01, 16. Mär. 2012 (CET)

Fertig - durch die Unterbrechungen meiner Arbeit hat es sich etwas hingezogen ... FG --Friedrich Graf (Diskussion) 17:39, 16. Mär. 2012 (CET)

Archivierung dieses Abschnittes wurde gewünscht von: Friedrich Graf (Diskussion) 23:24, 16. Mär. 2012 (CET)