Adventure-Treff

Floyd hat geschrieben:Was ist paradox an deinen gewählten Beispielen? Das erste terminiert bei Eingabe einer negativen Zahl nicht, schön. Warum ist das paradox?Zu den von dir verlinkten Mengenlehren kann ich momentan nicht viel sagen, da ich mich damit nicht befasst habe, sorry.

Ich wollte damit kein Paradoxon zeigen, sondern wie man anhand der Filterung der Eingangswerte eine Terminierung sicherstellt.

Floyd hat geschrieben:Wenn du Eingabewerte "filterst", schränkst du - grob gesprochen - die Mächtigkeit deiner Maschine ein.

Richtig. Wenn die Maschine zu mächtig ist, kann es zu Widersprüchen führen... dies gilt auch für Mengen. Daher ist z.B. die Linear beschränkte Turingmaschine anscheinend nicht dem Halteproblem unterworfen.

Floyd hat geschrieben:Den Beweis der Unentscheidbarkeit desselben hast du ja als "süß" abgetan, stattdessen argumentierst du - für mich immer noch nicht ganz verständlich - mit Hilfe von einfachem Programmcode - nur für was (in Bezug auf das Halteproblem)?

Weil man sich einfach nur an gewisse Regeln halten muss (also die Mächtigkeit einschränken), dann ist die Unentscheidbarkeit kein Thema mehr. Deine Frage verwundert mich etwas, schließlich hast du ja das Halteproblem hier eingebracht als Beispiel für mathematische Beweise. Mir ging es darum, dass auch Beweise immer nur innerhalb der gegebenen Axiome ihre Richtigkeit haben.

Und damit haben wir natürlich wieder den Bogen zu Gott bekommen: Wir können nur dann Paradoxien vermeiden, wenn wir unsere Denkmodelle in ihrer Mächtigkeit einschränken. Bezüglich Gott taucht ja immer wieder das Allmachtsparadoxon auf: Kann Gott einen Stein erschaffen, den er nicht heben kann?
Auch andere Paradoxien verschließen sich der Logik: Wo ist der Anfang des Universums? Wenn es einen Gott gibt, wo kommt dieser Gott dann her? Wenn es einen Schöpfer Gottes gibt, wer hat dann den Schöpfer des Schöpfers erschaffen?
Darum geht es hier doch eigentlich: Kann man die Logik derart ausweiten, dass sie den ultimativen Ursprung ergründen kann? Oder ist es gar ein Fehler, nach einem Ursprung zu suchen?

Trotz aller Logik bleiben viele existentielle Fragen total unbeantwortet, und das ist eben die Kerbe, in die die Religionen schlagen. Sie erweitern das Weltbild um gewisse Axiome (deren Bestätigung mitunter natürlich etwas schwer fällt ), damit man als nachgrübelnder Mensch nicht zu sehr an den Paradoxien scheitert.

Beowulf hat geschrieben:Ich wollte damit kein Paradoxon zeigen, sondern wie man anhand der Filterung der Eingangswerte eine Terminierung sicherstellt.

Deine Aussage war

Beowulf hat geschrieben:Das stimmt wohl. Aber mir ging es eher darum, dass man mit Programmiersprache ein Paradoxon formulieren kann.

, darauf hatte ich mich rückbezogen.

Linear beschränkte Turingmaschinen sind nicht dem Halteproblem unterworfen, akzeptieren dafür aber auch nicht alle Sprachen, die gewöhnliche Turingmaschinen akzeptieren. Dadurch geht letztlich doch die Möglichkeit verloren, für beliebige M und w zu überprüfen, ob M auf w hält.

Beowulf hat geschrieben:Weil man sich einfach nur an gewisse Regeln halten muss (also die Mächtigkeit einschränken), dann ist die Unentscheidbarkeit kein Thema mehr. Deine Frage verwundert mich etwas, schließlich hast du ja das Halteproblem hier eingebracht als Beispiel für mathematische Beweise. Mir ging es darum, dass auch Beweise immer nur innerhalb der gegebenen Axiome ihre Richtigkeit haben.

