Lektion 3.2

Berechenbarkeit und die Church-Turing-These

40 min Lesezeit
Lesen anpassen

Nach dieser Lektion kannst du

  • entscheidbare und semi-entscheidbare Sprachen unterscheiden und Beispiele nennen,

  • WHILE-Programme lesen und erklären, warum verschiedene Rechnermodelle dieselben Funktionen berechnen,

  • sagen, was die Church-Turing-These behauptet und warum sie sich nicht beweisen lässt,

  • Turingmaschinen als Wörter kodieren und die Idee der universellen Turingmaschine erklären,

  • mit Cantors Diagonalargument beweisen, dass es Sprachen gibt, die keine Turingmaschine erkennt.

Vorausgesetzt: Turingmaschinen

David Hilbert stellte 1928 eine Frage, die als "Entscheidungsproblem" bekannt wurde: Gibt es ein mechanisches Verfahren, das für jede Formel der Prädikatenlogik entscheidet, ob sie allgemeingültig ist? Wer mit "ja" antworten will, muss nur ein Verfahren vorführen. Wer mit "nein" antworten will, hat ein viel schwereres Problem: Er muss zeigen, dass kein Verfahren funktioniert, und dafür muss er erst genau sagen, was ein Verfahren überhaupt ist.

1936 gaben Alonzo Church (mit dem λ\lambda-Kalkül) und Alan Turing (mit seiner Maschine) zwei solche Präzisierungen an und bewiesen damit, dass die Antwort auf Hilberts Frage "nein" ist. Die beiden Modelle sehen völlig verschieden aus, berechnen aber genau dasselbe. Und es muss Probleme geben, die keines davon löst.

Vermute zuerst

Jede Turingmaschine lässt sich als endlicher Text aufschreiben. Eine Sprache über {0,1}\{0, 1\} ist eine beliebige Menge von Wörtern. Gibt es mehr Sprachen als Turingmaschinen?

Definition

Berechenbare Funktion

Eine partielle Funktion f:Σ∗⇀Σ∗f: \Sigma^* \rightharpoonup \Sigma^* muss nicht für jedes Argument definiert sein. Sie heißt (Turing-)berechenbar, wenn es eine Turingmaschine MM gibt mit:

  • Ist f(w)f(w) definiert, hält MM auf ww in qjaq_\text{ja}, und auf dem Band steht f(w)f(w), sonst nur Blanks.
  • Ist f(w)f(w) nicht definiert, hält MM auf ww nicht.

Funktionen auf natürlichen Zahlen N={0,1,2,… }\mathbb{N} = \{0, 1, 2, \dots\} behandelt man über die Binärdarstellung. Beispiel: Die Maschine "Binärzahl plus 1" aus der letzten Lektion berechnet f(n)=n+1f(n) = n + 1. Die Maschine, die in einem Zustand für immer stehen bleibt, berechnet die nirgends definierte Funktion.

Definition

Entscheidbar und semi-entscheidbar

Sei L⊆Σ∗L \subseteq \Sigma^* eine Sprache.

  • LL heißt entscheidbar, wenn es eine Turingmaschine gibt, die auf jeder Eingabe hält, jedes w∈Lw \in L akzeptiert und jedes w∉Lw \notin L verwirft. Sie heißt Entscheider für LL.
  • LL heißt semi-entscheidbar oder rekursiv aufzählbar, wenn es eine Turingmaschine MM mit L(M)=LL(M) = L gibt. Auf w∉Lw \notin L darf MM verwerfen oder nicht halten.

Jede entscheidbare Sprache ist semi-entscheidbar, denn ein Entscheider MM erfüllt L(M)=LL(M) = L. Ist LL entscheidbar, so auch das Komplement L‾=Σ∗∖L\overline{L} = \Sigma^* \setminus L: Vertausche im Entscheider qjaq_\text{ja} und qneinq_\text{nein}.

Der Name "rekursiv aufzählbar" kommt daher, dass sich genau diese Sprachen von einer Maschine Wort für Wort auflisten lassen. Diese Gleichwertigkeit ist ein Satz, den wir hier nicht brauchen.

Beispiel

Entscheidbar, semi-entscheidbar und eine Falle

Entscheidbar: {anbn:n≥0}\{a^n b^n : n \ge 0\} und die Palindrome. Die Maschinen aus der letzten Lektion halten auf jedem Wort.

