Das war das erste Video von dir, das ich nicht verstanden habe. Aber ich gehe davon aus, dass es an mir liegt. Ich gucke es mir Morgen nochmal an wenn ich nicht schon 5 Stunden gelernt habe. Trotzdem vielen lieben Dank für all die Mühe die du dir gibst.
Ich stutzte erst bei "Wortproblem ist unentscheidbar", aber hier geht es ja um Chomsky-Typ-0-Sprachen (turing-erkennbare, rekursiv aufzählbare Sprachen). Vielen Dank für Deine Serien.
Lieber Leif, warum würde man eine TM bauen, die beim Verwerfen des Wortes hält und beim Akzeptieren in eine Endlosschleife geht? Wäre es nicht sinnvoll, beim Verwerfen des Wortes zu halten und beim Akzeptieren in einen verwerfenden Endzustand zu gehen?
Folgende Überlegung. Ich habe einen reguären Ausdruck und baue eine Turingmaschine M dazu. Dann kann ich doch zu jeder Eingabe eines Wortes eindeutig entscheiden ob das Wort von M akzeptiert wird?
Turing-Maschinen können aber auch bei Worten, die nicht regulären Sprachen angehören, in akzeptierende Zustände, z.B. {a^n b^n | n>=0} oder {a^n b^n c^n | n>= 0}. Und viele weitere abzählbare Sprachen die nicht regulär, CFL, CSL sind. Klar gibt es Sprachen die erkennbar sind und von denen man womöglich schon ohne große Überlegung sagen kann ob die TM auf ihnen hält oder nicht. Hier geht es aber um den generischen Fall: Eine TM (jede erdenkliche TM M, über die wir nicht viel wissen), ein Eingabewort (jeder nur erdenkliche String, auch so ein Quatch wie code(M)), und die Frage: NICHT ob sie jemals hält, SONDERN die Frage ob man ein Verfahren bauen kann, welches automatisch zeigen kann ob die Maschine auf diesem Wort hält. Das wirklich schlimme an dem Beweis ist: Der Grund weswegen man dieses Verfahren nicht bauen kann. Er ist sehr undurchsichtig und nicht auf ersten Blick logisch nachvollziehbar. Hat aber mit Diagonalisierung zu tun. Kennst du die Überabzählbarkeit von reellen Zahlen? Wenn du unendlich lange Dezimalstrings erlaubst und glaubst "alle aufgezählt zu haben" wirst du immer noch eine neue Dezimalzahl konstruieren können aus allen bisherigen. Hier ist es ähnlich: Sagen wir du zählst alle Programme auf die du kennst, mit allen möglichen Eingaben für sie. Die Programme sind super logisch und konsistent und du hast sie so modifiziert dass sie mit jeder Eingabe umgehen können. Selbst wenn du das Akzeptierverhalten all dieser abzählbaren Programme, auf allen möglichen Eingaben tabellarisch darstellst, wirst du aufgrund der Natur der Frage selbst, aus der Tabelle heraus ein neues Programm konstruieren können, welches sich im Akzeptanzverhalten von allen anderen Programmen unterscheidet. Schreiben wir dieses neue Akzeptierverhalten mal unter unsere Tabelle und nennen das "Erweiterte Tabelle". Jetzt liegt hier aber die Katze auf dem heißen Dach: Es gibt nur abzählbar viele Programme/Algorithmen, nicht wie bei reellen Zahlen. Das heißt was wir aus unserer Tabelle bekommen haben ist gar kein Algorithmus sondern irgendeine String-Funktion, die wie in ihrer Trotzphase alles anders machen muss als andere String-Funktionen die Algorithmen abbildeten. Ein Programm das Wort-/Halteproblem entscheidet, muss allerdings in der alten Tabelle sein, in der du schon alle anderen Programme aufgezählt hast. Das Programm unten aus der "Erweiterten Tabelle" ist jedoch auch, obwohl es eine sinnlose String-Funktion ist, theoretisch von Wort-/Halte-Entscheider entscheidbar. Genauso wie Wort-/Halte-Entscheider, mit sich selbst, codiert als code(Wortentscheider) für Wortentscheider und code(Halteentscheider) für Halteentscheider in endlicher Zeit eine Ja/Nein-Antwort liefert. Der Entscheider ist theoretisch als TM/Programm/Algorithmus definierbar. Er ist in unserer alten -Akzeptanzverhalten-Tabelle an abzählbaren Algorithmen, was ist jetzt also das große Problem? Die Annahme dass der Entscheider exisitert würde bedeuten: jedes Akzeptierverhalten aus der Tabelle sei entscheidbar. Es ist allerdings immer möglich ein neues Akzeptierverhalten zu konstruieren, welches theoretisch auch entscheidbar sein müsste, welches allerdings nicht existiert. Das weiß der Entscheider aber nicht. Er findet sinnlose Antworten auf Fragen, unter anderem, die er über sich selbst stellt. TLDR: 95% aller echten, nützlichen Programme sind auf gültigen Eingabewörtern wsl entscheidbar. Ich mein schau dir mal irgendein Debug-Tool an. Das Halte-/Wortproblem hier ist einfach nur eine formelle Überlegung die dich auch nicht näher an das Licht der Wahrheit bringen wird, sonder nur Aua im alten Kürbis macht.
Das versteh ich einfach nicht. Halterproblem: Wir nehmen etwas falsches an, damit funktioniert es und aufgrund dessen können wir sagen, dass es nicht funktioniert? Warum ist nicht die Aussage, dass es Falsch ist nicht falsch? Wäre es nicht viel einleuchtender zu sagen, das Halteproblem fragt, ob die DTM irgendwann anhält. Durch die endlosschleife können wir aber nie sagen, ob es nun wirklich anhält oder noch einen Schritt geht und dadurch nicht entscheidbar, da wir nur "ja" entscheiden können aber nicht "nein"
Das ist genau der Knackpunkt. Schau dir zb mal das Collatz-Problem an: Für manche Zahlen (1, 2, 4, 8, 16, ...) findet man schnell Antworten für manch andere braucht man lange, bisher hat man noch keine Zahl gefunden für die es nicht hält. Aber man will ja wissen: Gibt es diese Zahl? Kann man aus der Vorschrift des Algorithmus allein, herausfinden ob es diese Zahl gibt? Jedenfalls nicht mit einfachen Algorithmus-Mitteln. Klar kannst du einfach ewig warten und schauen ob ein rechnendes Programm hält, aber du lebst nun mal nicht ewig. Kannst du auf andere Weise durch andere Beobachtungen herausfinden, ob das Programm halten wird? Bzw ob irgendein wohldefinierter Algorithmus auf irgendeiner validen Eingabe halten wird? Der Beweis sagt nein: Für dieses Problem ist kein Algorithmus konstruierbar, da die Annahme der Existenz dieses Algorithmus an einer ganz anderen Stelle, ganz unabhängig vom Akzeptanz/Halteproblem für Kopfschmerzen sorgt. Fair enough: Du könntest die Frage stellen: Jaa aber wieso macht man so ein Quatschprogramm, bei dem man akzeptiert, wenn die subroutine ablehnt und ablehnt wenn die Subroutine akzeptiert? - Dreh es ruhig um, du hast nun einen Wrapper um deine Subroutine gemacht, der genau das gleiche wie sie ausgibt, von der du nicht mal weißt ob sie korrekt ist. Jaa aber wieso geben wir unserem Entscheider sich selbst kodiert als Eingabe? Wie soll ein Mikrophon sich selbst aufnehmen? Das erzeugt eine Rückkopplung! Wie soll eine Kamera sich selbst filmen? Wie kann ein Auge sich selber sehen? Würde es die Frage erleichtern dem Halte-Entscheider nicht zu erlauben sich selbst zu betrachten und nur sinnvolle Fragen zu stellen? Das blöde ist: Es ist nun mal ein Algorithmus, der die Macht hat Algorithmen auf Herz und Nieren zu testen und unter verschiedenen Bedingungen performen zu sehen. Algorithmen sind nach strengen Regeln konstruierbar und es gibt nur abzählbar viele von ihnen. Entweder er mach seinen Job nicht. Weil er zB keine gewinnbringende semantische oder syntaktische Analyse vollführen kann (Satz von Rice, Bedingungen für Kontrollfluss können sehr komplex sein, oder schlichtweg Vorzeichenfehler haben, es sind allerdings immer noch, wenn auch sinnlose, Algorithmen) oder er schafft es nicht zu entscheiden ob er halten wird, bspw. weil er immer wieder aufs neue sich selbst simuliert, und dann in der neuen Rekusrsionsstufe wieder sich selbst simuliert etc. etc. dann hält er nie. Hält. Nie. Weißt wie ich meine? Versteh mich nicht falsch, Akzeptanz und Halteproblem sind **semi-entscheidbar** aber nun mal nicht entscheidbar.
![[UA] NAVI vs MOUZ | BO5 | IEM Rio 2024](http://i.ytimg.com/vi/CMBYk0cbGoA/mqdefault.jpg)
Retter. Bester Mann wirklich, die ganzen Videos sind größte Hilfe für Theo, Danke 🙏!
Super. Main Gehirn brennt. Er ist in einer Endlossschleife gekommen...
Das war das erste Video von dir, das ich nicht verstanden habe. Aber ich gehe davon aus, dass es an mir liegt.
Ich gucke es mir Morgen nochmal an wenn ich nicht schon 5 Stunden gelernt habe.
Trotzdem vielen lieben Dank für all die Mühe die du dir gibst.
Ich stutzte erst bei "Wortproblem ist unentscheidbar", aber hier geht es ja um Chomsky-Typ-0-Sprachen (turing-erkennbare, rekursiv aufzählbare Sprachen).
Vielen Dank für Deine Serien.
Genau, das Wortproblem ist für viele andere Modelle (DEA, NEA, Kellerautomat, LBA) entscheidbar, nicht aber für Turingmaschinen.
Lieber Leif,
warum würde man eine TM bauen, die beim Verwerfen des Wortes hält und beim Akzeptieren in eine Endlosschleife geht? Wäre es nicht sinnvoll, beim Verwerfen des Wortes zu halten und beim Akzeptieren in einen verwerfenden Endzustand zu gehen?
Folgende Überlegung. Ich habe einen reguären Ausdruck und baue eine Turingmaschine M dazu. Dann kann ich doch zu jeder Eingabe eines Wortes eindeutig entscheiden ob das Wort von M akzeptiert wird?
Turing-Maschinen können aber auch bei Worten, die nicht regulären Sprachen angehören, in akzeptierende Zustände, z.B. {a^n b^n | n>=0} oder {a^n b^n c^n | n>= 0}. Und viele weitere abzählbare Sprachen die nicht regulär, CFL, CSL sind.
Klar gibt es Sprachen die erkennbar sind und von denen man womöglich schon ohne große Überlegung sagen kann ob die TM auf ihnen hält oder nicht.
Hier geht es aber um den generischen Fall:
Eine TM (jede erdenkliche TM M, über die wir nicht viel wissen), ein Eingabewort (jeder nur erdenkliche String, auch so ein Quatch wie code(M)),
und die Frage:
NICHT ob sie jemals hält, SONDERN die Frage ob man ein Verfahren bauen kann, welches automatisch zeigen kann ob die Maschine auf diesem Wort hält.
Das wirklich schlimme an dem Beweis ist: Der Grund weswegen man dieses Verfahren nicht bauen kann. Er ist sehr undurchsichtig und nicht auf ersten Blick logisch nachvollziehbar. Hat aber mit Diagonalisierung zu tun.
Kennst du die Überabzählbarkeit von reellen Zahlen? Wenn du unendlich lange Dezimalstrings erlaubst und glaubst "alle aufgezählt zu haben" wirst du immer noch eine neue Dezimalzahl konstruieren können aus allen bisherigen. Hier ist es ähnlich: Sagen wir du zählst alle Programme auf die du kennst, mit allen möglichen Eingaben für sie. Die Programme sind super logisch und konsistent und du hast sie so modifiziert dass sie mit jeder Eingabe umgehen können. Selbst wenn du das Akzeptierverhalten all dieser abzählbaren Programme, auf allen möglichen Eingaben tabellarisch darstellst, wirst du aufgrund der Natur der Frage selbst, aus der Tabelle heraus ein neues Programm konstruieren können, welches sich im Akzeptanzverhalten von allen anderen Programmen unterscheidet. Schreiben wir dieses neue Akzeptierverhalten mal unter unsere Tabelle und nennen das "Erweiterte Tabelle".
Jetzt liegt hier aber die Katze auf dem heißen Dach:
Es gibt nur abzählbar viele Programme/Algorithmen, nicht wie bei reellen Zahlen. Das heißt was wir aus unserer Tabelle bekommen haben ist gar kein Algorithmus sondern irgendeine String-Funktion, die wie in ihrer Trotzphase alles anders machen muss als andere String-Funktionen die Algorithmen abbildeten.
Ein Programm das Wort-/Halteproblem entscheidet, muss allerdings in der alten Tabelle sein, in der du schon alle anderen Programme aufgezählt hast. Das Programm unten aus der "Erweiterten Tabelle" ist jedoch auch, obwohl es eine sinnlose String-Funktion ist, theoretisch von Wort-/Halte-Entscheider entscheidbar. Genauso wie Wort-/Halte-Entscheider,
mit sich selbst,
codiert als code(Wortentscheider) für Wortentscheider
und code(Halteentscheider) für Halteentscheider
in endlicher Zeit eine Ja/Nein-Antwort liefert.
Der Entscheider ist theoretisch als TM/Programm/Algorithmus definierbar. Er ist in unserer alten -Akzeptanzverhalten-Tabelle an abzählbaren Algorithmen, was ist jetzt also das große Problem?
Die Annahme dass der Entscheider exisitert würde bedeuten: jedes Akzeptierverhalten aus der Tabelle sei entscheidbar. Es ist allerdings immer möglich ein neues Akzeptierverhalten zu konstruieren, welches theoretisch auch entscheidbar sein müsste, welches allerdings nicht existiert. Das weiß der Entscheider aber nicht. Er findet sinnlose Antworten auf Fragen, unter anderem, die er über sich selbst stellt.
TLDR: 95% aller echten, nützlichen Programme sind auf gültigen Eingabewörtern wsl entscheidbar. Ich mein schau dir mal irgendein Debug-Tool an.
Das Halte-/Wortproblem hier ist einfach nur eine formelle Überlegung die dich auch nicht näher an das Licht der Wahrheit bringen wird, sonder nur Aua im alten Kürbis macht.
Das mit dem Aua im alten Kürbis habe ich grad sehr gefühlt
Das versteh ich einfach nicht.
Halterproblem:
Wir nehmen etwas falsches an, damit funktioniert es und aufgrund dessen können wir sagen, dass es nicht funktioniert?
Warum ist nicht die Aussage, dass es Falsch ist nicht falsch?
Wäre es nicht viel einleuchtender zu sagen, das Halteproblem fragt, ob die DTM irgendwann anhält. Durch die endlosschleife können wir aber nie sagen, ob es nun wirklich anhält oder noch einen Schritt geht und dadurch nicht entscheidbar, da wir nur "ja" entscheiden können aber nicht "nein"
Das ist genau der Knackpunkt. Schau dir zb mal das Collatz-Problem an: Für manche Zahlen (1, 2, 4, 8, 16, ...) findet man schnell Antworten für manch andere braucht man lange, bisher hat man noch keine Zahl gefunden für die es nicht hält.
Aber man will ja wissen: Gibt es diese Zahl?
Kann man aus der Vorschrift des Algorithmus allein, herausfinden ob es diese Zahl gibt? Jedenfalls nicht mit einfachen Algorithmus-Mitteln.
Klar kannst du einfach ewig warten und schauen ob ein rechnendes Programm hält, aber du lebst nun mal nicht ewig.
Kannst du auf andere Weise durch andere Beobachtungen herausfinden, ob das Programm halten wird? Bzw ob irgendein wohldefinierter Algorithmus auf irgendeiner validen Eingabe halten wird? Der Beweis sagt nein: Für dieses Problem ist kein Algorithmus konstruierbar, da die Annahme der Existenz dieses Algorithmus an einer ganz anderen Stelle, ganz unabhängig vom Akzeptanz/Halteproblem für Kopfschmerzen sorgt.
Fair enough:
Du könntest die Frage stellen:
Jaa aber wieso macht man so ein Quatschprogramm, bei dem man akzeptiert, wenn die subroutine ablehnt und ablehnt wenn die Subroutine akzeptiert?
- Dreh es ruhig um, du hast nun einen Wrapper um deine Subroutine gemacht, der genau das gleiche wie sie ausgibt, von der du nicht mal weißt ob sie korrekt ist.
Jaa aber wieso geben wir unserem Entscheider sich selbst kodiert als Eingabe? Wie soll ein Mikrophon sich selbst aufnehmen? Das erzeugt eine Rückkopplung!
Wie soll eine Kamera sich selbst filmen? Wie kann ein Auge sich selber sehen?
Würde es die Frage erleichtern dem Halte-Entscheider nicht zu erlauben sich selbst zu betrachten und nur sinnvolle Fragen zu stellen?
Das blöde ist: Es ist nun mal ein Algorithmus, der die Macht hat Algorithmen auf Herz und Nieren zu testen und unter verschiedenen Bedingungen performen zu sehen. Algorithmen sind nach strengen Regeln konstruierbar und es gibt nur abzählbar viele von ihnen.
Entweder er mach seinen Job nicht. Weil er zB keine gewinnbringende semantische oder syntaktische Analyse vollführen kann (Satz von Rice, Bedingungen für Kontrollfluss können sehr komplex sein, oder schlichtweg Vorzeichenfehler haben, es sind allerdings immer noch, wenn auch sinnlose, Algorithmen) oder
er schafft es nicht zu entscheiden ob er halten wird, bspw. weil er immer wieder aufs neue sich selbst simuliert, und dann in der neuen Rekusrsionsstufe wieder sich selbst simuliert etc. etc. dann hält er nie. Hält. Nie. Weißt wie ich meine?
Versteh mich nicht falsch, Akzeptanz und Halteproblem sind **semi-entscheidbar** aber nun mal nicht entscheidbar.
Was sollte dieses spezWP quer nochmal darstellen?
das Komplement von spezWP, also alle Worte, die nicht im spezWP sind
im wesentlichen ist das alles ja ein erweitertes "dieser Satz ist falsch" Problem.