Ja, ich hatte es eingebracht als eines von drei Beispielen für mathematische Beweise in der Informatik. Was mich verwunderte war dieser Absatz:

Beowulf hat geschrieben:Programmierer, die viel Geld verdienen wollen, werden wohl eher ihren gesunden Menschenverstand einsetzen. Denn es gibt natürlich auch ohne Lösung des HP Möglichkeiten, ein stabiles Programm zu liefern. ...

An keiner Stelle wurde impliziert, dass es ohne Lösung keine stabilen Programme gibt. Bezüglich Beweisen & Axiomen habe ich auch nie etwas anderes behauptet. Ich sah und sehe demnach keinen Grund für derartige Ausführungen, auch wenn mittlerweile immerhin klar ist, worauf du eventuell hinaus wolltest.

Beowulf hat geschrieben:Trotz aller Logik bleiben viele existentielle Fragen total unbeantwortet, und das ist eben die Kerbe, in die die Religionen schlagen. Sie erweitern das Weltbild um gewisse Axiome (deren Bestätigung mitunter natürlich etwas schwer fällt ), damit man als nachgrübelnder Mensch nicht zu sehr an den Paradoxien scheitert.

Interessante Sichtweise. Im Fall der Religion löst das Hinzunehmen von Axiomen Paradoxien allerdings nicht wirklich, sondern nur scheinbar. Jede Frage, die es davor gab, könnte man in unserem Denksystem auch weiterhin stellen ("Was war der Ursprung des Universums?" -> "Was war der Ursprung von Gott?"), nur wird nun für "Gott" postuliert, dass er außerhalb von Zeit und Raum ist (dann aber doch wiederum immer bei uns) und man deshalb diese Fragen nicht mehr stellen muss/soll.
Aber nette Überleitung zum eigentlichen Off-Topic, das muss ich zugeben .

Floyd hat geschrieben:Linear beschränkte Turingmaschinen sind nicht dem Halteproblem unterworfen, akzeptieren dafür aber auch nicht alle Sprachen, die gewöhnliche Turingmaschinen akzeptieren. Dadurch geht letztlich doch die Möglichkeit verloren, für beliebige M und w zu überprüfen, ob M auf w hält.

Ganz genau, meine Rede! Das Paradoxon wurde ja schon durch das Knilch-Programm gezeigt. Dieses Programm legt es natürlich auch ganz besonders darauf an. Vielleicht sollte man dies auch als Beispiel für die Mächtigkeit der Programmiersprachen anführen, weniger für ihre Unzulänglichkeit.

An keiner Stelle wurde impliziert, dass es ohne Lösung keine stabilen Programme gibt. Bezüglich Beweisen & Axiomen habe ich auch nie etwas anderes behauptet. Ich sah und sehe demnach keinen Grund für derartige Ausführungen, auch wenn mittlerweile immerhin klar ist, worauf du eventuell hinaus wolltest.

Nein, derartige Aussagen wollte ich dir natürlich nicht unterstellen. Es geht eher um den Umstand, das man das Halteproblem "ums Verrecken" auf ganz allgemeine Weise lösen wollte, obwohl doch offensichtlich ist, dass die Programmiersprachen dafür zu mächtig sind. Denn folgender Satz aus dem Beweis will mir nicht so richtig aus dem Kopf, weil mir immer noch nicht einleuchtet, warum so viele Prädikate berechnet werden müssen wie die Potenzmenge des Programms Elemente hat:

Wikipedia hat geschrieben:Da es so viele Gödelnummern (Programme) gibt, wie natürliche Zahlen, muss es auch so viele Prädikate geben, wie die Potenzmenge der natürlichen Zahlen Elemente hat, wobei jedes Prädikat irgendeine Eigenschaft der mit ihnen getesteten Programme in eine Aussage fasst. Die Zahl der Prädikate über einer Menge ist aber gerade so groß wie die Zahl der Teilmengen dieser Menge.