Semi-entscheidbar: Die Sprache der Polynome mit ganzzahligen Koeffizienten (etwa x2+y2−25x^2 + y^2 - 25), die eine ganzzahlige Nullstelle haben. Eine Maschine probiert für B=0,1,2,…B = 0, 1, 2, \dots alle Tupel mit Einträgen zwischen −B-B und BB aus und akzeptiert, sobald eines das Polynom zu null macht. Gibt es eine Nullstelle, wird sie nach endlich vielen Runden gefunden. Gibt es keine, sucht die Maschine ewig. Dass es keinen Entscheider gibt, hat Juri Matijassewitsch 1970 bewiesen (Hilberts zehntes Problem).

Die Falle: Die Maschine M′M' aus der letzten Lektion hält auf Wörtern, die mit aa beginnen, nicht. Daraus folgt nicht, dass L(M′)={bw:w∈Σ∗}L(M') = \{bw : w \in \Sigma^*\} unentscheidbar ist: Eine andere Maschine entscheidet sie in einem Schritt. Entscheidbarkeit ist eine Eigenschaft der Sprache, nicht einer bestimmten Maschine.

Kurz geprüft

Eine Turingmaschine MM akzeptiert jedes Wort aus LL und hält auf manchen Wörtern außerhalb von LL nicht. Was folgt sicher?

Definition

WHILE-Programme

Ein zweites Modell, näher an echten Programmiersprachen. Es gibt Variablen x0,x1,x2,…x_0, x_1, x_2, \dots mit Werten in N\mathbb{N} und genau diese Anweisungen (cc ist eine feste Zahl):

  • xi:=xj+cx_i := x_j + c und xi:=xj−cx_i := x_j - c, wobei die Subtraktion bei 00 stehen bleibt (3−53 - 5 ergibt 00),
  • P1;P2P_1; P_2: erst P1P_1, dann P2P_2 ausführen,
  • WHILE xi≠0 DO P END\texttt{WHILE } x_i \neq 0 \texttt{ DO } P \texttt{ END}: PP wiederholen, solange xi≠0x_i \neq 0 ist.

Ein Programm berechnet f:Nk⇀Nf: \mathbb{N}^k \rightharpoonup \mathbb{N}, wenn es mit den Argumenten in x1,…,xkx_1, \dots, x_k und 00 in allen anderen Variablen startet und genau dann endet, wenn ff definiert ist, und dann x0x_0 den Wert ff hat. Die Endlosschleife WHILE x1≠0 DO x1:=x1+1 END\texttt{WHILE } x_1 \neq 0 \texttt{ DO } x_1 := x_1 + 1 \texttt{ END} berechnet die Funktion, die nur bei 00 definiert ist (mit Wert 00).

Beispiel

Multiplikation als WHILE-Programm

Das Programm berechnet f(x1,x2)=x1⋅x2f(x_1, x_2) = x_1 \cdot x_2. Die Einrückung zeigt, was zu welcher Schleife gehört.

ZeileEinrückungAnweisung
10WHILE x1≠0 DO\texttt{WHILE x1} \neq \texttt{0 DO}
21x3 := x2 + 0;\texttt{x3 := x2 + 0;}
31WHILE x3≠0 DO\texttt{WHILE x3} \neq \texttt{0 DO}
42x0 := x0 + 1;\texttt{x0 := x0 + 1;}
52x3 := x3 - 1\texttt{x3 := x3 - 1}
61END;\texttt{END;}
71x1 := x1 - 1\texttt{x1 := x1 - 1}
80END\texttt{END}

Die äußere Schleife läuft x1x_1-mal. Jedes Mal kopiert Zeile 2 den Wert x2x_2 nach x3x_3, und die innere Schleife zählt x0x_0 um x2x_2 hoch. Mit x1=3x_1 = 3, x2=4x_2 = 4 wird Zeile 4 zwölfmal ausgeführt, am Ende ist x0=12x_0 = 12. Laufzeit: Zeile 4 läuft x1⋅x2x_1 \cdot x_2-mal, das Programm macht also Θ(x1x2)\Theta(x_1 x_2) Schritte.

Definition

Registermaschinen und λ\lambda-Kalkül

Registermaschine: Register R0,R1,…R_0, R_1, \dots mit Werten in N\mathbb{N} und ein nummeriertes Programm aus den Befehlen "erhöhe RiR_i um 1", "verringere RiR_i um 1 (bei 00 bleibt es 00)", "springe zu Befehl jj, falls Ri=0R_i = 0" und "halte". Das ist ein Modell eines Prozessors mit unbegrenzt großen Speicherzellen.

