Zusammenfassung KE5 PDF

Preview

Summary

KE 5 Unentscheidbare Sprachen 5 Existenz von nichtaufzählbaren Sprachen - Definition 5. Zwei Mengen X und Y heißen gleichmächtig, falls eine Bijektion zwischen X und Y existiert. - Definition 5 — abzählbar. Eine Menge X heißt abzählbar, falls o (i) X endlich ist oder o (ii) X und die Menge der natür...

Description

KE 5 Unentscheidbare Sprachen 5.1 Existenz von nichtaufzählbaren Sprachen • Definition 5.1 Zwei Mengen X und Y heißen gleichmächtig, falls eine Bijektion zwischen X und Y existiert. • Definition 5.2 — abzählbar. Eine Menge X heißt abzählbar, falls o (i) X endlich ist oder o (ii) X und die Menge der natürlichen Zahlen ℕ gleichmächtig sind. • Lemma 5.1 Die Menge der ganzen Zahlen ℤ ist abzählbar. o Beispiel: wir müssen eine Bijektion f zwischen ℕ und ℤ finden: 2𝑥 𝑥≥ 0 f(x) = {|2𝑥| − 1 𝑥 < 0 f(0) = 0; f(-1) = 1; f(1) = 2; f(-2) = 3…. • Cantor-Nummerierung: Anstatt die Nummern zeilen- oder spaltenweise zu vergeben, werden wir sie diagonal verteilen. Wir bezeichnen mit der k-ten Gegendiagonalen der Tabelle alle Einträge (i, j) mit i+j = k. Die k-te Gegendiagonale hat also k−1 Einträge, welche wir nach aufsteigender Zeilennummer sortieren.

•

•

•

•

Lemma 5.2 Die Menge ℕ2 = ℕ × ℕ ist abzählbar o Die Menge ℕ × ℕ ist die Menge der geordneten Paare von natürlichen Zahlen. Diese Menge kann man sich gut in einer (unbeschränkten) Tabelle vorstellen, bei welcher der Eintrag der i-ten Zeile und der j-ten Spalte das Tupel (i, j) enthält. o „Abzählen“ mit Cantor-Nummerierung Korollar 5.1 Die Menge der positiven rationalen Zahlen ℚ+ ist abzählbar. o Jede Zahl aus ℚ+ ist als Bruch p/q darstellbar. Diese Brüche tragen wir in eine Tabelle ein, sodass p/q in der Zelle (p, q) eingetragen wird. Nun nummerieren wir die Tabelleneinträge mit der Cantornummerierung → Folge F o Wir streichen in dieser Folge F alle Brüche, die wir kürzen können. Die daraus entstandene Folge nennen wir F‘. o f (i) := i-ter Eintrag in F‘ als rationale Zahl (f: ℕ → ℚ+) Diagonalisierung: o nachzuweisen, dass eine Folge in einer Nummerierung von Folgen (Fi)i∈ℕ fehlt ▪ eintragen der Folgen Fi als Zeilen in eine unbeschränkte Tabelle. Die Folge Fi wird in die i-te Zeile geschrieben. ▪ nehme die Diagonale der Tabelle als neue Folge und verändere jeden Wert in dieser Folge →die so konstruierte Folge G unterscheidet sich von allen Folgen der Tabelle. G unterscheidet sich von der Folge Fi an der i-ten Stelle (Tabelleneintrag (i, i)). Lemma 5.3 Die Menge der reellen Zahlen ℝ ist überabzählbar o Widerspruchsbeweis mit Hilfe der Digitalisierung

•

•

•

Lemma 5.4 Die Menge Σ* ist abzählbar o Beispiel: {0, 1}* ist abzählbar f(w) = bin(1°w)-1 f(ε) = bin(1)-1 = 0; f(0) = bin(10)-1 = 1; f(1) = bin(11)-1 = 2 … Lemma 5.5 Die Menge {L ⊆ Σ*} aller Sprachen über Σ ist überabzählbar o Beweis als Diagonalisierungsbeweis ▪ alle Sprachen in eine Tabelle T (Li in die i-te Zeile eintragen) ▪ Die Spalten von T sind mit den Wörtern aus Σ* beschriftet (Reihenfolge der Standardaufzählung). Beschriftung der i-ten Spalte bezeichnen wir mit wi ▪ markieren der wi, wi ∈ Li → 1 ansonsten 0 (charakteristische Funktion der Menge Li in die i-te Zeile eintragen) ▪ konstruieren einer Sprache L‘ → Diagonalisierung und Übernahme der so erzeugte Sequenz als charakteristische Funktion von L‘ Formal: L‘ := {wi | wi ∉ Li}. Die Sprache L‘ fehlt in der Nummerierung der Li, da wi ∈ Li ⇔ wi ∉ L‘ Satz 5.1 Es gibt eine Sprache, die nicht aufzählbar ist. o Es gibt höchstens so viele aufzählbare (erkennbare) Sprachen über Σ, wie es Turingmaschinen gibt. o Jede Turingmaschine können wir als Wort über Σ‘ = {0, 1} kodieren. o Nach Lemma 5.4 ist (Σ‘)* abzählbar →es gibt nur abzählbar viele Turingmaschinen → und damit nur abzählbar viele erkennbare Sprachen. o Da es aber nach Lemma 5.5 überabzählbar viele Sprachen über Σ gibt, können nicht alle diese Sprachen erkennbare Sprachen sein.

5.2 Konstruktion von nichtaufzählbaren Sprachen • Satz 5.2 Die Sprache ATM := {⟨⟨M, w⟩ | M ist Turingmaschine die w akzeptiert} ist nicht entscheidbar. Beweis: o angenommen ATM ∈ 𝔼, dann existiert für ATM ein Entscheider H

o

•

•

Wir geben nun eine Turingmaschine D(⟨M⟩) an, welche wie folgt arbeitet. 1. D simuliert H(⟨M,⟨M⟩⟩) 2. D gibt das entgegengesetzte Ergebnis der Simulation zurück

o o Widerspruch zur Annahme Satz 5.3 Das Komplement der Sprache ATM ist nicht aufzählbar. o ATM ist erkennbar (durch UTM), d.h. ATM ∈ 𝔸 o ATM ist nicht entscheidbar o Es gilt: 𝔼 = 𝔸 ∩ co-𝔸 o also folgt, dass ATM ∉ co-𝔸 o somit gilt, das Komplement von ATM ∉ 𝔸 Satz 5.4 Die Sprache HALT ist nicht entscheidbar und nicht co-aufzählbar. o analog zu Satz 5.2 und 5.3

5.3 Entscheidbarkeit des universellen Wortproblems • Für die Modelle endlicher Automat und kontextfreie Grammatik existiert ein universeller Algorithmus für das Wortproblem. (Satz 4.8)

•

•

• •

•

Definition 5.3 Die Menge der Sprachen, die durch einen linear beschränkten Automaten (LBA) erkannt werden, nennen wir DSPACE(n). Wir wissen, dass REG ⊊ CFL. Da wir das Wortproblem für kontextfreie Sprachen mit dem CYK-Algorithmus lösen können, gilt CFL ⊆ 𝔼. Weiter wissen wir, dass Labc = {anbncn | n ≥ 0} nicht kontextfrei ist, aber natürlich entscheidbar. Also gilt REG ⊊ CFL ⊊ 𝔼 ⊊ 𝔸 es gilt: REG ⊊ CFL ⊊ DSPACE(n) ⊊ 𝔸 Lemma 5.6 Sei M ein LBA. Dann existiert ein LBA M‘, welcher die gleiche Sprache wie M erkennt und der auf jeder Eingabe hält. Es gibt zudem eine berechenbare Funktion, welche ⟨M‘⟩ aus ⟨M⟩ berechnet. o Beweis: Schlüssel zum Beweis, beschränken der Anzahl der möglichen Konfigurationen des LBAs M. ▪ sei n die Länge der Eingabe (d.h n Zellen auf dem Band nutzbar) ▪ |Γ|n viele Möglichkeiten, wie das Band beschrieben sein kann ▪ n mögliche Kopfpositionen ▪ |Q| mögliche Zustände ▪ LBA M besitzt somit n|Q||Γ|n Konfigurationen. ▪ Anzahl der Konfigurationen kann durch cn von oben beschränkt werden, wobei c eine Konstante ist, die nur von M abhängt ▪ benutzt ein LBA 2x gleiche Konfiguration zykelt er (einzige Möglichkeit) ▪ M laufen lassen und Schritte mitzählen ▪ bei mehr als cn Schritten, Konfiguration doppelt → verwerfen ▪ Zähler passt aufs Band (Mehrspurtechnik) Satz 5.5 ALBA ∈ 𝔼 o LBA ist TM, die nur auf der Eingabe arbeiten darf o ALBA ist erkennbar ▪ benutze die UTM und kontrolliere bei der Simulation ob der zulässige Bandinhalt verlassen wird ▪ wenn jeder LBA M in einen Entscheider-LBA umgebaut werden könnte, dann würde die modifizierte UTM auch ALBA entscheiden

5.4 Das Konzept der Reduktion • Versuch das Problem A in das Problem B zu „übersetzen“. • Definition 5.4 — Reduktion. Eine Reduktion der Sprache A ⊆ Σ*1 auf die Sprache B ⊆ Σ*2 ist eine berechenbare totale Funktion f : Σ*1‘ → Σ*2 , für die gilt ∀ w ∈ Σ*1 : w ∈ A ⇔ f(w) ∈ B. Existiert eine Reduktion von A auf B, nennen wir A auf B reduzierbar und schreiben kurz A ≤m B. o berechenbare Funktion: es gibt eine TM, welche die beschriebene Funktion realisiert o nicht nur alle w ∈ A auf Wörter aus B abgebildet werden, sondern alle Wörter w ∉ A müssen auch auf Wörter abgebildet werden, die nicht in B sind

o o o

f muss weder injektiv noch surjektiv sein (many-one) eine Sprache L1 ist reduzierbar auf L2 gdw. es eine Reduktion von L1 auf L2 gibt. Schreibweise: L1 ≤m L2

•

•

•

• • •

Satz 5.6 Seien A und B Sprachen mit A ≤m B. Dann gilt o (a) wenn B ∈ 𝔼, dann auch A ∈ 𝔼, o (b) wenn B ∈ 𝔸, dann auch A ∈ 𝔸, o (c) wenn B ∈ co- 𝔸, dann auch A ∈ co- 𝔸. ▪ Beweis zu a): • Sei M Entscheider für L2 und f eine many-one-Reduktion von L1 auf L2 • Sei Mf TM; die f berechnet • Konstruiere neue TM‘, als Hintereinanderschaltung von M und Mf

