Das Halteproblem | Theoretische Informatik

[@noah1239]

Das Beispiel welches du angebracht hast mit dem Friseur macht das Video so unglaublich viel verständlicher!! Wenn ich morgen im Colloquium darüber was gefragt werde werde ich genau das Beispiel nennen

[@Florian.Dalwigk]

Perfekt, viel Erfolg!

[@levynx1770]

Wie schwer es uns fällt schon sowas zu verstehen....Überlegt mal wie Turing auf sowas überhaupt gekommen ist. Trotzdem ein sehr gutes Video.

[@95Coaster]

Bin gerade komplett zufällig über die Suche nach "NFA DFA" auf deinen Kanal und diese Playlist gestoßen und merke dann erst an deiner Aussage im Video "Stand 30.04.2020", dass das Video ja noch ofenwarm ist.. witzig :D Und sehr schön erklärt!

[@Florian.Dalwigk]

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

[@julianon161]

Sehr interessant!! Gerne mehr solcher Videos

[@Florian.Dalwigk]

Ja, wird kommen :)

[@ZER-kb6mb]

echt gut erklärt, das wird mir morgen im Abi sicher helfen!

[@Florian.Dalwigk]

Danke und viel Erfolg :)

[@Leetsch]

Ein jahr später und das selbe feeling XD

[@Florian.Dalwigk]

Viel Erfolg!

[@Leetsch]

@@Florian.Dalwigk danke! :)

[@neogruber3031]

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

[@mrdestruktiv]

Mein Kopf raucht, aber dennoch interessant :D

[@Florian.Dalwigk]

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

[@cassinoname4585]

Dann müsste es also zwei Barbiere geben?

[@Florian.Dalwigk]

Das ist nicht der Sinn dieses Gedankenexperiment s

[@TimTaste]

Hey, habe mir nun mehrere Videos zum Halteproblem angesehen. Erstmal cooles Video, ist hier mit am anschaulichsten erklärt. Ich hätte allerdings noch eine (wahrscheinlich dumme) Frage. Wieso baut man am Ende, wenn der eigentliche Output 1 wäre, also das Programm terminiert, eine Endlosschleife ein und gibt nicht einfach das eigentliche Ergebnis aus, also dass das Programm eben terminiert?

[@klawenn01]

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.

[@Bunny99s]

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.

[@TimTaste]

@@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 :)

[@derrick6718]

Danke toll erklährt!

[@Florian.Dalwigk]

Gerne

[@belix8801]

Ist die Henne-Ei Überlegung nicht auch ein weiteres Beispiel für so etwas? Liebe Grüße!

[@Florian.Dalwigk]

Nein, das ist etwas anderes.

[@xyoxus]

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)

[@seeking9145]

Abo! Direkt abonniert! Richtig gut erklärt und mich bestätigt, dass ich es doch richtig verstanden habe. Stimme ist zudem außerordentlich beruhigend! Bin jetzt schon ein großer Fan!

[@Florian.Dalwigk]

Ui, vielen Dank :)

[@Florian.Dalwigk]

Willkommen an Bord ;)

[@tangerinegames4515]

Beste Empfehlung zu beweistechniken ?

[@Florian.Dalwigk]

Was meinst du genau?

[@tangerinegames4515]

@@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.

[@BannerTVcooler]

Eine Frage, wie lerne ich programieren Bücher oder Kurse (bin 12)

[@Florian.Dalwigk]

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.

[@BannerTVcooler]

@@Florian.Dalwigk danke

[@linnard5489]

wie soll ich denn auf 0 kommen. bei der 1. Lösungsmaschine. es gibt keinen wert der durch 2 null ergibt

[@Florian.Dalwigk]

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

[@then00bh3ro7]

Super Video, ich mag deine Erklärweise. Könntest du in einem Video bitte den "Satz von Rice" erklären? Das würde bestimmt vielen helfen, da es zu dem Thema meiner Meinung nach nicht viele gute Videos gibt.

[@Florian.Dalwigk]

