VL-05: Unentscheidbarkeit II · VL-05: Unentscheidbarkeit II (Berechenbarkeit und Komplexit at, WS 2019) Gerhard Woeginger WS 2019, RWTH BuK/WS 2019 VL-05: Unentscheidbarkeit II 1/42

VL-05: Unentscheidbarkeit II

(Berechenbarkeit und Komplexitat, WS 2019)

Gerhard Woeginger

WS 2019, RWTH

BuK/WS 2019 VL-05: Unentscheidbarkeit II 1/42

Organisatorisches

Nachste Vorlesungen:

Freitag, November 1: Keine Vorlesung

Mittwoch, November 6, 10:30–12:00, Aula

Freitag, November 8, 12:30–14:00 Uhr, Audimax

Webseite:

https://algo.rwth-aachen.de/Lehre/WS1920/BuK/BuK.py


Wiederholung


Wdh.: Abzahlbarkeit

Eine Menge M heisst abzahlbar,

wenn M leer oder wenn es surjektive Funktion c : N→ M gibt.

Beispiele: endliche Mengen; N, Z, Q; {0, 1}∗; jede formale Sprache;

Menge der Godelnummern; Menge der TMen; Menge der Algorithmen

Eine Menge heisst uberabzahlbar, wenn sie nicht abzahlbar ist.

Beispiele: R; P(N); P({0, 1}∗); Menge aller Berechnungsprobleme

Direkte Schlussfolgerung

Es existieren nicht-berechenbare Probleme.


Wdh.: Unentscheidbarkeit der Diagonalsprache

Definition (Diagonalsprache)

D = {w ∈ {0, 1}∗ | w = wi und Mi akzeptiert w nicht}

Satz

Die Diagonalsprache D ist nicht entscheidbar.

Beweis: Durch Diagonalisierung


Wdh.: Unentscheidbarkeit der Diagonalsprache

Ai ,j =

