Einleitung, Überblick

Inhalt und Ziel der Vorlesung

(Quelle: Modulbeschreibung)

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

Nein! (Das ist ein wichtiges Resultat und wir sehen eine wichtige Beweismethode.)

Eigenschaften von Grammatiken

gesucht ist jeweils Algorithmus mit dieser Eigenschaft:

Eingabe ist Paar \((G_1,G_2)\) von Grammatiken,
Ausgabe ist 1, falls \(L(G_1)=L(G_2)\), sonst 0

praktische Motivation: Test bzw. Verkleinerung von regulären Ausdrücken, von Grammatiken (automatische Bewertung von Übunsgaufgaben zu AFS!)

Methode: Reduktion: wenn \(E_2\) entscheidbar, dann auch …

Sind diese Aufgaben gleich schwer?

(eine typische Frage der Komplexitätstheorie)

Praktische Problemstellungen

Berechenbarkeitsmodell \(=\) Programmierparadigma

für jede dieser Def.:

zwischen diesen Def.:

Geschichte des Algorithmenbegriffs

Suche nach Lösungsverfahren für mathematische Aufgaben (symbolische Differentiation, Integration, Gleichungssysteme)

…bzw. nach Beweisen für deren Nicht-Existenz

Bedeutung des Algorithmenbegriffs

(nach K. Wagner: Theor. Inf., Springer 2003)

Literatur

(akt.) Lehrbücher

Klassisch:

Registermaschinen

Motivation, Eigenschaften

wir formalisieren das imperative Programmieren:

Eigenschaften dieses Modells:

Semantik: Speicher

Syntax: Befehle und Programme

Bsp. für ein Programm:

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

Semantik: Befehle

Semantik: Programme

Ü: 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:

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

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

Elementare goto-berechenbare Fkt.

diese Funktionen sind goto-berechenbar:

Abschluß-Eigenschaften

Zusammenfassung GOTO (bis jetzt)

später werden wir sehen

Übungsaufgaben

  1. GOTO-Programme für elementare Funktionen: in Olat/Autotool ausprobieren. (Ggf. Highscore-Wertung für kurze Programme.)

  2. Ü: gilt \(s[a:=b][c:=d] = s[c:=d][a:=b]\) ?

  3. 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.)

  4. 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.

  5. 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.

  6. 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\)

Beispiel:

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)=\)

Semantik für zusammengesetzte Prog.

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

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

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

While-berechenbare Funktionen

Übungsaufgaben:

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

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:

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:

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:

zusammengesetzte:

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):

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

Von Goto zu While

das scheint schwieriger:

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=\)

Ü: 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:

zusammen mit \(\operatorname{\textsf{WHILE}}\subseteq\operatorname{\textsf{GOTO}}\) folgt

äquivalent\(=\) berechnet dieselbe partielle Funktion.

Ü: wie unterscheiden sich die Laufzeiten?

Garantierte Termination: Loop

Motivation

Loop-Programme

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

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

LOOP und WHILE

Die Ackermann-Funktion

Eigenschaften der Ackermann-Funktion

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

Übung KW 47

  1. Aufgaben zu While- und Loop-Programmen in autotool

  2. 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}}\).

  3. Zeigen Sie für einstellige partielle Funktionen:

    \(f,g\in\operatorname{\textsf{WHILE}}\Rightarrow (x\mapsto f(g(x)))\in\operatorname{\textsf{WHILE}}\).

  4. 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\).

  5. 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

Kodierung von Zahlenpaaren

gesucht sind (goto-berechenbare) Funktionen

mit Spezifikation (vgl. objektorientierte Datenmodellierung)

da gibt es viele verschiedene Möglichkeiten

Ü: 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:

Ü: 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

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:

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

Ein universelles Goto-Programm

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)

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:

Anwendungen bisher:

Maschinenunabhängige Berechenbarkeitstheorie

Motivation

Übliche Namen für Funktionenklassen

Begründung:

These von Church und Turing

Ein Fixpunktsatz

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

Beweis:

Ü: 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:

Beispiele (semantisch oder nicht?)

Der Satz von Rice (Beweis)

Busy-Beaver-Programme

Übung KW48

  1. Beispiel-Rechnungen (siehe Folien) zu Kodierung von Paaren, Listen, Bäumen

  2. 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.

  3. 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.

  4. 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\).

  5. 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.

  6. 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.)

  7. Ü-Aufgabe von Folie Fixpunktsatz.

  8. 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

  9. 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

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

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

wenn \(A,B\in \operatorname{REC}\), dann

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\).

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)

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.