Vielen Dank :) Kann ich gerne mal machen. Das folgende Video ist aber schon recht gut: kzbin.info/www/bejne/l2nXnmSdh9KAZpo

[@tangerinegames4515]

Reduktion auch bitte vielleicht konkreten Beweis zu einer Aufgabe ?

[@helloworld14895]

Vielleicht das erste Video ohne Dislikes dass ich auf KZbin endeckt habe:D

[@Florian.Dalwigk]

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

[@DannyGaendon]

:(

[@stn6428]

Super video und auch so gut erklärt, dass ich denke den Grundgedanken verstanden zu haben ;) Auch cool, dass du weitere videos zu dem thema verlinkt hast

[@Florian.Dalwigk]

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

[@johnnysteed2878]

jetzt mal angenommen, es gibt eine überlagerung von "Halt" und "nicht Halt", also "0" und "1"... ;P ne klasse video, wobei ja "kein gutes Video" eigentlich auch eine art paradoxon wäre oder? -> es bis zum ende zu schauen, obwohl es schlecht ist wäre ja nicht logisch, da wir uns auf einer Entertainment Platform befinden. Einen Komment zu schreiben, ohne das ganze Video zu sehen aber auch... ... ... ... ...

[@Florian.Dalwigk]

😁

[@marcello4258]

na toll wollte gerade bei amazon schauen wo man die maschine her kriegt :D

[@Florian.Dalwigk]

😄

[@BloxxingDinosaurus]

Bedeutet "entscheidbar" einfach deterministisch?

[@Florian.Dalwigk]

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

[@ody7850]

einfach mal das halteproblem rasiert xD

[@atha6632]

ich hoffe die menschen die sich das ausgedacht haben haben die gtrößten schmenrzen

[@Florian.Dalwigk]

Was, warum? 😂

[@atha6632]

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

[@schulem1409]

🎉🎉🎉

[@schulem1409]

👍

[@pentestical]

0:22 ich habe eine absolute Insekten-Phobie, bitte machj das nicht !! Haha

[@Florian.Dalwigk]

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

[@pentestical]

Ich lerne mehr von deinem 7 min Video als von einer 2 stündigen Vorlesung..

[@Florian.Dalwigk]

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

[@ehong3398]

42😏

[@Florian.Dalwigk]

?

[@ehong3398]

@@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...

[@Florian.Dalwigk]

Ja, wurde es auch ;)

[@Helldrungen]

Kurt Gödel lässt grüßen.

[@Florian.Dalwigk]

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

[@moritz7683]

Mit HTML kann man aber ganz interessante Dinge machen: brunodantas.github.io/html-fda/

[@Florian.Dalwigk]

Ja, das kann man ;) Es ist aber trotzdem keine Programmiersprache :D kzbin.info/www/bejne/gn_cdqWsq9SNr5o

[@Helldrungen]

@@Florian.Dalwigk TeX aber :)

[@mivoe99]

Ich hätte es besser gefunden wenn du den Zuschauer ab und zu etwas mehr Zeit gegeben hättest das Erzählte zu verstehen. Das muss nicht unbedingt lange sein. Dabei reichen schon ein oder zwei Sekunden in denen man der Visualisierung und dem Gedankengang folgen kann. Ich habe mich mehrmals dabei erwischt das Video für wenige Sekunden zu pausieren um genau das zu tun. Das ist per se jetzt nicht weiter schlimm aber ich bezweifle, dass ich der einzige war dem es so ergangen ist :)

[@Florian.Dalwigk]

Video pausieren? 😃

[@bluekernel2448]

Was isn das für ein Matheproblem? X=9999999999421337 If X not 9999999999421337: print(geschafft) Oh mein Gott!! Jetz haben wir ein Problem!! EDIT: oder ist gemeint, dass man noch nicht weiß obs jemals 9999999999421337 wird gemeint, sieht aber ganz eindeutig aus

[@Florian.Dalwigk]

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.

[@softknk1422]

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