cards-deck: university::theo_complexity

Satz von Rice:

broad part of [[112.00_anchor_overview]]

Motivation für Satz von Rice:

Wir haben zuvor bereits betrachtet, dass diverse kritische Eigenschaften von Turingmaschinen / Programmen nicht immer entscheidbar sind. Dabei stellt sich die Frage, ob diese Eigenschaften in den Betrachtungen dann nur Ausnahmen oder Regel sind. MIt dieser Eigenschaft können wir weitere Betrachtungen schlussfolgern.

So gut, wie alle interessanten Eigenschaften von TMs sind (leider) unentscheidbar.

Definition von interessanten Eigenschaften: #card

Wir interessieren uns meist nur für die Ausgaben, denn wenn wir später äquivalente TMs betrachten, ist es interessant, ihre Eigenschaften zu betrachten. Wir wollen also Eigenschaften von TMs anschauen, die sich nur an der von ihr erkannten Sprachen festmachen lassen –> wir lassen also die konkrete Implementierung und ihre Struktur heraus/weg. ^1686505898165

EIne Äquivalenz von Turingmaschinen haben wir so definiert, dass beide Turingmaschinen, die gleiche Sprache entscheiden können.

ferner benötigen wir erneut die Definition von nicht trivialen Sprachen: ![[theo2_SprachenUnendlichkeit#Nicht-triviale Sprachen]]

Semantisches Entscheidungsproblem:

Definition:

Sei $L$ eine Sprache, deren Wörter nur aus Codes von TM bestehen –> also gleich einer nicht-trivialen Sprache! $L \subset {w \in {0, 1}^{*} ∣ w ist Code einer TM}$ -> Jedes Wort ist Code einer TM. Wir nennen diese Sprache $L$ jetzt semantisch #card:

Wenn $M_{1}$ und $M_{2}$ äquivalente TMs sind, Dann sind entweder beide in L oder beide nicht in L enthalten:
$⟨ M_{1} ⟩ \in L ⟺ ⟨ M_{2} ⟩ \in L$

Satz von Rice:

Wie lautet er? Jedes semantische, nichttriviale Entscheidungsproblem ist unentscheidbar.

Beweisidee:

Wir betrachten einen Beweis, welcher multiple Fälle betrachten muss, um sinnvoll gelöst werden zu können. was sind nötige Grundstrukturen für einen solchen Beweis? #card Dabei legen wir jetzt folgende Parameter fest:

Sei $L$ eine nichttriviale, semantische Sprache
wir wollen das Halteproblem $H_{0}$ auf diese Sprache $L$ reduzieren
Sei dazu $M_{l eer}$ eine TM, welche kein einziges Wort akzeptiert.
- beschrieben wird sie mit: $L (M_{l eer}) = \emptyset$ ^1686505898173

können wir eine solche TM konstruieren? #card:

Ja, sie soll einfach bei jeder Eingabe direkt rejecten und somit nicht entscheiden!

Wir können jetzt passend reduzieren, jenachdem, ob $⟨ M_{l eer} ⟩ \in L$ ist oder nicht: also wie können wir die beiden Fälle definieren? #card

Falls $⟨ M_{l eer} ⟩ \in L$ , dann konstruieren wir eine passend Reduktion $\overset{ˉ}{H}_{0} ⪯_{m} L$ als Fall 1
und Falls $⟨ M_{l eer} ⟩ \neq \in L$ m dann konstruieren wir eine Reduktion $H_{0} ⪯_{m} L$ als Fall 2
Wir wissen noch, dass $H_{0}$ und $\overset{ˉ}{H}_{0}$ nicht entscheidbar sind und können jetzt schon erkennen, dass $L$ auch untenscheidbar sein muss! ^1686505898177

Beweis:

Starten wir nun den Beweis des Satz von Rice. #card Dafür sei gegeben: $L$ eine nicht triviale, semantische Sprache Da $L$ nicht trivial ist, gibt es also :

eine $M_{0}$ mit $⟨ M_{0} ⟩ \neq \in L$ und
eine $M_{1}$ mit $⟨ M_{1} ⟩ \in L$ Wir werden beide diese TMs später wieder anwenden müssen, wenn wir zeigen, dass sie equivalent in der Ausführung sind. Fall 1 - Also $⟨ M_{l eer} ⟩ \in L$ :
Wir möchten nun eine Reduktion von $\overset{ˉ}{H}_{0} ⪯ L$ konstruieren und haben dann eine TM $M_{L}$ die L entscheiden kann. Das Ziel unserer Reduktion ist dann:
wir betrachten eine Eingabe $⟨ N ⟩$ und wollen dann entscheiden, ob N auf $ϵ$ stoppt oder nicht
wir wollen $⟨ N ⟩$ so transformieren, dass wir sie in die Form $⟨ M ⟩$ bekommen, um sie dann der TM $M_{l}$ als Argument geben zu können. Es soll dann also gelten: $N \in \overset{ˉ}{H}_{0} ⟺ M \in L$ also, wenn N sich in Komplement der Menge des Halteproblemes befindet, dann ist auch die verarbeitende TM M in der Sprache $L$ ^1686505898182

Fall 1 - Konstruktion zum Lösen: Stellen wir eine Turingmaschine $R$ zur Lösung von $\overset{ˉ}{H}_{0}$ bei Eingabe $⟨ N ⟩$ auf:

Die Eingabe $⟨ N ⟩$ entspricht des Codes einer TM – also dessen Gödelnummer beispielsweise
Die gewünschte Ausgabe gibt dann an, ob $N$ auf $ϵ$ stoppt Um dies zu bewerkstelligen gehen wir folgend for:

Konstruiere Gödel-Code $⟨ M ⟩$ einer TM $M$ , die dann die folgende Berechnung durchführen würde, also nur konzeptuell gedacht:
1. Simulieren von $⟨ N, ϵ ⟩$ (muss es nicht berechnen, bzw keine Ausgabe geben, sondern nur zeigen, wie es ungefähr funktionieren würde)
2. $M_{0} (z)$ zurückgeben ( also einfach die TM, die auf nichts eine Ausgabe gibt) DIe TM M wird hier nicht ausgeführt!, wir berechnen nur ihren Code. Dieser Schritt entspricht der Berechnung der neuen Instanz in der Reduktion.
Wir geben jetzt $M_{L (⟨} M ⟩)$ zurück, also wir geben die konvertierte Instanz zurück und rufen dann die TM $M_{l}$ mit diesem Wert auf

Ist diese Konstruktion abgeschlossen, dann müssen wir folglich die Äquivalenz der Aussagen zeigen. Dafür müssen wir auch wieder zwei Fälle betrachten: Fall 1, von 1: Sei $N \neq \in \overset{ˉ}{H}_{0}$ :

Gelte dieser fall, dann heißt das, dass $N \in H_{0}$ , also $N$ hält nur bei **eingabe $ϵ$ **an.
In diesem Fall ist dann die obige TM (welche simuliert und $M_{0}$ zurückgibt) äquivalenz zur TM $M_{0}$ –> sie gibt ja die gleiche TM zurück xd;
Da $L$ semantisch ist, gilt also unsere Betrachtung des Satzes von Rice: $M \in L ⟺ M_{0} \in L$
Wir wissen aber weiterhin, dass $M_{0} \neq \in L$ gilt. Also folgt daraus dann auch $M \neq \in L$

Fall 2, von 1: Sei $N \in \overset{ˉ}{H}_{0}$ :

Gelte dieser Fall, dann gilt also $N \neq \in H_{0}$ also hält $N$ bei einer Eingabe von $ϵ$ nicht an
Tritt dieser Fall ein, dann ist unsere obige TM ( die simuliert!) äquivalent zur TM $M_{l eer}$ , denn beide liefern genau das gleiche Ergebnis: Die Simulation hält nie an, egal was die Eingabe z in M war. die TM M akzeptiert hier also auch kein einziges Wort
Da L semantisch ist, können wir auch wieder anwenden: $M \in L ⟺ M_{l eer} \in L$
Wir wissen ferner, dass $M_{l eer} \neq \in L$ gilt und somit dann auch $M \neq \in L$

Resultat der Betrachtung: Wir haben gesehen, dass die Reduktionseigenschaft mit $N \in \overset{ˉ}{H}_{0} ⟺ M \in L$ erfüllt wird. Diese Reduktion ist berechenbar! (wir beweisen sie aber nicht)

Fall 2 - Analog zum ersten Fall: In dieser Instanz gehen wir ähnlich, wie oben vor, jedoch reduzieren wir jetzt $H_{0} ⪯ L$ anstatt $\overset{ˉ}{H}_{0}$ ! Weiterhin nutzen wir jetzt die Sprache $M_{1}$ , statt $M_{0}$ , in unserer Konstruktion. Wire resultieren dann mit folgender Konstruktion: Turingmaschine $R$ zur Lösung von $\overset{ˉ}{H}_{0}$ auf Eingabe $⟨ N ⟩$ :

Eingabe $⟨ N ⟩$ entspricht Code einer TM
Gewünschte Ausgabe der Konstruktion: N stopp auf $ϵ$ oder nicht Wir konstruieren hierfür dann:

Gödel-Code einer TM M, die die folgende Berechnung durchführen würde:
TM m auf Eingabe $z$ :
1. Simuliere $⟨ N, ϵ ⟩$
2. Return $M_{1} (z)$
Am Ende geben wir auch hier dann die Transformation in der neuen Eingabe zurück, also $M_{L} (⟨ M ⟩)$

zusammengefasst Betrachtung des Beweis: Wir haben beide Fälle betrachtet und resultieren folgend: Fall 1: $N \in H_{0}$ , also $⟨ N, ϵ ⟩$ stoppt, was impliziert $⟹$ die konstruierte TM ist äquivalent zu $M_{1}$ , und da $M_{1} \in L$ folgt auch $M \in L$ Fall 2: $N \neq \in H_{0}$ als $⟨ N, ϵ ⟩$ stopp nicht, woraus folgt $⟹$ die konstruierte TM ist äquivalent zu $M_{l eer}$ und im Fall 2 gilt dann $M_{l eer} \neq \in L$ also dann auch $M \neq \in L$ !

Umkehrung ist im Allgemeinen falsch: #card

Das Theorem von Rice sagt intuitiv:

semantisch ==> unentscheidbar

aber logischerweise gilt die Umkehrung nicht!

Es gibt untenscheidbare Sprachen, die nicht semantisch sind! ^1686505898187

Bedeutung des Satzes:

Was können wir aus dem Satz schließen? #card Wir haben demnach erkennen können, dass eine allgemeine Verifikation von Programmen eigentlich unmöglich ist. Das ist doof, wenn wir sicherheitskritische Funktionen von irgendwelchen Computern ausführen lassen wollen.
Beispielsweise etwa ein Autopilot für Flugzeuge oder eine automatische Steuerung von Atomkraftwerken. ^1686505898191

Ein spezifisches Code-Beispiel:

def halloo():
	print("Hello World")
hallo()

In diesem Beispiel können wir schon aussagen, ob das Programm terminieren würde, denn wir können es als eine einmalige Ausführung betrachten.

Weiter können wir also Betrachten, ob eine Einschränkung der Sorte von Programmen helfen könnte, über ihre Eigenschaften von Terminierung zu urteilen. Welchen Schluss können wir ziehen? #card

Programme die keine Schleifen, Variablen benutzen, halten an!
Wir nehmen als Einschränkungen in Kauf: Programme dürfen nur bestimmte DInge tun, etwa bestimmte Stellen im Speicher beschreiben oder nur diverse Invarianzen aufweisen.
Eine tiefere Betrachtung liefert dann das Fachgebiet der Software-Verifikation! ^1686505898194

scattered-lenity