Aufzählbare Mengen

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

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

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:

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\)

Ü: \(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:

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:

Übungsaufgaben

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

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

  1. (KW49) \(\le_m\) ist: transitiv, reflexiv?, symmetrisch? antisymmetrisch?

  2. (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\).

  3. (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.

  4. (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}\)

  5. 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\}\) ?

  6. \(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)

  7. (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.

  8. (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

  9. (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}\)

Turing-Maschinen

Motivation Turing-Maschine

TM: Semantik (im Grundsatz)

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

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

Bezeichnungen für \(k\)-Band-Turing-Maschine:

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

Das Programm einer TM besteht aus

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

TM: Beispiel

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\}\)

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

finale Konfiguration mit Ausgabe \(v\in\Sigma^*\):

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

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.

\(\operatorname{\textsf{Goto}}\subseteq \textsf{Turing}\)

Satz: \(f\) ist Goto-berechenbar \(\Rightarrow\) \(f\) ist Turing-berechenbar.

Beweis (Idee):

Ü: 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):

Beachte bei Realisierung:

Maschinen mit wenigen Registern

Übung TM

  1. 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)

  2. 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

SRS, Markov-Algorithmen (MA)

Vergleich MA — TM

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:

Das Postsche Korrespondenzproblem

Motivation

Definition

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)

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')\)

\(\operatorname{\textsf{PCP}}\notin\operatorname{REC}\)

Eine unentscheidbare Eigenschaft von CFG

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

Unentscheidbarkeit in der Logik

Prädikatenlogik

Das Allgemeingültigkeitsproblem \(\textsf{APL}\) ist

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

Arithmetik

Unvollständigkeit von Beweissystemen

Bezeichnung: eine PL-Formel \(F\) heißt

Satz: Menge der ableitbaren Formeln \(\in\) RE

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

Bezeichnung: ein Inferenzsystem heißt

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

  1. In der Kleinschen 4-Gruppe gilt: \(ab=ba\). Beweise durch

    1. geometrischen Anschauung,

    2. eine Gleichungskette unter Benutzung der Relationen

  2. Für das SRS \(\{ab\to baa\}\): Normalform von \(a^kb\), von \(a b^k\).

  3. Ergänze Simulation der TM durch MA (Kopfbewegungen \(H\), \(L\))

  4. autotool-Aufgabe PCP

  5. 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.

  6. 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)

  7. 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

Eine Charakterisierung von RE

Orakel-Maschinen

Komplexitätstheorie

Motivation

Definition

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

Eigenschaften von Zahlen

Das Erfüllbarkeitsproblem

Boolesche Schaltkreise

Das Färbungsproblem

Bemerkung zur Genauigkeit

bisher:

jetzt:

Deterministische Zeit, Bps.: P

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

Nichtdeterministische Zeit, Bsp: NP

Die Klasse coNP

Vergleich: Berechenbarkeit/Komplexität

bis jetzt:

nächste VL:

Übungsaufgaben P/NP

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

  1. (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.

  2. 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

  3. (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}\).

  4. Zahlen

    1. \(\textsf{SQUARES}\in\textsf{NP}\) (trivial), \(\textsf{SQUARES}\in \textsf{P}\)

    2. \(\textsf{PRIMES}\in\textsf{NP}\) (Satz von Fermat, primitive Wurzeln)

  5. 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}\)?

  6. 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)

NP-Vollständigkeit

Motivation

nach bisherigen Definitionen/Beispielen:

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

Polynomialzeit-Reduktion \(\le_\textsf{P}\)

\(\le_\textsf{P}\) ist transitiv

Abschluß-Eigenschaften von \(\le_\textsf{P}\)

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

\(\textsf{CIRC}\textsf{SAT}\in\textsf{NPc}\)

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

Gregory Tseitin, 1966

Tseitin-Transformation. Einzelheiten

Cook und Tseitin in der Praxis

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

…und gute CNFSAT-Solver gibt es tatsächlich

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

Übungsaufgaben NP, SAT

Vergangenheit und Zukunft

Aktueller Stand der Vorlesung: wir sind hier

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\)

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

Vertex Cover

Edge Cover

3-Färbbarkeit

Rucksack (Subset Sum)

Definition:

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

Konstruktion: \(F\) mit \(n\) Variablen, \(m\) Klauseln,

Hamiltonkreis

Handlungsreisender (TSP)

(travelling salesperson)

Formulierung als eingeschränktes Optimierungsproblem:

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

Clique, Subgraph Isomorphism, Graph Isomorphism

Übungsaufgaben KW55

Plan der Vorlesung

Übersicht nach Kalenderwochen