Irgendwie kann ich Programme und Potenzmengen nicht in eine Beziehung bringen, ich denke dafür wohl noch etwas zu konkret. Hast du da vielleicht ein Beispiel für?

Nun, meine Bemerkung war vielleicht auch etwas schnippisch gegenüber gewisse Programmierer gemeint, die z.B. verschiedene Programmversionen zusammen"mergen" müssen, weil sie nicht in der Lage sind ein Problem gescheit zu zerlegen. Ich musste öfters mit Leuten zusammenarbeiten, die einfach in den Tag hineinprogrammiert haben und anscheinend froh waren, den ganzen Tag möglichst keinen Kontakt mit ihren Kollegen haben zu müssen. Man hatte ja schließlich das Programm, dass am Ende alles zusammengewurstet hat. Wie du dir vorstellen kannst, haben sich die Fehler mit der Zeit gehäuft, bis sie irgendwann unkontrollierbar wurden...
Ähnlich "naiv" sehe ich da den Wunsch nach einem Programm welches auf das Halteproblem untersucht. Schließlich ist z.B. die Message-Loop von Windows auch nichts anderes als eine Endlosschleife... solange man den Rechner nicht runterfährt.

Im Fall der Religion löst das Hinzunehmen von Axiomen Paradoxien allerdings nicht wirklich, sondern nur scheinbar.

Richtig, die komplexe Entstehungsgeschichte der Erde wird da auf Gott verlagert. Wo Gott selber herkommt... nun, vielleicht hat das damals einfach keinen interessiert?

Beowulf hat geschrieben:Irgendwie kann ich Programme und Potenzmengen nicht in eine Beziehung bringen, ich denke dafür wohl noch etwas zu konkret. Hast du da vielleicht ein Beispiel für?

Ein Programm, das das Halteproblem loest, ist eine Abbildung von der Menge aller Programme (ich nenne sie mal N) in die Menge {wahr, falsch}. So eine Funktion laesst sich auch als Teilmenge von N begreifen, naemlich als genau diejenigen Programme, die auf wahr abgebildet werden. Folglich gibt es so viele derartige Funktionen von N nach {wahr, falsch}, wie es Teilmengen von N gibt. Und das sind nach dem Diagonalargument echt mehr als |N|.

In dem Zusammenhang noch zu "Diese surjektive Abbildung gibt es 'praktischerweise' ja auch nicht": Die Abbildung f(x) := {x} gibt es durchaus. Sie hat nur eben nicht die Eigenschaft, surjektiv zu sein und spielt deswegen in dem Beweis keine Rolle.

Ich denke uebrigens, dass du diese Probleme zu konkret angehst. Das Halteproblem ist eine Frage der theoretischen Informatik, und da ist man ganz weit weg von konkreten Dingen wie Programmiersprachen, Sicherheitsabfragen, Programmcode, Programme "mergen" etc., der einzige Rechner und damit auch die einzige "Programmiersprache", die da erst mal von Interesse sind, ist eine Turingmaschine.

Das Jan

Danke für deine Antwort Jan!

Folglich gibt es so viele derartige Funktionen von N nach {wahr, falsch}, wie es Teilmengen von N gibt.

Siehst du, genau diesen Zusammenhang verstehe ich noch nicht so richtig. Warum auf einmal die Potenzmenge? Warum nicht eine Funktion, die alle N irgendwie auf {0, 1} abbildet? Würde das nicht ausreichen? Warum müssen alle Teilmengen erfassbar sein?

