Theoretische Informatik

Lektion 10: Entscheidbarkeit
Theoretische Informatik
Lektion 10: Entscheidbarkeit
Kurt-Ulrich Witt
Wintersemester 2013/14
Kurt-Ulrich Witt
Theoretische Informatik • Lektion 10
1/15
Lektion 10: Entscheidbarkeit
Inhaltsverzeichnis
Existenz unentscheidbarer Probleme
Entscheidbare und semi-entscheidbare Mengen
Reduzierbarkeit von Mengen
Unentscheidbare Mengen
Kurt-Ulrich Witt
Theoretische Informatik • Lektion 10
2/15
Lektion 10: Entscheidbarkeit
Existenz unentscheidbarer Probleme
Entscheidbare und semi-entscheidbare Mengen
Reduzierbarkeit von Mengen
Unentscheidbare Mengen
Existenz unentscheidbarer Probleme
Übung 10 Aufgabe 3:
NN = { ϕ : N → N | ϕ total } ist überabzählbar.
=⇒ Es existieren überabzählbar viele nicht berechenbare Probleme.
Kurt-Ulrich Witt
Theoretische Informatik • Lektion 10
3/15
Lektion 10: Entscheidbarkeit
Existenz unentscheidbarer Probleme
Entscheidbare und semi-entscheidbare Mengen
Reduzierbarkeit von Mengen
Unentscheidbare Mengen
Entscheidbare und semi-entscheidbare Mengen
Definition: Sei Σ ein Alphabet. Eine Menge L ⊆ Σ∗ ist entscheidbar, falls die
charakteristische Funktion von L
χL : Σ∗ → { 0, 1 }
definiert durch
(
χL (w) =
1, falls w ∈ L
0, falls w ∈
/L
berechenbar ist. L heißt semi-entscheidbar, falls die semi-charakteristische
Funktion
χ0L : Σ∗ → { 0, 1 }
definiert durch
(
0
χL (w) =
1, falls w ∈ L
⊥, falls w ∈
/L
berechenbar ist.
Kurt-Ulrich Witt
Theoretische Informatik • Lektion 10
4/15
Existenz unentscheidbarer Probleme
Entscheidbare und semi-entscheidbare Mengen
Reduzierbarkeit von Mengen
Unentscheidbare Mengen
Lektion 10: Entscheidbarkeit
Entscheidbare und semi-entscheidbare Mengen
Satz 10a: L ⊆ Σ∗ ist genau dann entscheidbar, wenn sowohl L als auch
L = Σ∗ − L semi-entscheidbar sind.
Beweis „⇒“: Ist L entscheidbar, dann ist χL berechenbar. Wir definieren
(
0
L
χ (w) =
1,
⊥,
falls χL (w) = 1
falls χL (w) = 0
sowie
0
χ (w) =
L
(
1,
⊥,
falls χL (w) = 0
falls χL (w) = 1
⇒ χ0 und χ0 berechenbar ⇒ L und L semi-entscheidbar.
L
L
„⇐“: Es sei TL und T mit fT
L
L
= χ0 bzw. fT
L
L
= χ0 . Dann berechnet das folgende Programm χL :
L
read(w);
` := 0; fertig := false;
while not fertig do
if TL stoppt bei Eingabe w in ` Schritten then x := 1; fertig := true
else if T stoppt bei Eingabe w in ` Schritten then x := 0; fertig := true
L
endif;
` := ` + 1
endwhile;
write(x).
Kurt-Ulrich Witt
Theoretische Informatik • Lektion 10
5/15
Lektion 10: Entscheidbarkeit
Existenz unentscheidbarer Probleme
Entscheidbare und semi-entscheidbare Mengen
Reduzierbarkeit von Mengen
Unentscheidbare Mengen
Entscheidbare und semi-entscheidbare Mengen
Definition: Sei Σ ein Alphabet. Eine Sprache L ⊆ Σ∗ heißt
rekursiv-aufzählbar, falls L = ∅ ist, oder falls eine totale berechenbare
Funktion f : N0 → Σ∗ existiert, so dass für alle w ∈ L ein i existiert mit
f (i) = w.
Es gilt also L = W (f ) für eine total berechenbare Funktion f : N0 → Σ∗ :
L = { f (0), f (1), f (2), . . . }
REΣ = Klasse der rekursiv-aufzählbaren Sprachen über Σ.
Kurt-Ulrich Witt
Theoretische Informatik • Lektion 10
6/15
Lektion 10: Entscheidbarkeit
Existenz unentscheidbarer Probleme
Entscheidbare und semi-entscheidbare Mengen
Reduzierbarkeit von Mengen
Unentscheidbare Mengen
Entscheidbare und semi-entscheidbare Mengen
Satz: Sei Σ ein Alphabet. Eine Sprache L ⊆ Σ∗ ist genau dann
rekursiv-aufzählbar, wenn sie semi-entscheidbar ist.
Beweis „⇒“: Es sei f : N0 → Σ∗ total berechenbar mit L = W (f ) und T Turingmaschine mit fT = f . Dann
berechnet das folgende Programm χ0 :
L
read(w);
i := 0; fertig := false;
while not fertig do
if fT (i) = w then x 0 := 1; fertig := true endif;
i := i + 1;
endwhile;
write(x 0 ).
read(w);
i := 0;
while fT (i) − w 6= 0 do
i := i + 1;
endwhile;
x 0 := sign(i + 1);
write(x 0 ).
g(w, i) = f (i) − w
χ0 = C [sign; µ [g]]
L
„⇐“: Es sei L 6= ∅, v ∈ L, und T Turingmaschine mit fT = χ0 . Dann berechnet das folgende Programm eine total
berechenbare Funktion f : N0 → Σ∗ mit L = W (f ):
L
read(i);
if T bei Eingabe von cantor−1
(i) in cantor−1
(i)-Schritten stoppt und 1 ausgibt
21
22
then w := cantor−1
(i)
21
else w := v
endif;
write(w).
Kurt-Ulrich Witt
Theoretische Informatik • Lektion 10
7/15
Lektion 10: Entscheidbarkeit
Existenz unentscheidbarer Probleme
Entscheidbare und semi-entscheidbare Mengen
Reduzierbarkeit von Mengen
Unentscheidbare Mengen
Entscheidbare und semi-entscheidbare Mengen
Satz: Sei Σ ein Alphabet und L ⊆ Σ∗ . Folgende Aussagen sind äquivalent:
L ist rekursiv-aufzählbar (es gibt eine total berechenbare Funktion
f : N0 → Σ∗ mit L = W (f )).
L ist semi-entscheidbar.
χ0L ist berechenbar.
Es gibt eine Turingmaschine T, die L akzeptiert: L = L(T).
Es gibt eine Typ-0-Grammatik G, die L erzeugt: L = L(G).
Es gibt eine berechenbare Funktion g : Σ∗ → N0 mit Def (g) = L.
Es gibt eine Turingmaschine, welche die Wörter von L auf ein Band
schreibt.
Satz: Sei Σ ein Alphabet und L ⊆ Σ∗ .
a) Dann ist L entscheidbar genau dann, wenn eine Turingmaschine existiert,
welche die Wörter von L längen-lexikografisch geordnet auf ein Band
schreibt.
b) ksS Σ ⊂ RΣ .
Kurt-Ulrich Witt
Theoretische Informatik • Lektion 10
8/15
Lektion 10: Entscheidbarkeit
Existenz unentscheidbarer Probleme
Entscheidbare und semi-entscheidbare Mengen
Reduzierbarkeit von Mengen
Unentscheidbare Mengen
Reduzierbarkeit von Mengen
Definition: Sei Σ∗ ein Alphabet. L1 ⊆ Σ∗ heißt reduzierbar auf L2 ⊆ Σ∗ , falls
es eine totale berechenbare Funktion f : Σ∗ → Σ∗ gibt mit
w ∈ L1 genau dann, wenn f (w) ∈ L2 für alle w ∈ Σ∗
Ist L1 reduzierbar auf L2 (mittels der totalen berechenbaren Funktion f ), so schreiben wir L1 ≤ L2 (oder L1 ≤f L2 ,
falls die Funktion, mit der die Reduktion vorgenommen wird, genannt werden soll).
Satz: Es seien L1 , L2 ⊆ Σ∗ . Ist L1 ≤ L2 und ist L2 entscheidbar oder
semi-entscheidbar, dann ist auch L1 entscheidbar bzw. semi-entscheidbar.
Beweis (für Entscheidbarkeit, für Semi-Entscheidbarkeit analog) Wir definieren χL
: Σ∗ → { 0, 1 } durch
1
χL (w) = χL (f (w))
1
2
Es gilt:
χL
1
ist die charakteristische Funktion von L1 , denn es ist

χL (f (w)) =
2
χL
1
1,
0,
ist berechenbar, denn f und χL
f (w) ∈ L2
f (w) ∈
/ L2
ff

=
1, w ∈ L1
0, w ∈
/ L1
ff
= χL (w)
1
sind berechenbar.
2
Kurt-Ulrich Witt
Theoretische Informatik • Lektion 10
9/15
Lektion 10: Entscheidbarkeit
Existenz unentscheidbarer Probleme
Entscheidbare und semi-entscheidbare Mengen
Reduzierbarkeit von Mengen
Unentscheidbare Mengen
Reduzierbarkeit von Mengen
Folgerung 10a: Es seien L1 , L2 ⊆ Σ∗ . Ist L1 ≤ L2 und ist L1 nicht
entscheidbar oder nicht semi-entscheidbar, dann ist auch L2 nicht
entscheidbar bzw. nicht semi-entscheidbar.
Kurt-Ulrich Witt
Theoretische Informatik • Lektion 10
10/15
Lektion 10: Entscheidbarkeit
Existenz unentscheidbarer Probleme
Entscheidbare und semi-entscheidbare Mengen
Reduzierbarkeit von Mengen
Unentscheidbare Mengen
Unentscheidbare Mengen
Das Halteproblem
H = { w&x ∈ Ω∗ | < T > = w und T stoppt bei Eingabe von x }
oder
H = { (i, j) | j ∈ Def(ϕi ) }
Das Selbstanwendbarkeitsproblem (spezielles Halteproblem)
K = { w ∈ Ω∗ | < T > = w und T stoppt bei Eingabe von w }
oder
K = { i | i ∈ Def(ϕi ) }
Kurt-Ulrich Witt
Theoretische Informatik • Lektion 10
11/15
Lektion 10: Entscheidbarkeit
Existenz unentscheidbarer Probleme
Entscheidbare und semi-entscheidbare Mengen
Reduzierbarkeit von Mengen
Unentscheidbare Mengen
Unentscheidbare Mengen
Satz 10b: K ist nicht entscheidbar.
Beweis Annahme: K sei entscheidbar. Dann ist χK berechenbar, d.h. es gibt ein p mit χK = ϕp . Wir definieren
die Funktion g durch
(
1, falls ϕp (j) = 0
g(j) =
⊥, falls ϕp (j) = 1
g ist berechenbar, also gibt es ein q mit g = ϕq . Damit gilt:
ϕq (q) = 1
genau dann, wenn
g(q) = 1
genau dann, wenn
ϕp (q) = 0
genau dann, wenn
χK (q) = 0
genau dann, wenn
q ∈
/ K
genau dann, wenn
q ∈
/ Def(ϕq )
genau dann, wenn
ϕq (q) = ⊥
0
Damit haben wir die Aussage
ϕq (q) = 1 genau dann, wenn ϕq (q) = ⊥
hergeleitet, die offensichtlich einen Widerspruch darstellt. Unsere Annahme, dass K entscheidbar ist, muss also
falsch sein.
Kurt-Ulrich Witt
Theoretische Informatik • Lektion 10
12/15
Lektion 10: Entscheidbarkeit
Existenz unentscheidbarer Probleme
Entscheidbare und semi-entscheidbare Mengen
Reduzierbarkeit von Mengen
Unentscheidbare Mengen
Unentscheidbare Mengen
Folgerung 10b: H ist nicht entscheidbar.
Beweis Definiere f : N0 → N0 durch f (i) = (i, i). Dann gilt
f ist berechenbar.
i ∈ K gdw. (i, i) ∈ H gdw. f (i, i) ∈ H
also K ≤ H, also mit Folgerung 10a H nicht entscheidbar, da K nicht entscheidbar (Satz 10b).
Satz 10c: K und H sind rekursiv-aufzählbar (semi-entscheidbar).
Beweis χK (i) = uϕ (i, i) + 1) bzw. χH (i, j) = uϕ (i, j) + 1)
Satz: K und H nicht rekursiv-aufzählbar (nicht semi-entscheidbar).
Beweis Wegen Sätze 10a, 10b bzw. Folgerung 10b und Satz 10c.
Satz: REGΣ ⊂ kfSΣ ⊂ ksSΣ ⊂ RΣ ⊂ REΣ ⊂ P(Σ∗ )
Kurt-Ulrich Witt
Theoretische Informatik • Lektion 10
13/15
Lektion 10: Entscheidbarkeit
Existenz unentscheidbarer Probleme
Entscheidbare und semi-entscheidbare Mengen
Reduzierbarkeit von Mengen
Unentscheidbare Mengen
Unentscheidbare Mengen
Das Korrektheitsproblem
Satz: Sei f : N0 → N0 eine Funktion, dann ist die Menge
Pf = { i | ϕi = f }
nicht rekursiv-aufzählbar, damit nicht semi-entscheidbar und somit auch nicht
entscheidbar.
Das Äquivalenzproblem
Satz: Die Menge
A = { (i, j) | ϕi = ϕj }
ist nicht rekursiv-aufzählbar, damit nicht semi-entscheidbar und somit auch
nicht entscheidbar.
Kurt-Ulrich Witt
Theoretische Informatik • Lektion 10
14/15
Lektion 10: Entscheidbarkeit
Existenz unentscheidbarer Probleme
Entscheidbare und semi-entscheidbare Mengen
Reduzierbarkeit von Mengen
Unentscheidbare Mengen
Unentscheidbare Mengen
Der Satz von Rice: Sei E ⊆ P mit E 6= ∅ und E 6= P, dann ist die Menge
A = { i | ϕi ∈ E } nicht entscheidbar.
Kurt-Ulrich Witt
Theoretische Informatik • Lektion 10
15/15

Download Report