Untentscheidbarkeit

Question 1

Warum gibt es unentscheidbare Probleme?

Answer 1

Weil es mehr Sprachen/Problemen gibt als TMs/Algorithmen.

Question 2

Eine Menge M heisst abzählbar, …

Answer 2

wenn M leer ist oder wenn es eine surjektive Funktion c: N -> M gibt. N=Menge der natürlichen Zahlen

Question 3

Jede endliche Menge ist.. (abzählbar/überabzählbar)

Answer 3

abzählbar

Question 4

Was für eine Funktion c: N -> M gibt es für eine abzählbar unendliche Menge?

Answer 4

bijektiv

Question 5

Was für eine Mächtigkeit haben die abzählbar unendlichen Menge?

Answer 5

dieselbe wir die Menge der natürlichen Zahlen

Question 6

Beispiele für abzählbar unendliche Mengen

Answer 6

• die Menge der natürlichen Zahlen mit der Bijektion c(i)=i
• die Menge der ganzen Zahlen mit der Bijektion
  c(i) = i/2, falls i gerade und
  c(i) = -(i+1)/2, falls i ungerade
• die Menge der rationalen Zahlen
  0, … i/1, (i-1)/2, (i-2)/3, …, 1/i, … .
• die Menge Σ* der Wörter über einem endlichen Alphabet Σ
• die Menge der Gödelnummer, da Gödelnummer Wörter über dem Alphabet {0, 1} sind
• die Menge der TMen, da jede TM durch eine eindeutigen Gödelnummer beschrieben ist
• die Menge der entscheidbaren Sprachen
• die Menge der regulären Sprachen
• irgendeine Teilmenge der Gödelnummer

Question 7

w_i

Answer 7

i-te Wort über dem Alphabet Σ = {0, 1} in kanonische Reihenfolge

Question 8

M_i

Answer 8

i-te TM in der kanonische Reihenfolge von Gödelnummer

Question 9

Die Potenzmenge P(N) ist.. (abzählbar/überabzählbar)

Answer 9

überabzählbar

Question 10

Wie viele Entscheigungsprobleme gibt es?

Answer 10

P({0,1}*), P=Potenzmenge

Question 11

Die Menge der Entscheidungsprobleme hat dieselbe Mächtigkeit wie …, ist also … (abzählbar/überabzählbar) .

Answer 11

P(N)=Potenzmenge der natürlichen Zahlen, überabzahlbar

Question 12

Definition von Diagonalsprache

Answer 12

D={w ϵ {0,1}* | w = w_i und M_i akzeptiert w nicht}

Question 13

Die Diagonalsprache D ist… (entscheidbar/unentscheidbar)

Answer 13

unentscheidbar

Question 14

Definition vom Komplement der Diagonalsprache

Answer 14

Dnot={w ϵ {0,1}* | w = w_i und M_i akzeptiert w }

Question 15

Das Komplement der Diagonalsprache D ist… (entscheidbar/unentscheidbar)

Answer 15

unentscheidbar

Question 16

Unterprogrammtechnik zum Beweis von Unentscheidbarkeiten

Answer 16

Sei L’ eine unentscheidbare Sprache. Sei L eine neue Sprache, die wir untersuchen wollen. Um nachzuweisen, dass L unentscheidbar, genügt es zu zeigen, dass man mithilfe von Unterprogrammaufrufen einer TM M_L auch die Spache L’ entscheiden kann.

Question 17

L⊆{0,1}* entscheidbar <=> not L …..

Answer 17

entscheidbar

Question 18

L⊆{0,1}* unentscheidbar <=> not L …..

Answer 18

unentscheidbar

Question 19

Definition von Halteproblem

Answer 19

H = {Gödelnummer von M. w | M hält auf w}

Question 20

Das Halteproblem H ist… (entscheidbar/unentscheidbar)

Answer 20

unentscheidbar

Question 21

Definition von Epsilon-Halteproblem

Answer 21

Hε = {Gödelnummer von M | M hält auf der Eingabe ε}

Question 22

Das Epsilon-Halteproblem ist… (entscheidbar/unentscheidbar)

Answer 22

unentscheidbar

Question 23

Form einer von TM M berechnete Funktion

Answer 23

f_M : {0,1}* →{0,1,⊥}
0 = Verwerfen
1 = Akzeptieren
⊥= Nicht Halten

Question 24

Satz von Rice Definition

Answer 24

Sei R die Menge der von TMen berechenbaren partiellen Funktionen. Sei S eine Teilmenge von R mit ∅⊊S⊊R. Dann ist die Sprache
L(S) = {Gödelnummer von M| M berechnet eine Funktion aus S} nicht entscheidbar.

Question 25

Konsequenzen des Satzes von Rice für hohe Programmiersprachen

Answer 25

Die automatische Verifikation von Programmen in TM-mächtigen Programmiersprachen ist unmöglich

Question 26

Methoden zum Nachweis von Nicht-Berechenbarkeit:

Answer 26

• Diagonalisierung
• Unterprogrammtechnik
• Reduktionen
• Satz von Rice

Question 27

Die Menge aller Funktionen f: Σ* -> Σ* ist.. (abzählbar/überabzählbar)?

Answer 27

überabzählbar