Ein Programm (eigentlich: eine Turingmaschine), die das Halteproblem entscheiden wuerde, waere eine Funktion H : N --> {0, 1}. Ein Programm, das als Input ein Element von N bekommt und immer 0 zurueckgibt, waere eine andere Funktion H' : N --> {0, 1}, gegeben durch H(n) := 0 fuer jedes n in N. Es gibt, wie oben erklaert, |P(N)| viele solcher Funktionen: | { g | g : N --> {0,1} } | = |P(N)|. Es existieren aber nur |N| viele verschiedene Programme, und das sind wegen |N| < |P(N)| weniger, als es Funktionen gibt. Es muss also Funktionen geben, die du nicht mit einem Programm berechnen kannst. Das Programm, das das Halteproblem entscheidet, ist ein Beispiel dafuer.

Das Jan

Verstehe. Dann ist der Beweis im Prinzip nicht völlständig, es gehören also noch andere Dinge hinzu. Denn man muss ja wissen, ob das HP zu den Funktionen gehört, die nicht abgebildet werden können. Denn trotz allem kann es ja immer noch unendlich viele Programme geben.

Trotzdem bereitet mir der Beweis noch Kopfzerbrechen, denn wie ich schon sagte, führt diese Beweisführung auch bei Abbildungen, die erwiesenermaßen surjektiv sind, zu diesem Paradoxon:

DasJan hat geschrieben:In dem Zusammenhang noch zu "Diese surjektive Abbildung gibt es 'praktischerweise' ja auch nicht": Die Abbildung f(x) := {x} gibt es durchaus. Sie hat nur eben nicht die Eigenschaft, surjektiv zu sein und spielt deswegen in dem Beweis keine Rolle.

Doch, sie ist surjektiv, oder etwa nicht? *grübel* Surjektivität heißt, dass es zu jedem y mindestens ein x geben muss, für das gilt dass f(x) = y; Genauer gesagt diese Funktion ist bijektiv, wodurch sie sowohl injektiv aus auch surjektiv ist.

Beowulf hat geschrieben:Doch, sie ist surjektiv, oder etwa nicht? *grübel* Surjektivität heißt, dass es zu jedem y mindestens ein x geben muss, für das gilt dass f(x) = y; Genauer gesagt diese Funktion ist bijektiv, wodurch sie sowohl injektiv aus auch surjektiv ist.

Nein, die Potenzmenge von {x} ist gegeben durch {Ø, {x}}

Genau elevar, hier spielst du eine spezielle Eigenschaft der Potenzmengen aus. Ich meinte jedoch die einfache Abbildung x -> {x}, also ohne Potenzmenge oder so. Da ich aber bei dem Beweis, der z.B. auch in Wikipedia steht, nicht erkennen kann, dass gezielt auf Potenzmengen eingegangen wird, habe ich das Gefühl, auch x -> {x} als potentielle Abbildung einsetzen zu können (um die Surjektivität zu überprüfen)... und für die dann der Beweis auch nicht stimmt.

Kann zwar sein dass der Beweis trotzdem gültig ist, aber ich habe das Gefühl, dass alles derart kryptisch und unvollständig dort steht, dass ich ihn nicht richtig verstehen kann.

Aber egal, bei Wikipedia ist man sich eh nicht immer 100%ig sicher. Da wird dort z.B. ziemlich allgemein und undefiniert von Quantenradieren geredet, diese als Tatsache angenommen... aber da liest man wieder auf anderen Seiten, dass die üblichen Quantenradierer sich normal durch die Wellenform des Lichts erklären lassen.

Schön das ihr mit der Potenzmenge wenigstens halbwegs wieder zurück zum ursprüglichen Thema kommt. Wär sonst etwas abgedriftet.

Ich hab die letzten Beiträge jetzt nur überfolgen...aber das erste, was mir in den Sinn kam war eine Szene mit Bart Simpson...

"Huhu! Ich bin ein Student. Ich bin im 24. Semester und hab letztes Jahr 300 Dollar verdient."

Erst wenn Ihr bei Schnittmengen seid, wärt Ihr wieder beim Thema.