λ\lambda-Kalkül: Es gibt nur Funktionen. Ein Term ist eine Variable xx, eine Abstraktion λx. M\lambda x.\,M (die Funktion, die xx auf MM abbildet) oder eine Anwendung (M N)(M\,N). Gerechnet wird mit einer einzigen Regel: (λx. M) N(\lambda x.\,M)\,N wird zu MM, in dem jedes freie xx durch NN ersetzt ist. Zahlen werden als Funktionen kodiert: nn ist λf. λx. f(f(⋯f(x)))\lambda f.\,\lambda x.\,f(f(\cdots f(x))) mit nn-mal ff.

Satz

Gleichwertigkeit der Modelle

Für eine partielle Funktion f:Nk⇀Nf: \mathbb{N}^k \rightharpoonup \mathbb{N} sind gleichwertig: ff ist Turing-berechenbar, ff ist WHILE-berechenbar, ff ist von einer Registermaschine berechenbar, ff ist im λ\lambda-Kalkül darstellbar.

Kurz geprüft

Warum ist die Church-Turing-These nicht bewiesen worden?

Definition

Gödelnummerierung von Turingmaschinen

Damit Maschinen über Maschinen rechnen können, kodiert man jede Turingmaschine als Wort über {0,1}\{0, 1\}. Nummeriere die Zustände q1,q2,q3,…q_1, q_2, q_3, \dots (dabei sei q1q_1 der Start, q2=qjaq_2 = q_\text{ja}, q3=qneinq_3 = q_\text{nein}), die Bandzeichen a1=0a_1 = 0, a2=1a_2 = 1, a3=□a_3 = \square, a4,…a_4, \dots und die Richtungen D1=LD_1 = L, D2=RD_2 = R, D3=ND_3 = N. Ein Übergang δ(qi,aj)=(qk,al,Dm)\delta(q_i, a_j) = (q_k, a_l, D_m) wird zu

0i 1 0j 1 0k 1 0l 1 0m0^i\,1\,0^j\,1\,0^k\,1\,0^l\,1\,0^m,

und die Kodierung ⟨M⟩\langle M \rangle ist die Folge aller Übergänge, getrennt durch 1111. Da in einem einzelnen Übergang nie zwei Einsen nebeneinander stehen, lässt sich ⟨M⟩\langle M \rangle eindeutig zurücklesen.

Ein Wort, das keine Maschine kodiert, ordnen wir einer festen Maschine zu, die sofort verwirft. So gehört zu jedem Wort x∈{0,1}∗x \in \{0,1\}^* eine Maschine MxM_x. Diese Vereinbarung macht spätere Beweise kürzer.

Beispiel

Ein Übergang als Wort

Der Übergang δ(q1,1)=(qja,0,R)\delta(q_1, 1) = (q_\text{ja}, 0, R) ist δ(q1,a2)=(q2,a1,D2)\delta(q_1, a_2) = (q_2, a_1, D_2), also i=1,j=2,k=2,l=1,m=2i = 1, j = 2, k = 2, l = 1, m = 2.

0 1 00 1 00 1 0 1 00=0100100101000\,1\,00\,1\,00\,1\,0\,1\,00 = 010010010100

Die Länge ist i+j+k+l+m+4=12i + j + k + l + m + 4 = 12. Umgekehrt liest man aus 010010010100010010010100 die Blöcke 0,00,00,0,000, 00, 00, 0, 00 ab und erhält den Übergang zurück.

Satz

Universelle Turingmaschine

Es gibt eine Turingmaschine UU, die auf Eingabe ⟨M⟩#w\langle M \rangle \# w (mit w∈{0,1}∗w \in \{0,1\}^*) genau dann akzeptiert, verwirft oder nicht hält, wenn MM auf ww dies tut.

Definition

Abzählbar und überabzählbar

Eine Menge AA heißt abzählbar, wenn sie leer ist oder es eine surjektive Abbildung N→A\mathbb{N} \to A gibt: Man kann ihre Elemente in einer Liste a0,a1,a2,…a_0, a_1, a_2, \dots aufschreiben, in der jedes Element irgendwann vorkommt. Sonst heißt AA überabzählbar.

