date-created: 2024-06-13 10:28:35 date-modified: 2024-06-24 04:46:49

Satz von Rice

anchored to 112.00_anchor_overview

nichttriviale Metadaten über manche Sprachen kann man einfach nicht beschreiben und festlegen!?

Aus 112.17_reduktionen wissen wir, dass wir diverse Dinge nicht entscheiden können und ferner werden wir jetzt herausfinden, dass das auch für bestimmte Eigenscahften gilt.

Was sind interessante Eigenschaften?

Wir interessieren uns im Kontext der Berechenbarkeit nicht dafür, wie eine TM ein Ergebnis erreicht (ihre Implementierung), sondern nur für das Ergebnis / die Ausgabe. “Interessante” Eigenschaften sind also nur solche, die sich an der erkannten Sprache definieren lassen.

Definition | Semantisch

Wir wollen uns nochmals das Problem der Gleichheit anschauen, also $M_1,M_2$ sind äquivalent, wenn $L(M_1)=L(M_2)$!

[!Definition]

Sei $L$ eine Sprache, deren Wörter alle Codes von TMS sind, also $L\subseteq \{w\in \{0,1{\}}^{\ast }\mid w\text{ ist Code einer TM}\}$

wann nennen wir die Sprache nicht-trivial?, wann nennen wir sie jetzt semantisch? #card

Die Sprache $L$ heißt nicht-trivial, falls gilt:

• $L\ne \varnothing$ - also es gibt TMs, deren Code in L enthalten ist!
• $L\ne \{w\in \{0,1{\}}^{\ast }\mid w\text{ ist Code einer TM}\}$ -> also es gibt TMs, deren Code nicht in L enthalten ist ( also es muss wohl eine Ausnahme geben, dass nicht einfach alle enthalten sind!)

Wir nennen die Sprache $L$ jetzt semantisch, falls gilt: Wenn $M_1$ und $M_2$ äquivalent sind, dann sind entweder beide oder keine von beiden in $L$ enthalten

Also anders heißt das: $(L(M_1)=L(M_2))=(⟨M_1⟩\in L\wedge ⟨M_2⟩\in L)$ oder $(⟨M_1⟩\notin L\wedge ⟨M_2⟩\notin L)$

[!Definition] Satz von Rice:

Es gilt: Quasi alle interessanten Eigenschaften von TMs sind unentscheidbar!

Jedes semantische, nichtriviale Entscheidungsproblem ist unentscheidbar (brauch also Definition Semantisch)

Was meinen wir hier mit interessant? Was folgt hieraus? #card

Grundsätzlich ist beim Kontext von Berechenbarkeit selten die Implementierung (wie das Ergebnis geschaffen wird), sondern eher das Ergebnis relevant ( ob / was die Ausgabe ist / wäre).

Daher sind interessante Eigenschaften solche, die sich an einer erkannten Sprache definieren lassen –> wenn wir also eine Ausgabe erhalten können!

(Betrachten wir etwa): Zwei TMs sind Äquivalent, wenn gilt: $L(M_1)=L(M_2)$

Sei dafür dann eine Sprache $L$, deren Wörter alle Codes von TMs sind. Beschrieben haben wir sie mit: $$L\subseteq \{w\in \{0,1{\}}^{\ast }\mid w\text{ ist Code einer TM}\}$$

Diese Sprache ist nicht trivial!, wenn folgend gilt:

• $L\ne \varnothing$ (also es gibt TMs, deren Code in $L$ enthalten ist!)
• $L\ne \{w\in \{0,1{\}}^{\ast }\mid w\text{ ist Code eienr TM}\}$ ( also es gibt TMs, deren Code nicht in $L$ enthalten ist)

Diese Sprache heißt dann semantisch, falls hier folgend gilt:

• Wenn $M_1\wedge M_2$ äquivalent sind, dann sind entweder beide oder keine von beiden $\in L$ ALSO: $$(L(M_1)=L(M_2))⟹(⟨M_1⟩\in L\wedge ⟨M_2⟩\in L)\vee (⟨M_1⟩\notin L\wedge ⟨M_2]rangle\notin L)$$

anders formulierte Varianten des Satz von Rice wären etwa:

(Sipser): Sei p eine Eigenschaft rekursiv aufzählbarer Sprachen (d.h. von Turingmaschinen). Wenn p nicht-trivial ist (d.h. mindestens eine, aber nicht alle Sprachen haben p), dann ist nicht entscheidbar, ob die Sprache L(M) einer bestimmten Turingmaschine M die Eigenschaft p hat

oder (Schöning): Sei S eine beliebige Teilmenge von R, mit Ausnahme von $S=\varnothing$ und $S=R$. Dann ist die Sprache $$L_S=\{⟨M⟩\text{ die von M berechnete Funktion liegt in S}\}$$ unentscheidbar!

(die Gödelisierung ist beinahe bijektiv, weil sie präfix-frei ist etc.

Wir möchten jetzt zeigen, dass alle nichtrivialen Eigenschaften von Turingmaschinen (also alle semantische Eigenschaften) nicht entscheidbar sind!

Beweis Satz von Rice

Wir wollen diesen Beweis unter Anwendung einer Abbildungsreduktion beschreiben.

Wir wollen eine Reduktion von den Sprachen $H_0^C,H_0$ 112.17_reduktionen (die Sprachen, die auf dem leeren Wort halten / oder auf diesen nicht halten) auf $L$ umsetzen!

Zur Erinnerung: $$H_0(⟨M⟩=\{\begin{array}{ll}1& \text{falls TM M bei Eingabe von }\epsilon \text{ anhalt}\\ 0& sonst\end{array})$$ und ferner: $$H_0^C(⟨M⟩)=\{\begin{array}{ll}1& \text{ falls TM M bei Eingabe von }\epsilon \text{ nicht anhalt}\\ 0& sonst\end{array}$$

Da $H_0\notin R$ wären wir damit schon fertig. Allerdings werden wir sehen, dass dieser Ansatz nur funktioniert, wenn $M_{\varnothing }-$ die TM die kein einziges Wort akzeptiert, also $L(M_{\varnothing })=\varnothing$ $-$ nicht in $L$ ist. (Das können auch viel verschiedene Sprachen sein, also die Äquivalenzklasse dazu!) –> Für den Fall $L(M_{\varnothing })\in L$ machen wir stattdessen eine Reduktion auf das Komplement $H_0^C\in coRE\setminus R$

(Problem): Wir haben keine konkrete Formulierung von $L$, nur die Existenz von $M_0\notin L$ und weiter $M_1\in L$. Der Beweis muss also direkt über die Semantik laufen. (nicht über was konkretes, weil wir es ja nicht wirklich definiert haben) Wir müssen, dann also Leerheit semantisch äquivalent zu $M_0\vee M_1$ machen!.

Fall 1: $⟨M_{\varnothing }⟩\in L$

Sei $L$ also semantisch und nicht-trivial. Das heißt es gibt dann

• eine TM $M_0$ mit $⟨M_0⟩\notin L$ und ferner auch
• TM $M_1$ mit $⟨M_1⟩\in L$

Außerdem sei zunächst $⟨M_{\varnothing }⟩\in L$

Wir wollen also erst eine Abbildung bauen, die berechenbar abilden kann. Danach möchten wir zeigen, dass sie tatsächlich Berechenbar ist .

Wir konstruieren eine Reduktion folgend: $H_0^C{⪯}_{}L$ (Sie also im Folgenden $M_L$ eine TM, welche $L$ entscheidet) Wir suchen eine Reduktionsabbildung: $F:⟨N⟩\mapsto ⟨M⟩$

• Mit Eingabe $⟨N⟩$ wollen wir entscheiden, ob $N$ auf $ϵ$ hält!
• Wir Bilden demnach dann $⟨N⟩$ auf einen anderen String $⟨M⟩$ ab, den wir $M_L$ als Eingabe geben!

Jetzt soll ferner gelten: $$N\in H_0^C⟺F(N)=M\in L$$ In der Umsetzung jetzt also:

Wir bauen jetzt eine TM $A$ zur Lösung von $H_0^C$ auf einer Eingabe $⟨N⟩$!

–>

1. Berechne die Gödelnumer der TM $M$, welche folgend funktioniert: Turingmaschine $M$ auf Eingabe $z$:
   • Simuliere hier $⟨N,z⟩$ (halteproblem!) und ferner
   • Return $M_0(z)$ (also die Ausgabe von $M_0$ auf z) ($M_0\notin L$ als Erinnerung!)
2. Anschließend geben wir folgend züruck: $$M_L(⟨M⟩)$$ Anmerkungen hier:

• Die Maschine $M$ wird nicht ausgeführt –> wir wollen nur die Gödelnummer erhalten!
• Die Abbildung $f$ der Abbildungsreduktion besteht aus der Konstruktion von $M$ und der Berechnung von $⟨M⟩,$ also $f(⟨N⟩)=⟨M⟩$ –> Beide können wir natürlich berechnen!
• $⟨N⟩$ ist hart in $M$ einprogrammiert –> und wir konstruieren somit für jedes $N$ wieder eine neue TM $M$, die aber in der Idee gleich ist!

Bemerkungen Auf beliebiger Eingabe $z$ macht sie das gleiche –> die Eingabe-TM auf dem leeren Wort simulieren (und eventuell halten, wenn sie das jemals tun sollte!)

Danach wird sie die Ausgabe von $M_0(z)$ berechen (wir wissen, dass sie $\notin L$ ist!)

Dadurch gibt diese neue Maschine dann die Gödelnummer der Maschine aus.

Wir nutzen die Semantik-Eigenschaft bei $M_0(z)$ (Also die Ausgabe betrachten etc.)

Diese Gödelnummer wird dann an einen Entscheider gegeben, der prüft ob diese beschrieben TM in der Sprache liegt oder nicht!

(Was folgt): Diese TM macht folgendes: Sie verhält sich erstmal, wie eine TM, die nicht in der Sprache liegt - weil sie erstmal das leere Wort simuliert und schaut, ob sie anhält / oder nicht.

Ferner kann sie auch einfach nicht anhlaten unnd sich nicht wie $M_0$ verhalten.

– Wir haben gesagt, Abbildungsreduktion bestehen immer aus zwei Schritten: Erst checken, ob berechenbar und danach zeigen, dass sie ein Homomorphismus ist.

Was wir hier machen: Wir bekommen den Code einer TM. Wir bauen eine neue TM, die diesen Code nutzt, und auch den Code von $M_0$ ( weil wir wissen, dass sie existiert). –> Jetzt geht es nicht zwingend darum, ob sie jemals beenden / terminieren wird / oder nicht. Was wir hier eigentlich betrachten / erfahren möchten: -> wenn sie am Ende terminiert, dann ist sie ja äquivalent zu $M_0$ und somit gleich ihrer Eigenschaften.

Unsere Sprache ist, bei erfolgreicher Reduktion auf $H_0^C$ dann nicht entscheidbar (wie das )

Wir betrachten jetzt zwei Fälle für diesen Fall:

1. Sei $N\notin H_0^C$ das heißt also $N\in H_0$ -> also $N$ hält bei Eingabe $\epsilon$ an! In diesem Fall ist die $M$ dann äquivalent zur TM $M_0$ -> denn $M$ simuliert $N$, welche hält und macht danach auf allen Eingaben $z$ genau das gleiche, wie $M_0$! –> sie liefert also genau die gleichen Ergebnisse

–> Es gilt (weil diesen beiden jetzt semantisch sind!) folgend: $$M\in L⟺M_0\in L$$ Aber was wir auch wissen: $M_0\notin L$ und somit gibt die TM $A$ das Ergebnis aus: $A(⟨N⟩)=M_L(⟨M⟩)=M_L(M_0)=0$

2. Der zweite Fall sagt $N\in H_0^C$ und das heist also: $N\notin H_0$, also $N$ hält nicht bei einer Eingabe $\epsilon$!

In diesem Fall ist die $M$ äquivalent zur TM $M_{\varnothing }$ ( denn $M$ simuliert auf allen Eingaben $z$ zunächst $N$, welche dann hier nicht anhalt! –> Sie hält also ferner auf keiner einzigen Eingabe!)

Da ferner $L$ semantisch ist, folgt dann entsprechend: $M\in L⟺M_{\varnothing }\in L$

Aber, was wir auch wissen: $M_{\varnothing }\in L$ und somit liefert die TM $A$ das folgende Ergebnis: $$A(⟨N⟩)=M_L(⟨M⟩)=M_L(M_{\varnothing })=1$$

[!Req] Was haben wir damit gezeigt?

Wir haben gezeigt, dass folgend: $$\begin{array}{rl}>N\notin H_0^C& ⟹f(⟨N⟩)=M\notin L\\ >N\in H_0^C& ⟹f(⟨N⟩)=M\in L>\end{array}$$

das heißt also, dass die Reduktion das macht, was sie sol - sie ist berechenbar und kann passend reduzieren!

In diesem Fall haben wir gezeigt, dass $H_0^C{⪯}_{}L$ und weil $H_0^C\in coRE\setminus R$ ist folgt auch, dass $L\in coRE\setminus R$

Was der Trick war: Dass wir den Entscheider $R$ für $L$ zu einem Entscheider für H0 “umbauen” konnten, in dem wir einer Maschine $M_0$ (von der wir wissen $M_0\notin L$, wir kennen also die Ausgabe des Entscheiders R) die zu entscheidende Maschine aus $H_0$ “vorschalten”.

Hierzu verwendeten wir die semantische Eigenschaft:

Weil die “vorgeschaltete” Maschine M semantisch äquivalent ist, muss der Entscheider R sie gleich entscheiden können

[!Attention] Das Ganze muss noch analog für $M_{\varnothing }\notin L$ gezeigt werden

Fall 2: $M_{\varnothing }\notin L$

Dieser Fall ist analog, aber wir reduzieren von $H_0^C\to H_0{⪯}_L$

Es ändern sich hier also nur zwei Dinge:

• Statt $H_0^C$ reduzieren wir $H_0{⪯}_{}L$!
• Statt der Sprache $M_0\notin L$ verwenden wir in der TM $M$ dann die Sprache $M_1\in L$

AAlso angenommen wir haben eine semantische / nicht triviale Sprachen. Die drin ist ist $M_0$, die die semantisch ist, ist $M_1$.

Wir konstruieren jetzt eine Reduktion vom Nullhalteproblem.

Gesucht ist also eine Abbildung von Gödelnummern nach Gödelnummern (TM die eine Gödelnummer baut, wenn sie eine bekommt): $F:⟨N⟩\mapsto ⟨M⟩$

Wir geben als $⟨N⟩$ ein und erhalten, ob $N$ auf $\epsilon$ hält oder nicht.

Dafür berechnen wir die Gödelnummer der TM $M$: Wir simulieren dann $⟨N,\epsilon ⟩$ und geben zurück $M_1(z)$

Warum verhält sie sich wie eine Sprache, die nicht in der Sprache ist?!

Sie akzeptiert keine Eingabe z. Warum? Weil sie imemr davor erstmal eine Eingabe und Berechnung durchführt die nicht beenden wird (also sie ist endloos!) –> Dadurch wird niemals $M_1(z)$ berechnet!!

Bemerkung | Aussage von Theorem von Rice

[!Feedback] Aussage des Theorems

Das Theorem von Rice sagt uns jetzt folgend zwei Dinge aus:

welche zwei Aussagen können wir treffen, welche nicht? #card

$$\text{ semantisch }\wedge \text{ nicht-rivial}⟹\text{ unentscheidbar!}$$

Aber es gilt nicht die Umkehrung, also: $$\text{ unentscheidbar}/⟹\text{ semantisch}\wedge \text{ nicht-trivial}$$

Es gibt unterscheidbare Sprachen, die nicht semantisch sind.

Es gilt hier eher “selbst semantische Sprachen sind unentscheidbar!” –> Alles was mit Implementierung zu tun hat - etwa kürzestes Programm möglich - ist tendenziell noch schwieriger

Ganz viele Eigenschaften von TMs sind eher eine Frage der Eigenschaft der Maschine, nicht den Sprachen selbst, sind unentscheidbar, außer triviale!

Die Aussage von Rice ist eine Aussage über $R$ –> Alle entscheidbare Sprachen und deren Eigenschaften sind trivial.

Wir haben aber eine ABbidlungsreduktion benutzt. Wir wissen, dass man damit auch Abbildungen auf größere Mengen machen kann –> Können wir auch was über $RE$ sagen, nicht nur $R$?

Der Satz von Rice sagt, dass alle entscheidbaren Eigenschaften ($\in R$) von TMs trivial sind.

Geht ein analoger Satz/Beweis auch für die semi-entscheidbaren Eigenschaften (∈ RE) von TMs?

Ja! ( Satz von Rice–Shapiro: Jede semi-entscheidbare Eigenschaft von TMs ist durch eine endliche Teilmenge der TMs charakterisierbar.)

Konsequenzen

Wir können eine TM nicht anschauen, und sagen, ob sie gleich einem endlichen Automaten ist oder nicht ! Obwohl das einfach scheint!

Wir können nicht erkennen, ob mein Laptop eine Waschmaschine ist oder nicht!

[!Satz]

Die Eigenschaft $p(⟨M⟩)=(L(M)\in REG)$ ( oder auch $L(M)=CFL$) ist nicht entscheidbar

warum folgt das? Wie beweisen wir das etwa? #card

Wir werden herausfinden, dass $p$ semantisch und nichtrivial ist!, denn

• Es gibt rekursiv auzählbare Sprachen $L_1\in REG$ und es gibt auch rekursiv aufzählbare Sprachen $L_{0}elmeREG$ –> Hatten wir schon 112.06_nicht_reguläre_Sprachen 112.03_reguläre_sprachen
• Die Eigenschaft ist dann per Definition semantisch!

Und weil wir obig gerade gezeigt haben, dass etwas mit diesen beiden Parametern nicht entscheidbar ist –> ist die Frage das auch nicht!

Das hat dann tatsächlich praktische Implikationen!

• Es ist unentscheidbar ob ein bestimmtes Problem mit endlichem Speicher gelöst werden kann
• Es kann also keine allgemeine Routine geben, die entscheidet, ob eine TM irgendwann “Memory-Overflows” produzieren würde -> gibt es eine Schranke auf dem Band?!
• Allgemeine Verifikation von Programmen ist nicht möglich!

Folgerung für Realität:

Wenn wir Computer so schlecht verstehen, können wir uns dann überhaupt noch erlauben, sie für sicherheitskritische Aufgaben (Autopilot, Kraftwerkssteuerung, …) einzusetzen?

• Der Satz von Rice ist eine Worst-Case Aussage: Unter allen TMs gibt es solche deren Eigenschaften wir nicht berechnen können. Aber natürlich gibt es Computerprogramme (also Untermengen der TMs), für die wir bestimmte, auch nichttriviale semantische Eigenschaften zeigen können.

• Erinnerung: Wort-, Leerheits-, Endlichkeits-, …, -Problem von FAs sind entscheidbar (Vorlesung 6).112.03_reguläre_sprachen

• Deshalb ist Software Verifikation natürlich dennoch eine Disziplin. Aber sie ist nur möglich wenn wir das Rechenmodell (und damit die Programmiersprache) einschränken!

• Frage: Warum funktioniert unser Beweis nicht mehr, wenn wir das Rechenmodell auf eine Teilmenge der TMs einschränken?

Beweistechniken für Berechenbarkeit

Wie beweisen wir, ob eine Sprache rekursiv aufzählbar ist oder wie eine nicht rekursiv aufzählbar ist.

Rekursiv aufzählbar zeigen

Auch: “Probleme, deren Lösung man hinschreiben kann”

meist kann man die konstruktiv lösen und so zeigen, wie man sie eventuell strukturieren kann

[!Example]

Beispiel dazu: $$L=\{w\in \{a,b,c{\}}^{\ast }\mid w=a^n{b}^n{c}^n\text{ fu¨r beliebiges, endliches }n\in \mathbb{N}\}$$

Wie würde man das jetzt beweisen? #card

Beweistechnik hierfür:

1. konstruiere explizit die TM, die das Problem entscheiden kann
2. Hier wäre das etwa: Beginne bei $a$, zähle dann bis zum ersten $b$, dann bis zum ersten $c$. W
3. Wenn hier irgendwo was unerwartetes steht, verwerfen wir sofort. Sonst akzeptieren wir nach genau $3n$ Schritten!

Rekursiv aufzählbar aber nicht entscheidbar

[!Definition]

Auch: “Probleme, die man manchmal aber nicht immer entscheiden kann”

Wir wollen diese Probleme jetzt beweisen / lösen:

Das macht man meist in zwei Schritten:

welche zwei Schritte durchlaufen wir dabei? #card

zuerst zeigen, dass sie aufzählbar sind.

–> Dafür zeigen, wir dass Wörter in der Sprache akzeptiert werden (müssen aber noch zeigen, dass sie nicht entscheidbar ist!) ( alo $\notin R\wedge \in RE$!)

Das können wir durch eine Reduktion umsetzen. Dabei nimmt man meist eine Abbildung zu einer Sprache, wo man weiß, dass sie garantiert nicht entscheidbar ist!

(etwa, dass die TM erst auf dem leeren Wort läuft und danach die ursprüngliche Sache betrachtet).

Alternativ kann man versuchen das Diagonalargument von Cantor wieder verwenden

Damit kann man dann ganz explizit konstruieren, wann diese Sprache entscheidet –> Dann, wenn die reduzierte Variante $w\in L$ hat ( auch wenn es vielleicht nicht entscheidet!)

Und gleichzeitig hat man das “Problem” einbezogen, dass u.U. auch einfach nicht entscheidbar sein könnte –> weil es niemals hält etwa

[!example] Beispiel

Sei jetzt $H=\{⟨M,w⟩\mid M\text{ ha¨lt auf }w\}$

Sei jetzt entsprechend $⟨M,w⟩$ gegeben –> ist das dann in $H$ ?

wie könnten wir das etwa beweisen? #card

Ansatz:

• Simuliere $M$ auf $w$. Wenn jetzt $⟨M,w⟩\in H$ , dann hält die Situation in einem akzeptierenden Zustand (top!)
• Das können wir $\forall ⟨M,w⟩$ realisiern! und somit $\approx H\in RE$!

Aber Wenn jetzt $⟨M,w⟩\notin H$, dann hält die Simulation nie an und wir können auch niemals verwerfen! –> Damit folgt $\approx H$ ist vermutlich nicht entscheidbar $\notin R$ (das geht aber nicht) –> man könnte ja einen besseren algorithmus haben… (sodass er nicht mehr anhählt)

Besser 112.17_reduktionen!!

Wir definieren eine Reduktion vom Halteproblem zur Sprache: $$A_{TM}{⪯}_{}H$$ mit: $A_{TM}=\{⟨M,w⟩\mid M\text{ ist der Code einer TM, der w akzeptiert}\}$ –> alternativ auch das Diagonalargument selbst! –> Angenommen sie ist entscheidbar, dann könnte man damti die Tabelle $h)⟨M_i,⟨M_j⟩⟩$ also eine TM, die als Eingaben verschiedene Turingmaschinen finden / erkennen. –> Dann kann man hier einen Widerspruch erzeugen und somit auh damit argumentieren!

nicht Aufzählbare Sprachen

[!Definition]

mit nicht aufzählbaren Sprachen, meinen wir solche, die $\notin RE$!

Auch “Probleme, bei denen jedes einzelne Element nicht entscheidbar ist”

Wie kann man solche Probleme zeigen? #card

Das kann man durch eine doppelte Reduktion umsetzen –> von Ursprung in das Halteproblem und dann auf $TOT$ reduzieren.

[!Example] Beispiel mit $TOT$:

Wir betrachten nochmal die Sprache $TOT=\{⟨M⟩\mid M\text{ ha¨lt auf jeder Eingabe}\}$

wie könnten wir das angehen und bearbeiten? #card

• Sei $⟨M⟩$ gegeben. Ist dann jetzt $⟨M⟩\in T$?!

Ansatz: Probiere $M$ nacheinander auf allen Worten $w$ aus.

(wir sehen, dass schon dieser Test für einen einzelnen Input $⟨M⟩$) niemals fertig wird –> niemals einen akzeptierenden Zustand erreicht ( weil wir halt Wörter haben können, wo sie nicht hält und eewig brauch) (also kein Ansatz für den Beweis!)

Alternativ:

1. Doppelte Reduktion umsetzen, von $H_0{⪯}_{}TOT\wedge H_0^C{⪯}_{}TOT$
2. Alternativ auch wieder das Diagonalargument
3. Angenommen $TOT$ sei aufzählbar. Dann müssen wir zeigen, dass es dann eine entscheidbare Sprache also $\in TOT$ gibt, die in der Aufzählung von $TOT$ nicht vorkommt (Sipser, Aufgabe 4.30)

Weitere Betrachtungen

• 112.19_unentscheidbare_probleme