Beowulf hat geschrieben:Dann ist der Beweis im Prinzip nicht völlständig, es gehören also noch andere Dinge hinzu.

In dem verlinkten Wikipedia-Artikel befindet sich auch kein Beweis für die Unentscheidbarkeit des Halteproblems. Was da als Beweis hervorgehoben ist, ist lediglich der Beweis für |X| < |P(X)|.

Beowulf hat geschrieben:Doch, sie ist surjektiv, oder etwa nicht? *grübel*

Nein. Nenne mir ein Element y von {x}, für das gilt f(y) = Ø.

Das Jan

Nein. Nenne mir ein Element y von {x}, für das gilt f(y) = Ø.

Nicht böse sein, aber wen interessiert die Leere Menge? Es ging doch darum, ob man Potenzmengen abzählen kann. Und wenn der Beweis schon für viel "unmächtigere" Abbildungen nicht funktioniert, klappt dies natürlich mit den Potenzmengen nicht.
Verstehst du, ich sehe da einfach keinen direkten Zusammenhang zu den Potenzmengen.
Da steht nur: f: A -> P(A) ist eine surjektive Abbildung. Wir definieren ein M := {x Element von A | x kein Element von f(x)} Element von P(A)
Und genau dies verstehe ich nicht: Warum darf x kein Element von f(x) sein?

DasJan hat geschrieben:In dem verlinkten Wikipedia-Artikel befindet sich auch kein Beweis für die Unentscheidbarkeit des Halteproblems.

Wäre ja auch zu logisch gewesen. Wie würde denn ein solcher Beweis aussehen?

Beowulf hat geschrieben:Nicht böse sein, aber wen interessiert die Leere Menge?

Die Definition von "surjektiv" zum Beispiel. "Surjektiv" bedeutet, dass für JEDES Element y der Bildmenge gilt, dass auch ein x in der Grundmenge existiert mit f(x) = y. Und die leere Menge ist, auch wenn es dich nicht interessiert, nun mal ein Element der Potenzmenge {Ø, {x}}. Also ist f per Definition nur dann surjektiv, wenn es auch ein Element von {x} gäbe, das auf die leere Menge abgebildet wird. So ist "surjektiv" definiert.

Beowulf hat geschrieben:Und wenn der Beweis schon für viel "unmächtigere" Abbildungen nicht funktioniert, klappt dies natürlich mit den Potenzmengen nicht.

Das ist ja auch ein Widerspruchsbeweis. Du nimmst an, dass X gilt, kommst dann zu einem Widerspruch, und weißt daher, dass X falsch sein muss. Der Beweis funktioniert für alle Mengen, auch für unendliche, das ist ja das Gute an ihm.

Das ist jetzt ernsthaft nicht böse gemeint, aber: Du versuchst komplexe Zusammenhänge aus der theoretischen Informatik zu verstehen und scheinst noch nicht mal mit Surjektivität und Widerspruchsbeweisen zurecht zu kommen. Das ist ja kein Beinbruch, aber vielleicht ist es einfach besser, wenn du mit Grundlagen anfängst. Beutelspacher schreibt eigentlich ganz nett (auch wenn ich konkret dieses Buch nicht gelesen habe).

Beowulf hat geschrieben:Wäre ja auch zu logisch gewesen. Wie würde denn ein solcher Beweis aussehen?

Auf der einen Seite gebe ich dir recht, dass der Artikel nicht besonders gut ist. Auf der anderen Seite ist Wikipedia auch kein Lehrbuch. Auf die Schnelle habe ich jetzt ein Skript von Uni Erlangen-Nürnberg und eins von der Uni Saarland gefunden, gerade letzteres macht auf den ersten Blick einen ziemlich guten Eindruck. Wenn es unbedingt die Wikipedia sein soll: Der englische Artikel scheint immerhin besser zu sein als der deutsche, dort gibt es aber auch nur einen Überblick über den Beweis.

Das Jan