M‘(w) akz. ⇔ M(f(w)) akz. ⇔ f(w) ∈ L2 ⇔ w ∈ L1 da M Entscheider → L1 ∈ 𝔼

• Korollar 5.2 o Seien A und B Sprachen mit A ≤m B. Dann gilt ▪ (a) wenn A ∉ 𝔼, dann auch B ∉ 𝔼, ▪ (b) wenn A ∉ 𝔸, dann auch B ∉ 𝔸, ▪ (c) wenn A ∉ co- 𝔸, dann auch B ∉ co- 𝔸 Alternativer Beweis für HALT ∉ 𝔼 (HALT = {(M,w) | M(w) stoppt}] o zeige ATM ≤m 𝔼 , denn da ATM ∉ 𝔼 folg daraus, dass HALT ∉ 𝔼 o gesucht: Reduktion f: Σ* → Σ* f(⟨M,w⟩) := ⟨M‘,w⟩, wobei: M‘(z) 1. Simuliere M(z) 2. Wenn M(z) verwirft, dann zykel 3. Ansonsten stoppe ⟨M,w⟩ ∈ ATM ⇔ M akz. w ⇔ M‘(w) ↓ ⇔ ⟨M‘,w⟩ ∈ HALT (↓ = hält) o also ⟨M,w⟩ ∈ ATM ⇔ f(⟨M,w⟩) ∈ HALT o da f berechenbar und total: ATM ≤m HALT → HALT ∉ 𝔼 Satz 5.7 Die folgende Sprache ist nicht entscheidbar. ETM := {⟨M⟩⟩ | M ist Turingmaschine mit L(M) = ∅} Korollar 5.3 Die Sprache ETM ist nicht aufzählbar Satz 5.8 Die folgenden Sprachen sind nicht entscheidbar: o REGTM := {⟨M⟩⟩ | M ist Turingmaschine mit L(M) ∈ REG}  ≤m REGTM, denn daraus folgt REGTM ∉ 𝔼 ▪ Beweis: zeige HALT ▪ gesucht: Reduktion f: Σ* → Σ* f(⟨M,w) := ⟨M‘⟩, wobei: M‘(z) (z = Eingabe vom M‘) 1. Simuliere M(w) 2. akzeptiere, wenn z die Form anbn hat  ⇒ M(w)↑ ⇒ L(M‘) = ∅ ⇒ L(M‘) ∈ REG ⟨M,w⟩ ∈ HALT (↑ = hält nicht) n n  ⟨M,w⟩ ∉ HALT ⇒ M(w)↓ ⇒ L(M‘) = { a b | n ≥ 0} ⇒ L(M‘) ∉ REG (↓ = hält )  ≤m REGTM → REGTM ∉ 𝔼 ▪ f berechenbar und total: HALT o FTM := {⟨⟨M⟩⟩ | M ist Turingmaschine mit |L(M)| < ∞}