Beispiel: {0,1}∗\{0,1\}^* ist abzählbar. Liste die Wörter der Länge nach und bei gleicher Länge wie Binärzahlen: w0=ε,w1=0,w2=1,w3=00,w4=01,…w_0 = \varepsilon, w_1 = 0, w_2 = 1, w_3 = 00, w_4 = 01, \dots Jedes Wort steht an einer endlichen Stelle. Gegenbeispiel einer untauglichen Liste: "erst alle Wörter aus Nullen, dann die anderen". Sie kommt nie bei 11 an.

Satz

Es gibt nur abzählbar viele Turingmaschinen

Die Menge der semi-entscheidbaren Sprachen über {0,1}\{0,1\} ist abzählbar.

Satz

Cantor: Die Sprachen sind überabzählbar

Die Menge P({0,1}∗)\mathcal{P}(\{0,1\}^*) aller Sprachen über {0,1}\{0,1\} ist überabzählbar.

Satz

Nicht alles ist berechenbar

Es gibt Sprachen über {0,1}\{0,1\}, die nicht semi-entscheidbar sind, also von keiner Turingmaschine erkannt werden.

Häufige Fehler

Die Diagonalsprache einfach hinzufügen

"Dann war die Liste eben unvollständig. Ich hänge DD vorne an, und jetzt ist sie vollständig." Und ein zweiter Fehler: "Der Beweis zeigt eine konkrete Sprache, die keine Maschine erkennt."

Richtig ist

Auf die neue Liste lässt sich das Argument wieder anwenden und liefert eine neue Diagonalsprache, die fehlt. Der Satz sagt: Jede Liste ist unvollständig. Zum zweiten Punkt: Der Abzählbarkeitsbeweis zeigt nur, dass es solche Sprachen gibt. Eine konkrete liefert das Halteproblem in der nächsten Lektion, mit demselben Diagonalprinzip.

Zusammenfassung

  • Eine Sprache ist entscheidbar, wenn eine TM auf jeder Eingabe hält und richtig antwortet; semi-entscheidbar, wenn eine TM genau ihre Wörter akzeptiert.

  • Entscheidbare Sprachen sind semi-entscheidbar, und ihr Komplement ist wieder entscheidbar.

  • Turingmaschinen, WHILE-Programme, Registermaschinen und der λ\lambda-Kalkül berechnen dieselben partiellen Funktionen; man beweist das durch gegenseitige Simulation.

  • Die Church-Turing-These setzt "intuitiv berechenbar" mit "Turing-berechenbar" gleich. Sie ist nicht beweisbar, weil eine Seite kein mathematischer Begriff ist.

  • Eine Gödelnummerierung macht aus jeder TM ein Wort ⟨M⟩\langle M \rangle; die universelle TM UU simuliert MM auf ww aus ⟨M⟩#w\langle M \rangle \# w.

  • Es gibt abzählbar viele Turingmaschinen, aber nach Cantors Diagonalargument überabzählbar viele Sprachen. Also sind die meisten Sprachen nicht semi-entscheidbar.

Übungen

Aufgabe 1Multiple Choice

Die Sprache LL ist entscheidbar. Welche Aussage folgt?

Aufgabe 2Numerisch

In der Liste w0=ε,w1=0,w2=1,w3=00,w4=01,…w_0 = \varepsilon, w_1 = 0, w_2 = 1, w_3 = 00, w_4 = 01, \dots (der Länge nach, bei gleicher Länge wie Binärzahlen geordnet): Welchen Index nn hat das Wort wn=101w_n = 101?

Aufgabe 3Numerisch

Wie viele Zeichen hat die Kodierung des Übergangs δ(q3,a1)=(q1,a2,D3)\delta(q_3, a_1) = (q_1, a_2, D_3) in der Gödelnummerierung der Lektion?

Aufgabe 4Multiple Choice

Welche dieser Mengen ist überabzählbar?

Aufgabe 5Freitext

Zeige: Sind L1L_1 und L2L_2 semi-entscheidbar, so ist auch L1∪L2L_1 \cup L_2 semi-entscheidbar. Warum darfst du nicht erst M1M_1 und danach M2M_2 laufen lassen?

Aufgabe 6Freitext

Zeige mit einem Diagonalargument: Es gibt eine totale Funktion f:N→Nf: \mathbb{N} \to \mathbb{N} (überall definiert), die von keiner Turingmaschine berechnet wird.