Semantik: Speicher

Speicher der Maschine besteht aus Registern (Zellen),
Registerinhalte sind aus $\mathbb{N}$
Register sind numeriert durch $\mathbb{N}$
es werden nur endlich viele Register benutzt
die Menge der möglichen Speicherbelegungen ist

$S:= \{s \mid s\in(\mathbb{N}\to\mathbb{N}), \{x\mid s(x)\neq 0\} \text{ist endlich} \}$.
Bsp. $s(0)=42, s(1)=10, \forall x: x\ge 2 \Rightarrow s(x)=0$.
Notation für Speicher-Änderungen: $s[x:=y]$

ist die Funktion $z \mapsto (\text{if~}z=x\text{~then~}y\text{~else~}s(z))$.
Bsp: $s[1:=8](1)=\dots, s[1:=8](2)=\dots$
Ü: gilt $s[a:=b][c:=d] = s[c:=d][a:=b]$ ?

Syntax: Befehle und Programme

Menge $B$ der Befehle:

Inc $(\mathbb{N})$, Dec $\mathbb{N}$, Goto $(\mathbb{N})$, GotoZ $(\mathbb{N}\times\mathbb{N})$, Stop.
Menge $P$ der Programme $= B^*$ (Folge von Befehlen)

Bsp. für ein Programm:

[GotoZ 1 5,Dec 1,Inc 0,Inc 0,Goto 0,Stop]

Semantik: Befehle

Konfigurationsmenge $C\subset\mathbb{N}\times S$

erste Komponente ist Befehlszähler (enthält die Nr. des nächsten auszuführenden Befehls)
Übergangsrelation des Programms $p$ ist $\operatorname{step}_p\subseteq C\times C$

$((l,s),(l',s'))\in\operatorname{step}_p$, falls $l < |p|$ und …
- wenn $p_l = \text{Inc}(i)$, dann $l'=l+1 ,s' = s[i:=s(i)+1]$
- wenn $p_l = \text{Dec}(i)$, dann …
- wenn $p_l=\text{Goto}(k)$, dann …
- wenn $p_l=\text{GotoZ} (i,k)$, dann:
  
  wenn $s(i)=0$, dann $\dots$ sonst $\dots$
Satz: Die Relation $\operatorname{step}_p$ ist eine partielle Funktion.

Semantik: Programme

initiale Konfigur. $I(x)$ mit Eingabe $x=(x_1,\ldots,x_n)\in \mathbb{N}^n$:

ist $(0,s)$ mit $s(1)=x_1,\ldots,s(n)=x_n, s(i)=0$ sonst
finale Konfiguration

$(l,s)$, wobei $l<|p| \wedge p_l=\text{Stop}$
die Ausgabe $O(l,s)$ einer Konfiguration ist $s(0)$
Programm $P$ berechnet die partielle Funktion $f:\mathbb{N}^n\hookrightarrow \mathbb{N}$.

Es gilt $(x,y) \in f$ gdw.
- $(I(x),F) \in\operatorname{step}_p^*$ und $F$ ist final und $y=O(F)$
Jede solche part. Fkt. nennen wir Goto-berechenbar
Die Menge dieser Fkt. nennen wir GOTO

Ü: ein $p$, das die Funktion $b(x_1)=42$ berechnet?
Ü: die Semantik des leeren Programms (mit $|p|=0$) ist?

Ein Programm für $x\mapsto 2x$

[GotoZ 1 5,Dec 1,Inc 0,Inc 0,Goto 0,Stop]

wirklich? glauben wir das? nein. wir beweisen:

das Programm hält für jede Eingabe (vgl. Def. $\operatorname{step}_p^*$)
die Ausgabe ist korrekt

wir ordnen jeder Konfiguration $(l,s)$ zu:

die Invariante $s(0)+2\cdot s(1)$
die Schranke $s(1)$

und zeigen (für die Teilfolge aller Konfig. mit $l=0$):

die Invariante ist: 1. anfangs wahr, 2. invariant,
3. schließlich nützlich.
die Schranke nimmt ab (um wieviel?) und bleibt $\ge 0$.

Elementare goto-berechenbare Fkt.

diese Funktionen sind goto-berechenbar:

jede konstante Funktion
die identische Funktion
jede Projektion $(x_1,\ldots, x_n)\mapsto x_k$
die Addition
die schwache Subtraktion $(x_1,x_2)\mapsto\max(0,x_1-x_2)$, Notation: $x_1\dotdiv x_2$

Abschluß-Eigenschaften

wenn $f:\mathbb{N}\to\mathbb{N}$ und $g:\mathbb{N}\to\mathbb{N}$ goto-berechenbar sind,

dann auch $x\mapsto f(g(x))$.

Beweis:

Programm für $g$; $R_1:=R_0; R_0 := 0$; Programm für $f$.

Ü: warum $R_0 := 0$?
wenn $f:\mathbb{N}^2 \to\mathbb{N},g_1,g_2:\mathbb{N}\to\mathbb{N}$ goto-berechenbar sind,

dann auch $x\mapsto f(g_1(x),g_2(x))$.

einfach Programm für $g_1$, Programm für $g_2$, …? Nein.

Zusammenfassung GOTO (bis jetzt)

formalisiert maschinennahe imperative Programmierung

(Programmausführung als Folge von Speicherzustandsänderungen)
der Befehlssatz ist klein, die Ausdruckskraft scheint gering, aber immerhin …
gewisse einfache Funktionen sind in GOTO
GOTO ist abgeschlossen bzgl. gewisser Operatoren

später werden wir sehen

die Ausdruckskraft ist tatsächlich sehr hoch,

GOTO $=$ Java-berechenbar $=$ …

Übungsaufgaben

GOTO-Programme für elementare Funktionen: in Olat/Autotool ausprobieren. (Ggf. Highscore-Wertung für kurze Programme.)
Ü: gilt $s[a:=b][c:=d] = s[c:=d][a:=b]$ ?
Beweisen Sie: die Relation $\operatorname{step}_p^*\cap \{(C_1,C_2)\mid C_2 \text{ist final}\}$ ist eine partielle Funktion.

(Dabei Wdhlg. Begriffe und Notation für Relationen und partielle Funktionen.)
Sei $A$ die Menge der partiellen Fkt., die durch ein Goto-Programm berechnet werden können, in dem der Befehl Goto nicht vorkommt. Beweisen Sie $\text{GOTO} = A$.

Das sind zwei Inklusionen, die eine ist trivial, für die andere übersetzen Sie einen unbedingten in einen bedingten Sprung.
Sei $B$ die Menge der partiellen Fkt., die durch ein Goto-Programm berechnet werden können, in dem der Befehl GotoZ nicht vorkommt (m.a.W., nur unbedingte Sprünge),

Geben Sie ein Verfahren an, das entscheidet, ob ein $B$-Programm eine totale Funktion berechnet.
Sei $C$ die Menge der partielle Ftk., die durch ein Goto-Programm berechnet werden können, in dem weder Goto noch GotoZ vorkommen (m.a.W., die Geradeaus-Programme).

Welche Geradeaus-Programme berechnen totale Funktionen?

Beweisen Sie $B=C$. (zwei Inklusionen, d.h. zwei Compiler)

Strukturierte Programmierung

Motivation

Goto-Programme sind flach (Listen von Befehlen), haben keine sichtbare Struktur. Das ist gut für die Hardware, schlecht für den Programmierer.

Struktur $=$ Hierarchie $=$ Bäume.

Programme sind ab jetzt Bäume. (entspricht etwa dem Schritt von Assembler/Fortran zu Algol, $\approx$ 1960)

NB: Das ist immer noch imperative Programmierung, deswegen immer noch schlecht für den Programmierer (weil die Semantikdefinition einen Maschinenzustand benutzt, den man im Programm nicht sieht).

Ausweg: funktionale Programmierung (kein Zustand).

Syntax

Menge der While-Programme $P$

elementare: $\operatorname{\textsf{Inc}}\mathbb{N}$, $\operatorname{\textsf{Dec}}\mathbb{N}$, leeres Programm: $\operatorname{\textsf{Skip}}$
zusammengesetzte:
- Nacheinander: $\operatorname{\textsf{Seq}}(P\times P)$
- Verzweigung: $\operatorname{\textsf{IfZ}}(\mathbb{N}\times P\times P)$
- Schleife: $\operatorname{\textsf{While}}(\mathbb{N}\times P)$
(kein Stop, kein Goto)

Beispiel:

$\operatorname{\textsf{While}}(1,\operatorname{\textsf{Seq}}(\operatorname{\textsf{Dec}}(1),\operatorname{\textsf{Inc}}(0)))$.
autotool-Syntax: While 1 (Seq (Dec 1) (Inc 0))

Semantik (Prinzip, elementare Prog.)

Semantik eines Programms $p\in P$

ist Relation (genauer: partielle Funktion) $\operatorname{sem}_p\subseteq S\times S$ auf Speicherbelegungen.

das ist big step semantics (ein Schritt!)

beachte: es gibt keinen program counter, diese Rolle übernimmt der Index $p$.

Semantik für elementare Programme: $\operatorname{sem}_p(s_1,s_2)=$

$p=\operatorname{\textsf{Skip}}\wedge s_1=s_2$
oder $p=\operatorname{\textsf{Inc}}(i) \wedge s_2=s_1[i:=s_1(i)+1]$
oder $p=\operatorname{\textsf{Dec}}(i) \wedge s_2=s_1[i:=\max(0,s_1(i)-1)]$
oder …(nächste Folie)

Semantik für zusammengesetzte Prog.

$\operatorname{sem}_p(s_1,s_2) = \dots$

