Theoretische Informatik II

Theoretische Informatik II

Abschnitte 1.6 bis 1.8

(Halteproblem, Satz von Rice, a rekursive Aufz¨ hlbarkeit)

Rolf Wanka Universit¨ t Erlangen-N¨ rnberg a u rwanka@cs.fau.de 23. Mai 2006

1.6 Unentscheidbare Probleme

1

1.6 Unentscheidbare Probleme

Gibt es Grenzen f¨ r das, was Turingmaschinen berechnen k¨ nnen? Wir werden sehen, daß es u o solche Grenzen gibt, die sehr wichtige Probleme betreffen. Genauer gesagt: Wir werden zeigen, daß Probleme, von denen wir uns w¨ nschten, daß sie l¨ sbar w¨ ren, algorithmisch nicht l¨ sbar u o a o sind! Die G¨ delnummer einer Turingmaschine M besteht nur aus Buchstaben aus {0, 1, #}. Durch die o Abbildung 0 → 00 1 → 01 # → 11 dieser eichen kommen wir sogar nur mit dem Alphabet {0, 1} aus. Wir k¨ nnen also jede 1o Band-Turingmaschine M eindeutig durch eine eichenkette M ∈ {0, 1}∗ kodieren. Da der gleiche Kodierungstrick f¨ r beliebige Bandalphabete Σ funktioniert, gehen wir im folgenden davon u aus, daß f¨ r alle Turingmaschinen, die uns begegnen, Σ = {0, 1} ist. u 1.13 Definition: Die Sprache H := { M w | M ist eine 1-Band-Turingmaschine, die, gestartet mit w, h¨ lt} a ist das (allgemeine) Halteproblem.

Beachten Sie, daß wir hier eine Menge von eichenfolgen (ein anderes Wort f¨ r Menge von u ” eichenfolgen“ ist ja Sprache) als Problem bezeichnen. Das ist eine Konvention, hinter der steckt, daß wir letztlich das zugeh¨ rige Wortproblem oder auch, in aquivalenter Bedeutung, o ¨ Entscheidungsproblem meinen. Wir haben also die Menge H definiert und meinen im Hinterkopf f¨ r alle w ∈ {0, 1}∗ die (maschinelle) Beantwortung der Frage w ∈ H ?“. Trotzdem: u ” Nur die Menge H ist das Halteproblem. Im ubrigen gilt auch f¨ r H: H ⊆ {0, 1}∗ . ¨ u

1.14 Satz: (Turing, 1936) ¨ H ist unentscheidbar ( eine andere, aber aquivalente Formulierung lautet: H ist nicht rekursiv). Beweis: Wir nehmen an, daß es eine Turingmaschine MH gibt, die H entscheidet. D. h. MH h¨ lt auf jeder a Eingabe x, und man kann am erreichten ustand erkennen, ob x ∈ H ist oder nicht! Diese Annahme werden wir nun auf einen Widerspruch f¨ hren. u Wenn es MH gibt, dann gibt es auch die folgende Turingmaschine Mschlau : Turingmaschine Mschlau (1) (2) die Eingabe sei y falls y = M , dann

23. Mai 2006, Version 0.97

1.6 Unentscheidbare Probleme

(3) (4) (5) entscheide mittels MH , ob M M ∈ H falls ja: schreibe nach rechts endlos viele 1en auf das Band falls nein: bleibe stehen

---

Die Turingmaschine Mschlau k¨ nnen wir explizit hinschreiben ( programmieren“), falls uns jeo ” mand die δ-Tabelle von MH gibt (die als Unterprogramm“ aufgerufen w¨ rde). u ” Was passiert, wenn wir Mschlau mit der Eingabe y = Mschlau starten? Nun, es gibt nur zwei M¨ glichkeiten, n¨ mlich die, daß die Maschine h¨ lt ( Fall (a)“), und die, daß sie nicht h¨ lt o a a a ” ( Fall (b)“). ” (a) Wenn Mschlau , gestartet mit Mschlau , h¨ lt, heißt das, daß die Abfrage in (3) die Antwort nein“ a ” ergeben hatte, also Mschlau Mschlau ∈ H. D. h. wiederum, daß Mschlau , gestartet mit Mschlau , nicht h¨ lt, im Widerspruch zum Anfang der Argumentation! a Also kann Fall (a) nicht gelten. Nun betrachten wir Fall (b). (b) Wenn Mschlau , gestartet mit Mschlau , endlos l¨ uft, muß sich die Maschine in eile (4) bea finden. Dorthin kommt sie nur, wenn die Abfrage in (3) die Antwort ja“ ergeben hatte, also ” Mschlau Mschlau ∈ H. D. h. wiederum, daß Mschlau gestartet mit Mschlau h¨ lt, im Widerspruch a zum Anfang der Argumentation! Also kann keiner der beiden F¨ lle eintreten, wir m¨ ssen somit irgendwo von etwas ausgegangen a u sein, das falsch ist. Unsere gesamte Argumentation hat aber nur eine Schwachstelle, n¨ mlich die a Annahme, daß es MH gibt. MH gibt es also gar nicht, und als Konsequenz ist H nicht entscheidbar! 1.15 Satz: (a) H ist rekursiv aufz¨ hlbar. a ¯ a (b) Das Komplement von H , d. h. H = {0, 1}∗ H , ist nicht rekursiv aufz¨ hlbar. Beweis: (a) Die universelle Turingmaschine M0 aus Satz 1.14 ist der rekursive Aufz¨ hler von H, d. h. a M w ∈ H ⇐⇒ M0 , gestartet mit M w, h¨ lt a ˜ o (b) W¨ re H rekursiv aufz¨ hlbar (mittels einer Turingmaschine M), k¨ nnte man folgende Turinga ¯ a maschine programmieren: Entscheider f¨ r H u die Eingabe sei M w f¨ hre gleichzeitig aus und stoppe, wenn eine stoppt: u – starte mit M w auf Band 1 die Turingmaschine M0 , die die W¨ rter aus H akzeptiert o (aus Teil (a)) ˜ ¯ – starte mit M w auf Band 2 die Turingmaschine M, die die W¨ rter aus H akzeptiert o h¨ lt M0 , halte akzeptierend, h¨ lt M, halte verwerfend. a a ˜

23. Mai 2006, Version 0.97