{1 falls Mi das Wort wj akzeptiert

0 sonst

w0 w1 w2 w3 w4M0 0 1 1 0 1 · · ·M1 1 0 1 0 1 · · ·M2 0 0 1 0 1 · · ·M3 0 1 1 1 0 · · ·M4 0 1 0 0 0 · · ·...

......

......

Die Diagonalsprache lasst sich

von der Diagonale der Matrix

ablesen. Es gilt

D = {wi | Ai ,i = 0}


Wdh.: Bisher betrachtete unentscheidbare Probleme

Die folgenden Probleme sind nicht entscheidbar:

Die Diagonalsprache:

D = {w ∈ {0, 1}∗ | w = wi und Mi akzeptiert w nicht}

Das Diagonalsprachenkomplement:

D = {w ∈ {0, 1}∗ | w = wi und Mi akzeptiert w}

Das Halteproblem:

H = {〈M〉w | M halt auf w}


Wdh.: Komplement der Diagonalsprache

MD

x

MD

accept

reject

accept

reject


Wdh.: Halteproblem

MD

w 〈Mi 〉w

accept accept

reject

reject

MHU

i mit

wi = wund

dann Mi


Vorlesung VL-05

Unentscheidbarkeit II

Das Epsilon-Halteproblem

Der Satz von Rice

Anwendungen von Rice

Abschlusseigenschaften





Definition (Epsilon-Halteproblem)

Hε = {〈M〉 | M halt auf der Eingabe ε }

Satz

Das Epsilon-Halteproblem Hε ist nicht entscheidbar.

Beweisidee:

Wir benutzen die Unterprogrammtechnik.

Aus einer TM Mε, die das Epsilon-Halteproblem Hε entscheidet,

konstruieren wir eine neue TM MH , die das (wie wir bereits wissen:

nicht-entscheidbare!!) Halteproblem H entscheidet.


Beweis (1)

Die neue TM MH mit Unterprogramm Mε arbeitet wie folgt:

(1) Falls die Eingabe nicht mit einer korrekten Godelnummer beginnt,

verwirft MH die Eingabe.

(2) Sonst, also auf Eingaben der Form 〈M〉w , berechnet MH die

Godelnummer einer TM M∗w mit den folgenden Eigenschaften:

Falls M∗w die Eingabe ε erhalt, so schreibt sie zunachst das Wort w

aufs Band und simuliert dann die TM M mit der Eingabe w .

Bei Eingaben ungleich ε kann sich M∗w beliebig verhalten.

(Wir legen fest, dass M∗w dann in eine Endlosschleife geht.)

(3) MH startet nun Mε mit der Eingabe 〈M∗w 〉 und akzeptiert (verwirft)

genau dann, wenn Mε akzeptiert (verwirft).


Beweis (2)

Illustration: Aus Mε konstruieren wir MH .

MH

x 〈M〉,w

accept

reject

reject (Syntax)

Mε〈M〉 und w

mit

x = 〈M〉w

〈M∗w 〉

Existenz von MH steht im Widerspruch zur Unentscheidbarkeit von H.

Daher gibt es Mε nicht.

Daher ist das Epsilon-Halteproblem Hε nicht entscheidbar.


Beweis (3): Korrektheit

Falls Eingabe nicht von der Form x = 〈M〉w ist, verwirft MH die Eingabe.

Wir nehmen nun an, dass Eingabe der Form x = 〈M〉w vorliegt.

Fur die Korrektheit ist somit noch zu zeigen:

〈M〉w ∈ H ⇒ MH akzeptiert 〈M〉w〈M〉w 6∈ H ⇒ MH verwirft 〈M〉w

〈M〉w ∈ H ⇒ M halt auf Eingabe w

⇒ M∗w halt auf der Eingabe ε

⇒ Mε akzeptiert 〈M∗w 〉⇒ MH akzeptiert 〈M〉w

〈M〉w 6∈ H ⇒ M halt nicht auf Eingabe w

⇒ M∗w halt nicht auf der Eingabe ε

⇒ Mε verwirft 〈M∗w 〉⇒ MH verwirft 〈M〉w


Entscheidbar vs unentscheidbar


Unentscheidbar versus entscheidbar (1)

Wir haben gesehen, dass die folgenden Probleme unentscheidbar sind:

Gegeben 〈M〉 und w , gilt w ∈ L(M)?

Gegeben 〈M〉, gilt ε ∈ L(M)?

Analoge Argumente zeigen, dass folgende Probleme unentscheidbar sind:

Ubung

Gegeben 〈M〉, gilt 〈M〉 ∈ L(M)?

Gegeben 〈M〉, ist L(M) leer?

Gegeben 〈M〉, gilt L(M) = Σ∗?

Gegeben 〈M〉, ist L(M) endlich?

Gegeben 〈M〉, ist L(M) unendlich?

Gegeben 〈M〉, ist L(M) regular?

Gegeben 〈M〉, ist L(M) kontext-frei?


Unentscheidbar versus entscheidbar (2)

Andrerseits ist jedes der folgenden Probleme entscheidbar:

Gegeben 〈M〉, gilt L(M) ⊆ {0, 1}∗?Gegeben 〈M〉, wird L(M) von einer TM akzeptiert?

Gegeben 〈M〉, gilt 2222 ∈ L(M)?

Gegeben 〈M〉, gilt 2222 /∈ L(M)?

Gegeben 〈M〉, hat M eine gerade Anzahl von Zustanden?

Gegeben 〈M〉, besitzt M einen Endzustand?

Gegeben 〈M〉, ist |〈M〉| eine Primzahl?

Anmerkung: Die TM M ist in Normalform mit Σ = {0, 1}


Partielle Funktionen

Da TMen im Allgemeinen nicht auf jeder Eingabe halten, berechnen sie

partielle Funktionen. Das konnen wir wie folgt formalisieren:

Die von einer TM M berechnete Funktion ist von der Form

fM : {0, 1}∗ → {0, 1}∗ ∪ {⊥}

Das Zeichen ⊥ (ausgesprochen als “bottom”) steht dabei fur

undefiniert und bedeutet, dass die Maschine nicht halt.

Im Fall von Entscheidungsproblemen ist die Funktion von der Form

fM : {0, 1}∗ → {0, 1,⊥}

Dabei steht 0 fur Verwerfen, 1 fur Akzeptieren und ⊥ fur

Nicht-Halten.


Der Satz von Rice


Henry Gordon Rice (1920–2003)

Wikipedia: Henry Gordon Rice was an American logician and

mathematician, best known as the author of Rice’s theorem, which he

proved in his doctoral dissertation of 1951 at Syracuse University.

He was also a Professor of Mathematics at the University of New

Hampshire. After 1960 he was employed by Computer Sciences

Corporation in El Segundo.

Mathematics Genealogy Project

Henry G. Rice

Ph.D.: Syracuse University 1951

Dissertation:

Classes of Recursively Enumerable Sets and Their Decision Problems

Advisor: Paul Charles Rosenbloom

No students known


Satz von Rice

Satz

Es sei R die Menge der von TMen berechenbaren partiellen Funktionen.

Es sei S eine Teilmenge von R mit ∅ ⊂ S ⊂ R mit S 6= ∅ und S 6= R.

Dann ist die Sprache

L(S) = {〈M〉 | M berechnet eine Funktion aus S}

nicht entscheidbar.

Mit anderen Worten: Alle nicht-trivialen Aussagen uber die von einer TM

berechnete Funktion sind unentscheidbar.


Anwendungsbeispiele (1)

Beispiel 1

Es sei S = {fM | fM(ε) 6= ⊥}.Dann ist

L(S) = {〈M〉 | M berechnet eine Funktion aus S}= {〈M〉 | M halt auf Eingabe ε}= Hε

Gemass dem Satz von Rice ist das Epsilin-Halteproblem Hε also nicht

entscheidbar. (Aber das wussten wir ja schon.)

RS



Beispiel 2

Es sei S = {fM | ∀w ∈ {0, 1}∗ : fM(w) 6= ⊥}.Dann ist

L(S) = {〈M〉 | M berechnet eine Funktion aus S}= {〈M〉 | M halt auf jeder Eingabe}

Diese Sprache ist auch als das totale Halteproblem Htot bekannt.

Gemass dem Satz von Rice ist die Sprache Htot nicht entscheidbar.

R

S



Beispiel 3

Es sei S = {fM | ∀w ∈ {0, 1}∗ : fM(w) = 1}.Dann ist

L(S) = {〈M〉 | M berechnet eine Funktion aus S}= {〈M〉 | M halt auf jeder Eingabe mit Ausgabe 1}

Gemass dem Satz von Rice ist die Sprache L(S) nicht entscheidbar.

R

S = {1}


Beweis des Satzes von Rice


Beweis des Satzes von Rice (0)

Hier ist noch einmal der Wortlaut des Satzes:

Satz

Es sei R die Menge der von TMen berechenbaren partiellen Funktionen.

Es sei S eine Teilmenge von R mit ∅ ⊂ S ⊂ R mit S 6= ∅ und S 6= R.

Dann ist die Sprache

L(S) = {〈M〉 | M berechnet eine Funktion aus S}

nicht entscheidbar.



Wir benutzen die Unterprogrammtechnik:

Aus einer TM ML(S), die L(S) entscheidet, konstruieren wir

eine TM MHε , die das Epsilon-Halteproblem Hε entscheidet.

Einige Vereinbarungen:

Es sei u die uberall undefinierte

Funktion u(w) ≡ ⊥.

O.B.d.A. u 6∈ S.

Es sei f eine Funktion aus S.

Es sei N eine TM, die f berechnet.

R

u

f

S

Anmerkung: Falls u ∈ S gilt, so betrachten wir einfach das Komplement R \ Sstatt S, und zeigen die Unentscheidbarkeit von L(R \ S). Hieraus ergibt sichauch unmittelbar die Unentscheidbarkeit von L(S).



Die neue TM MHε mit dem Unterprogramm ML(S) arbeitet wie folgt:

(1) Falls die Eingabe nicht aus einer korrekten Godelnummer besteht,

so verwirft MHε die Eingabe.

(2) Andernfalls berechnet MHε aus der Eingabe 〈M〉 die Godelnummer

der TM M∗:

Verhalten von M∗ auf Eingabe x

Zuerst simuliert M∗ das Verhalten von TM M bei Eingabe ε auf

einer fur diesen Zweck reservierten Spur.

Danach simuliert M∗ das Verhalten von TM N bei Eingabe x .

M∗ halt, sobald N halt, und ubernimmt die Ausgabe.

(3) Schlussendlich starten wir ML(S) mit der Eingabe 〈M∗〉.Wir akzeptieren (verwerfen) genau dann, wenn ML(S) akzeptiert

(verwirft).


Mε

w w=〈M〉〈M∗〉

reject (Syntax)

ML(S)

Ist w eine

Godel-

nummer?

accept

reject

M∗

x f (x)M N

ε



Korrektheit:

Bei Eingabe von w , wobei w keine Godelnummer ist, verwirft MHε .

Bei Eingabe von w = 〈M〉 gilt:

w ∈ Hε ⇒ M halt auf ε

⇒ M∗ berechnet f

f ∈S⇒ 〈M∗〉 ∈ L(S)

⇒ ML(S) akzeptiert 〈M∗〉⇒ MHε akzeptiert w

w /∈ Hε ⇒ M halt nicht auf ε

⇒ M∗ berechnet u

u /∈S⇒ 〈M∗〉 /∈ L(S)

⇒ ML(S) verwirft 〈M∗〉⇒ MHε verwirft w


Satz von Rice fur Java Programme

Konsequenzen fur Java:

Es gibt keine algorithmische Methode (von Hand oder automatisiert;

heute oder morgen oder in ferner Zukunft) um festzustellen, ob ein

gegebenes Java Programm einer nicht-trivialen Spezifikation entspricht.

Analoge Konsequenzen gelten fur alle anderen hoheren

Programmiersprachen wie C, C++, Pascal, Algol, COBOL, Python,

FORTRAN, LISP, Prolog, Haskell, Scala, Idris, etc.


Weitere Anwendungsbeispiele



Beispiel 4

Es sei

L17 = {〈M〉 | M berechnet bei Eingabe der Zahl 17 die Zahl 42}.Es ist L17 = L(S) fur S = {fM | fM(bin(17)) = bin(42)}.Da ∅ ( S ( R gilt, ist diese Sprache L17 gemass dem Satz von Rice

nicht entscheidbar.



Beispiel 5

Es sei H32 = {〈M〉 | auf jeder Eingabe halt M

nach hochstens 32 Schritten }.Uber diese Sprache sagt der Satz von Rice nichts aus!

Ist H32 entscheidbar?



Beispiel 6

Es sei L44 = {〈M〉 | Es existiert ein Wort w , sodass die TM M bei

Abbarbeitung von w mindestens einmal im Zustand q44 ist }.Uber diese Sprache sagt der Satz von Rice nichts aus!

Ist L44 entscheidbar?



Beispiel 7

Es sei LD = {〈M〉 | M entscheidet die Diagonalsprache}.Dann ist LD = L(S) fur S = {fD} wobei

fD(w) =

{1 wenn w ∈ D0 sonst.

Uber diese Sprache sagt der Satz von Rice nichts aus!

Aber: Diese Sprache ist entscheidbar, denn LD = {}.

RS = {fD}


Noch einmal: Das Collatz Problem

Die Collatz’sche Iterationsgleichung lautet:

x ←

{x/2 wenn x gerade

3x + 1 wenn x ungerade

Collatz Problem

Erreicht die Collatz’sche Iteration von jedem naturlichen Startwert x aus

irgendwann einmal die Zahl x = 1?

Das Collatz-Problem ist eine konkrete Instanz des totalen

Halteproblems.

Wir wissen nicht, ob diese Instanz eine Ja- oder eine Nein-Instanz ist.

Der Satz von Rice ist fur konkrete Probleminstanzen nutzlos.


Abschlusseigenschaften


Komplement, Durchschnitt, Vereinigung

Satz

Wenn die Sprache L entscheidbar ist,

so ist auch ihr Komplement Σ∗ − L entscheidbar.

Satz

Wenn die beiden Sprachen L1 und L2 entscheidbar sind,

(a) so ist auch die Sprache L1 ∩ L2 entscheidbar.

(b) so ist auch die Sprache L1 ∪ L2 entscheidbar.

Also: Die Menge der entscheidbaren Sprachen ist abgeschlossen unter

Komplement, Durchschnitt und Vereinigung.


Beweis: Durchschnitt

Es seien M1 und M2 zwei TMen, die L1 respektive L2 entscheiden.

Eine TM M, die L1 ∩ L2 entscheidet:

Bei Eingabe w simuliert M zunachst das Verhalten von M1 auf w

und dann das Verhalten von M2 auf w .

Falls M1 und M2 beide das Wort w akzeptieren, so akzeptiert auch

M; andernfalls verwirft M.

Korrektheit:

Falls w ∈ L1 ∩ L2, so wird w akzeptiert.

Andernfalls wird w verworfen.


Beweis: Vereinigung

Es seien M1 und M2 zwei TMen, die L1 respektive L2 entscheiden.

Eine TM M, die L1 ∪ L2 entscheidet:

Bei Eingabe w simuliert M zunachst das Verhalten von M1 auf w

und dann das Verhalten von M2 auf w .

Falls M1 oder M2 das Wort w akzeptiert, so akzeptiert auch M;

andernfalls verwirft M.

Korrektheit:

Falls w ∈ L1 ∪ L2, so wird w von M1 oder von M2 und somit auch

von M akzeptiert.

Andernfalls verwerfen sowohl M1 als auch M2, und damit auch M.


Documents

VL-05: Unentscheidbarkeit II · VL-05: Unentscheidbarkeit II (Berechenbarkeit und Komplexit at, WS 2019) Gerhard Woeginger WS 2019, RWTH BuK/WS 2019 VL-05: Unentscheidbarkeit II 1/42