oder $p=\operatorname{\textsf{Seq}}(p_1,p_2) \wedge$ $\exists s': \operatorname{sem}_{p_1}(s_1,s')\wedge\operatorname{sem}_{p_2}(s',s_2)$.
oder $p=\operatorname{\textsf{IfZ}}(i,p_1,p_2) \wedge$

($s_1(i)=0 \wedge \operatorname{sem}_{p_1}(s_1,s_2)$ oder $s_1(i)>0 \wedge \operatorname{sem}_{p_2}(s_1,s_2)$)
oder $p=\operatorname{\textsf{While}}(i,q) \wedge$

($s_1(i)=0 \wedge s_1=s_2$ oder $s_1(i)>0\wedge \operatorname{sem}_{\operatorname{\textsf{Seq}}(q,p)}(s_1,s_2)$)

Notation $p\cong q \iff \operatorname{sem}_p=\operatorname{sem}_q$. — Ü: Satz

$\operatorname{\textsf{Seq}}(\operatorname{\textsf{Skip}},p) \cong p \cong \operatorname{\textsf{Seq}}(p,\operatorname{\textsf{Skip}})$
$\operatorname{\textsf{Seq}}(\operatorname{\textsf{Seq}}(p,q),r) \cong \operatorname{\textsf{Seq}}(p,\operatorname{\textsf{Seq}}(q,r))$
$\operatorname{\textsf{While}}(i,p)\cong \operatorname{\textsf{IfZ}}(i,\operatorname{\textsf{Skip}},\operatorname{\textsf{Seq}}(p,\operatorname{\textsf{While}}(i,p)))$

Ü: $\operatorname{\textsf{IfZ}}$ wird gar nicht benötigt, da man es simulieren kann.

While-berechenbare Funktionen

initiale Speicherbelegung $I(x)$ für Eingabe $x\in\mathbb{N}^n$:

$s(i)=$ wenn $1\le i\le n$, dann $x_i$, sonst $0$.
Programm $p$ berechnet partielle Funktion $f:\mathbb{N}^n\hookrightarrow \mathbb{N}:$

$\forall x\in\mathbb{N}^n: f(x)=y \iff\exists s: \operatorname{sem}_p(I(x),s) \wedge y=s(0)$.
jede so berechenbare partielle Fkt. heißt While-berechenbar.

Übungsaufgaben:

die üblichen elementaren Funktionen sind $\in\operatorname{\textsf{WHILE}}$
$\operatorname{\textsf{WHILE}}$ ist abgeschlossen unter Substitution

Bsp: $f,g\in\operatorname{\textsf{WHILE}}\Rightarrow (x\mapsto f(g(x))\in\operatorname{\textsf{WHILE}}$

Ein Interpreter für $\operatorname{\textsf{WHILE}}$

Interpreter realisiert Semantik. Echter autotool-Quelltext:

https://gitlab.imn.htwk-leipzig.de/autotool/all0/blob/master/collection/src/While/Step.hs

Konfiguration $c=(t,m)$ enthält

$t$ (todo): Liste (Keller) von Programmen
$m$ (memory): Speicherbelegung

mit der Bedeutung: wenn $t=[p_1,\ldots,p_n]$, dann ist $S(t):=\operatorname{\textsf{Seq}}(p_1,\ldots,\operatorname{\textsf{Seq}}(p_n,\operatorname{\textsf{Skip}})\dots)$ noch auszuführen.

Relation (small-step semantics) $\to$ auf Konfigurationen.

Spezifikation (Korrektheit): $\operatorname{sem}_{S(t)}(i,f) \iff$ $\left(|t|=0\wedge i=f\right) \vee \left(\exists t', m: (t,i)\to(t',m) \wedge \operatorname{sem}_{S(t')}(m,f) \right)$

es soll gelten: Satz: $\operatorname{sem}_p(i,f)\iff ([p],i)\to^*([],f)$

Beziehungen zw. Goto- und While-B.

Satz (Ziel): für jede part. Fkt. $f$ gilt:

$f$ ist while-berechenbar $\iff$ $f$ ist goto-berechenbar.
äquivalent, kürzer: $\operatorname{\textsf{WHILE}}=\operatorname{\textsf{GOTO}}$

praktisches Argument für $\Rightarrow$: das macht jeder Compiler (etwa von C nach Assembler/Maschinensprache)

Beweis (Ideen): folgen.

(Wenn man das genau macht, dann heißt die Vorlesung Compilerbau)

Von While zu Goto (Prinzip)

wir schreiben den Übersetzer:

$\operatorname{\textsf{compile}}:\mathbb{N}\times\operatorname{\textsf{WHILE}}\to \mathbb{N}\times \operatorname{\textsf{GOTO}}$

wobei $\operatorname{\textsf{compile}}(a,p)=(e,q)$ bedeutet:

das Programm $p\in\operatorname{\textsf{WHILE}}$ wird übersetzt
in ein äquivalentes Programm $q\in\operatorname{\textsf{GOTO}}$,
das auf Adresse $a$ beginnt
und auf $e-1$ endet (d.h. $e=a+|q|$)

dabei bedeutet Äquivalenz:

$\forall p\in\operatorname{\textsf{WHILE}},a\in\mathbb{N}:$ sei $(e,q)=\operatorname{\textsf{compile}}(a,p)$,

dann $\forall s_1,s_2: \operatorname{sem}_p(s_1,s_2) \iff \operatorname{step}_q^*((a,s_1),(e,s_2))$

Von While zu Goto (elementar, Seq)

einfache Programme:

$\operatorname{\textsf{compile}}(a,\operatorname{\textsf{Skip}})=(a,[])$
$\operatorname{\textsf{compile}}(a,\operatorname{\textsf{Inc}}(i))=(a+1,[\operatorname{\textsf{Inc}}(i)])$.
$\operatorname{\textsf{compile}}(a,\operatorname{\textsf{Dec}}(i))=(a+1,[\operatorname{\textsf{Dec}}(i)])$.

zusammengesetzte:

$\operatorname{\textsf{compile}}(a,\operatorname{\textsf{Seq}}(p_1,p_2)) =$

sei $(m,q_1)=\operatorname{\textsf{compile}}(a,p_1)$ und $(e,q_2)=\operatorname{\textsf{compile}}(m,p_2)$,

dann $(e,q_1\circ q_2)$.

Von While zu Goto (IfZ)

Ansatz:

compile (_, IfZ i p1 p2) =>
  A: GotoZ i M
     compile (_, p2) ; 
     Goto E ; 
  M: compile (_, p1); 
  E:

Realisierung:

compile (a, IfZ i p1 p2) = 
  let (h,q2) = compile (a+1,p2)
      (e,q1) = compile (h+1,p1)
  in  (e,   [GotoZ i (h+1)] ++ q2 
         ++ [Goto e] ++ q1)

Von While zu Goto (While)

Ansatz:

compile (_, While i p) =>
  A: GotoZ i E
     compile (_, p) ; 
     Goto A ; 
  E:

Realisierung:

compile (a, While i p) = 
  let (h,q) = compile (a+1,p)
      e = h+1
  in  (e, [GotoZ i e] ++ q ++ [Goto a]

Von While zu Goto (insgesamt)

Satz: Für jedes While-Programm $p$ existiert ein Goto-Programm $q$, das dieselbe partielle Funktion berechnet wie $p$.

(äquivalente Formulierung: $\operatorname{\textsf{WHILE}}\subseteq\operatorname{\textsf{GOTO}}$)

Beweis(plan):

$q=\operatorname{\textsf{compile}}(0,p) \circ[\operatorname{\textsf{Stop}}]$
Aussage folgt aus Korrektheit bzgl. der Spezifikation

$\forall p\in\operatorname{\textsf{WHILE}},a\in\mathbb{N}:$ sei $(e,q)=\operatorname{\textsf{compile}}(a,p)$,

dann $\forall s_1,s_2: \operatorname{sem}_p(s_1,s_2) \iff \operatorname{step}_q^*((a,s_1),(e,s_2))$

https://gitlab.imn.htwk-leipzig.de/autotool/all0/blob/master/collection/src/Compiler/While_Goto.hs

Von Goto zu While

das scheint schwieriger:

goto-Programm $=$ Spaghetti-Code,
while-Programm $=$ strukturierter Code.

Es geht aber, und das erzeugte While-programm hat eine ganz besondere (einfache) Struktur, die später noch ausgenutzt wird (Kleene-Normalform-Thm)

Von Goto nach While: Ansatz

Eingabe: goto-Programm $p$,
Ausgabe: äquivalentes While-program $q$

bestimme $c=$ das erste in $p$ nicht benutzte Register, das verwenden wir als PC. Das nächste Register $h$ verwenden wir zum Anhalten.

Struktur von $q$ ist:

Inc h;
While (h) {
  if (c == 0) { ... } else {
    if (c == 1) { ... } else {   
      if (c == 2) { ... } else { 
        ..                  else Skip
}

Von Goto nach While: Einzelheiten

für Befehl $p_i$ erzeuge: if (c==i) q_i else mit $q_i=$

wenn $p_i\in\{\operatorname{\textsf{Inc}}r,\operatorname{\textsf{Dec}}r\}$, dann $[p_i , \operatorname{\textsf{Inc}}c]$
wenn $p_i=\operatorname{\textsf{Stop}}$, dann $[\operatorname{\textsf{Dec}}h]$
wenn $p_i=\operatorname{\textsf{Goto}}(l)$, dann $[c:=l]$,
wenn $p_i=\operatorname{\textsf{GotoZ}}(r, l)$, dann IfZ r (c := l) (Inc c)

Ü: zeige: $p$ erreicht $\operatorname{\textsf{Stop}}$ $\iff$ $q$ hält.

beachte dabei auch den Fall $\operatorname{\textsf{Goto}}l$ mit $l\ge |p|$

Ü: hier wird if(c==i) und $c:=l$ benutzt,
das kann man jeweils mit While implementieren,
geht hier aber auch ohne Schleife, warum?

https://gitlab.imn.htwk-leipzig.de/autotool/all0/blob/master/collection/src/Compiler/Goto_While.hs

Das Normalform-Theorem für While

Vorige Konstruktion zeigt den Satz:

zu jedem Goto-Programm gibt es ein äquivalentes While-programm ($\operatorname{\textsf{GOTO}}\subseteq\operatorname{\textsf{WHILE}}$)
mit genau einem While.

zusammen mit $\operatorname{\textsf{WHILE}}\subseteq\operatorname{\textsf{GOTO}}$ folgt

$\operatorname{\textsf{WHILE}}=\operatorname{\textsf{GOTO}}$
zu jedem While-Programm gibt es ein äquivalentes While-Programm mit genau einem While.

äquivalent$=$ berechnet dieselbe partielle Funktion.

Ü: wie unterscheiden sich die Laufzeiten?

Garantierte Termination: Loop

Motivation

$\operatorname{\textsf{While}}(i,q)$ bedeutet: solange $s(i)>0$ ist, $q$ ausführen
es gibt While-Programme, die nicht für jede Eingabe terminieren (es gibt $f\in\operatorname{\textsf{WHILE}}$ mit $f$ nicht total)
$\operatorname{\textsf{Loop}}(i,q)$ bedeutet: $q$ genau $s(i)$ mal ausführen

(der Wert von $i$ vor Beginn der Schleife)
Loop-Programme terminieren (jede $f\in\operatorname{\textsf{LOOP}}$ ist total)

das ist softwaretechnisch nützlich
aber auch eine Einschränkung:

es gibt $f\in(\operatorname{\textsf{WHILE}}\cap\operatorname{\textsf{TOTAL}}) \setminus\operatorname{\textsf{LOOP}}$

Loop-Programme

Syntax und Semantik wie While-Programme, außer:

(Syntax) kein While(i,q), sondern Loop(i,q)
(Semantik) wenn $p=\operatorname{\textsf{Loop}}(i,q)$, dann $\operatorname{sem}_p(s_1,s_2) = \operatorname{sem}_q^{s_1(i)}(s_1,s_2)$

der Befehl $q$ wird genau $s_1(i)$ mal ausgeführt (der Wert von $i$, wenn die Schleife zu erstenmal betreten wird — egal, was später mit $i$ passiert)

Jede so berechenbare Fkt. heißt loop-berechenbar.

Die Menge der loop-berechenbaren Fkt. heißt $\operatorname{\textsf{LOOP}}$.

Bsp: Addition, Subtraktion, Multiplikation, Potenz,

$n\mapsto n$ ist gerade, $n\mapsto n$ ist Quadratzahl, $n\mapsto n$ ist prim,…

Loop-Programme und Softwaretechnik

bei Loop(i,q) wird $q$ genau $s_1(i)$-mal durchlaufen
so realisiert in der Sprache Ada (http://www.adaic.org/resources/add_content/standards/12rm/html/RM-5-5.html)

A loop parameter is a constant; it cannot be updated…
```
for X in 0 .. 10 loop  P;  end loop;
```
Iteration (Induktion) über (Peano-)Zahlen (Strichlisten)
verallgemeinert auf andere (strukturierte) Datentypen: Rekursiosmuster (fold), Entwurfsmuster Iterator

(besucht jedes Element genau einmal)

Java: for (E x : c) { .. }, C#: foreach

LOOP und WHILE

$\operatorname{\textsf{LOOP}}\subseteq\operatorname{\textsf{WHILE}}\cap\operatorname{\textsf{TOTAL}}$ (Beweis: Übung)
$\operatorname{\textsf{WHILE}}\cap\operatorname{\textsf{TOTAL}}\not\subseteq\operatorname{\textsf{LOOP}}$. Beweis:
- $L_0,L_1,\dots$ längen-lexikografische Aufzählung aller LOOP-Programme, die einstellige Fkt. berechnen,
  
  diese Fkt. sind $f_0,f_1,\ldots$
- für $d: x\mapsto f_x(x)+1$ gilt: $d\in\operatorname{\textsf{WHILE}}\cap\operatorname{\textsf{TOTAL}}$
  
  Begründung: Interpreter für LOOP-Programme
- dieses $d$ hat keinen $L$-Index (also $d\notin\operatorname{\textsf{LOOP}}$)
  
  Begründung: falls doch $d = f_i$, dann betrachte $d(i)$.
eine arithmetische Funktion $f \in\operatorname{\textsf{WHILE}}\cap\operatorname{\textsf{TOTAL}}\setminus \operatorname{\textsf{LOOP}}$: die Ackermann-Funktion

Die Ackermann-Funktion

$A:\mathbb{N}^2\to\mathbb{N}$

$A(0,y)=y+1; A(x+1,0)=A(x,1);$

$A(x+1,y+1)=A(x,A(x+1,y))$
bestimme $A(2,4), A(3,3), A(4,2)$
Satz: $\forall f\in\operatorname{\textsf{LOOP}}\exists x: \forall \vec{y}: f(\vec{y})\le A(x,\max_i\vec{y}_i)$

folgt aus
Lemma: (Bezeichnung $\max s := \max\{s(i)\mid i\in\mathbb{N}\}$ )

$\forall p\in\operatorname{\textsf{LOOP}}\exists x: \forall (s_1,s_2)\in\operatorname{sem}_p: A(x,\max s_1)\ge \max s_2$

Beweis durch Induktion über Programmtexte

Eigenschaften der Ackermann-Funktion

(…, die im Beweis des Lemmas benötigt werden)

für $p=\operatorname{\textsf{Inc}}(i)$: (Übung)
für $p=\operatorname{\textsf{Seq}}(p_1,p_2)$ betrachte Zustände $s_1\stackrel{\operatorname{sem}_{p_1}}{\longrightarrow} s' \stackrel{\operatorname{sem}_{p_2}}{\longrightarrow} s_2$

und nach Induktion $A(x_1,m_1)\ge m', A(x_2,m')\ge m_2$.

Gesucht ist für jedes $x_1,x_2$
ein $x$ mit $\forall y: A(x,y)\ge A(x_1,A(x_2,y))$.

Wir können $x=x_1+x_2+2$ wählen

(Beweis: Übung. Benötigt $A(x,y+1)\le A(x+1,y)$)
für $p=\operatorname{\textsf{Loop}}(i,q)$: Welche Eigenschaft wird benötigt? (Ü)

Übung KW 47

Aufgaben zu While- und Loop-Programmen in autotool
Sei $W_{\textsf{Syn}}$ die Menge der While-Programme, in denen $\operatorname{\textsf{IfZ}}$ nicht vorkommt, und $W_{\textsf{Sem}}$ die Menge der durch solche Programme berechenbaren partiellen Funktionen.

Zeigen Sie $W_{\textsf{Sem}}=\operatorname{\textsf{WHILE}}$.
Zeigen Sie für einstellige partielle Funktionen:

$f,g\in\operatorname{\textsf{WHILE}}\Rightarrow (x\mapsto f(g(x)))\in\operatorname{\textsf{WHILE}}$.
Zur Kompilation von Goto nach While:
1. Zeigen Sie: $p$ erreicht Stop $\iff$ $q$ hält
2. Es werden if (c==i) und c := l benutzt, das kann man im Allgemeinen mit While implementieren (wie?) geht aber hier auch ohne Schleife (wie?)
3. Vergleichen Sie die Laufzeiten von $p$ und $q$.
zur Ackermann-Funktion:
1. Bestimmen Sie $A(2,4),A(3,3),A(4,2)$
2. Aufgaben auf Folie Eigensch. Ackermann

Kodierung strukturierter Daten

Motivation

In vielen Anwendungen sind Daten strukturiert (z.B. Tupel, Listen, Bäume). Goto-Programme rechnen aber nur mit Zahlen.
Satz: Das ist keine Einschränkung der Allgemeinheit, denn man kann jedes strukturierte Datum in eine einzige (mglw. große) Zahl kodieren.
wird Gödelisierung genannt (Kurt Gödel, 1906–1978)
anschauliches Argument: der Speicherinhalt eines PC ist eine Bitfolge, die kann man als Binärdarstellung einer Zahl auffassen. — exakte Argumente: folgen.

Kodierung von Zahlenpaaren

gesucht sind (goto-berechenbare) Funktionen

Konstruktor: $C:\mathbb{N}^2\to \mathbb{N}$ Destruktoren: $P_1,P_2:\mathbb{N}\to\mathbb{N}$
Testfunktion: $T:\mathbb{N}\to\{0,1\}$

mit Spezifikation (vgl. objektorientierte Datenmodellierung)

$\forall x_1,x_2: P_1(C(x_1,x_2))=x_1\wedge P_2(C(x_1,x_2)) = x_2$
$\forall x: T(x)=1 \iff \exists x_1,x_2: x=C(x_1,x_2)$

da gibt es viele verschiedene Möglichkeiten

$C(x_1,x_2)= (x_1+x_2)(x_1+x_2+1)/2 + x_1$
$C(x_1,x_2)=2^{x_1}(2x_2+1)$, $\bullet$ $C(x_1,x_2)=2^{x_1}\cdot 3^{x_2}$

Ü: jeweils $C(2,3), C(3,2), T(10), T(12), P_1(12),P_2(12)$,

Algorithmen (Loop-Programme) für $T, P_i$.

Kodierung von Listen

Kostruktor: $L:\mathbb{N}^*\to \mathbb{N}$, Destruktoren $D_i:\mathbb{N}^*\hookrightarrow \mathbb{N}$.

zwei (von vielen) Möglichkeiten:

mittels einer Paar-Kodierung $C$

L (l) = if null l then 0 
        else 1 + C (head l, L (tail l))

direkte Kodierung als Produkt von Primzahlpotenzen $L([x_0,x_2,\ldots, x_n]) = 2^{x_0+1}\cdot 3^{x_1+1}\cdot \dots \cdot p(n)^{x_n+1}$.

Ü: jeweils $L([]), L([5]), L([2,3,0])$, Algorithmus für $D_i$

Ü: die Funktion $p:n\mapsto$ die $n$-te Primzahl, also $p(0)=2, p(1)=3, p(2)=5,\dots$ ist While-berechenbar.

Ü : $p$ ist Loop-berechenbar. — Hinweis: Euklid.

Kodierung von Bäumen

Motivation

allgemein: Baum $=$ Term in einer Signatur,
Signatur: eine endlichen Menge von Funktionssymbolen mit zugeordneter Stelligkeit.
Bsp: $\Sigma=\{(f,2),(g,1),(a,0)\}$, $t = f(f(a,g(a)),a)\in\operatorname{Term}(\Sigma)$.

Notation $\text{root}(t)=f, \text{args}(t)=[f(a,g(a)),a]$.
wird u.a. benötigt, um (prädikatenlogische) Formeln als Zahlen zu kodieren.

Realisierung: $B(t) = C(\text{num}(\text{root}(t)), L([B(t_1),\ldots,B(t_k)]))$

mit $\text{args}(t)=[t_1,\ldots]$, Paar-Kodierung $C$,
Listen-Kodierung $L$, sowie Symbol-Numerierung

Ü: Kodierung für endliche Mengen von Zahlen

Universelle Programme und Halteproblem

Kodierung von Programmen

man kann mit eben gezeigten Methoden nach $\mathbb{N}$ kodieren:

Goto-Programme

(Programm ist Liste von Befehlen, Befehl ist Tupel)
Maschinen-Konfigurationen

(Paar von Zahl und Speicherbelegung, diese ist Liste (!))

Damit kann man in der Sprache GOTO
einen Interpreter für GOTO-Programme schreiben.

Ein universelles Goto-Programm

Insbesondere sind für jedes $p$ die Übergangsfunktion $\operatorname{step}_p$ sowie ihre transitive reflexive Hülle goto-berechenbar (nach Kodierung):
bei Eingabe einer Kodierung von $p$ und einer Konfig. $K$ kann die Folgekonfiguration berechnet werden und dies solange wiederholt werden, bis finale Konf. erreicht wird.
D.h. die part. Funktion $\phi:\mathbb{N}^2\hookrightarrow\mathbb{N}$ ist goto-berechenbar: $\phi_x(y)=$ die Ausgabe einer Maschine, die das Programm mit Kodierung $x$ auf Eingabe mit Kodierung $y$ ausführt.
Das Programm für $\phi$ heißt universell, denn es kann die Rechnung jedes Goto-Programms simulieren.

Das Halteproblem

Def: das (spezielle) Halteproblem ist die Menge $K_0 = \{ x \mid \phi_x(x)\downarrow \}\subseteq\mathbb{N}$.

(die Menge der Kodierungen von Programmen, die anhalten, wenn man sie auf sich selbst, d.h. ihren eigenen Code, anwendet).

Satz: die charakteristische Funktion $c_{K_0}:\mathbb{N}\to\{0,1\}$ der Menge $K_0$ ist nicht goto-berechenbar.

Beweis (indirekt): falls doch, dann gibt es ein Programm, das $c_{K_0}$ berechnet. Es gibt dann auch ein Programm

$x\mapsto$ wenn $c_{K_0}(x)=0$, dann 1, sonst $\bot$ (eine nicht haltende Rechnung).

Sei $q$ der Code dieses Programms. Ist $q \in K_0$? Gdw. $\phi_q(q)\downarrow$, gdw. $c_{K_0}(q)=0$, gdw. $q\notin K_0$.

Das Halteproblem (Folgerung)

Satz: es gibt Funktionen $\mathbb{N}\to\mathbb{N}$, die durch kein goto-Programm berechenbar sind.

Beweise: $c_{K_0}$
Def: das (allgemeine) Halteproblem ist die Menge $K=\{ C(x,y) \mid \phi_x(y)\downarrow \}$.
Satz: charakterist. Funkt. $c_K$ ist nicht goto-berechenbar.
Beweis: sonst könnte man auch $c_{K_0}$ berechnen.

Es gibt also kein allgemeines Verfahren, mit dem man entscheiden kann, ob ein Programm für eine Eingabe nach endlich vielen Schritten hält.

Diagonalisierung

schon zweimal benutzt, und kommt noch öfter:

für eine Menge $F$ von Funktionen
gibt es eine Aufzählung $f_0, f_1, f_2\ldots$
konstruiere $g: x \mapsto$ geeignete Änderung von $f_x(x)$,

so daß $g$ in Aufzählung nicht vorkommt ($\neg\exists i: g=f_i$)

Anwendungen bisher:

$F =$ die totalen berechenbaren Funktionen

$\Rightarrow$ es gibt totale nicht berechenbare Fkt.
$F =$ die partiellen berechenbaren Funktionen

$\Rightarrow$ das Halteproblem ist nicht entscheidbar

Maschinenunabhängige Berechenbarkeitstheorie

Motivation

wir haben gezeigt: $\operatorname{\textsf{GOTO}}= \operatorname{\textsf{WHILE}}$

die Syntax und Semantik (Interpreter) waren jeweils spezifisch, aber wir haben Compiler konstruiert
Verallgemeinerung (Alonzo Church, Alan Turing)

alle vernünftigen Berechenbarkeitsmodelle definieren die gleiche Klasse von partiellen Funktionen
weitere Modelle: Wortersetzung (Turing-Maschinen), funktionale Programmierung (rekursive Fkt.)

Übliche Namen für Funktionenklassen

$f:\mathbb{N}^*\hookrightarrow \mathbb{N}$ ist partiell-rekursiv, $f\in\operatorname{\text{Part}}$:

$f$ ist While-berechenbar ($=$ Goto-berechenbar

$=$ Turing-berechenbar $=$ …-berechenbar $=$ …)
$f:\mathbb{N}^*\hookrightarrow\mathbb{N}$ ist allgemein-rekursiv, $f \in \operatorname{\text{Allg}}$:

$f$ ist partiell rekursiv und total.
$f:\mathbb{N}^* \to \mathbb{N}$ ist primitiv-rekursiv, $f\in\operatorname{\text{Prim}}$:

$f$ ist Loop-berechenbar ($=$ …)

Begründung:

While-Schleife $\iff$ beliebige Rekursion
Loop-Schleife $\iff$ eingeschränkte (primitive) Rekursion

These von Church und Turing

alle intuitiv vernünftigen Berechenbarkeitsmodelle definieren die gleiche Klasse von partiellen Funktionen
ein Berechnungsmodell ist gegeben durch
- eine Tupel-Kodierung $C$
- eine universelle Funktion (Interpreter) $\phi:\mathbb{N}\times\mathbb{N}\hookrightarrow\mathbb{N}$
und bestimmt Menge von in diesem Modell berechenbaren partiellen Funktionen $M = \{ \vec{x}\mapsto \phi_p(C(\vec{x})) \mid p\in\mathbb{N}\} \subseteq (\mathbb{N}^*\hookrightarrow \mathbb{N})$
Die C-T-These kann man auffassen als empirische Aussage oder als Definition ($M$ ist vernünftig $\iff$ es gibt beide Compiler $M \leftrightarrow \operatorname{\textsf{WHILE}}$)

Ein Fixpunktsatz

Satz (Stephen Kleene, 1938): Sei $f$ total und berechenbar.
Dann gibt es ein $i$ mit $\phi_i = \phi_{f(i)}$.

Beweis:

bestimme $h$, so daß $h(x)$ ein Index für diese Funktion ist: $y \mapsto \phi_{\phi_x(x)}(y)$.
Bestimme $e$ als einen Index für $x \mapsto f(h(x))$.
Das gesuchte $i$ ist $h(e)$.

Ü: wende Satz an auf die Funktion
$f: x\mapsto$ ein Index für die konstante Funktion $y \mapsto x$.

Der Fixpunkt-Index für $f$ ist (indiziert) ein Programm,
das seinen eigenen Quelltext ausgibt.

Geht in jeder (in unserem Sinne vernünftigen) Sprache!

Der Satz von Rice

Satz: jede nichttriviale semantische Eigenschaft von Programmen ist unentscheidbar.

dabei bedeuten:

Eigenschaft: Menge $E\subseteq\mathbb{N}$ von Gödelnummern
nichttrivial: $E\neq\emptyset\wedge E\neq\mathbb{N}$
semantisch: $\forall x,y: (\phi_x=\phi_y) \Rightarrow (x\in E \iff y\in E)$

Beispiele (semantisch oder nicht?)

das Programm berechnet eine totale Funktion
$\{x\mid \dom(\phi_x)=\mathbb{N}\}$
die Länge des Programmtextes ist eine gerade Zahl
$\{x\mid \dom(\phi_x)=2\mathbb{N}\}$
die Gödelnummer ist gerade ($2\mathbb{N}$)

Der Satz von Rice (Beweis)

wähle $y\in E, n\in\mathbb{N}\setminus E$.
sei $E$ entscheidbar, d.h., $c_E$ berechenbar.

Dann ist dieses $f$ berechenbar und total:

$f:x\mapsto$ wenn $c_E(x)=1$, dann $n$, sonst $y$.
Nach Konstruktion $x\in E \iff f(x)\notin E$.
nach Fixpunktsatz gibt es $x$ mit $\phi_x=\phi_{f(x)}$.
Damit $x\in E\iff f(x)\in E$.

Busy-Beaver-Programme

vgl. Aufgabe autotool und Übung 5 zu $B_{\operatorname{\textsf{While}}}$.

ein Programm, das ziemlich lange rechnet:

Seq (Inc 1) 
  (While 1 
    (Seq (Inc 1) 
      (Seq (Inc 1) 
        (Seq (Inc 1) 
          (Seq (While 2 
                 (Seq (Dec 2) 
                   (While 1 
                     (Seq (Inc 2) 
                       (Seq (Inc 2) (Dec 1))))))
                (Inc 2))))))

für Turingmaschinen:
- Heiner Marxen, Jürgen Buntrock, Attacking the Busy Beaver 5, Bulletin of the EATCS, Number 40, February 1990, pp. 247-251 https://www.drb.insel.de/~heiner/BB/
- Pascal Michel: Historical Survey of Busy Beavers http://www.logique.jussieu.fr/~michel/ha.html

Übung KW48

Beispiel-Rechnungen (siehe Folien) zu Kodierung von Paaren, Listen, Bäumen
für die Primzahlfunktion $p$ gilt: $p\in\operatorname{\textsf{LOOP}}$.

Hinweis: $p\in\operatorname{\textsf{WHILE}}$ ist einfach, man muß jetzt zusätzlich eine Loop-berechenbare obere Schranke für $p(n)$ angeben. Diese kann großzügig sein, z.B. aus Beweis von Euklid für es gibt unendlich viele Primzahlen.
Def. $T(x,y,z):=$ die vom Goto-Programm $x$ bei Eingabe $y$ nach $z$ Schritten erreichte Konfiguration.

(genauer: $x$ ist die Kodierung des Programmtextes, $y$ ist die Kodierung des Eingabevektors, Ausgabe ist die Kodierung einer Konfiguration oder einer Fehlermeldung, falls Programm schon vorher gehalten hat)

$T$ ist Loop-berechenbar.
zur Diagonalisierung: wende das Verfahren an auf
- $F=$ alle linearen Funktionen $x\mapsto ax+b$ mit $a,b\in\mathbb{N}$, $g(x)=f_x(x)+1$
- $F=$ alle Loop-berechenbaren Funktionen, $g(x)=(f_x(x)+1) \textbf{mod} 2$
- $F= (\mathbb{N}\to\mathbb{N})$, d.h., alle Funktionen (egal, ob berechenbar), $g(x)=f_x(x)+1$.
Def. $B_{\operatorname{\textsf{While}}}(x):=$ die größte Schrittzahl aller bei leerer Eingabe haltenden While-Programme der Größe $\le x$ (vgl. autotool-Aufgabe).

Beweisen Sie: ${B_{\operatorname{\textsf{While}}}}$ ist nicht berechenbar.

Hinweis: indirekt. Wenn ${B_{\operatorname{\textsf{While}}}}$ berechenbar, dann Halteproblem entscheidbar.
Entspr. $B_{\operatorname{\textsf{Loop}}}$. Ist ${B_{\operatorname{\textsf{Loop}}}}\in\operatorname{\textsf{WHILE}}$? Ist ${B_{\operatorname{\textsf{Loop}}}}\in\operatorname{\textsf{LOOP}}$?

(Ja. Nein. Hinweis: betrachte Loop-Programm für $f : x\mapsto 1+2\cdot {B_{\operatorname{\textsf{Loop}}}}(x)$, rufe dieses geeignet auf.)
Ü-Aufgabe von Folie Fixpunktsatz.
Geben Sie ein Programm in Java (C, Haskell,…) an,
das seinen eigenen Quelltext ausgibt.

(Nur Schreiben auf Standardausgabe, keine Dateioperationen, d.h., Programm darf seinen Quelltext nicht von externem Speicher holen, sondern muß ihn selbst enthalten oder erzeugen)

Hinweis: (Garry Thompson, 1999) http://www.nyx.net/~gthompso/quine.htm
Beweisen Sie: für jedes $i\in\mathbb{N}$ gibt es unendlich viele Indizes (die Menge $E_i:= \{j \mid \phi_i=\phi_j\}$ ist unendlich)

Hinweis: $j\in E_i$ ist eine semantische Eigenschaft.

Entscheidbare Mengen, Reduktion

Motivation, Definition REC

allgemeines Ziel ist Einordnung der Schwierigkeit von Entscheidungsproblemen
nach Kodierung: Problem $=$ Teilmenge $P$ von $\mathbb{N}$

zu entscheiden ist dann, ob $x\in P$, d.h. $c_P(x)=1$
Def: $\operatorname{REC}= \{ P \mid P\subseteq \mathbb{N}, c_P \text{ist berechenbar}\}$

(Name kommt von berechenbar durch rekursive Fkt.)
Beispiele: Primzahlen $\in\operatorname{REC}$, $K_0\notin \operatorname{REC}$
konkrete Ziele:
- (Abschluß-)Eigenschaften von $\operatorname{REC}$
- Beweisverfahren für $P\in\operatorname{REC}, P\notin\operatorname{REC}$
- genauere Struktur für $2^\mathbb{N}\setminus\operatorname{REC}$

Abschlußeigenschaften von $\operatorname{REC}$

Satz ($\operatorname{REC}$ ist abgeschlossen unter Booleschen Operationen):

wenn $A,B\in \operatorname{REC}$, dann

$A\cup B \in \operatorname{REC}$
$A\cap B \in \operatorname{REC}$
$(\mathbb{N}\setminus A)\in\operatorname{REC}$

Beweis (Beispiel):

Wenn $c_A, c_B$ rekursive Fkt, dann auch $c_{A\cup B}$:
$c_{A\cup B}(x)=\max(c_A(x),c_B(x))$,
d.h. $c_{A\cup B}=\text{SUBST}(\max,c_A,c_B)$.

Reduktion $\le_m$

Zum Vergleich der algorithmischen Schwierigkeit von Probleme definiert man:

$P\le_m Q$ ($P$ ist reduzierbar auf $Q$) durch:

es existiert eine berechenbare totale Funktion $f:\mathbb{N}\to\mathbb{N}$ mit $\forall x\in\mathbb{N}: x\in P\iff f(x)\in Q$.

beachte die Richtung: $P$ ist höchstens so schwierig wie $Q$
reduzieren bedeutet: ein Entscheidungsverfahren für $P$ auf ein Verfahren für $Q$ zurückführen.
Index $m$ kommt von many-one-Reduktion

Satz: $P\le_m Q\wedge Q\in\operatorname{REC}\Rightarrow P\in\operatorname{REC}$.

Beweis: gegeben $c_Q$, konstruiere $c_P=\text{SUBST}(\dots)$

Satz (Ü): $\le_m$ ist transitiv

Anwendungen der Reduktion

Def (Wdhlg)

das allgemeine Halteproblem, $K=\{C(x,y)\mid \phi_x(y)\downarrow\}$.
das spezielle Halteproblem, $K_0=\{x\mid \phi_x(x)\downarrow\}$.

Satz: $K_0\le_m K$. Beweis: $x\in K_0\iff C(x,x)\in K$.

Folgerung: wir hatten gezeigt $K_0\notin\operatorname{REC}$, also gilt $K\notin\operatorname{REC}$.

Ü: zeige $K\le_m K_0$.

Wir bezeichen $T=\{ x \mid \phi_x \text{ist total}\}$.

Satz: $T\notin\operatorname{REC}$.

Beweis (Ü): zeige $K\le_m T$.

Betrachte dazu die 3-stellige (!) Fkt $g:(x,y,z)\mapsto \phi_x(y)$
und wende $s^2_1$ an.

Motivation, Definition RE

$K_0\notin\operatorname{REC}, T\notin \operatorname{REC}$. Sind beide Probleme gleich schwer?

Nein. $K_0$ ist rekursiv aufzählbar, $T$ ist es nicht.

Def. $P\subseteq\mathbb{N}$ heißt rekursiv aufzählbar, falls $P=\emptyset$ oder

es gibt totale berechenbare Funktion $f$ mit $P=f(\mathbb{N})$.

Im zweiten Fall ist $P=\{f(0),f(1),f(2),\ldots\}$. — Beachte:

jedes Element von $P$ kommt wenigstens einmal vor,
$f$ ist nicht notwendig injektiv (wiederholungsfrei),
$f$ ist nicht notwendig monoton.

Die Menge der rek. aufzählbaren Mengen heißt $\operatorname{RE}$.

Ü: $P\in\operatorname{RE}\wedge \text{$P$unendlich}\Rightarrow$ $P$ ist injektiv aufzählbar

Ü: $\text{$P$unendlich} \wedge$ $P$ streng monoton aufzählbar $\Rightarrow$ $P\in\operatorname{REC}$.

Eine äquivalente Charakterisierung von RE

(Wdhlg.) $P\in\operatorname{RE}$ : $P=\emptyset$ oder $\exists f\in\operatorname{\text{Allg}}: P=\rng(f)$

Satz: $P\in \operatorname{RE}\iff \exists f\in\operatorname{\text{Part}}: P=\dom(f)$

Beweis: $\Rightarrow$. $P=\emptyset$: $f$ hält niemals.

$P$ wird aufgezählt durch $g$: $f(x):=$ wenn $x$ in $g(0),g(1),\ldots$ vorkommt, dann 1. (sonst hält die Rechnung nicht.)

Beweis: $\Leftarrow$ trivial für $P$ endlich.

Tabelle mit $(x,y)$: die Konfiguration nach $y$ Schritten in der Rechnung $f(x)$ (oder Markierung, daß schon fertig).

Tabelle gemäß Kodierung von $\mathbb{N}^2$ durchlaufen.

Wenn Konfiguration $(x,y)$ final, dann $x$ ausgeben.

Anwendung: $K_0\in\operatorname{RE}$. Beweis: $K_0=\dom(x\mapsto \phi_x(x))$.

Bezeichnung (Gödelisierung for $\operatorname{RE}$) $W_x := \dom (\phi_x)$

Abschlußeigenschaften von RE

Satz (offensichtlich): $A\in\operatorname{RE}, B\in\operatorname{RE}\Rightarrow (A\cup B)\in\operatorname{RE}$.

Beweis: trivial wenn $A=\emptyset$ oder $B=\emptyset$.

Sei $f$ die aufzählende Funktion für $A$, $g$ die für $B$.

Dann $h(2n)=f(n), h(2n+1)=g(n)$.

Satz (nicht offensichtlich): $A\in\operatorname{RE}, B\in\operatorname{RE}\Rightarrow (A\cap B)\in\operatorname{RE}$.

Die Schwierigkeit ist: wenn man ein $x=f(n)\in A$ hat,
kann man nicht ausrechen, ob $x\in B$,
denn möglicherweise ist $B\notin\operatorname{REC}$.

Beweis: 2-dim. unendliche Tabelle,

In Zeile $x$, Spalte $y$ steht Zahlenpaar $(f(x),g(y))$.

Wenn …, gibt …aus.

Ü: alternativer Beweis über Def.-Bereiche

Eine Beziehung zw. RE und REC

Satz: $P\in\operatorname{RE}\wedge (\mathbb{N}\setminus P)\in\operatorname{RE} \iff P\in\operatorname{REC}$

Beweis: $\Leftarrow$ als Ü. – Für $\Rightarrow$:

trivial, wenn $P=\emptyset$ oder $P=\mathbb{N}$. — ansonsten:

Sei $f$ eine Aufzählung für $P$, $g$ eine Aufzählung für $\mathbb{N}\setminus P$.
um zu bestimmen, ob $x\in P$:
- berechne $f(0),g(0),f(1),g(1),f(2),\ldots$
- bis $x$ erscheint
diese Verfahren hält. (Beweis durch Fallunterscheidung.)

Diese Aussage in anderer Bezeichnung:

Def: $\operatorname{coRE}=\{P \mid (\mathbb{N}\setminus P) \in \operatorname{RE}\}$ Satz: $\operatorname{RE}\cap\operatorname{coRE}=\operatorname{REC}$.

Folgerung: $(\mathbb{N}\setminus K_0)\notin\operatorname{RE}$.

RE und $\le_m$

Satz: $P\le_mQ \wedge Q\in\operatorname{RE}\Rightarrow P\in\operatorname{RE}$.
Beweis (Variante 1)

$f$ die Funktion aus der Reduktion $\le_m$, $Q=\dom(\phi_i)$.

Dann $P=\dom(x \mapsto \phi_i(f(x))$.
Beweis (Variante 2 – Übung)

Sei $g$ die Aufzählung für $Q$.

(Falls existiert. Sonst $Q=\emptyset$, was dann?)

Bestimme Aufzählung für $P$ mit 2-dim unendl. Tabelle.

Was steht in Spalte $x$, Zeile $y$, was wird ausgegeben?

Ü: $K_0\not\le_m (\mathbb{N}\setminus K_0)$, $(\mathbb{N}\setminus K_0)\not\le_m K_0$

Die schwersten Probleme in RE

Def: $Q$ heißt $\operatorname{RE}$-vollständig (bzgl. $\le_m$), falls:

$Q\in\operatorname{RE}$ und $\forall P\in\operatorname{RE}: P\le_m Q$.

Satz: $K$ ist $\operatorname{RE}$-vollständig.

Beweis: Sei $P\in\operatorname{RE}$, gegeben als $\dom(\phi_i)$.

Dann $x\in P\iff x\in\dom(\phi_i)\iff \phi_i(x)\downarrow \iff C(i,x)\in K$.

Die Reduktion ($\le_m$) benutzt also die Funktion $x \mapsto C(i,x)$.

Übungen:

$P$ ist RE-vollständig $\Rightarrow$ $P\notin\operatorname{REC}$.
$P$ ist RE-vollst. $\wedge P\le_m Q \wedge Q\in\operatorname{RE}$ $\Rightarrow$ $Q$ ist RE-vollst.
definiere den analogen Begriff REC-vollständig. Welche analogen Sätze gelten? Welche Mengen sind REC-vollst? (Zu viele, deswegen ist das nicht interessant)

Übungsaufgaben

Aufgaben für Übung KW49/KW50 sind markiert.

Aufgaben mit (!) enthalten evtl. schwere Teilaufgaben. Bilden Sie sich trotzdem eine Meinung.

(KW49) $\le_m$ ist: transitiv, reflexiv?, symmetrisch? antisymmetrisch?
(KW 49) $K\le_m K_0$.

Musterlösung: die Reduktionsfunktion $f$ bildet Eingabe $x$ ab auf einen Index der Funktion $z \mapsto \phi_{P_1(x)} (P_2(x))$. Dann $x\in K\iff \phi_{P_1(x)}(P_2(x))\downarrow \iff \phi_{f(x)}(f(x))\downarrow \iff f(x)\in K_0$.
(KW 49) (!) gehören diese Mengen zu $\operatorname{REC}, \operatorname{RE}, \operatorname{coRE}$?

$\{ x\mid W_x =\emptyset\}, \{x\mid 1 = |W_x| \}, \{ x\mid W_x ~ \text{ist endlich} \}, \{ x\mid W_x ~ \text{ist unendlich} \}, \{x\mid W_x=\mathbb{N}\}, \{C(x,y) \mid W_x=W_y \},$

dabei ist $C$ eine Paar-Kodierung.
(KW 49) Definition: $A\otimes B := \{C(x,y)\mid x\in A, y\in B\}$.

Für $A,B$ in REC bzw. RE (d.h., 4 Fälle):
ist $A\otimes B$ in REC bzw. RE? (d.h., je 2 Fragen)

Musterlösung (teilw.)
- Es gilt $\forall A\in \operatorname{REC}, B\in\operatorname{REC}: A\otimes B\in \operatorname{REC}$, denn $c_{A\otimes B}(x)=c_A(P_1(x))\wedge c_B(P_2(x))$. Nach Voraussetzung sind $c_A$ und $c_B$ allgemein rekursiv, also auch $c_{A\otimes B}$.
- Es gilt nicht $\forall A\in \operatorname{RE}, B\in\operatorname{RE}: A\otimes B\in \operatorname{REC}$. Gegenbeispiel: $A=\mathbb{N}, B=K_0$. Dann gilt $K_0\le_m \mathbb{N}\otimes K_0$ mit Reduktionsfunktion $f_x\mapsto C(42,x)$. Aus $K_0\notin\operatorname{REC}$ folgt $\mathbb{N}\otimes K_0\notin\operatorname{REC}$.
- Es gibt Mengen $A\in\operatorname{RE}, B\in\operatorname{RE}\setminus\operatorname{REC}$ mit $A\otimes B\in\operatorname{REC}$. Beispiel: $A=\emptyset, B=K_0$, denn $\emptyset\otimes K_0=\emptyset\in\operatorname{REC}$
gibt es für jede $A,B\in\operatorname{RE}$ mit $A\cap B=\emptyset$
- $f\in\operatorname{\text{Part}}$ mit $f(A)=\{0\}$ und $f(B)=\{1\}$ ?
- $f\in\operatorname{\text{Allg}}$ mit $f(A)=\{0\}$ und $f(B)=\{1\}$ ?
$f:\mathbb{N}\to\mathbb{N}$ heißt Permutation, wenn $f$ bijektiv ist.

Zeige, daß die (allgemein) rekursiven Permutationen bzgl. Nacheinanderausführung eine Gruppe bilden

(…aber die primitiv rekursiven nicht)
(KW 49) Jede unendliche rek. aufzählbare Menge hat eine unendliche entscheidbare Teilmenge.

aber (!) es gibt eine unendliche Menge ohne unendliche rek. aufzählbare Teilmenge.
(KW 50)
- $\{ x\mid W_x ~ \text{ist unendlich} \} \equiv_m \{ x\mid W_x = \mathbb{N}\}$
  
  Musterlösung: bezeichne die linke Seite mit $A$, rechte mit $B$.
  - Zu zeigen: $A \le_m B$. Die Reduktionsfunktion $f$ bildet $x$ ab auf einen Index des folgenden Programms:
    
    $e \mapsto$ bei der Diagonal-Durchquerung der Tabelle von $(a,b) \mapsto \phi_x(a)$ hält nach genau $b$ Schritten wird wenigstens $e$ mal True angetroffen.
    
    Dann $x\in A \iff$ Tabelle enthält unendlich viele True $\iff$ $\phi_{f(x)}$ ist total $\iff f(x)\in B$.
  - zu zeigen: $B \le_m A$. Die Reduktionsfunktion $f$ bildet $x$ ab auf einen Index des folgenden Programms:
    
    $e \mapsto$ for i from 0 to e-1 do $\phi_x(i)$.
    
    Dann $x\in B \Rightarrow \phi_x$ total $\Rightarrow \phi_{f(x)}$ total
    
    und $x\notin B \Rightarrow$ es gibt ein kleinstes $i$ mit $\phi_x(i)\uparrow$ $\Rightarrow \dom(\phi_{f(x)})=\{0,\ldots,i\}$ und damit endlich, also $f(x)\notin A$.
- $(\mathbb{N}\setminus K_0) \le_m \{ x\mid W_x ~ \text{ist endlich} \}$
- $\{ x\mid W_x ~ \text{ist endlich} \} \not\le_m K_0$
- $\{ x\mid W_x \neq \emptyset \}$ ist RE-vollständig
(KW 50) Zeige $M\le_m (\mathbb{N}\setminus M) \wedge M\in\operatorname{RE}\Rightarrow M\in\operatorname{REC}$.

Konstruiere $M$ mit $M\le_m (\mathbb{N}\setminus M)$ und $M\notin\operatorname{REC}$

Motivation Turing-Maschine

bisher: Rechnen mit Zahlen,
jetzt: Rechnen mit Wörtern (Zeichenfolgen)
stellt Verbindung her zw. Berechenbarkeit und Theorie der formalen Sprachen
liefert ein genaueres Modell zur Messung des Ressourcenverbrauchs (in Komplexitätstheorie), (Rechnen mit beliebig großen Zahlen ist zu ungenau)
es war nie beabsichtigt, Turing-Maschinen tatsächlich zu bauen (anders als bei goto-Programmen)
aber die Natur macht es: (Umformungen von RNA)

TM: Semantik (im Grundsatz)

Grundsatz: ein Schritt einer Rechnung ist eine lokal beschränkte Speicher-Änderung.

Speicher ist Zustand sowie Folge von Bändern
Band ist Folge von Zellen
jedes Band hat eine markierte Position (Kopfposition)
ein Schritt besteht aus: Lesen, Schreiben, Bewegen

(evtl. über den Rand, dabei wird das Band verlängert)

Zustandsmenge ist fixiert und endlich
Zeichenvorrat (Zelleninhalt) ist fixiert und endlich
Anzahl der Bänder ist fixiert und endlich
jedes Band ist endlich, aber nicht beschränkt

TM: Syntax und Semantik (Rel. auf Konfig.)

Bezeichnungen für $k$-Band-Turing-Maschine:

endliche Zustandsmenge $Q$ , $\bullet$ endliches Alphabet $\Sigma$
Leerzeichen $\Box\notin\Sigma$, Bezeichnung $\Sigma_\Box=\Sigma\cup\{\Box\}$
Band-Inhalte: $B(\Sigma):=\{ f:\mathbb{Z}\to \Sigma_\Box$ mit $f^-(\Sigma)$ endlich $\}$
endliche Zahl $k\ge 2$ (Anzahl der Bänder)

Die Konfigurationsmenge einer TM ist $Q\times (B(\Sigma)\times \mathbb{Z})^k$.

Das Programm einer TM besteht aus

Initialzustand $q_i\in Q$, Finalzustand $q_f\in Q$
Übergangstabelle $t : Q \times \Sigma_\Box^k \hookrightarrow Q \times (\Sigma \times \{L,H,R\})^k$

Definiert Relation (partielle Funktion) $\to_M$ auf Konfigurationen durch …

TM: Beispiel

mit 1 Arbeitsband.
$\Sigma=\{0,1\}$, Leerzeichen $\Box$
$Q=\{i,a,f\}$, initial: $i$, final: $f$
für $x\in\Sigma$: $t(i,[x,p,y]) = (i,[(x,R),(x,R),(y,H)])$

$t(i,[\Box,p,y])=(a,[(\Box,H),(p,L),(y,H)])$

für $p\in\Sigma$: $t(a,[x,p,y])=(a,[(x,H),(p,L),(p,R)])$

$t(a,[x,\Box,y])=(f,[(x,H),(\Box,H),(y,H)])$

berechnet Wortfunktion $\Sigma^*\to\Sigma^* : w\mapsto \text{reverse}(w)$

TM: Semantik (berechnete Wortfunktion)

für TM mit Einschränkung: jede Bewegung für Kopf 1 (Eingabe) und Kopf $k$ (Ausgabe) ist $\in\{H,R\}$

Eingabe ist read-only, Ausgabe ist write-only
restliche Bänder heißen Arbeitsbänder

initiale Konfiguration für Eingabe $u\in\Sigma^*$:

Zustand $q_i$, Band 1 enthält $u$ (ab 0), sonst leer, Köpfe: 0

finale Konfiguration mit Ausgabe $v\in\Sigma^*$:

Zustand $q_f$, Inhalt von Band $k$ ist $\dots,\Box,v,\Box,\dots$

TM $M$ berechnet $f_M: \Sigma^*\hookrightarrow\Sigma^*$ mit

$y=f_M(x)$, gdw. $\exists c: \text{initial}(x)\to_M^* c\wedge \text{final}(c) \wedge \text{output}(c)=y$

TM: Semantik (berechnete Zahlfunktion)

TM $M$ mit Alphabet $\{1,\#,\ldots\}$ (Zählzeichen, Trennzeichen)

berechnet Zahlfunktion $g:\mathbb{N}^n\hookrightarrow\mathbb{N}$ mit

$g(x_1,\ldots,x_n)=y$, gdw. $f_M(1^{x_1}\#1^{x_2}\#\ldots\# 1^{x_n})=1^y$

Wir nennen die so berechenbaren partiellen Funktionen Turing-berechenbar.

Genauer: $\textsf{Turing}_k:=$ die durch TM mit $k$ Arbeitsbändern berechenbaren partiellen Funktionen, $\textsf{Turing}:=\bigcup_{k\ge 0}\textsf{Turing}_k$

Ü: Nachfolger $\in\textsf{Turing}$, Addition $\in\textsf{Turing}$, Multipl. $\in\textsf{Turing}$

Nach der These von Church und Turing ist zu erwarten: $\operatorname{\textsf{Goto}}=\operatorname{\textsf{While}}=\operatorname{\text{Part}}=\textsf{Turing}$,

Beweis durch Compiler von und nach Goto.

$\textsf{Turing}\subseteq \operatorname{\textsf{Goto}}$

Satz: $f$ ist TM-berechenbar $\Rightarrow$ $f$ ist Goto-berechenbar.

Beweis (Idee): simuliere Band mit Kopf durch $(l,r)\in\mathbb{N}^2$, d.h. zwei Register.
Jede Zahl ist Wort zur Basis $b = 1+|\Sigma|$.
In $l$ der Bandinhalt links vom Kopf,
in $r$ der Bandinhalt rechts vom Kopf (gespiegelt).
Zeichen am Kopf lesen: $r$ modulo $b$.
Zeichen $x$ schreiben und Kopf nach rechts: $l' := b\cdot l+x; r'=\lfloor r/b\rfloor;$
für diese Rechnungen braucht man noch ein Register, insgesamt: $k$ Bänder $\Rightarrow$ $2k+1$ Register

$\operatorname{\textsf{Goto}}\subseteq \textsf{Turing}$

Satz: $f$ ist Goto-berechenbar $\Rightarrow$ $f$ ist Turing-berechenbar.

Beweis (Idee):

$k$ Register $\to$ $k$ Arbeits-Bänder
Register $i$ hat Inhalt $x$ $\to$ Arbeits-Band $i$ hat Inhalt $1^x$
Programmablaufsteuerung: Befehlsnummer (PC) im Zustand der TM merken

Ü: ergänze Details zur Herstellung der Initialkonfiguration, Ablesen des Resultates aus Finalkonfiguration

Simulation von Mehrbandmaschinen

Mehrere Arbeitsbänder sind nützlich, aber nicht nötig:

Satz: $\forall k\ge 1: \textsf{Turing}_k =\textsf{Turing}_1$.

Beweis (Idee):

Kodiere Inhalte der $k$ Zellen auf Position $p$ der Arbeitsbänder in ein einziges Zeichen aus $\Sigma^k_\Box$.

Beachte bei Realisierung:

es müssen dann immer alle Köpfe genau untereinander stehen
es werden nicht die Köpfe, sondern die Bänder bewegt,
eine simulierte Bewegung eines Kopfes ändert das gesamte simulierte Band

Maschinen mit wenigen Registern

nach voriger Idee kann man Eingabe-, Ausgabe- und Arbeitsbänder in ein einziges Band kodieren
diesen Bandinhalt in zwei Registern $x,y$ verwalten
zur Simulation eines Schrittes (Division, Multiplikation mit $|\Sigma|+1$) benötigt man ein drittes Register $z$
diese drei Register $x,y,z$ kann man durch zwei simulieren: in $a$ steht immer $2^x 3^y 5^z$, und $b$ zum Rechnen.
$\Rightarrow$ das Halteproblem ist bereits für While- (oder Goto-)-Programme mit 2 Registern (die nur Inc/Dec ausführen) unentscheidbar.
…für 1 Register entscheidbar (spezieller Kellerautomat)

Übung TM

Ein einseitig unendliches Band ist ein Band, dessen Kopf nur Positionen $\ge 0$ einimmt.

(bei unserer Def. der TM gilt: Ein- und Ausgabeband sind einseitig unendlich, Arbeitsbänder nicht.)

Begründen Sie, daß man ein unbeschränktes (d.h. zweiseitig unendliches) Band durch zwei einseitig unendliche Bänder schrittweise simulieren kann.

(schrittweise: ein Schritt der Original-Maschine $\Rightarrow$ ein Schritt in der simulierenden Maschine)
Wir nennen einen TM-Befehl stationär, wenn dabei alle Köpfe stehenbleiben.

Beweisen Sie, daß jede TM-berechenbare Wortfunktion auch durch ein TM-Programm ohne stationäre Befehle berechnet werden kann.

Wortersetzungssysteme

Historische Motivation

Darstellungen von Gruppen
durch Generatoren und Relationen
Bsp: $G=\langle a,b\mid a^2=b^2=(ab)^2=1 \rangle$

Symmetriegruppe des Rechtecks (Kleinsche 4-Gruppe)

($a,b$ sind Spiegelungen, was ist $ab$?)
Rechnen in $G$ : $bab^3a^3ba =_G\dots =_G a^2ba$

Wortproblem: gegeben $G=\langle \dots\mid R\rangle, u, v$, gilt $u=_G v$?
Felix Klein (1849–1925, in Leipzig: 1880–1886)

Erlanger Programm (der Geometrie), vgl. auch $\equiv_m, \le_m$

SRS, Markov-Algorithmen (MA)

(Syntax) Regelsystem $R\subseteq \Sigma^*\times\Sigma^*$
(Semantik) Teilwort-Ersetzungs-Relation $\to_R$ auf $\Sigma^*$ $u\to_R v :\iff \exists p\in\Sigma^*:\exists (l,r)\in R:\exists q\in\Sigma^*: u=plq\wedge prq=v$
Bsp. $\Sigma=\{1,A\}, R=\{(A1,11A),(AE,\epsilon)\}$. Nf. von $k111$?
Markov-Algorithmus $:=$ SRS $R$ mit Strategie $s$

zur Auswahl genau eines Nachfolgers (z.B. leftmost)
Andrej Markov Jr., 1903 – 1979
die durch MA $(R,s)$ berechnete Wortfunktion:

$f_R(u)=v \iff \textsf{initial}(u)\to_{R,s}^* v\wedge \textsf{final}(v)$,

wobei $\textsf{initial}(w):= AwE$, $\textsf{final}(w):=w$ ist $R$-Normalform
die durch Markov-Algorithmus berechnete Zahlfunktion:

kodiere Eingabe $x\in\mathbb{N}^k$ als $1^{x_1}\#\ldots\#1^{x_k}$

Vergleich MA — TM

Satz: für jede Wortfunktion $f:\Sigma^*\hookrightarrow\Sigma^*$ gilt:

$f$ ist Markov-berechenbar $\iff$ $f$ ist Turing-berechenbar
Beweis-Plan $\Rightarrow$
- $w$ auf Arbeitsband
- TM bestimmt Regel und Stelle der Anwendung
Beweis-Plan $\Leftarrow$
- kodiere alle Bänder in eines
- übersetze Konfig $(q,b,k)$ in Wort $b[\dots, k-1] ~q~ b[k,\dots]$
- übersetze TM-Befehl $(q,x)\to(q',x',R)$
  
  in SRS-Regel $qx \to x'q'$, entspr. für $H,L$ (Übung)
- für dieses $R$ ist $\to_R$ partielle Fkt. $\Sigma^* Q \Sigma^*\hookrightarrow\Sigma^* Q \Sigma^*$

Das Erreichbarkeitsproblem

$E_{\textsf{Markov}} := \{ (R,u,v) \mid u \to_{R,\det}^* v \}$, $E_{\textsf{SRS}} := \{ (R,u,v) \mid u \to_R^* v \}$

Eigenschaften:

$E_{\textsf{SRS}}\in\operatorname{RE}$ (Beweis: Übung)
$E_{\textsf{SRS}}\notin\operatorname{REC}$

Beweis: zeige $K_{\textsf{Turing}}\le_m E_{\textsf{Turing}}\le_m E_{\textsf{Markov}}\le_m E_{\textsf{SRS}}$

TM $M$ hält (nach Def.) durch Erreichen des Zustandes $q_f$.

Konstruiere $M'$: wie $M$, aber für $q_f$ Regeln zum Löschen aller Bänder, dann Halt in neuem, finalen Zustand $q_f'$

Dann $M(u)\downarrow \iff M'(u)=v_0=$ leeres Band (Bänder)

D.h. Reduktion (für $\le_m$) durch $(M,u)\mapsto (M',u,v_0)$

Das Postsche Korrespondenzproblem

Motivation

ein leicht zu definierendes kombinatorisches Problem

(eine Eigenschaft einer Folge von Paaren von Wörtern)

(leicht heißt: Def. PCP ist kürzer als Def. TM)
das trotzdem schwierig ist.

(schwierig heißt: $\operatorname{\textsf{PCP}}\notin\operatorname{REC}$)
ist Hilfsmittel für Beweise der Unentscheidbarkeit von Eigenschaften formale Sprachen, logischer Formeln, usw.

(Hilfsmittel heißt: wir verwenden $\le_m$)
Emil Post (1897 – 1954)

Definition

Eine Instanz des Postschen Korrespondenzproblems besteht aus:

endl. Menge $\Sigma$ (Bsp. $\{0,1\}$), endl. Menge $\Gamma$ (Bsp, $\{a,b,c\}$),

zwei Morphismen (Wdhlg. Def.?) $f,g:\Gamma^*\to\Sigma^*$

Bsp. $f(a)=10, f(b)=101, f(c)=1,$
$g(a)=1, g(b)=010101, g(c)=0$
$w\in\Gamma^+$ heißt Lösung der Instanz, wenn $f(w)=g(w)$
$\operatorname{\textsf{PCP}}$ ist die Menge der lösbaren PCP-Instanzen

Für das Beispiel gilt: $\epsilon$ ist keine Lösung. $ab$ ist keine Lösung. Keine Lösung beginnt mit $ab$. Es gibt eine Lösung. Es gibt unendliche viele Lösungen.

$E_{\textsf{SRS}} \le_m \operatorname{\textsf{PCP}}$ (Plan)

Ziel: berechenbare Funktion $f$ mit für alle $R$, Wörter $u,v$:

$u\to_R^* v \iff f(R,u,v)\in\operatorname{\textsf{PCP}}$

Sei $f(R,u,v) = I = (\Gamma,\Sigma, g,h)$
Plan: $w$ ist Lösung von $I$ gdw.

Lösungswort $g(w)=h(w) = Au_0\#u_1\#\ldots\#u_n\#E$

mit $u=u_0$ und $\forall i: u_i\to_R u_{i+1}$ und $u_n=v$
$I = \begin{array}{c||c|c|c|c|c|c|c|c} g & A & l_1 & \dots & l_{|R|} & v \# E & x_1 & \dots & x_k\\ \hline h & A u \# & r_1 & \dots & r_{|R|} & E & x_1 & \dots & x_k \end{array}$

mit $\Sigma=\{x_1,\ldots,x_k\}$
außer dem gewünschten Lösungswort

gibt es triviale Lösungen wegen der Kopier-Regeln.
PCP $\Rightarrow$ MPCP, Lösungen sollen mit ersten Paar beginnen

Das start-beschränkte PCP

(in der Literatur oft: modifiziertes PCP, MPCP)

zusätzlicher Parameter $a\in\Gamma$

$\textsf{MPCP}= \{(\Gamma,\Sigma,f,g,a)\mid \exists w: f(aw)=g(aw) \}$

Satz: $\textsf{MPCP}\le_m\operatorname{\textsf{PCP}}$

Beweis: $I:(\Gamma,\Sigma,f,g,a)\mapsto I':(\Gamma \cup\{e\},\Sigma\cup\{M,E\},f',g')$

neuer Buchstabe $M$ soll an jeder zweiten Stelle von $f'(w')=g'(w')$ vorkommen,
benutze Morphismen $L(x)=Mx, R(x)=xM$
$\begin{array}{c||c|c|c|c|c|c|c} f' & L(f(a))M & R(f(b)) & \dots & E \\ \hline g' & L(g(a)) & L(g(b)) & \dots & ME \end{array}$
$aw$ löst $I$ gdw. $awe$ löst $I'$,
jede Lösung von $I'$ beginnt mit $a$ und endet mit $e$

$\operatorname{\textsf{PCP}}\notin\operatorname{REC}$

wir haben nun gezeigt: $E_{\textsf{SRS}} \le_m \textsf{MPCP}\le_m \operatorname{\textsf{PCP}}$
aus $E_{\textsf{SRS}}\notin\operatorname{REC}$ folgt $\operatorname{\textsf{PCP}}\notin\operatorname{REC}$
damit beweisen wir nun die Unentscheidbarkeit weiterer Probleme aus den Bereichen
- formale Grammatiken
- Logik

Eine unentscheidbare Eigenschaft von CFG

Def. $\textsf{CFGine}= \{ (G_1,G_2)\mid G_i\in\textsf{CFG}, L(G_1)\cap L(G_2)\neq\emptyset \}$

(context-free grammar intersection non-emptiness)

Satz: $\textsf{CFGine}\notin\operatorname{REC}$. Beweis: $\operatorname{\textsf{PCP}}\le_m \textsf{CFGine}$
Beweis: gegeben PCP-Instanz $I=(\Gamma,\Sigma,f,g)$, konstruiere
- $G_1$ mit $L(G_1)=\{ \textsf{reverse}(g(w))\# f(w) \mid w\in\Gamma^+ \}$
- $G_2$ mit $L(G_2)=\{\textsf{reverse}(u)\#u\mid u\in\Sigma^*\}$

Übung: untersuche Mitgliedschaft in REC, RE, coRE für

$\{ (G_1,G_2)\mid G_i\in\textsf{CFG}, L(G_1)\subseteq L(G_2) \}$
$\{ (G_1,G_2)\mid G_i\in\textsf{CFG}, L(G_1) = L(G_2) \}$
$\{ G \mid G\in\textsf{CFG}, L(G)=\Sigma^* \}$, $\{ G \mid G\in\textsf{CFG}, L(G)=\emptyset \}$
$\{ G \mid G\in\textsf{CFG},$ $G$ ist eindeutig $\}$

Unentscheidbarkeit in der Logik

Prädikatenlogik

Das Allgemeingültigkeitsproblem $\textsf{APL}$ ist

Eingabe: PL-Formel $F$, ohne freie Variablen, in Sign. $\Sigma$,
Frage: $F$ allgemeingültig? (gilt in jeder $\Sigma$-Struktur $S$)

Bsp: $(\exists x:\forall y: P(x,y))\to(\forall y:\exists x:P(x,y))$

Satz: $\operatorname{\textsf{PCP}}\le_m\textsf{APL}$. Folg. $\textsf{APL}\notin\operatorname{REC}$

Beweis-Plan: Aus PCP-Instanz mit Paaren $(ab,ba),\dots$ konstruiere Formel $(F_1\wedge F_2)\to \exists R(x,x)$ mit

$F_1 = R(a(b(e)),b(a(e))) \wedge \dots$
$F_2 = \forall x,y: R(x,y)\rightarrow R(a(b(x)),b(a(x)))\wedge\dots$

Arithmetik

Die Theorie einer Struktur $S$ ist die Menge der Formeln $F$ mit $S\models F$.
Die Theorie der Arithmetik $\textsf{TA}$ besteht aus allen wahren Aussagen über $\mathbb{N}$ in der Signatur $\{0/0,1/0,+/2,\cdot/2\}$

Bsp. $(\exists x:\forall y: x \neq 2\cdot y)\in\textsf{TA}$
Satz (1931, Kurt Gödel, 1906–1978): $\textsf{TA}\notin\operatorname{REC}$.

Beweis: $E_{\operatorname{\textsf{While}}}\le_m\textsf{TA}$, denn

die Zustandsübergangsrelation $\to_P$ eines While-Programms kann arithmetisiert werden.

Für $P=\text{while}(x)Q$ verwende

$\exists t,c:$ $c$ ist Kodierung einer Folge von $t$ Zuständen …

Unvollständigkeit von Beweissystemen

Bezeichnung: eine PL-Formel $F$ heißt

wahr, wenn $\forall S: S\models F$ (gilt in jeder Struktur)
ableitbar (durch Inferenzsystem (Axiomen und Regeln))

Satz: Menge der ableitbaren Formeln $\in$ RE

Beweis: Inf.-Syst. ist endlich und jede Ableitung ist endlich.

Bezeichnung: ein Inferenzsystem heißt

korrekt, wenn jede ableitbare Formel wahr ist
vollständig, wenn jede wahre Formel ableitbar ist

Satz (Gödel): jedes korrekte Inferenzsystem für die Arithmetik ist unvollständig.

Bew.: $\text{co-}\textsf{TA}\le_m \textsf{TA}$ (wg. $F\mapsto \neg F$), $\textsf{TA}\in\operatorname{RE}\cap\operatorname{coRE}=\operatorname{REC}$

Übungen KW51

In der Kleinschen 4-Gruppe gilt: $ab=ba$. Beweise durch
1. geometrischen Anschauung,
2. eine Gleichungskette unter Benutzung der Relationen
Für das SRS $\{ab\to baa\}$: Normalform von $a^kb$, von $a b^k$.
Ergänze Simulation der TM durch MA (Kopfbewegungen $H$, $L$)
autotool-Aufgabe PCP
Für PCP mit $|\Sigma|=1$:
- Geben Sie je eine lösbare und eine nicht lösbare Instanz mit $|\Gamma|=3$ an.
- Geben Sie ein Entscheidungsverfahren an.
Die folgende Variante des PCP ist entscheidbar:
- Eingabe: Morphismen $f,g:\Gamma^*\to\Sigma^*$,
- Lösung: Wörter $w_1,w_2\in\Gamma^+$ mit $f(w_1)=g(w_2)$
(Hinweis: endliche Automaten)
Aufgaben auf Folie eine unentsch. Eig. von CFG

Hinweis: $\Sigma^*\setminus L(G_2)$ ist auch kontextfrei.

(1. warum? 2. was nützt es?)

Orakel und Nichtdeterminismus

Motivation

bisher: deterministische Rechnungen
- Rechnung ist Pfad
- ist erfolgreich, falls finaler Zustand erreicht wird
jetzt: Such-Aufgaben (nichtdeterministische Rechnungen)
- Rechnung ist Baum (d.h., mglw. mehrfach verzweigt)
- ist erfolgreich, falls ein finales Blatt existiert
alternative Sichtweise: Orakel-Berechnung
- ein Orakel beschreibt den Weg zum finalen Blatt,
- deterministische Maschine verifiziert diesen Weg

Eine Charakterisierung von RE

$M\in \operatorname{RE}\iff \exists i:M=\dom \phi_i$
$x\in M\iff\exists y:$ Rechn. $\phi_i(x)$ hält nach genau $y$ Schritten
$\{C(x,y)\mid$ Rechn. $\phi_i(x)$ hält nach genau $y$ Schr. $\} \in \operatorname{REC}$
Satz: $\forall M\subseteq\mathbb{N}: M\in \operatorname{RE}\iff\exists M'\in\operatorname{REC}: \forall x: x\in M\iff \exists y: C(x,y)\in M'$
Ü: Beweis für $\Longleftarrow$
Bezeichnungen: $y$ ist Orakel-Wort oder Zertifikat für $x$.
Ü: falls $\exists M'\in \operatorname{REC}:\forall x: x\in M \iff \exists y:C(x,y)\in M' \wedge y\le x$, dann $M\in\operatorname{REC}$

Orakel-Maschinen

Def: eine Orakel-Maschine $A$ hat Eingabeband (Alphabet $\Sigma$), Orakelband (Alphabet $\Gamma$) und Arbeitsbänder
Def: die von $A$ akzeptierte Sprache $\textsf{Lang}_{\textsf{Acc}}(A)\subseteq\Sigma^*$:

Menge aller Eingabewörter $x$, für die ein Orakelwort $y$ existiert, so daß Rechnung $M(x,y)$ erfolgreich hält.
nach dieser Def: das Orakel sieht $x$ und schreibt $y$, dann rechnet (verifiziert) $A$ (deterministisch)
alternative Sichtweise: $y$ ist unbekannt, bei jedem Lesen eines unbekannten Zeichens von $y$ verzweigt die Rechnung: $A$ ist nicht-deterministische TM
die Rechnung $A(x)$ ist ein Baum $T$, Eingabe wird akzeptiert, wenn $T$ ein erfolgreiches Blatt enthält

Komplexitätstheorie

Motivation

bis jetzt: Berechenbarkeit als qualitativer Begriff

(eine Funktion ist berechenbar oder nicht,
eine Menge ist entscheidbar oder nicht)
ab jetzt: quantitative Untersuchung:

für berechenbare Funktionen/entscheidbare Mengen:

mit welchem Aufwand läßt sich Rechnung durchführen?
Komplexität sowohl für det. als auch für nichtdet. Berechnungsmodelle (Suchprobleme)
verwendet Methoden der Berechenbarkeitstheorie (insb. Reduktion, Vollständigkeit)

Definition

Ressourcen:

z.B. Rechenzeit, Speicherplatz, Kommunikationsaufwand
Komplexität eines Algorithmus (eines Programmes, einer Maschine):

Ressourcenverbrauch als Funktion der Eingabegröße

Bsp: die Komplexität von Bubblesort ist quadratisch.
Komplexität eines Problems: Komplexität für besten Algorithmus, der das Problem löst.

Bsp: die Komplexität des Sortierens ist $\in \Theta(n\mapsto n\cdot\log n)$

Komplexitätstheorie ist die Lehre von der Schwierigkeit von Problemen.

Eigenschaften von Zahlen

Zahlen sind hier: ganz, nichtnegativ und binärkodiert
zusammengesetzte Zahlen

$\textsf{COMP}=\{ x \mid \exists y,z\ge 2: x=y\cdot z\}$
Primzahlen

$\textsf{PRIMES}=\{ x \mid x\ge 2\} \setminus \textsf{COMP}$
Quadratzahlen

$\textsf{SQUARES}= \{ x\mid\exists y: x=y^2\}$
Motivation: u.a. Kryptographie

RSA-Schlüssel $\in\textsf{COMP}$, aber die Ursache (die Faktoren) soll geheim bleiben

Das Erfüllbarkeitsproblem

$\textsf{AL}=$ die Menge der aussagenlogischen Formeln
$b\models F$: die Belegung $b$ erfüllt die Formel $F$
$\textsf{SAT}=\{ F \mid F \in\textsf{AL}, \exists b: b\models F \}$
Bsp. $((x \to \neg y)\wedge (x\leftrightarrow y))\in\textsf{SAT}$, $(x \wedge \neg x)\notin\textsf{SAT}$
Spezialfälle (durch syntaktische Einschränkungen)
- CNF-SAT:
  
  wie oben und $F$ ist in konjunktiver Normalform
- $k$-CNF-SAT:
  
  …mit $\le k$ Literalen je Klausel
Motivation: Entwurf und Überprüfung von digitalen Schaltungen

Boolesche Schaltkreise

Schaltkreis ist DAG mit:
- Startknoten (keine Vorgänger): Eingaben
- andere Knoten: markiert mit Boolescher Op. ($\wedge,\vee,\neg$)
- Endknoten (keine Nachfolger): Ausgaben
jeder Knoten realisiert Bool. Fkt. der Eingabe
Schaltkreis-Erfüllbarkeit $\textsf{CIRC}\textsf{SAT}=\{C\mid$ $C$ ist unärer Schaltkreis (mit einer Ausgabe) $\wedge\exists$ Eingabe $e$ mit Ausgabe $C(e)=1$, Schreibweise $e\models C$ $\}$
Satz: $\textsf{CIRC}\textsf{SAT}\in\textsf{NP}$,

Beweis: das Orakel rät die Eingabe $e$, dann kann $C(e)$ in Polynomialzeit berechnet werden (z.B. schichtweise)

Das Färbungsproblem

eine $k$-Färbung eines Graphen $G=(V,E)$ ist eine Abbildung $f:V\to\{1,2,\ldots,k\}$
die Färbung $f$ von $G=(V,E)$ ist konfliktfrei,
wenn $\forall xy\in E: f(x)\neq f(y)$
$k\textsf{COL}:= \{ G \mid \exists f:$ $f$ ist konfliktfreie $k$-Färbung von $G$ $\}$
Bsp: $K_3\notin 2\textsf{COL}$, $C_5\notin 2\textsf{COL}$,

Ü: finde $G$ mit: $G$ enthält keinen $K_3$ und $G\notin 3\textsf{COL}$

Ü: jeder Knoten von $G$ hat $< k$ Nachbarn $\Rightarrow$ $G\in k\textsf{COL}$.
Motivation: Ressourcenzuordnungsprobleme,

z.B. Frequenzbereiche zu Funkzellen

Bemerkung zur Genauigkeit

bisher:

wg. These von Church und Turing war das Berechnungsmodell beliebig
wg. Gödelisierung war die Art der Eingabe (Zahlen, Wörter usw.) beliebig

jetzt:

wg. exakter Ressourcenmessung muß ein Modell fixiert werden (Turingmaschine)
wg. Komplexität als Fkt. der Eingabegröße

muß Größe exakt definiert werden

(Länge des Wortes auf dem Eingabeband, Länge der Binärkodierung einer Zahl)

Deterministische Zeit, Bps.: P

für $f:\mathbb{N}\to\mathbb{N}$ bezeichnet $\textsf{DTIME}_{\textsf{Alg}}(f)$

die Menge der TM $M$ mit $\forall x\in\textsf{Lang}_{\textsf{Acc}}(M)$
$\iff$ $M$ akzeptiert $x$ nach $\le f(|x|)$ Schritten.
für $f:\mathbb{N}\to\mathbb{N}$ bezeichnet $\textsf{DTIME}_{\textsf{Prob}}(f)$

die Menge der Sprachen $L$ mit $\exists M\in \textsf{DTIME}_{\textsf{Alg}}(f) : L=\textsf{Lang}_{\textsf{Acc}}(M)$.
Abkürzung $\textsf{DTIME}= \textsf{DTIME}_{\textsf{Prob}}$

Satz: $f$ berechenbar $\Rightarrow$ $\textsf{DTIME}(f)\subseteq \operatorname{REC}$

für Menge $F$ von Funktionen: $\displaystyle\textsf{DTIME}(F) = \bigcup_{f\in F} \textsf{DTIME}(f)$
Abkürzung: $\textsf{P}= \text{PTIME}=\textsf{DTIME}(\text{Menge der Polynome})$
$\{ w \mid w\in\{0,1\}^*, w=\overline{w}\}\in\textsf{P}$, $\textsf{CFL}\subseteq \textsf{P}$, $2\textsf{COL}\in\textsf{P}$, $2\textsf{SAT}\in\textsf{P}$

Nichtdeterministische Zeit, Bsp: NP

für $f:\mathbb{N}\to\mathbb{N}$ bezeichnet $\textsf{NTIME}_{\textsf{Alg}}(f)$ die Menge der Orakel-TM $M$ mit $\forall x: x\in\textsf{Lang}_{\textsf{Acc}}(M)$ $\iff$ es gibt ein Orakelwort $y$ mit: $M(x,y)$ akzeptiert in $\le f(|x|)$ Schritten.

(dabei werden $\le f(|x|)$ Zeichen von $y$ gelesen)
entsprechend $\textsf{NTIME}_{\textsf{Prob}}(f), \textsf{NTIME}(f), \textsf{NTIME}(F)$
Ü: $f$ berechenbar $\Rightarrow$ $\textsf{NTIME}(f)\subseteq \operatorname{REC}$
Abkürzung $\textsf{NP}=\textsf{NPTIME}=\textsf{NTIME}(\text{Polynome})$
Bsp. $\textsf{COMP}\in\textsf{NP}, \textsf{SAT}\in\textsf{NP}, \forall k:k\textsf{COL}\in\textsf{NP}$
Satz: $A\in\textsf{NP}\wedge B\in\textsf{NP}\Rightarrow (A\cup B)\in\textsf{NP}$
Satz: $\textsf{P}\subseteq \textsf{NP}$ (trivial) , Frage $\textsf{P}=\textsf{NP}$ (schwierig: $10^6$ $, http://www.claymath.org/millennium-problems/p-vs-np-problem)

Die Klasse coNP

Def: $\textsf{coNP}= \{ L \mid (\Sigma^*\setminus L)\in\textsf{NP}\}$
Bsp: $\textsf{PRIMES}\in\textsf{coNP}$ wegen $\textsf{COMP}\in\textsf{NP}$
es gilt auch $\textsf{PRIMES}\in\textsf{NP}$, Beweis benötigt etwas Zahlentheorie
$\textsf{PRIMES}\in\textsf{P}$,

Manindra Agrawal, Neeraj Kayal, Nitin Saxena, 2004.

http://annals.math.princeton.edu/2004/160-2/p12

Vergleich: Berechenbarkeit/Komplexität

bis jetzt:

es gibt Analogien zwischen:
- Berechenbarkeit: $\operatorname{REC}, \operatorname{RE}, \operatorname{coRE}$
- Komplexität: $\textsf{P},\textsf{NP},\textsf{coNP}$
der Unterschied ist, daß man $\operatorname{REC}\neq\operatorname{RE}$, $\operatorname{RE}\neq\operatorname{coRE}$ und $\operatorname{RE}\cap\operatorname{coRE}=\operatorname{REC}$ beweisen kann,

die entsprechenden Komplexitätsaussagen bisher nicht

nächste VL:

Reduktion (Vergleich der Komplexität von Problemen)
Vollständigkeit (zur Def. der schwersten Probleme einer Klasse)

Übungsaufgaben P/NP

Markierte Aufgaben besonders empfohlen zur Diskussion in Übung KW 54.

(KW54) Beweise: für alle $M'\in \operatorname{REC}$ und totale berechenbare $f:\mathbb{N}\to\mathbb{N}$ gilt $\{ x \mid \exists y:C(x,y)\in M' \wedge y\le f(x)\} \in\operatorname{REC}$

auf Deutsch: wenn die Größe der Orakelzahlen durch eine berechenbare Funktion beschränkt ist, dann ist jede mit diesem Orakel entscheidbare Menge auch ohne Orakel entscheidbar.
FP und LOOP:
1. Geben Sie eine Funktion $f\in\operatorname{\textsf{LOOP}}$ an, die nicht in Polynomialzeit berechenbar ist (Hinweis: z.B., weil sie zu schnell wächst)
2. $\operatorname{\textsf{LOOP}}^-$-Programme: wie LOOP, aber
  - zusätzlich ein Befehl $\textsf{Copy}(x,y)$ mit Semantik $y:= x$
  - Falls $\operatorname{\textsf{Inc}}(x)$ in einer Schleife vorkommt, dann heißt $x$ vergiftet. Falls $\textsf{Copy}(x,y)$ und $x$ vergiftet, dann auch $y$ vergiftet. Vergiftetes Register darf nicht als Schleifenzähler benutzt werden.
  Beweise: Addition, Multiplikation $\in \operatorname{\textsf{LOOP}}^-$.
  
  Beweise: $\operatorname{\textsf{LOOP}}^-$-Programme haben polynomielle Laufzeit
(KW 54) Abschlußeigenschaften
1. ist $\textsf{P}$ abgeschlossen unter: Vereinigung, Durchschnitt, Komplement? (trivial)
2. … Verkettung? (ja.) Stern?
3. die gleichen Fragen für $\textsf{NP}$.
Zahlen
1. $\textsf{SQUARES}\in\textsf{NP}$ (trivial), $\textsf{SQUARES}\in \textsf{P}$
2. $\textsf{PRIMES}\in\textsf{NP}$ (Satz von Fermat, primitive Wurzeln)
Graphen
1. 3COL: autotool
2. gesucht: ein $G$ mit $G\notin 3\textsf{COL}$ und $G$ enthält kein $K_3$ (Dreieck)
3. (KW 54) für alle $G$ mit $\deg(G)< k$ gilt $G\in k\textsf{COL}$.
  
  Hinweis: geben Sie einen Algorithmus an, der unter dieser Voraussetzung eine $k$-Färbung für $G$ konstruiert.
4. Für welche Graphen gilt: $G$ hat Maximalgrad $k$ und $G\notin k\textsf{COL}$?
Logik
1. CNF-SAT: autotool
2. (KW 54) $2\textsf{CNF}\textsf{SAT}\in\textsf{P}$ (schreibe jede Klausel als Implikation und betrachte einen dazu passenden Graphen)
3. $\textsf{DNF}\textsf{SAT}\in\textsf{P}$ (disjunktive Normalform)

Motivation

nach bisherigen Definitionen/Beispielen:

$\textsf{P}$: Klasse der (auf sequentiellen Maschinen) effizient lösbaren Probleme
$\textsf{NP}$: enthält häufig vorkommende Suchprobleme

für (neues) Problem $L$ wüßte man gern: $L\in \textsf{P}$ oder $L\notin\textsf{P}$?

bis heute ist kein $L\in\textsf{NP}\setminus\textsf{P}$ bekannt, obwohl es viele Kandidaten gibt.
Bekannt ist jedoch eine Charakterisierung der schwersten Probleme in NP:

die Klasse NPc der NP-vollständigen Probleme

Polynomialzeit-Reduktion $\le_{\textsf{P}}$

Def: $\textsf{FTIME}(f):=$ die in Zeit $\le f(|x|)$ auf DTM berechenbaren Fkt., $\textsf{FP}:= \textsf{FTIME}(\text{poly})$.
Def: $A\le_{\textsf{P}}B := \exists f\in\textsf{FP}:\forall x\in\Sigma^*: x\in A\iff f(x)\in B$.
Bsp: $\textsf{DHC}\le_{\textsf{P}}\textsf{HC}$.

$\textsf{HC}:= \{ G\mid$ $G$ ist ungerichteter Graph und $G$ enthält Kreis durch alle Knoten $\}$ (Hamiltonian Circuit)

$\textsf{DHC}:= \{ G\mid$ $G$ ist gerichteter Graph und $G$ enthält gerichteten Kreis durch alle Knoten $\}$ (Directed HC)

Beweis: $f(V,E)=(V\times\{1,2,3\} ,E')$ mit $E' = \{ (v,1)(v,2) \mid v\in V\}\cup\{ (v,2)(v,3) \mid v\in V\}\cup \{ (u,3)(v,1) \mid (u,v)\in E$.

zu zeigen sind für $f$: Korrektheit, Laufzeit

$\le_{\textsf{P}}$ ist transitiv

vgl.: $\le_m$ ist transitiv,
Beweis: sei $A \le_{\textsf{P}}B$ mit Reduktionsfunktion $f$,
$B\le_{\textsf{P}}C$ mit Reduktionsfunktion $g$.

zeige: $A\le_{\textsf{P}}C$ durch Reduktionsfunktion $h:x\mapsto g(f(x))$

Korrektheit ist offensichtlich, Laufzeit: folgt aus:
Satz: $f\in\textsf{FP}\wedge g\in\textsf{FP}\Rightarrow (x\mapsto g(f(x)))\in\textsf{FP}$.
Bew.: sei $f\in\textsf{FTIME}(n\mapsto c\cdot n^k), g\in\textsf{FTIME}(n\mapsto d\cdot n^l)$.
- die Ausgabe von $f$ ist die Eingabe von $g$
- Ausgabenlänge $\le$ Rechenzeit
daraus folgt $(x\mapsto g(f(x))\in\textsf{FTIME}(n \mapsto \ldots \cdot n^{\dots})$

Abschluß-Eigenschaften von $\le_{\textsf{P}}$

Satz: $A\le_{\textsf{P}}B \wedge B\in\textsf{P}\Rightarrow A\in\textsf{P}$
Beweis: benutze Abschluß von $\textsf{FP}$ bzg. Komposition für
- die Reduktionsfunktion $f$ von $A$ nach $B$
- die charakteristische Fkt. $c_B$ von $B$
Satz: $A\le_{\textsf{P}}B \wedge B\in\textsf{NP}\Rightarrow A\in\textsf{NP}$
Beweis: sei $f$ die Reduktionsfunktion von $A$ nach $B$,

$c_B$ wird orakel-berechnet $M:(x,y)\mapsto\{0,1\}$.

Dann wird $c_A$ orakel-berechnet durch $(x,y)\mapsto M(f(x),y)$

zu betrachten sind: Korrektheit, Laufzeit, Orakelgröße.

vgl. $A\le_m B \wedge B\in\operatorname{REC}\Rightarrow A\in\operatorname{REC}$, $A\le_m B \wedge B\in\operatorname{RE}\Rightarrow A\in\operatorname{RE}$.

$\textsf{NPc}$ und Satz von Cook

Def:$B$ heißt NP-schwer, gdw. $\forall A\in\textsf{NP}: A\le_{\textsf{P}}B$.
Def: $B$ NP-vollständig, gdw. $B$ NP-schwer und $B\in\textsf{NP}$
$\textsf{NPc}:= \{B\mid \text{$B$ist NP-vollständig}\}$
Satz (Steven Cook, 1971): $\textsf{SAT}\in\textsf{NPc}$
wir zeigen zunächst: $\textsf{CIRC}\textsf{SAT}\in\textsf{NPc}$
Bew: $\textsf{CIRC}\textsf{SAT}\in\textsf{NP}$ wurde schon gezeigt.

Bleibt zu zeigen: $\textsf{CIRC}\textsf{SAT}$ ist NP-schwer. Dazu:

gegeben $A\in \textsf{NP}$, zu zeigen ist $A\le_{\textsf{P}}\textsf{CIRC}\textsf{SAT}$.

$\textsf{CIRC}\textsf{SAT}\in\textsf{NPc}$

Bew: gegeben $A\in \textsf{NP}$, zu zeigen ist $A\le_{\textsf{P}}\textsf{CIRC}\textsf{SAT}$.
$A=\textsf{Lang}_{\textsf{Acc}}(M)$ für O.-TM $M$ mit Zeitschranke $s\in\text{poly}$
Reduktionsfunktion $f: x\mapsto$ Schaltkreis $C$, der Konfigurationsfolge einer erfolgreichen Rechnung von $M$ mit $\le s(|x|)$ Schritten bei Eingabe $x$ und Orakelwort $y$ beschreibt, d.h., $x\in A\iff \exists y: C(x,y)=1$
Eingangsknoten: Kodierung von $x,y$

andere Knoten: indiziert durch Platz $p$ und Zeit $t$, $K(p,t)$ enthält Kodierung von Zeichen, Kopfposition, Zustand

Ausgabeknoten: akzeptierender Zustand wurde erreicht
$C$ kann in FP konstruiert werden (Zeit und Platz sind $\le s(|x|)$ )

CIRCSAT $\le_{\textsf{P}}$ CNFSAT (Tseitin-Transformation)

Gregory Tseitin, 1966

Plan: aus Schaltkreis $C$ wird Formel $G$ konstruiert

mit Knoten von $C$ $=$ $\textsf{Var}(G)$

und $\forall e: e \models C \iff \exists b:e\subseteq b \wedge b\models G$.

(jedes Modell von $G$ ist Erweiterung eines Modells von $C$ und jedes Modell von $C$ läßt sich zu Modell von $G$ erweitern)
Realisierung: für jeden nicht-Eingabeknoten $k$ von $C$ mit Vorgängern $k_1,k_2,\dots$ und Verknüpfung $f$:

Menge von CNF-Klauseln, die äquivalent ist zu $k\leftrightarrow f(k_1,k_2,\dots)$.

Tseitin-Transformation. Einzelheiten

Einzelheiten, Bsp $f=\wedge$.

$\overline k\vee k_1, \overline k\vee k_2,\dots, k\vee\overline{k_1}\vee \overline{k_2}\vee\dots$

(andere Verknüpfungen: Übung)
Folgerung: $\textsf{CIRC}\textsf{SAT}\le_{\textsf{P}}\textsf{CNF}\textsf{SAT}\le_{\textsf{P}}\textsf{SAT}$
$\textsf{CNF}\textsf{SAT}$ ist NP-schwer, $\textsf{SAT}$ ist NP-schwer
Übung: $\textsf{SAT}\le_{\textsf{P}}3\textsf{CNF}\textsf{SAT}$. Hinweis: $\textsf{SAT}\le\textsf{CIRC}\textsf{SAT}$ und dann den Schaltkreis umformen, so daß bei unsere Reduktion $\textsf{CIRC}\textsf{SAT}\le_{\textsf{P}}\textsf{CNF}\textsf{SAT}$ nur 3-Klauseln entstehen

Cook und Tseitin in der Praxis

wenn sich ein Anwendungsproblem $L$ als NP-vollständig heraustellt, dann folgt:

es gibt derzeit keinen effizienten Algorithmus für $L$
$L\le_{\textsf{P}}\textsf{SAT}\le_{\textsf{P}}\textsf{CNF}\textsf{SAT}$, d.h. man kann $L$ lösen, wenn man CNFSAT lösen kann

…und gute CNFSAT-Solver gibt es tatsächlich

Niklas Een, Niklas Sörensson: http://minisat.se/
Wettbewerbe: http://satcompetition.org/

Einzelheiten: siehe VL Constraint-Programmierung http://www.informatik.uni-leipzig.de/~waldmann/

Übungsaufgaben NP, SAT

Es gilt: zu jeder Formel $F$ gibt es eine äquivalente Formel $G$ in disjunktiver Normalform. Es gilt auch: DNFSAT$\in\textsf{P}$. Warum folgt daraus nicht $\textsf{SAT}\in\textsf{P}$?

Bem: $\textsf{SAT}\in\textsf{P}$ ist damit nicht ausgeschlossen, es geht nur darum, daß es so jedenfalls nicht folgt.
(KW 55) Für den Schaltkreis für die Formel $(x_1\wedge x_2)\vee x_3$:

Führe die Tseitin-Transformation durch.
gib eine CNF an für genau eine von $(x_1,\ldots,x_n)$ ist wahr.

(z.B. $n=4, n = 8$)
gib, falls möglich, eine kleinere erfüllbarkeitsäquivalente CNF dafür an (d.h.: mit Zusatzvariablen, und so, daß die Tseitin-Spezifikation wahr ist)
(KW 55) Def. $A\equiv_{\textsf{P}} B$ gdw. $A\le_{\textsf{P}}B$ und $B\le_{\textsf{P}}A$.

Seien $A,B\in\textsf{P}$. Wann gilt und gilt nicht $A\equiv_{\textsf{P}} B$?
(KW 55) zeige $A\in \textsf{NPc}\wedge B\in\textsf{NPc}\Rightarrow A\equiv_{\textsf{P}} B$
(KW 55) Für $A,B\subseteq\Sigma^*$ gilt $A\le_{\textsf{P}}B \iff (\Sigma^*\setminus A)\le_{\textsf{P}}(\Sigma^*\setminus B)$.
man könnte definieren: $B$ ist P-vollständig bzgl $\le_{\textsf{P}}$ gdw. $B\in\textsf{P}$ und $\forall A\in\textsf{P}: A\le_{\textsf{P}}B$.

Das ist aber nicht interessant, denn sehr viele Mengen aus P haben diese Eigenschaft — welche nicht?
(KW 55) Es gilt $3\textsf{COL}\le_{\textsf{P}}\textsf{SAT}$ (warum? erfordert keine Rechnung, sondern nur die Kombination von zwei bereits bekannten Aussagen). Gib explizit eine Reduktionsfunktion an, die in P-Zeit aus einem Graphen $G$ eine Formel $F$ berechnet mit $F\in 3\textsf{COL}\iff G\in\textsf{SAT}$. Hinweis: für jeden Knoten 3 Variablen.

Weitere NP-vollständige Probleme

Motivation, Vorgehen

Motivation: $L\in\textsf{NPc}$ bedeutet $L\in\textsf{NP}\wedge \forall L'\in\textsf{NP}:L'\le_{\textsf{P}}L$

es gibt derzeit keinen effizienten Algorithmus für $L$

(sonst auch für SAT, und das wäre eine Sensation)
es hat auch wenig Sinn, einen solchen zu suchen
besser: Aufgabenstellung einschränken o. variieren

Informatiker muß deswegen $L\in\textsf{NPc}$ schnell erkennen, um sinnlose Arbeit zu vermeiden.

$L\in\textsf{NP}$ ist meist offensichtlich,
statt $\forall L'\in\textsf{NP}:\dots$ reicht ein $L'\in\textsf{NPc}$ (warum?)
deswegen braucht man Beispiel-Probleme aus $\textsf{NPc}$

Vertex Cover

Def: Menge $M$ heißt Knoten-Überdeckung von $G=(V,E)$ $\iff M\subseteq V\wedge \forall e\in E:\exists v\in M: v\in e$

($M$ ist Menge von Knoten, die jede Kante überdeckt)
Def: $\textsf{VC}=\{(G,k)\mid \exists M:$ $M$ ist Knotenüberdeckung von $G$ $\wedge |M|\le k\}$
Satz: $\textsf{VC}\in\textsf{NPc}$
Beweis: $\textsf{VC}\in\textsf{NP}$ ist klar (Orakel liefert $M$)

zeigen $3\textsf{SAT}\le_{\textsf{P}}\textsf{VC}$

($K_2$ für jede Variable, $K_3$ für jede Klausel)
Ü: ist die 3 hier wirklich nötig?

Edge Cover

Def: Menge $M$ heißt Kanten-Überdeckung von $G=(V,E)$ $\iff M\subseteq E\wedge \forall v\in V:\exists e\in M: v\in e$

($M$ ist Menge von Kanten, die jeden Knoten überdeckt)
Def: $\textsf{EC}=\{(G,k)\mid \exists M:$ $M$ ist Kantenüberdeckung von $G$ $\wedge |M|\le k\}$
Satz: $\textsf{EC}\in\textsf{P}$

Beweis: evtl. Übung

3-Färbbarkeit

Satz: $3\textsf{COL}\in\textsf{NPc}$
Beweis: $3\textsf{SAT}\le_{\textsf{P}}3\textsf{COL}$
- eine $K_3$ $\{0,\text{Falsch},\text{Wahr}\}$
- für jede Variable $v$ ein $K_3$ : $\{v, \neg v, 0\}$
- für jede Klausel $l_1\vee l_2\vee l_3$: 6 Knoten $K_3 - K_3$,
  
  4 Endpunkte verbunden mit $l_1,l_2,l_3,\text{Falsch}$
Lemma: in jeder konfliktfreien 3-Färbung:
die Nachbarn der vier Endpunkte des $K_3-K_3$
haben nicht die gleiche Farbe.
vgl. mit Ü: $3\textsf{COL}\le_{\textsf{P}}\textsf{SAT}$
Ü: Def: $\textsf{COL}=\{(G,k)\mid G\in k\textsf{COL}\}$, Satz: $\textsf{COL}\in\textsf{NPc}$

Rucksack (Subset Sum)

Definition:

Instanz: Zahlen $a_1,\ldots,a_n, b\in\mathbb{N}$
Lösung: Teilmenge $I\subseteq\{1,\ldots,n\}$ mit $b=\sum_{i\in I}x_i$

Satz: $\textsf{Knapsack}\in\textsf{NPc}$, Beweis: $3\textsf{SAT}\le_{\textsf{P}}\textsf{Knapsack}$

Konstruktion: $F$ mit $n$ Variablen, $m$ Klauseln,

für $x\in \{a_1,\dots,b\}:\text{decimal}(x)\in\{0,1,\dots,4\}^*$,
$\text{decimal}(b)=4^m 1^n$
Gewichte $a_i$ für: positive Vorkommen von Variable in Klausel, negative Vorkommen, Zusatzgewichte
Überträge kommen nach Konstruktion nicht vor

Hamiltonkreis

Satz: $\textsf{HC}\in\textsf{NPc}$
Beweis: $\textsf{VC}\le_{\textsf{P}}\textsf{HC}$

Handlungsreisender (TSP)

(travelling salesperson)

Formulierung als eingeschränktes Optimierungsproblem:

Instanz: Matrix $D\in\mathbb{N}^{n\times n}$, Schranke $K\in\mathbb{N}$
Lösung: Permutation $p$ von $[1,\ldots,n]$ (Rundreise)
Maß: $c(D,p)=\sum_{i=1}^n D(p(i),p((i \bmod n)+1))$

Formulierung als Sprache (Entscheidungsproblem):

$\textsf{TSP}=\{(D,K)\mid \exists \text{Permutation} ~ p: c(p,D)\le K \}$

Satz: $\textsf{TSP}\in\textsf{NPc}$

Beweis: $\textsf{HC}\le_{\textsf{P}}\textsf{TSP}$

Ü: weitere Optimierungsprobleme http://www.nada.kth.se/~viggo/problemlist/compendium.html

Starfree Regexp Inequivalence

Def: $R_0:=$ reguläre Ausdrücke mit: Buchstabe, Verkettung, Vereinigung (kein Stern)
Def: $\textsf{SRI}=\{ (X,Y) \mid X,Y\in R_0\wedge \textsf{Lang}(X)\neq\textsf{Lang}(Y)$
Ü: $\textsf{SRI}\in\textsf{NP}$

Clique, Subgraph Isomorphism, Graph Isomorphism

Übungsaufgaben KW56

$\textsf{VC}\in\textsf{NPc}$
zeige: planar 3COL $\in\textsf{NPc}$ mittels $3\textsf{COL}\le_{\textsf{P}}\text{planar} 3\textsf{COL}$

Dazu jede Kreuzung von zwei Kanten durch einen geeigneten Teilgraphen ersetzen.
Dominating Set:

$M\subseteq V$ ist dominierende Menge in $G=(V,E)$,
falls $\forall v \in V\setminus M:\exists u\in M: vu\in E$

$\textsf{DS}:=\{(G,k)\mid\exists M: |M|\le k\wedge$ $M$ ist dominierend in $G$ $\}$
- zeige durch Beispiel, daß $\textsf{DS}\neq\textsf{VC}$ und $\textsf{DS}\neq\textsf{EC}$
- Zeige $\textsf{DS}\in\textsf{NPc}$ durch geeignete Reduktion
Edge Cover (EC) $\in \textsf{P}$

Zusammenfassung, Ausblick

Themen

Berechnungsmodelle

Goto, While, Loop, Markov, Turing

konkrete und abstrakte Sytax, Semantik (Interpreter), Äquivalenzen (Compiler)
Berechenbarkeit

REC, $\phi_x(y)$, $K$, $K_0$, Rice, PCP, RE, $\le_m$, Vollständigkeit
Komplexität

Nichtdeterminismus, Zeit, Platz, P, NP, $\le_{\textsf{P}}$, NPc

SAT, COL, VC

Beweisverfahren: Diagonalisierung

Verfahren:

Aufzählung einer Menge von Funktionen $F=\{f_0, f_1,\ldots\}$
modifizierte Diagonalfunktion $d':x\mapsto \text{change}(f_x(x))$,
$d'\in F \Rightarrow \exists i: d'=f_i \Rightarrow d'(i)=\text{change}(f_i(i)) \stackrel{?}{=}f_i(i)=d'(i)$

Übung/Wiederholung: wende an für $F =\dots$

alle Funktionen $\mathbb{N}\to\mathbb{N}$
alle Polynome
alle totale berechenbaren Funktionen $\mathbb{N}\to\mathbb{N}$
alle partiellen berechenbaren Funktionen $\mathbb{N}\hookrightarrow\mathbb{N}$
alle primitiv rekursiven Funktionen
alle in $\textsf{DTIME}(f)$ berechenbaren Funktionen

Algorithmen-Entwurfsmuster: Dovetailing

Verfahren:

zähle $\mathbb{N}^2$ auf in Reihenfolge monoton steigender $C(x,y)$.

(Wdhlg.) Anwendungen:

$M\in\operatorname{RE}\iff \exists x: M=\dom(\phi_x)$
$\{x\mid W_x$ ist unendlich $\} \le_m \{x\mid W_x =\mathbb{N}\}$

Weitere Aspekte der Komplexitätstheorie

Platz-Schranken (oberhalb von $\textsf{P}$, schwere Suchprobleme)
Schaltkreise (unterhalb von $\textsf{P}$, parallele Algorithmen)
probabilistische Maschinen BPP (mit beschränkter Fehlerhäufigkeit) (kann Prob-$\textsf{P}$ mehr als $\textsf{P}$?)
Quanten-Computer (BQP) (Beziehung zu NP?)
Kryptografie (z.B. zero-knowledge proofs)
implizite Komplexität von Programmen (syntaktische oder andere statische Bedingungen (Typen) $\textsf{P}$)
Dexter Kozen: Theory of Computation, Springer 2006
S. Arora, B.Barak: Computational Complexity, CUP 2009
Scott Aaronson:

https://www.scottaaronson.com/blog/

Die Ressource Speicherplatz

Deterministischer Platz

wir messen den Platz nur auf dem Arbeitsband
(nicht Eingabe-, nicht Ausgabe-band)
für $f:\mathbb{N}\to\mathbb{N}$ bezeichnet $\textsf{DSPACE}_\text{Alg}(f)$ die Menge der DTM $M$ mit $\forall x\in\textsf{Lang}_\textsf{Acc}(M)$ $\iff$ $M$ akzeptiert $x$ mit Arbeitsband der Breite $\le f(|x|)$
für $f:\mathbb{N}\to\mathbb{N}$ bezeichnet $\textsf{DSPACE}_\text{Prob}(f)$ die Menge der Sprachen $L$ mit $\exists M\in\textsf{DSPACE}_\text{Alg}(f): L=\textsf{Lang}_\textsf{Acc}(M)$
Abkürzung $\textsf{DSPACE}=\textsf{DSPACE}_\text{Prob}$
für Menge $F$ von Funkt.: $\textsf{DSPACE}(F)=\bigcup_{f\in F} \textsf{DSPACE}(f)$
Abkürzung $\textsf{PSPACE}=\textsf{DSPACE}(\text{poly})$

Beispiele für DSPACE: DSPACE(0)

(nach unserer Definition der TM) Eingabe ist read-only, Ausgabe ist write-only,
Arbeitsband darf nicht benutzt werden (Breite 0)

einzige Speichermöglichkeit ist Zustand
das sind endliche Automaten mit Ein- und Ausgabe
andere Namen dafür: finite (rational) transducer
Bsp: Berechnung des Nachfolgers in Binärdarstellung

Beispiele für DSPACE: $\textsf{QBF}\in \textsf{PSPACE}$

$\textsf{QBF}=$ die Menge der wahren aussagenlogischen Formeln mit Quantoren, ohne freie Variablen
Bsp: welche $F_i$ sind in QBF?

$F_1\equiv \forall x\exists y:(x\leftrightarrow\neg y)$, $F_2\equiv \exists x\forall y\exists z:(x\oplus y\oplus z)$
Satz: $\textsf{QBF}\in\textsf{PSPACE}$
Beweis: Auswertung der Formel rekursiv

z.B. $\textsf{eval}(\forall x:F) = \textsf{eval}(F[x:=0]) \wedge \textsf{eval}(F[x:=1])$

benutze Keller (auf Arbeitsband) für die Verwaltung der UP-Aufrufe, die Kellertiefe ist $\le |F|$
das Bsp zeigt: die Ressource Platz kann man nachnutzen

…und dabei sehr viel mehr Zeit verbrauchen

Beispiele: Spiele in PSPACE

$\textsf{QBF}$ für Formeln der Gestalt $\forall x_1\exists y_1\forall x_2\exists y_2 \cdots\forall x_n\exists y_n: P(x_1,y_1,x_2,y_2,\ldots,x_n,y_n)$

als Zweipersonenspiel: für den ersten Zug von $x$ gibt es einen Antwortzug für $y$, so daß für jeden …

und $P(\cdots)$ beschreibt die Gewinnbedingung
viele andere Zweipersonenspiele $\in \textsf{PSPACE}$

genauer, das Entscheidungsproblem $\{s \mid \text{Position$s$ist sicherer Gewinn für Spieler 2}\}$

wenn die Länge des Spiels polynomiell beschränkt ist

Bsp: Stefan Reisch, HEX ist PSPACE-vollständig, Acta Inf. 15(2)1981, 167–191

Beziehungen zwischen Platz und Zeit

Satz: $\textsf{DTIME}(f)\subseteq\textsf{DSPACE}(f)$. Beweis: klar.
Satz: $\textsf{DSPACE}(f)\subseteq\textsf{DTIME}(2^{O(f)})$

(dabei $2^{O(f)} := \bigcup_{c>0} (n\mapsto 2^{c\cdot f(n)}$)
Beweis: sei $M\in\textsf{DSPACE}_\text{Alg}(f)$.

wenn $M(x)$ mit $f(|x|)$ Platz akzeptiert,

dann sind alle Konfigurationen verschieden (sonst $\bot$),

es gibt $\le |\Sigma|^{f(|x|)} = 2^{\log_2 |\Sigma| f(|x|)}$ Konfigurationen

also höchstens so viele Schritte.
Folgerung: $f$ berechenbar $\Rightarrow$ $\textsf{DSPACE}(f)\subseteq \operatorname{REC}$

Beweis $\textsf{DSPACE}(f)\subseteq \textsf{DTIME}(2^{O(f)})\subseteq \operatorname{REC}$
Folgerung: $\textsf{DSPACE}(\log)\subseteq P$, $\textsf{PSPACE}\subseteq \textsf{DEXPTIME}$

Reduktion, Vollständigkeit

Def. $\le_{\textsf{P}}$ wie gehabt
Satz: $\textsf{PSPACE}$ ist abgeschlossen bzgl. $\le_{\textsf{P}}$:

$\forall L_1,L_2: L_1\le_{\textsf{P}}L_2 \wedge L_2\in\textsf{PSPACE}\Rightarrow L_1\in\textsf{PSPACE}$

Beweis: Reduktionsfunktion $f$ ist in polynomieller Zeit, also in polynomiellem Platz berechenbar.
Def: $L$ ist PSPACE-vollständig, gdw. $L\in\textsf{PSPACE}\wedge\forall L'\in\textsf{PSPACE}: L'\le_{\textsf{P}}L$
Satz: $\textsf{QBF}$ ist PSPACE-vollständig.

Beweis (folgt)

Nichtdeterministischer Platz

Def: $\textsf{NSPACE}(f)$ : Probleme lösbar durch nichtdeterministische TM mit Arbeitsband $\le f(|\text{Eingabe}|)$
Satz $\textsf{DSPACE}(f)\subseteq \textsf{NSPACE}(f)$. (ist trivial)
Satz (Savitch) $\textsf{NSPACE}(f)\subseteq \textsf{DSPACE}(f^2)$.

Beweis (Idee): es ist $I(x)\to_M^{\le 2^{c\cdot f(|x|)}} F$ zu entscheiden.

verwende UP mit Spez. $R(x,e,y) \iff x\to_M^{\le 2^e}y$ :

$R(x,0,y) := x\to_M^{0,1} = (x=y) \vee (x\to_M y)$

$R(x,e+1,y) := \bigvee_{h\in\text{Config}} (R(x,e,h)\wedge R(h,e,y))$.

mit Nachnutzung des Platzes. Kellertiefe ist $\le f(|x|)$, jeder Eintrag im Keller ist $\le f(|x|)$, Keller braucht Platz $\le f(|x|)^2$
Bemerkung: gilt nur für platzkonstruierbare $f\in\Omega(\log)$
Folgerung $\textsf{DSPACE}(\text{poly})=\textsf{NSPACE}(\text{poly})=\textsf{PSPACE}$

QBF ist PSPACE-vollständig

noch zu zeigen: $L\in\textsf{PSPACE}\Rightarrow L\le_{\textsf{P}}\textsf{QBF}$.
sei $M$ eine PSPACE-Maschine für $L$,
benutze Formel von vorhin

$R(x,e+1,y) := \bigvee_{h\in\text{Config}} (R(x,e,h)\wedge R(h,e,y))$.
äquivalent:

$R(x,e+1,y) := \exists h \forall a,b: ((a=x\wedge b=h)\vee \dots)\Rightarrow R(a,e,b)$
damit erhält man eine Formel

der Größe $\le \log_2(|\Sigma|^{\text{poly}(|x|)})$, also polynomiell in $|x|$

diese ist wahr gdw. $M$ akzeptiert Eingabe $x$.

PSPACE-vollst. Einpersonenspiele

$M\in\textsf{PSPACE}$ akzeptiert $x$

$\iff$ es gibt eine passende Konfigurationsfolge.
Platz für jede Konf. $\le f(|x|)$ mit $f\in\text{poly}$, Länge $\le 2^{O(f)}$
Konf. kann auch die Anordnung von Spielsteinen auf einem (beschränkten) Brett sein
Übergang $=$ Spielzug $=$ (z.B.) Verschieben von Steinen
Joseph C. Culberson: Sokoban is PSPACE-complete, 1997 , http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.41

$\textsf{Sokoban}\in\textsf{PSPACE}$ ist leicht, Vollständigkeit ist schwer.
Rush Hour ist PSPACE-vollständig. Lunar Lockout auch?

Zusammenfassung Zeit und Platz

aus bisherigen Betrachtungen folgt:

$\textsf{L}\subseteq \textsf{NL}\subseteq \textsf{P}\subseteq \textsf{NP}\subseteq \textsf{PSPACE}\subseteq \textsf{EXP}\subseteq \textsf{NEXP}$

(dabei $\textsf{L}=\textsf{DSPACE}(\log)$, $\textsf{EXP}=\textsf{DTIME}(\exp)$)
es ist anzunehmen, daß alle Inklusionen echt sind

aber zeigen kann man derzeit nur

$\textsf{L}\subset \textsf{PSPACE}$, $\textsf{P}\subset \textsf{EXP}$

durch Platz- und Zeithierarchiesätze

Ein Hierarchie-Satz

Def. zeit-beschränktes Halteproblem

$K_f := \{(x,y) \mid \phi_x(y) \text{akzeptiert in} \le f(|y|) \text{Schritten}\}$
Satz: $K_f\in\textsf{DTIME}(f^3)$. Beweis: Simulation durch eine Maschine $S$ mit zwei Bändern (eines für $x$, anderes als Arbeitsband für $\phi_x$)
Satz: $K_f\notin\textsf{DTIME}(f/2)$. Beweis (indirekt). Falls $K_f$ entschieden durch $M$, dann betrachte Programm $P: x\mapsto \neg M(x,x)$ und Aufruf $P(P)$.
Folgerung $\textsf{DTIME}(f)\subset\textsf{DTIME}((2f)^3)$.
Folgerung $\textsf{PTIME}\subset \text{EXPTIME}$

Bew: $K_f$ für $f=(n\mapsto 2^n)$.

Schaltkreise und Parallelität

Schaltkreis-Klassen

$\textsf{AC}^d,\textsf{NC}^d$: Menge der Entscheidungsprobleme,

die lösbar sind durch Schaltkreise mit Operationen

$\neg$ sowie $\wedge, \vee$ (zweistellig: $\textsf{NC}^d$, mehrstellig: $\textsf{AC}^d$)

uniform mit Größe $O(\text{poly})$, Tiefe $O(\log^d(n))$
Satz: Parität $\in\textsf{NC}^1$, Parität $\notin\textsf{AC}^0$
Bsp: Produkt von Relationen (Booleschen Matrizen) $\in\textsf{AC}^0$, auch $\in \textsf{NC}^1$
Bsp: reflexiv-transitive Hülle $\in \textsf{AC}^1$, auch $\in\textsf{NC}^2$
vgl. https://complexityzoo.uwaterloo.ca/

Beziehungen zu Zeit- und Platzklassen

Satz: $\forall d \ge 0: \textsf{NC}^d\subseteq \textsf{AC}^d \subseteq \textsf{NC}^{d+1}$
Def: $\textsf{NC}:= \bigcup_{d\ge 0} \textsf{NC}^d$, $\textsf{AC}:= \bigcup_{d\ge 0} \textsf{AC}^d$.
Satz: $\textsf{NL}\subseteq\textsf{NC}= \textsf{AC}\subseteq \textsf{P}$. Beweise:
- $\textsf{NC}=\textsf{AC}$: wg. vorigem Satz
- $\textsf{NL}\subseteq\textsf{AC}$: refl-tr. Hülle der Übergangsrelation
  
  (auf $\exp(c\cdot \log |x|) = \text{poly}(|x|)$ vielen Zuständen)
- $\textsf{AC}\subseteq \textsf{P}$: Schaltkreis-Auswertung schichtweise

$\operatorname{\le_{\textsf{L}}}$ und $\textsf{P}$-Vollständigkeit

Def: $A \operatorname{\le_{\textsf{L}}}B$ falls $\exists f\in\textsf{FSPACE}(\log): \forall x: x\in A\iff f(x)\in B$
Satz: $\operatorname{\le_{\textsf{L}}}$ ist transitiv.

Beweis — Vorsicht: $g(f(x))$ naiv benötigt zuviel Platz!
Satz: $A\operatorname{\le_{\textsf{L}}}B\wedge B\in\textsf{NC}\Rightarrow A\in\textsf{NC}$
Satz: $A\operatorname{\le_{\textsf{L}}}B\wedge B\in\textsf{P}\Rightarrow A\in\textsf{P}$
Def: $B$ heißt $\textsf{P}$-vollständig: $B\in\textsf{P}\wedge\forall A\in\textsf{P}:A\operatorname{\le_{\textsf{L}}}B$.
Satz: Schaltkreisauswertung ist $\textsf{P}$-vollständig.
Modellierung für parallele Komplexität:
- $\textsf{NC}$: Aufgaben mit gut parallelisierbarer Lösung
- $\operatorname{\le_{\textsf{L}}}$: Reduktion, die Parallelisierbarkeit erhält
- $\textsf{P}$-vollständig: keine gute parallelen Alg. bekannt,

Einleitung, Überblick

Inhalt und Ziel der Vorlesung

Ist jede Funktion \(\mathbb{N}\to\mathbb{N}\) berechenbar?

Eigenschaften von Grammatiken

Sind diese Aufgaben gleich schwer?

Praktische Problemstellungen

Geschichte des Algorithmenbegriffs

Bedeutung des Algorithmenbegriffs

Literatur

Registermaschinen

Motivation, Eigenschaften

Semantik: Speicher

Syntax: Befehle und Programme

Semantik: Befehle

Semantik: Programme

Ein Programm für \(x\mapsto 2x\)

Elementare goto-berechenbare Fkt.

Abschluß-Eigenschaften

Zusammenfassung GOTO (bis jetzt)

Übungsaufgaben

Strukturierte Programmierung

Motivation

Syntax

Semantik (Prinzip, elementare Prog.)

Semantik für zusammengesetzte Prog.

While-berechenbare Funktionen

Ein Interpreter für \(\operatorname{\textsf{WHILE}}\)

Beziehungen zw. Goto- und While-B.

Von While zu Goto (Prinzip)

Von While zu Goto (elementar, Seq)

Von While zu Goto (IfZ)

Von While zu Goto (While)

Von While zu Goto (insgesamt)

Von Goto zu While

Von Goto nach While: Ansatz

Von Goto nach While: Einzelheiten

Das Normalform-Theorem für While

Garantierte Termination: Loop

Motivation

Loop-Programme

Loop-Programme und Softwaretechnik

LOOP und WHILE

Die Ackermann-Funktion

Eigenschaften der Ackermann-Funktion

Übung KW 47

Kodierung strukturierter Daten

Motivation

Kodierung von Zahlenpaaren

Kodierung von Listen

Kodierung von Bäumen

Universelle Programme und Halteproblem

Kodierung von Programmen

Ein universelles Goto-Programm

Das Halteproblem

Das Halteproblem (Folgerung)

Diagonalisierung

Maschinenunabhängige Berechenbarkeitstheorie

Motivation

Übliche Namen für Funktionenklassen

These von Church und Turing

Ein Fixpunktsatz

Der Satz von Rice

Der Satz von Rice (Beweis)

Busy-Beaver-Programme

Übung KW48

Entscheidbare Mengen, Reduktion

Motivation, Definition REC

Abschlußeigenschaften von \(\operatorname{REC}\)

Reduktion \(\le_m\)

Anwendungen der Reduktion

Aufzählbare Mengen

Motivation, Definition RE

Eine äquivalente Charakterisierung von RE

Abschlußeigenschaften von RE

Eine Beziehung zw. RE und REC

RE und \(\le_m\)

Die schwersten Probleme in RE

Übungsaufgaben

Turing-Maschinen

Motivation Turing-Maschine