5.5 Der Satz von Rice • nutzbar wenn die Sprache über ihre Eigenschaften bestimmt wird o Beispiel: L = {⟨M⟩ | L(M) ∈ REG} • Eigenschaft einer Sprache: allgemein etwas, was eine Sprache haben kann, oder auch nicht haben kann. • Eigenschaft einer erkennbaren Sprache eine Teilmenge U ⊆ 𝔸

• •

Eigenschaft U trivial, falls U = 𝔸 oder U = ∅ Satz 5.9 — Satz von Rice. Für jede nichttriviale Eigenschaft U ist die Sprache LU := {⟨M⟩ | L(M) ∈ U} nicht entscheidbar. o Beweis: o 1. Fall: ∅ ∈ U:  ≤m Lu; f : ⟨M,w⟩ → ⟨M‘⟩ ▪ z.z.: HALT sei H ∉ U und TM MH die H berechnet (existiert, da U ≠ 𝔸) die Reduktion arbeitet wie folgt: Zu einem gegebenen ⟨M,w⟩ konstruieren wir folgende Maschine M‘: M‘(z) 1. Simuliere M(w) 2. Simuliere MH(z) ⟨M, w⟩ ∈ HALT ⇒ M‘ zykelt auf jeder Eingabe ⇒ M‘ erkennt ∅ ⇒ ⟨M‘⟩ ∈ LU ⟨M, w⟩ ∉ HALT ⇒ M‘ rechnet wie MH ⇒ ⟨M‘⟩ ∉ LU o 2. Fall: (∅ ∉ U) ▪ Es gilt LU = {⟨M⟩ | M erkennt Sprache nicht aus U} = {⟨M⟩ | M erkennt Sprache aus U} = LU nach Fall 1 haben wir (da ∅ ∈ U), dass LU ∉ 𝔼 ⇒ LU ∉ 𝔼 da die entscheidbaren Sprachen aber unter Komplement abgeschlossen sind, folgt dass LU ∉ 𝔼

