Das Halteproblem | Theoretische Informatik 

Perfekt, viel Erfolg!

Ja, das Video ist noch recht frisch :) Danke und freut mich, dass du hierher gefunden hast!

Ja, wird kommen :)

Natürlich! Super, dass es dir weitergeholfen hat.

Gerne

Das freut mich, danke!

Danke und viel Erfolg :)

Ein jahr später und das selbe feeling XD

Viel Erfolg!

@@Florian.Dalwigk danke! :)

Same, meine Prüfung geht in 4 stunden los...

Ui, vielen Dank :)

Willkommen an Bord ;)

Ja, in das Halteproblem muss man sich erstmal hineindenken ;)

Vielen Dank :) Kann ich gerne mal machen. Das folgende Video ist aber schon recht gut: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-a8tm1gRmM08.html

Reduktion auch bitte vielleicht konkreten Beweis zu einer Aufgabe ?

Hab über die gleiche Frage gegrübelt. Ich denke die Antwort könnte wie folgt sein: Die Halteproblem-Lösungsmaschine soll ja eigentlich korrekt erkennen können, ob ein Programm hält oder nicht - auch wenn man so eine „fehlerhafte Endlosschleife“ einbaut, wo eigentlich True sein sollte. Und nun wird aber ausgespuckt, dass es nicht hält, wenn es gerade anhält, und da ist der Widerspruch.

Du hast einen wichtigen punkt übersehen. Nennen wir mal unsere "Halteproblemlösungsmaschine" einfach nur H. Das ist ja einfach eine Funktion die 2 parameter bekommt, einmal das Programm das analysiert werden soll und die parameter / eingaben zu diesem Programm. Stell dir einfach vor das wäre einfach eine funktion die du in deinem code aufrufen kannst, um entweder true oder false zurück zu bekommen ob das programm mit dieser eingabe hält oder nicht. function H(p, e) { //---magic--- returns true when program "p" stops when provided with "e" } Wir schreiben jetzt eine neue funktion die einfach das hier macht: function M(e) { if (H(e, e)){ while (true) { } // deliberately create a bug here and get stuck } print("fertig") } Wenn du jetzt H aufrufst um eine klare antwort zu bekommen, ob M denn mit einer gewissen eingabe hält oder nicht machen wir einfach // Hauptprogramm if (H(M, M)){ pring("M hält") } else { pring("M hält nicht") } Das wäre ja die Anwendung wie wir unsere tolle funktion H benutzen wollen. Wir wollen eine klare Aussage haben und H soll das ja liefern, egal welches programm es bekommt. M benutzt ebenfalls die funktion H intern wie oben beschrieben. D.h. jetzt H soll M analysieren und uns eine Antwort geben. Angenommen H sagt uns "M hält". Was bedeutet das für den logischen Ablauf innerhalb der funktion M? Da die funktion hält muss H innerhalb von M aber false zurückgegeben haben, ansonsten würde M ja in der Endlosschleife feststecken. Da das "H" innerhalb M aber exakt die gleichen argumente übergeben bekommt, wie unser H im Hauptprogramm, muss H ja das gleiche zurückgeben. Also in diesem Fall müsste H(e,e) auch "true" zurück geben, was aber dazu führen würde, dass M doch nicht hält obwohl wir ja gesagt haben H kann uns das klar sagen. Genauso ist es anders herum. Wenn uns H(M, M) sagt "M hält nicht", muss H ja false zurück geben. Innerhalb von M wird ja wieder H mit den gleichen argumenten aufgerufen, also müsste und H(e, e) ebenfalls sagen, dass das programm nicht hält. Allerdings wenn H(e, e) false ergibt, bedeutet dass, dass M ganz normal endet und hält. also wieder genau das Gegenteil von dem, was uns H ja angeblich sagen kann. Obwohl wir nicht wissen wie H intern arbeitet, können wir damit zeigen, dass H nicht möglich ist. Denn H sollte ja selbst ein endlicher algorithmus sein (wie der auch immer aussieht). Deswegen muss H auch in der Lage sein sich selbst zu überprüfen und eine klare Aussage geben.

@@Bunny99s Nach dieser ausführlichen und anschaulichen Erklärung habe ich es nun verstanden. An sich völlig logisch wie alles in der Informatik ^^ Das wird mir bei meiner nächsten Klausur helfen. Vielen lieben Dank für die Zeit, die du dir genommen hast :)

Sehr schön :) Hoffentlich bleibt das so :D

:(

😁

Nein, das ist etwas anderes.

Nö, Eier gibt's ja schon länger. Es legen ja nicht nur Hühner Eier. Irgendwann hat sich eben einfach mal ein Tier das sowieso schon Eier legt zu nem Huhn entwickelt. (Dinosaurier-X wurde zu Huhn)

Ich würde dir tatsächlich zu einem guten Buch raten! Kurse vermitteln oft nur Teilaspekte des Programmierens und man erhält nicht den Gesamtzusammenhang bzw. lernt nur einzelne kleine Codesnippets nachzuprogrammieren. Ich würde dir als Programmiersprache Python für den Anfang empfehlen.

@@Florian.Dalwigk danke

😄

Das ist nicht der Sinn dieses Gedankenexperiment s

Was meinst du genau?

@@Florian.Dalwigk Wir müssen für die Prüfungen in theoretischen Informatik Modulen wovon es echt viele gibt Beweistechniken können. Wie zum Beispiel Berechenbarkeit un Komplexität als Modul. Reduktionsbeweise würden sehr hilfreich sein, aber auch generell wie man her angehen könnte generell daran, wie man Beweise macht. Ich weiß, es braucht ein gewisses Grad an Kreativität, aber eine Hilfe step by step wie man an bestimmte Aufgaben her angeht. Ich tue mich da echt sehr schwer mit.

??? Das codiert doch nur die Werte *true* und *false*.

Hoppla ... dann werde ich so etwas zukünftig vermeiden :)

?

@@Florian.Dalwigk wegen des Buches per Anhalter durch die Galaxis. Der Supercomputer spuckt aus einer Ewigkeit die Antwort auf das Leben und alles oder keine Ahnung was das war aus und das war 42. Ich dachte 42 wurde deshalb genommen...

Ja, wurde es auch ;)

Super, das freut mich sehr! :) Meine Videos ersetzen aber keine Vorlesung ;)

Nicht unbedingt, siehe www.ruhr-uni-bochum.de/lmi/lehre/materialien/ti/vorlesung/kap2-2f.pdf

Video pausieren? 😃

Ja, das kann man ;) Es ist aber trotzdem keine Programmiersprache :D ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-LNyErvvoZy8.html

@@Florian.Dalwigk TeX aber :)

Was, warum? 😂

@@Florian.Dalwigk Ich mein natürlich haben ein schönes Leben im Jenseits :D

Danke, lieber Kurt :) Sorry, ich habe das Gefühl, dieser Gruß ist irgendwie unvollständig :D

In meinem Beispiel-Programm steht eine while-Schleife. Es geht darum, ob das Programm irgendwann terminiert und ob man einen Algorithmus entwerfen kann, der in der Lage ist zu entscheiden, ob das Programm terminiert.

@Linus Man merkt, dass du dich im Bereich Informatik noch nicht gut auskennst ... schau dir am Besten mal die Grundlagen-Videos an.