7. Übung – TGI
Lorenz Hübschle-Schneider, Tobias Maier
I NSTITUT
FÜR
T HEORETISCHE I NFORMATIK , P ROF. S ANDERS
Hübschle-Schneider, Tobias Maier
1 KITLorenz
– Die Forschungsuniversität in der Helmholtz-Gemeinschaft
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
www.kit.edu
Institut für Theoretische
Informatik
Organisatorisches
Da es wohl noch nicht klar genug war:
Verspätete Abgaben geben keine Punkte!
(Wenn euer Tutor ganz besonders nett ist,
korrigiert er es vielleicht aber trotzdem)
2 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Universelle Turingmaschinen
Turingmaschinen, die Turingmaschinen simulieren, die
Turingmaschinen simulieren, . . .
Reale Beispiele:
3 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Universelle Turingmaschinen
Turingmaschinen, die Turingmaschinen simulieren, die
Turingmaschinen simulieren, . . .
Reale Beispiele:
Interpreter für Scriptsprachen
Emulatoren
3 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Universelle Turingmaschinen
Turingmaschinen, die Turingmaschinen simulieren, die
Turingmaschinen simulieren, . . .
Reale Beispiele:
Interpreter für Scriptsprachen
Emulatoren
Andere Beispiele:
Turingmaschinensimulatoren
Game of Life in Game of Life https://youtu.be/xP5-iIeKXE8
3 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Quines
Können wir ein selbstreplizierendes Programm schreiben, also eines,
das seinen eigenen Quellcode ausgibt?
4 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Quines
Können wir ein selbstreplizierendes Programm schreiben, also eines,
das seinen eigenen Quellcode ausgibt?
Ja! Diese Programme heißen Quines. In Python:
s = 's = %r\nprint(s%%s)'
print(s%s)
4 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Quines
Können wir ein selbstreplizierendes Programm schreiben, also eines,
das seinen eigenen Quellcode ausgibt?
Ja! Diese Programme heißen Quines. In Python:
s = 's = %r\nprint(s%%s)'
print(s%s)
Rekursionssatz: Es gibt Turingmaschinen, die ihre eigene
Gödelnummer aufs Band schreiben
⇒ Quines gibt es in jedem turingmächtigen System
4 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Quines
Können wir ein selbstreplizierendes Programm schreiben, also eines,
das seinen eigenen Quellcode ausgibt?
Ja! Diese Programme heißen Quines. In Python:
s = 's = %r\nprint(s%%s)'
print(s%s)
Rekursionssatz: Es gibt Turingmaschinen, die ihre eigene
Gödelnummer aufs Band schreiben, und jede TM lässt sich in eine
äquivalente TM überführen, die diese Eigenschaft erfüllt
⇒ Quines gibt es in jedem turingmächtigen System
4 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Quines
Können wir ein selbstreplizierendes Programm schreiben, also eines,
das seinen eigenen Quellcode ausgibt?
Ja! Diese Programme heißen Quines. In Python:
s = 's = %r\nprint(s%%s)'
print(s%s)
Rekursionssatz: Es gibt Turingmaschinen, die ihre eigene
Gödelnummer aufs Band schreiben, und jede TM lässt sich in eine
äquivalente TM überführen, die diese Eigenschaft erfüllt
⇒ Quines gibt es in jedem turingmächtigen System
⇒ TMs dürfen ihre eigene Beschreibung verwenden (vgl. Reflections)
4 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Unentscheidbarkeit
Gegeben zwei Konfigurationen in Game of Life. Können
diese ineinander überführt werden?
Unentscheidbar!
5 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Der Satz von Rice
Ungefähr: ”Es ist unmöglich, eine beliebige nicht-triviale Eigenschaft
der erzeugten Funktion einer Turing-Maschine (oder eines Algorithmus
in einem anderen Berechenbarkeitsmodell) algorithmisch zu
entscheiden.”
6 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Der Satz von Rice
Ungefähr: ”Es ist unmöglich, eine beliebige nicht-triviale Eigenschaft
der erzeugten Funktion einer Turing-Maschine (oder eines Algorithmus
in einem anderen Berechenbarkeitsmodell) algorithmisch zu
entscheiden.”
6 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Der Satz von Rice
Ungefähr: ”Es ist unmöglich, eine beliebige nicht-triviale Eigenschaft
der erzeugten Funktion einer Turing-Maschine algorithmisch zu
entscheiden.”
Klasse unentscheidbarer Sprachen
6 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Der Satz von Rice
Ungefähr: ”Es ist unmöglich, eine beliebige nicht-triviale Eigenschaft
der erzeugten Funktion einer Turing-Maschine algorithmisch zu
entscheiden.”
Klasse unentscheidbarer Sprachen
Sprachen von Turingmaschinen abhängig von der berechneten
Funktion
6 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Der Satz von Rice
Ungefähr: ”Es ist unmöglich, eine beliebige nicht-triviale Eigenschaft
der erzeugten Funktion einer Turing-Maschine algorithmisch zu
entscheiden.”
Klasse unentscheidbarer Sprachen
Sprachen von Turingmaschinen abhängig von der berechneten
Funktion
Vage gefasst ⇒ nicht direkt einsetzen
6 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Der Satz von Rice
Ungefähr: ”Es ist unmöglich, eine beliebige nicht-triviale Eigenschaft
der erzeugten Funktion einer Turing-Maschine algorithmisch zu
entscheiden.”
Klasse unentscheidbarer Sprachen
Sprachen von Turingmaschinen abhängig von der berechneten
Funktion
Vage gefasst ⇒ nicht direkt einsetzen
Stattdessen merkt euch die folgenden Beweisschemata
6 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Es gibt keine perfekten Virenscanner
Virus ⇔ Turingmaschine die VIRUS auf das Band schreibt.
7 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Es gibt keine perfekten Virenscanner
Virus ⇔ Turingmaschine die VIRUS auf das Band schreibt.
Satz von Rice ⇒ LVIRUS = {hM i | M ist ein Virus} ist unentscheidbar
7 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Beweis über das Halteproblem
Ansatz: LVIRUS entscheidbar ⇒ Halteproblem lösbar!
8 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Beweis über das Halteproblem
Ansatz: LVIRUS entscheidbar ⇒ Halteproblem lösbar!
Sei (hMIN i, wIN ) eine Instanz des Halteproblems
8 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Beweis über das Halteproblem
Ansatz: LVIRUS entscheidbar ⇒ Halteproblem lösbar!
Sei (hMIN i, wIN ) eine Instanz des Halteproblems
mit Hilfe dieser Instanz konstruieren wir die TM TIN
8 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Beweis über das Halteproblem
Ansatz: LVIRUS entscheidbar ⇒ Halteproblem lösbar!
Sei (hMIN i, wIN ) eine Instanz des Halteproblems
mit Hilfe dieser Instanz konstruieren wir die TM TIN
TIN schreibt hMIN i#wIN auf das Band
8 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Beweis über das Halteproblem
Ansatz: LVIRUS entscheidbar ⇒ Halteproblem lösbar!
Sei (hMIN i, wIN ) eine Instanz des Halteproblems
mit Hilfe dieser Instanz konstruieren wir die TM TIN
TIN schreibt hMIN i#wIN auf das Band
TIN simuliert MIN auf der Eingabe wIN
8 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Beweis über das Halteproblem
Ansatz: LVIRUS entscheidbar ⇒ Halteproblem lösbar!
Sei (hMIN i, wIN ) eine Instanz des Halteproblems
mit Hilfe dieser Instanz konstruieren wir die TM TIN
TIN schreibt hMIN i#wIN auf das Band
TIN simuliert MIN auf der Eingabe wIN
TIN löscht den Bandinhalt und schreibt VIRUS
8 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Beweis über das Halteproblem
Ansatz: LVIRUS entscheidbar ⇒ Halteproblem lösbar!
Sei (hMIN i, wIN ) eine Instanz des Halteproblems
mit Hilfe dieser Instanz konstruieren wir die TM TIN
TIN schreibt hMIN i#wIN auf das Band
TIN simuliert MIN auf der Eingabe wIN
TIN löscht den Bandinhalt und schreibt VIRUS
Beobachtung: TIN ist genau dann ein Virus, wenn (hMIN i, wIN ) hält.
8 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Beweis über das Halteproblem
Ansatz: LVIRUS entscheidbar ⇒ Halteproblem lösbar!
Sei (hMIN i, wIN ) eine Instanz des Halteproblems
mit Hilfe dieser Instanz konstruieren wir die TM TIN
TIN schreibt hMIN i#wIN auf das Band
TIN simuliert MIN auf der Eingabe wIN
TIN löscht den Bandinhalt und schreibt VIRUS
Beobachtung: TIN ist genau dann ein Virus, wenn (hMIN i, wIN ) hält.
TSCAN entscheidet LVIRUS ⇒ TSCAN entscheidet das Halteproblem
8 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Einschub: Rekursionssatz
Kurzfassung:
Für jede partiell berechenbare Funktion f existiert eine TM Trec(f )
9 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Einschub: Rekursionssatz
Kurzfassung:
Für jede partiell berechenbare Funktion f existiert eine TM Trec(f )
Trec(f ) schreibt hTrec(f ) i auf das Band
9 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Einschub: Rekursionssatz
Kurzfassung:
Für jede partiell berechenbare Funktion f existiert eine TM Trec(f )
Trec(f ) schreibt hTrec(f ) i auf das Band
Trec(f ) wendet die Funktion f auf hTrec(f ) i an
9 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Beweis mit Rekursionssatz
Angenommen es gäbe die TM TSCAN , die LVIRUS entscheidet
Ansatz: konstruiere TM THIDDEN , die von TSCAN falsch klassifiziert wird
10 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Beweis mit Rekursionssatz
Angenommen es gäbe die TM TSCAN , die LVIRUS entscheidet
Ansatz: konstruiere TM THIDDEN , die von TSCAN falsch klassifiziert wird
THIDDEN schreibt zunächst hTHIDDEN i auf das Band
Rekursionssatz
10 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Beweis mit Rekursionssatz
Angenommen es gäbe die TM TSCAN , die LVIRUS entscheidet
Ansatz: konstruiere TM THIDDEN , die von TSCAN falsch klassifiziert wird
THIDDEN schreibt zunächst hTHIDDEN i auf das Band
THIDDEN schreibt nun hTSCAN i# links daneben
bei der Konstruktion ist TSCAN bekannt
10 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Beweis mit Rekursionssatz
Angenommen es gäbe die TM TSCAN , die LVIRUS entscheidet
Ansatz: konstruiere TM THIDDEN , die von TSCAN falsch klassifiziert wird
THIDDEN schreibt zunächst hTHIDDEN i auf das Band
THIDDEN schreibt nun hTSCAN i# links daneben
THIDDEN simuliert TSCAN auf der Eingabe hTHIDDEN i
Universelle Turingmaschinen
10 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Beweis mit Rekursionssatz
Angenommen es gäbe die TM TSCAN , die LVIRUS entscheidet
Ansatz: konstruiere TM THIDDEN , die von TSCAN falsch klassifiziert wird
THIDDEN schreibt zunächst hTHIDDEN i auf das Band
THIDDEN schreibt nun hTSCAN i# links daneben
THIDDEN simuliert TSCAN auf der Eingabe hTHIDDEN i
TSCAN akzeptiert ⇒ THIDDEN schreibt FALSE POSITIVE
TSCAN akzeptiert nicht ⇒ THIDDEN schreibt VIRUS
10 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
Beweis mit Rekursionssatz
Angenommen es gäbe die TM TSCAN , die LVIRUS entscheidet
Ansatz: konstruiere TM THIDDEN , die von TSCAN falsch klassifiziert wird
THIDDEN schreibt zunächst hTHIDDEN i auf das Band
THIDDEN schreibt nun hTSCAN i# links daneben
THIDDEN simuliert TSCAN auf der Eingabe hTHIDDEN i
TSCAN akzeptiert ⇒ THIDDEN schreibt FALSE POSITIVE
TSCAN akzeptiert nicht ⇒ THIDDEN schreibt VIRUS
Da TSCAN die Eingabe THIDDEN falsch klassifiziert, kann TSCAN die Sprache
LVIRUS nicht korrekt entscheiden.
Widerspruch
10 Lorenz Hübschle-Schneider, Tobias Maier
7. Übung – Theoretische Grundlagen der Informatik
Fakultät für Informatik
Institut für Theoretische Informatik
© Copyright 2024 ExpyDoc