5.6 Das Äquivalenzproblem für Turingmaschinen • Satz 5.10 Die Sprache EQTM := {⟨M1, M2⟩ | M1, M2 sind Turingmaschinen mit L(M1) = L(M2)} ist weder aufzählbar noch co-aufzählbar o Beweis: o 1. Teil: EQTM ∉ 𝔸 ▪ z.z.: ATM ≤m EQTM ⟨M,w⟩ Eingabe-Reduktion bildet ab auf ⟨M,M2⟩ M1(z) : verwirft immer M2(z) : simuliert M(w) es gilt: ⟨M, w⟩ ∈ ATM ⇒ M2 akzeptiert nie ⇒ L(M1) = L(M2) ⇒ ⟨M1, M2⟩ ∈ EQTM ⟨M, w⟩ ∉ ATM ⇒ M2 akzeptiert immer ⇒ L(M1) ≠ L(M2) ⇒ ⟨M1, M2⟩ ∉ EQTM o 2. Teil: EQTM ∉ co-𝔸 ▪ z.z.: ATM ≤m EQTM ⟨M,w⟩ Eingabe-Reduktion bildet ab auf ⟨M,M2⟩ M1(z) : akzeptiert immer M2(z) : simuliert M(w) es gilt: ⟨M, w⟩ ∈ ATM ⇒ M2 akzeptiert immer ⇒ L(M1) = L(M2) ⇒ ⟨M1, M2⟩ ∈ EQTM ⟨M, w⟩ ∉ ATM ⇒ M2 akzeptiert nie ⇒ L(M1) ≠ L(M2) ⇒ ⟨M1, M2⟩ ∉ EQTM...