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
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!
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!
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
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.
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
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... ... ... ... ...
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?
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 :)
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 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.
@@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...
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 :)
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
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.