Grenzen der Mathematik || Berechenbarkeitstheorie

Behalten Sie stets im Auge,dass sich die Berechenbar-keitstheorie mit der Existenzvon algorithmischen Lösun-

gen beschäftigt, aber nicht mit deren Effi-zienz. Die ersten Arbeiten auf diesem Ge-biet stammen aus einer Zeit, in der es denComputer in seiner modernen Form nochgar nicht gab, und so waren Fragen nachdem Ressourcenverbrauch eines algorith-mischen Verfahrens ohne Belang. Eherzufällig erhielt die Berechenbarkeitstheo-rie mit dem Bau der ersten Rechenma-schinen eine ganz praktische Bedeutung.In der Folgezeit entstand mit der Kom-plexitätstheorie ein eigenständiger For-schungszweig, der sich mit der Laufzeit-und der Platzkomplexität von Algorith-men beschäftigt. Die Berechenbarkeits-theorie und die Komplexitätstheorie sindmittlerweile zu einem festen Bestandteildes Informatikstudiums geworden, und je-der Absolvent ist heute mit den Grund-zügen beider Theorien vertraut. Dennochwissen nur wenige, dass insbesondere dieBerechenbarkeitstheorie ihre Wurzeln garnicht in der Informatik hat. Sie wurde ge-schaffen, um Fragestellungen der mathe-matischen Logik zu beantworten, und istälter als der erste real gebaute Computer.

5 Berechenbarkeitstheorie

„If it should turn out that the basiclogics of a machine designed for the numerical solutionof differential equations coincide with the logics of amachine intended to make bills for a department store, Iwould regard this as the most amazing coincidence thatI have ever encountered.“

Howard Aiken [44]

Die Berechenbarkeitstheorie ist neben der Beweistheorie die zweite tra-gende Säule der mathematischen Logik. Unter ihrem Schirm vereintsie alle Methoden und Erkenntnisse, die sich mit den Möglichkeitenund Grenzen der algorithmischen Methode beschäftigen. Zwei Frage-stellungen sind in diesem Zusammenhang von vorrangiger Bedeutung:

� Wie lässt sich der Berechenbarkeitsbegriff formal definieren?

Jeder von uns besitzt eine intuitive Vorstellung davon, was es bedeu-tet, etwas zu berechnen. Bei genauerer Betrachtung entpuppen sichunsere Gedankenmodelle aber schnell als zu vage, um daraus hand-feste Schlüsse zu ziehen. In der Berechenbarkeitstheorie wird dieintuitive Vorstellung durch die Definition präziser Berechnungsmo-delle mit einem formalen Unterbau versehen. Einige dieser Modellebesitzen durch und durch mathematischen Charakter, während sichandere sehr nahe an der Hardware-Architektur realer Computersys-teme orientieren.

� Wo sind die Grenzen der Berechenbarkeit?

Es ist ein Kernergebnis der Berechenbarkeitstheorie, dass viele un-entscheidbare Probleme existieren, Probleme, deren Lösungen zwarexistieren, aber nicht auf algorithmischem Wege bestimmt werdenkönnen. Die Konsequenzen, die sich hieraus ergeben, sind folgen-schwer, und ihre Auswirkungen sind weit über die Algorithmen-oder Computertechnik hinaus zu spüren. So wissen wir heute, dassdie Berechenbarkeits- und die Beweistheorie eng miteinander ver-flochten sind und sich viele Negativresultate des einen Gebiets aufdas andere übertragen.

D. W. Hoffmann, Grenzen der Mathematik, DOI 10.1007/978-3-642-34720-7_5, © Springer-Verlag Berlin Heidelberg 2013

Turing-

Maschine

Configuration Behaviourfinal

m-config. symbol operations m-config.b None P0,R cc None R ee None P1,R ff None R b

b → q1c → q2e → q3f → q4

’None’ → S00 → S11 → S2

Q = {q1,q2,q3,q4}S = {S0,S1,S2}I = {(q1,S0,S1,R,q2),

(q2,S0,S0,R,q3),

(q3,S0,S2,R,q4),

(q4,S0,S0,R,q1)}

Abbildung 5.1: Formale Beschreibung derersten Maschine aus Turings Originalarbeit

270 5 Berechenbarkeitstheorie

In diesem Kapitel werden wir uns diesen Zusammenhang in zwei-erlei Hinsicht zu Nutze machen. Zum einen werden wir zeigen, wiesich für bereits bekannte Ergebnisse der Beweistheorie verblüffendeinfache Beweise konstruieren lassen. Zum anderen werden wir dieErgebnisse der Berechenbarkeitstheorie dazu verwenden, um bisheroffen gebliebene Fragen zu beantworten.

5.1 Berechnungsmodelle

In den folgenden beiden Unterabschnitten werden wir mit der Turing-Maschine und der Register-Maschine zwei der wichtigsten Berech-nungsmodelle genauer untersuchen. Anschließend werden wir dieChurch’sche These diskutieren und dabei feststellen, dass es keine Rollespielt, welches Modell wir für die Untersuchung des Berechenbarkeits-begriffs konkret verwenden.

5.1.1 Turing-Maschinen

In Abschnitt 1.2.8 haben wir die grundlegende Funktionsweise vonTuring-Maschinen dargelegt und auch schon eine konkrete Beispielma-schine in Aktion erlebt. Wir wollen nun daran gehen, den Turing’schenMaschinenbegriff formal zu definieren:

Definition 5.1 (Turing-Maschine)

Eine Turing-Maschine ist ein Tripel (Q,S, I). Sie besteht aus

� der endlichen Zustandsmenge Q = {q1, . . . ,qN},� dem Bandalphabet S = {S0, . . . ,SM} und

� der Instruktionsmenge I = {I1, . . . , IK}.Eine Instruktion aus der Menge I hat die Form

(qi,S j,Sk,L,ql) oder (qi,S j,Sk,R,ql) oder (qi,S j,Sk,N,ql)

mit qi,ql ∈ Q und S j,Sk ∈ S.

Abbildung 5.1 zeigt, wie sich die erste Beispielmaschine aus TuringsOriginalarbeit in der vereinbarten Nomenklatur beschreiben lässt. Es ist

5.1 Berechnungsmodelle 271

(qi,S j,Sk,L,ql) (qi,S j,Sk,R,ql) (qi,S j,Sk,N,ql)

� Wird im Zustand qi

das Symbol S j gelesen, dann

Sj ......

qi

� ersetze S j durch Sk,� gehe nach links,� wechsle in den Zustand ql .

Sk ......ql



Sj ......

qi

� ersetze S j durch Sk,� gehe nach rechts,� wechsle in den Zustand ql .

Sk ......ql



Sj ......

qi

� ersetze S j durch Sk,� behalte die aktuelle Position,� wechsle in den Zustand ql .

Sk ......ql

Abbildung 5.2: Interpretation der Instruktionen einer Turing-Maschine

die gleiche Maschine, die uns in Abschnitt 1.2.8 als Demonstrationsob-jekt treu zur Seite stand.

Der Zustand q1 und das Bandsymbol S0 besitzen in unserem Modelleine besondere Bedeutung. q1 ist der Initialzustand oder Startzustand,in dem jede Turing-Maschine per Definition beginnt. Das Symbol S0wird dazu verwendet, um eine leere Bandstelle zu markieren. Um esoptisch von den anderen zu unterscheiden, verwenden wir für S0 auchdas Zeichen �. Turing ließ seine Maschinen stets auf einem leeren Bandstarten, d. h., auf einem Band, dessen Felder allesamt mit dem Symbol� vorbeschrieben waren.

Nach dem Start beginnt eine Turing-Maschine mit der Ausführung vonBerechnungsschritten (Abbildung 5.2). Zu Beginn eines Berechnungs-schritts liest sie das Zeichen unter dem Schreib-Lese-Kopf ein. Findetdie Maschine dort beispielsweise das Bandzeichen S j, so sucht sie in


Abhängigkeit vom aktuellen Zustand qi nach einer passenden Instrukti-on der Form

(qi,S j,_,_,_) (5.1)

Die gefundene Instruktion wird ausgeführt und im nächsten Berech-nungsschritt der gesamte Vorgang wiederholt.

Zwei Sonderfälle dürfen wir an dieser Stelle nicht übergehen. UnsereDefinition schließt nicht aus, dass für ein Bandzeichen S j und einenZustand qi mehr als eine Instruktion der Form (5.1) existiert. SolcheMaschinen heißen indeterministisch und spielen in der Komplexitäts-theorie eine wichtige Rolle (siehe z. B. [95]). Für unsere Betrachtungengehen wir davon aus, dass die betrachteten Turing-Maschinen allesamtdeterministisch sind und somit für kein Bandzeichen S j und Zustand qimehr als eine Instruktion der Form (5.1) existiert. Davon unberührt istes immer möglich, dass überhaupt keine passende Regel gefunden wer-den kann. In diesem Fall hält die Maschine an und führt keine weiterenBerechnungen mehr aus; wir sagen, die Maschine terminiert.

Wir wollen nun darangehen, den geschilderten Berechnungsablauf for-mal zu beschreiben. Im Kern steht der Begriff der Konfiguration, deruns erlaubt, den augenblicklichen Zustand einer Turing-Maschine imSinne einer Momentaufnahme zu erfassen.

Definition 5.2 (Konfiguration)

Sei M = (Q,S, I) eine Turing-Maschine. Jeder Vektor der Form

x = (q, i,s0,s1, . . . ,sn)

heißt Konfiguration von M.

� q ist der aktuelle Zustand der Maschine,

� i die Position des Schreib-Lese-Kopfs (0≤ i≤ n)

� und s0,s1, . . . ,sn der bisher benutzte Bandabschnitt.

Weiter oben haben wir festgelegt, dass eine Turing-Maschine im Zu-stand q1 beginnt und alle Bandstellen initial mit dem Zeichen � be-schrieben ist. Demnach startet jede Turing-Maschine in der Start- oderInitialkonfiguration

xStart := (q1,0,�)

Ausgehend von der Initialkonfiguration können wir die Berechnungsse-quenz einer Turing-Maschine in eine Folge von Konfigurationen über-

(q1, 0 , �)

(q1,�,S1,R,q2)

(q2, 1 ,S1, �)

(q2,�,�,R,q3)

(q3, 2 ,S1, � , �)

(q3,�,S2,R,q4)

(q4, 3 ,S1, � ,S2, �)

(q4,�,�,R,q1)

(q1, 4 ,S1, � ,S2, � , �)

(q1,�,S1,R,q2)

(q2, 5 ,S1, � ,S2, � ,S1, �)

(q2,�,�,R,q3)

(q3, 6 ,S1, � ,S2, � ,S1, � , �)

(q3,�,S2,R,q4)

(q4, 7 ,S1, � ,S2, � ,S1, � ,S2, �)

(q4,�,�,R,q1)

(q1, 8 ,S1, � ,S2, � ,S1, � ,S2, � , �)

(q1,�,S1,R,q2)

(q2, 9 ,S1, � ,S2, � ,S1, � ,S2, � ,S1, �)

(q2,�,�,R,q3)

(q3,10,S1, � ,S2, � ,S1, � ,S2, � ,S1, � , �)

(q3,�,S2,R,q4)

. . .

Abbildung 5.3: Konfigurationsübergängeder diskutierten Beispielmaschine


setzen. Abbildung 5.3 demonstriert, wie diese für unsere Beispielma-schine aussieht.

Behalten Sie stets im Gedächtnis, dass die Maschinen aus Turings Ori-ginalarbeit für die Erzeugung von reellen Zahlen konzipiert waren. Ei-ne solche Maschine schreibt die Ziffern einer reellen Zahl nacheinanderauf ein initial leeres Band und hält im Normalfall niemals an.

An dieser Stelle werden wir Turings historische Route verlassen und dasVerhalten seiner Maschinen in einem moderneren Sinne interpretieren;wir werden sie dazu verwenden, um Funktionen der Form

f : S∗ → S∗

zu berechnen. Hierzu wird zunächst ein Eingabewort ω ∈ S∗ an einerbeliebigen Stelle auf das Band geschrieben und der Schreib-Lese-Kopfauf das erste Zeichen positioniert. Anschließend werden die oben be-schriebenen Berechnungsschritte durchgeführt. Terminiert die Maschi-ne, so interpretieren wir den Bandinhalt als den Funktionswert f (ω).Terminiert sie nicht, so betrachten wir die Funktion f an der Stelle ωals undefiniert. Turing-Maschinen sind damit auf natürliche Weise inder Lage, partielle Funktionen zu berechnen. Im Folgenden bezeichnenwir jede Funktion, die sich auf die geschilderte Weise berechnen lässt,als Turing-berechenbar.

Wir halten fest: Turing-Maschinen nehmen von Hause aus Zeichense-quenzen entgegen und keine Zahlen. Wollen wir mit Turing-Maschinenarithmetische Operationen ausführen, d. h., Funktionen der Form

f : N→ N

berechnen, so müssen wir eine geeignete Codierung finden, die Zahlen-werte auf Wörter der Menge S∗ abbildet. Zwei Codierungen drängensich an dieser Stelle regelrecht auf:

� Unäre Codierung

Die Ein- und Ausgabewerte werden durch Einserfolgen entsprechen-der Länge repräsentiert (vgl. Abbildung 5.4 Mitte). Die unäre Co-dierung besitzt den Vorteil, dass sich viele Algorithmen besonderseinfach in eine entsprechende Turing-Maschine übersetzen lassen.Für Komplexitätsbetrachtungen ist sie nicht geeignet, da bereits dasSchreiben einer Zahl n einen linear steigenden Aufwand verursacht.

� Binäre Codierung

Die Ein- und Ausgabewerte werden im Binärformat auf das Bandgeschrieben (vgl. Abbildung 5.4 unten). Die Codierung entspricht

� Allgemeines Berechnungsschema

...

Turing-Maschine

Band

...

f ( )

f ( )... ...

� Unäre Codierung

1 11...

Turing-Maschine

Band

...

f (x) = x + 1

1 11... ...1

f (3) = 4

� Binäre Codierung

11...

Turing-Maschine

Band

...

f (x) = x + 1

0 01... ...

f (3) = 4

Abbildung 5.4: Die unäre und die binäreCodierung im Vergleich


jener, die in realen Computersystemen zum Einsatz kommt. Im Be-reich der Komplexitätstheorie ist die binäre Codierung die bevorzug-te Darstellung, da sich viele Ergebnisse direkt auf reale Rechnerar-chitekturen übertragen lassen.

Mithilfe einer Turing-Maschine lässt sich die unäre Codierung einer na-türlichen Zahl vergleichsweise einfach in die binäre Codierung überset-zen und umgekehrt. Für die Problemstellungen aus dem Gebiet der Be-rechenbarkeitstheorie ist die Wahl der Codierung damit irrelevant, da eshier lediglich um die Frage geht, ob und nicht wie effizient eine Lösunggefunden werden kann.

5.1.1.1 Erweiterungen des Basismodells

In der Vergangenheit wurden aus dem Turing’schen Maschinenmodellverschiedene Varianten abgeleitet, von denen wir drei skizzenhaft vor-stellen wollen (Abbildung 5.5). Eine ausführliche Beschreibung derMaschinentypen finden Sie in [95] oder [181].

� Einseitig beschränkte Turing-Maschinen

Einseitig beschränkte Turing-Maschinen verwenden ein Band, dassich nur in einer Richtung unendlich weit ausbreitet. Ohne Beschrän-kung der Allgemeinheit können wir von einem nach links begrenztenBand ausgehen und die Felder mit den natürlichen Zahlen durch-nummerieren. Der Bandanfang besitzt den Index 0 und speichertdas erste Zeichen der Eingabesequenz. Der Schreib-Lese-Kopf ei-ner einseitig beschränkten Turing-Maschine kann sich nicht über dasBandende hinausbewegen. Eine angeforderte Linksbewegung wirdin diesem Fall ignoriert, und der Schreib-Lese-Kopf verharrt in sei-ner Position.

� Mehrspur-Turing-Maschinen

Eine k-Spur-Turing-Maschine besteht aus einem Band, das in k sepa-rate Spuren unterteilt ist. Die einzelnen Spuren werden von fest an-einandergekoppelten Schreib-Lese-Köpfen angesprochen. Ähnlichdem Prinzip, das konventionellen Festplattenlaufwerken zugrundeliegt, können sich die Köpfe alle gleichzeitig nach links oder rechts,aber nicht unabhängig voneinander bewegen.

� Mehrband-Turing-Maschinen

Eine k-Band-Turing-Maschine besteht aus k Bändern, die von se-paraten Schreib-Lese-Köpfen angesprochen werden. Im Gegensatz


Einseitig beschränkte Maschine Mehrspur-Maschine gMehrband-Maschineg

1 01 ...

Turing-

Maschine

Band

1 01 ......

Turing-

Maschine

Band

0 1 ......

1 01 ...... 0 1 01 ......

10 ......Band 2

Band 1

Turin

g-M

asch

ine

Abbildung 5.5: Die einseitige Beschränkung des Bandes sowie das Hinzufügen neuer Spuren oder Bänder ändert nichts an derBerechnungsstärke der Turing-Maschine. Die entstehenden Maschinenmodelle sind äquivalent.

zu Mehrspur-Turing-Maschinen gestattet sie, dass alle Schreib-Lese-Köpfe unabhängig voneinander bewegt werden.

Es ist ein bekanntes Ergebnis der Berechenbarkeitstheorie, dass sichdie vorgestellten Maschinenmodelle ineinander überführen lassen unddie gleiche Berechnungsstärke besitzen wie das Basismodell [95]. Kon-kret besagt die Äquivalenz das Folgende: Ist eine Funktion mit einerTuring-Maschine berechenbar, so ist sie z. B. auch mit einer einseitigbeschränkten Turing-Maschine berechenbar und umgekehrt. Das glei-che gilt für die anderen Maschinentypen. Diese Eigenschaft wird inder Berechenbarkeitstheorie häufig ausgenutzt. Wird ein Ergebnis bei-spielsweise für einseitig beschränkte Maschinen hergeleitet, so stellendie Äquivalenzen sicher, dass die Ergebnisse auch für die anderen Ma-schinenmodelle Bestand haben.

Am Beispiel der einseitig beschränkten Turing-Maschinen wollen wirdemonstrieren, wie sich die verschiedenen Maschinenmodelle gegen-seitig simulieren lassen. Einseitig beschränkte Turing-Maschinen lassensich durch das Basismodell simulieren, indem das Bandende durch eindediziertes Symbol ‚♦‘ markiert und für alle qi ∈ Q eine Instruktion

(qi,♦,♦,R,qi)

hinzugefügt wird. Hierdurch wird der Schreib-Lese-Kopf auf die Start-position zurückbewegt, bevor der Bandanfang verlassen wird.

S1 S2♢ ...

Turing-

Maschine

Band

S1 S2♢ ...Turing-

Maschine

Band

S1♢ ...

Turing-

Maschine

Band

S2

Abbildung 5.6: Jede Turing-Maschine lässtsich durch eine einseitig beschränkte Ma-schine simulieren. Steht der Schreib-Lese-Kopf, wie hier, ganz links, so wird dieKopfbewegung simuliert, indem der gesam-te Bandinhalt eine Stelle nach rechts kopiertwird. Das Symbol ‚♦‘ wird benötigt, um daslinke Ende des Bands zu markieren.


Die Umkehrung gilt ebenfalls, d. h., wir können jede Turing-Maschinedurch eine einseitig beschränkte Turing-Maschine simulieren. Wir be-ginnen, indem wir den Bandanfang erneut mit dem dedizierten Sym-bol ‚♦‘ markieren. Anschließend bewegen wir den Schreib-Lese-Kopfnach rechts auf das erste Zeichen der Eingabe und starten die Maschi-ne. Solange sich der Kopf rechts des ersten Eingabezeichens befindet,verläuft die Berechnung wie gehabt. Bewegt die Maschine den Schreib-Lese-Kopf jedoch über die linke Grenze hinaus, treffen wir also auf dasvorher eingefügte Symbol ‚♦‘, so müssen wir ein wenig Sonderarbeitleisten. Wir schaffen zunächst Platz für ein neues Zeichen, indem wirden gesamten Bandinhalt um eine Stelle nach rechts verschieben (Ab-bildung 5.6). Anschließend führen wir die Berechnung in gewohnterWeise fort.

Die Konstruktion zeigt, dass wir jede Turing-Maschine in eine äqui-valente Maschine übersetzen können, die niemals versuchen wird, denSchreib-Lese-Kopf nach links über die Startposition hinauszubewegen.

5.1.1.2 Alternative Beschreibungsformen

Die bisherige Darstellung von Turing-Maschinen orientierte sich engan Turings Originalarbeit. In diesem Abschnitt wollen wir eine andereDarstellungsvariante diskutieren, die auf den britischen MathematikerStephen Wolfram zurückgeht und sich an jener des linearen Automatenorientiert [213]. Lineare Automaten bilden eine Untergruppe der zellu-lären Automaten:

Definition 5.3 (Zellulärer Automat)

Ein zellulärer Automat (cellular automaton), kurz ZA, ist ein 4-Tupel (Z,Q,ν ,δ ). Er besteht aus

� der Zellmenge Z,

� der endlichen Zustandsmenge Q,

� der Nachbarschaftsfunktion ν : Z → Zn,

� der Zustandsübergangsfunktion δ : Q×Qn → Q

Ein zellulärer Automat setzt sich aus mehreren Elementarautomaten zu-sammen, die in der Menge Z zusammengefasst sind und als Zellen be-zeichnet werden. Jede Zelle befindet sich zu jedem Zeitpunkt in einem


gVon-Neumann-Nachbarschaftg gMoore-Nachbarschaftg gHexagon-Nachbarschaftg

z

z1z2z3

z4

z5

z6z7z8

ν(z) = (z2,z4,z5,z7)

z

z1z2z3

z4

z5

z6z7z8

ν(z) = (z1,z2,z3,z4,z5,z6,z7,z8)

z5

z1

z4

z3

z6

z

z2

ν(z) = (z1,z2,z3,z4,z5,z6)

Abbildung 5.7: Verschiedene Nachbarschaftsbeziehungen zellulärer Automaten

von endlich vielen Zuständen aus der Menge Q. In der Literatur werdendie Zustände gern durch verschiedene Farben dargestellt. In diesem Fallentspricht die Menge Q dem verfügbaren Farbvorrat.

In einem zellulären Automaten stehen die einzelnen Zellen in ständi-ger Interaktion. Wie sich eine Zelle verhält, wird zum einen durch ihreneigenen, aktuell eingenommenen Zustand und zum anderen durch denZustand ihrer Nachbarzellen bestimmt. In welcher Nachbarschaftsbe-ziehung sich die Zelle befinden, definiert die Funktion ν . Sie bildet eineZelle z auf einen n-elementigen Vektor ab, der alle Nachbarn von z ent-hält. Abbildung 5.7 zeigt, dass mit ν beliebige Topologien von Nach-barschaftsbeziehungen modelliert werden können.

Das Schaltverhalten eines zellulären Automaten wird durch die Zu-standsübergangsfunktion δ bestimmt. Befinden sich die Nachbarzellenz1, . . . ,zn von z in den Zuständen

qz1 , . . . ,qzn ,

so lässt sich der Nachfolgezustand von z wie folgt berechnen:

q′z = δ (qz,qz1 , . . . ,qzn) (5.2)

Jede Auswertung von δ entspricht der Änderung des Zustands einereinzelnen Zelle.

Lineare Automaten sind zelluläre Automaten mit einer eindimensiona-len Topologie; die Zellen sind nebeneinander angeordnet und erstreckensich in beide Richtungen in das Unendliche. Damit bilden sie exakt

� Regelschema

Aktuelles Bandzeichen

Neues Bandzeichen

Folgezustandund Bewegung

nach links

AktuellerZustand

� Vollständiger Regelsatz

Regel 3Regel 1 Regel 2 Regel 4

� Automat in Aktion

Zeit

Abbildung 5.8: Durch eine Modifikationdes Grundmodells lassen sich lineare zel-luläre Automaten für die Simulation vonTuring-Maschinen einsetzen.


das unendliche Band nach, das wir für die Modellierung von Turing-Maschinen benötigen. Der Bandinhalt wird durch die Färbungen derZellen dargestellt, so dass wir die zur Verfügung stehende Farbmengein direkter Weise als das Bandalphabet einer Turing-Maschine interpre-tieren können.

Beachten Sie, dass die Berechnung in einem linearen Automaten ver-teilt erfolgt und alle Zellen parallel eine Zustandsänderung durchführen.Im Gegensatz hierzu arbeitet eine Turing-Maschine mit einem dedizier-ten Schreib-Lese-Kopf, der sich zu jeder Zeit an einer wohldefinier-ten Position befindet. Um das Verhalten einer Turing-Maschine trotz-dem mithilfe eines linearen Automaten beschreiben zu können, müs-sen wir das Automatenmodell geringfügig anpassen. Zunächst erwei-tern wir den linearen Automaten um eine dedizierte Kopfzelle (headcell), die als Schreib-Lese-Kopf fungiert. Das Schaltverhalten des er-weiterten linearen Automaten legen wir analog zur Funktionsweise derTuring-Maschine fest. In jedem Berechnungsschritt wird die Kopfzelleumgefärbt und gegebenenfalls um eine Position nach links oder rechtsgeschoben. Außerdem reichern wir die Kopfzelle um einen zusätzlichenZustand an, der mit dem Zustand der modellierten Turing-Maschineidentisch ist.

Abbildung 5.8 zeigt, wie sich die Beispielmaschine aus Abbildung 5.1in der Notation des modifizierten linearen Automaten beschreiben lässt.Die Zustände q1,q2,q3,q4 werden durch die Richtungen der verwende-ten Keilsymbole und die Bandzeichen S0,S1,S2 durch die unterschiedli-chen Einfärbungen der Zellen repräsentiert. Jede der vier Instruktionenwird durch je zwei Farbfelder und zwei Keilsymbole beschrieben. Dasobere Farbfeld definiert das aktuelle und das untere das neu zu schrei-bende Bandzeichen. Die Richtung des oberen Keils gibt an, in welchemZustand sich die Maschine befinden muss, damit die entsprechende Re-gel angewendet werden kann. Der Folgezustand und die auszuführendeKopfbewegung werden durch den unteren Keil festgelegt. Ist das Keil-symbol links des Folgezustands eingezeichnet, bewegt sich der Schreib-Lese-Kopf nach links, ist es rechts eingezeichnet, bewegt er sich nachrechts. In unserem Beispiel führen alle Instruktionen eine Kopfbewe-gung nach rechts aus.

In der Nomenklatur von Stephen Wolfram wird der so konstruierte Au-tomat als 4,3-Maschine bezeichnet, da er insgesamt 4 Keilrichtungenund 3 Farben unterscheidet.

� Turing-Maschine M

...

Ber

echn

ung

...

M

f ( ) ......

Eingabeband von M

Ausgabeband von M

� Universelle Turing-Maschine U

S.D. ......

M

Codierung von M

U

f ( ) ......

Eingabeband von U

Ausgabeband von U

Ber

echn

ung

Abbildung 5.9: Arbeitsweise der universel-len Turing-Maschine. Eine andere Maschi-ne M wird simuliert, indem M als Zeichen-kette codiert und zusammen mit dem Einga-bewort ω auf das Band von U geschriebenwird. Nach dem Start wird U den Bandin-halt analysieren und das Verhalten von MSchritt für Schritt simulieren.


5.1.1.3 Universelle Turing-Maschine

In seiner Arbeit aus dem Jahr 1936 hat Turing gezeigt, dass seine Ma-schinen zu weit mehr fähig sind, als einfache Berechnungen durchzu-führen. Besonders eindrucksvoll stellte er dies mit der Konstruktioneiner universellen Maschine unter Beweis, die in der Lage ist, andereMaschinen zu simulieren. In seiner Arbeit hat Turing die universelleMaschine ausführlich in §6 beschrieben. Seine Ausführung beginnt mitden folgenden Worten [195]:

„It is possible to invent a single machine which can be usedto compute any computable sequence. If this machine U issupplied with a tape on the beginning of which is writtenthe S.D of some computing machine M, then U will compu-te the same sequence as M. “

Abbildung 5.9 veranschaulicht auf grafische Weise, wie die universel-len Turing-Maschine arbeitet. Als Eingabe nimmt sie die Beschreibungeiner anderen Maschine M in einer codierten Form entgegen, die Turingals Standardbeschreibung bezeichnet (standard description, kurz S.D).Nach dem Start beginnt die universelle Turing-Maschine, das Verhaltenvon M Schritt für Schritt zu simulieren. Ist die Berechnung beendet, sosteht der gleiche Inhalt auf dem Band, den auch M produziert hätte; vonaußen ist dann nicht mehr zu unterscheiden, ob die Bandausgabe von Mselbst geschrieben wurde oder im Rahmen einer Simulation entstandenist. Insgesamt ist die universelle Turing-Maschine in ihrer Funktions-weise dem modernen Computer sehr ähnlich; sie agiert als Interpreter,der das Verhalten einer anderen Maschine in stoischer Manier simuliert.Die Standardbeschreibung ist das Programm, das von der universellenMaschine nach dem Start abgearbeitet wird.

Für die Definition der Standardbeschreibung machte sich Turing zuNutze, dass das Verhalten einer Maschine durch ihre Instruktionsmengeeindeutig definiert ist. Werden die Instruktionen hintereinander aufge-schrieben, so entsteht eine Zeichenkette, aus der sich die Funktions-weise einer Turing-Maschine vollständig rekonstruieren lässt. Für dieMaschine aus Abbildung 5.1 sieht diese Zeichenkette z. B. so aus:

;q1S0S1Rq2;q2S0S0Rq3;q3S0S2Rq4;q4S0S0Rq1

Mit dem Semikolon hatte Turing ein neues Symbol eingeführt, das alsOrientierungsmarke fungiert. Seine universelle Maschine sucht gezieltnach diesem Symbol, um mit wenig Aufwand den Anfang oder das En-de einer Instruktion anzusteuern. Unbedingt benötigt wird es nicht, da

(q1,S0,S1,R,q2)(q2,S0,S0,R,q3)(q3,S0,S2,R,q4)(q4,S0,S0,R,q1)

⎫⎪⎪⎬⎪⎪⎭ Instruktions-tabelle

;q1S0S1Rq2;q2S0S0Rq3;q3S0S2Rq4;q4S0S0Rq1

⎫⎪⎪⎬⎪⎪⎭ Instruktions-kette

qi := DA . . .A︸︷︷︸i-mal

, Si := DC . . .C︸︷︷︸i-mal

;DADDCRDAA;DAADDRDAAA;DAAADDCCRDAAAA;DAAAADDRDA

⎫⎪⎪⎬⎪⎪⎭Standard

description(S.D)

A ↔ 1 C ↔ 2 D↔ 3L ↔ 4 R ↔ 5 N ↔ 6; ↔ 7

7313325311731133 . . .5311173111332253 . . .111173111133531

⎫⎬⎭Description

number(D.N)

Abbildung 5.10: Gödelisierung vonTuring-Maschinen

Ein Blick in Turings Ori-ginalarbeit deckt auf, dassdort eine andere Gödelnum-mer abgedruckt ist als jene,die wir in Abbildung 5.10 ermittelt haben.Schuld daran ist die Position des Semiko-lons. In seinen Erklärungen hatte Turingdas Symbol benutzt, um das Ende einerInstruktion zu markieren, ganz so, wie esin modernen Programmiersprachen üblichist. In Wahrheit funktioniert seine univer-selle Maschine aber anders; sie erwartetdas Semikolon am Anfang und nicht amEnde einer Instruktion [144].


sich die Instruktionen mit etwas Zusatzaufwand auch ohne das Semiko-lon rekonstruieren lassen.

Abbildung 5.10 zeigt, wie es weitergeht. Nachdem die Instruktionskettegebildet ist, werden die Symbole qi und Si nach dem folgenden Schemadurch die Bandsymbole D, A und C ersetzt.

qi := DAAA . . .A︸︷︷︸i-mal

Si := DCCC . . .C︸︷︷︸i-mal

Als Ergebnis erhalten wir das, was Turing als standard description, kurzS.D, bezeichnet. Es ist eine Folge von Zeichen, die das Verhalten dercodierten Maschine eindeutig beschreibt. Zusätzlich hat Turing den Be-griff der description number, kurz D.N, eingeführt. Sie wird aus derStandardbeschreibung gewonnen, indem jedes Zeichen durch eine fest-gelegte Ziffer ersetzt wird.

Den Einfluss, den die Gödel’sche Arbeit aus dem Jahr 1931 auf Turinggehabt haben muss, wird an keiner anderen Stelle so deutlich wie hier.Gödel hatte gezeigt, dass sich die Formeln eines formalen Systems innatürliche Zahlen übersetzen lassen. Turings Codierung erfüllt den glei-chen Zweck; sie zeigt, dass wir das Verhalten einer Turing-Maschinevollständig in eine einzige natürliche Zahl hineincodieren können. Wirwollen die Gemeinsamkeit auch sprachlich zum Ausdruck bringen unddie description number einer Turing-Maschine M im Folgenden als dieGödelnummer von M bezeichnen.

Turing war sich der großen Bedeutung seiner universellen Maschinebewusst und beschrieb sie in entsprechend großer Akribie. Neben einermehrseitigen Erklärung der grundlegenden Funktionsweise ist in sei-ner Arbeit die vollständige Instruktionstabelle abgedruckt (vgl. Abbil-dung 5.11 und 5.12). Die universelle Maschine ist modular aufgebautund setzt sich aus mehr als 50 Einzelmaschinen zusammen, die sichgegenseitig referenzieren. Um eine möglichst kompakte Darstellung zuerreichen, ließ er den Folgezustand einer Maschine auf den Startzustandeiner anderen Maschine verweisen und versah die Referenz zusätzlichmit einem oder mehreren Parametern. Auf diese Weise hatte Turingeinen Sprungbefehl erschaffen und damit auf ein Konzept zurückge-griffen, das viele Jahre später zum Standardrepertoire imperativer Pro-grammiersprachen werden sollte.

J. P. Burgess bezeichnet die universelle Maschine als „one of the intel-lectual landmarks of the last century“ [16], und es ist unzweifelhaft,dass Turing 1936 ein begeisterndes Kapitel Wissenschaftsgeschichtegeschrieben hat. Teil dieses Kapitels sind aber auch zwei kleine Schön-heitsfehler, die an dieser Stelle nicht unerwähnt bleiben sollen:


f(C,B,α)

⎧⎪⎪⎪⎨⎪⎪⎪⎩

e L f1(C,B,α)

Not e L f(C,B,α)

None L f(C,B,α)

f1(C,B,α)

⎧⎪⎪⎪⎨⎪⎪⎪⎩α C

Not α R f1(C,B,α)

None R f2(C,B,α)

f2(C,B,α)

⎧⎪⎪⎨⎪⎪⎩α C

Not α R f1(C,B,α)

None R B

pe(C,β ) f(pe1(C,β ),C,

e)

pe1(C,β )

⎧⎨⎩ Any R,R pe1(C,β )

None Pβ C

l(C) L C

r(C) R C

f′(C,B,α) f(l(C),B,α)

f′′(C,B,α) f(r(C),B,α)

c(C,B,α) f′(c1(C),B,α)

c1(C) β pe(C,β )

ce(C,B,α) c(e(C,B,α),B,α)

ce(B,α) ce(ce(B,α),B,α)

cp(C,U,F,α,β ) f′ (cp1(C1,U,β ), f(U,C,β ),α)

cp1(C,U,β ) γ f′ (cp2(C,U,γ),U,β )

cp2(C,U,γ)

⎧⎨⎩ γ C

Not γ U

cpe(C,U,F,α,β ) cp(e(e(C,C,β ),C,α) ,U,F,α,β )

cpe(U,F,α,β ) cpe(cpe(U,F,α,β ),U,F,β )

q(C)

⎧⎨⎩ Any R q(C)

None R q1(C)

q1(C)

⎧⎨⎩ Any R q(C)

None C

q(C,α) q(q1(C,α))

q1(C,α)

⎧⎨⎩ α C

Not α L q1(C,α)

pe2(C,α,β ) pe(pe(C,β ),α)

ce2(B,α,β ) ce(ce(B,β ),α)

ce3(B,α,β ,γ) ce(ce2(B,β ,γ),α)

ce4(B,α,β ,γ,δ ) ce(ce3(B,β ,γ,δ ),α)

ce5(B,α,β ,γ,δ ,ε) ce(ce4(B,β ,γ,δ ,ε),α)

e(C)

⎧⎨⎩

e R e1(C)

Not e L e(C)

e1(C)

⎧⎨⎩ Any R,E,R e1(C)

None C

Abbildung 5.11: Hilfsroutinen für die Konstruktion von Turings universeller Maschine aus dem Jahr 1936 [195]. Die farblichhervorgehobenen Passagen sind Korrekturen, die später von Emil Post und Donald Davies eingebracht wurden [40, 144].

� Streng genommen arbeitet Turings universelle Maschine nicht ex-akt so, wie es in Abbildung 5.9 beschrieben ist. Das Problem stelltsich wie folgt dar: Simuliert die Maschine U die Maschine M, soist sichergestellt, dass U die gleiche Ziffernfolge wie M generiert,allerdings erscheinen die Ziffern nicht an den gleichen Bandpositio-nen. Turings hatte seine Maschine so konstruiert, dass sie zusätzlicheHilfszeichen auf das Band schreibt, die zur Ablaufsteuerung dienen.Für ihn spielte der unterschiedliche Bandinhalt keine Rolle. Inter-pretieren wir aber den kompletten Bandinhalt als Ausgabe, so wiees heute üblich ist, dann produziert die universelle Maschine U eineandere Ausgabe als die simulierte Maschine M.


b f(b1,b1, ::)

b1 R,R,P :,R,R, anf

PD,R,R,PA

anf q(anf1, :)

anf1 con(kom,y)

con(C,α)

⎧⎨⎩ Not A R,R con(C,α)

A L,Pα,R con1(C,α)

con1(C,α)

⎧⎪⎪⎪⎨⎪⎪⎪⎩A R,Pα,R con1(C,α)

D R,Pα,R con2(C,α)

None PD,R,Pα,R,R,R C

con2(C,α)

⎧⎨⎩ C R,Pα,R con2(C,α)

Not C R,R C

kom

⎧⎪⎪⎪⎨⎪⎪⎪⎩; R,Pz,L con(kmp,x)

z L,L kom

Not z nor ; L kom

kmp cpe(e(kom,x,y),sim,x,y)

sim f′(sim1,sim1,z)

sim1 con(sim2,)

sim2

⎧⎨⎩ A sim3

Not A L,Pu,R,R,R sim2

sim3

⎧⎨⎩ Not A L,Py e(mk,z)

A L,Py,R,R,R sim3

mk q(mk1, :)

mk1

⎧⎨⎩ Not A R,R mk1

A L,L,L,L mk2

mk2

⎧⎪⎪⎨⎪⎪⎩C R,Px,L,L,L mk2

: mk4

D R,Px,L,L,L mk3

mk3

⎧⎨⎩ Not : R,Pv,L,L,L mk3

: mk4

mk4 con(l(l(mk5)) ,)

mk5

⎧⎨⎩ Any R,Pω,R mk5

None P : sh

sh f(sh1, inst,u)

sh2

⎧⎨⎩ D R,R,R,R sh3

Not D inst

sh3

⎧⎨⎩ C R,R sh4

Not C inst

sh4

⎧⎨⎩ C R,R sh5

Not C pe2(inst,0, :)

sh5

⎧⎨⎩ C inst

Not C pe2(inst,1, :)

inst q(l(inst1),u)

inst1

⎧⎪⎪⎪⎨⎪⎪⎪⎩L R,E ce5(ov,v,y,x,u,w)

R R,E ce5(ov,v,x,u,y,w)

N R,E ce5(ov,v,x,y,u,w)

Abbildung 5.12: Ein Stück Wissenschaftsgeschichte: Alan Turings universal machine aus dem Jahr 1936 [195]. Die farblichhervorgehobenen Passagen sind Korrekturen, die später von Emil Post und Donald Davies eingebracht wurden [40, 144].

� Turings ursprüngliche Instruktionstabelle ist an mehreren Stellenfehlerhaft. Vereinzelt hatte er Symbole vertauscht, die falschen Indi-zes verwendet oder schlicht eine Instruktionsregel vergessen. Vieledieser Fehler wurden später von Emil Post und Donald Davies ent-deckt [40, 144]. Die meisten davon sind vergleichsweise einfach zukorrigieren; sie sind das, was wir heute als typische Implementie-rungsfehler bezeichnen.

� 2,5-Maschine

(q1,S4,S3,L,q2)(q1,S3,S4,R,q2)(q1,S2,S0,R,q1)(q1,S1,S0,R,q1)(q1,S0,S1,L,q1)

(q2,S4,S2,L,q2)(q2,S3,S4,R,q2)(q2,S2,S4,R,q1)(q2,S1,S0,R,q1)(q2,S0,S3,L,q1)

� 2,3-Maschine

(q1,S2,S1,L,q1)(q1,S1,S2,L,q1)(q1,S0,S1,R,q2)

(q2,S2,S1,R,q1)(q2,S1,S2,R,q2)(q2,S0,S2,L,q1)

Abbildung 5.13: Turing-Maschinen vonStephen Wolfram aus dem Jahr 2002 [213]


� Schwerer wiegt, dass Turing auch architektonische Fehler unterlie-fen, die sich kaum beseitigen lassen. Beispielsweise versagt die Si-mulation bei Maschinen, die den Schreib-Lese-Kopf mehrmals andie gleiche Stelle bewegen und eine vormals geschriebene Zifferdurch eine andere ersetzen. Wahrscheinlich hatte Turing diesen Fallschlicht nicht bedacht, da er gedanklich immer nur solche Maschi-nen im Sinn hatte, die eine reelle Zahl Ziffer für Ziffer von links nachrechts auf das Band schreiben. Dennoch lässt sein Maschinenmodelldas geschilderte Verhalten explizit zu.

Dass seine Maschine in ihrer ursprünglichen Form kleine Fehler auf-weist, mindert Turings Leistung nicht. Die Defizite sind nicht vongrundsätzlicher Natur, und so war es nur eine Frage der Zeit, bis dieersten Maschinen entwickelt wurden, die jede andere Turing-Maschinefehlerfrei simulieren konnten und damit exakt so funktionierten, wiees in Abbildung 5.9 beschrieben ist. Ein Meilenstein in dieser Rich-tung war die universelle Turing-Maschine von Marvin Minsky aus demJahr 1962. Sie beseitigte sämtliche Fehler und Limitierungen des Tu-ring’schen Originalentwurfs und war zudem deutlich einfacher aufge-baut; die Minsky-Maschine unterscheidet lediglich 7 Zustände und 4Bandzeichen. In der von Stephen Wolfram vorgeschlagenen Nomen-klatur wird sie als 7,4-Maschine bezeichnet.

Im Jahr 2002 stellte Wolfram eine weiterentwickelte Maschine vor, dieebenfalls universell ist, aber mit noch weniger Zuständen auskommt(Abbildung 5.13 oben). Während Minskys Modell noch 7 Zustände be-nötigte, kommt die neue 2,5-Maschine mit nur 2 Zuständen aus. DieAnzahl der Bandzeichen musste Wolfram allerdings von 4 auf 5 er-höhen. Bedeutender sollte jedoch seine zeitgleich veröffentlichte 2,3-Maschine werden (Abbildung 5.13 unten). Wolfram schlug die Maschi-ne als einen potenziellen Kandidaten für die kleinstmögliche universelleTuring-Maschine vor [213]. Obwohl er seine Vermutung nicht beweisenkonnte, erzielte er ein beachtliches Zwischenresultat: Ihm gelang derNachweis, dass 2 Bandzeichen und 2 Zustände nicht ausreichen, umdie Eigenschaft der Universalität zu erreichen. Wäre die 2,3-Maschinealso tatsächlich universell, so wäre sie gleichzeitig die kleinste.

2007 hat die Suche nach der kleinstmöglichen universellen Maschineein erfolgreiches Ende gefunden. In jenem Jahr gelang dem 20-jährigenBriten Alex Smith der Nachweis, dass die 2,3-Maschine tatsächlich uni-versell ist. Leider ist sie nicht einfach zu „programmieren“. Bevor eineMaschine simuliert werden kann, muss sie mit einem speziellen Compi-ler in eine passende Eingabe übersetzt werden, die bereits für primitiveMaschinen eine gigantische Größe erreicht.

1i Li

234

Programm

...5

1i Ri

234

Speicher

...5

Abbildung 5.14: Allgemeiner Aufbau ei-ner Registermaschine

Der Begriff der Registerma-schine wird in der Literaturunterschiedlich definiert. Manche Auto-ren statten die Maschinen mit unend-lich vielen Registern aus, die entwederbeliebig große natürliche Zahlen spei-chern können oder nur Zahlen aus ei-nem begrenzten Bereich. Noch unter-schiedlicher fallen die Befehlssätze aus.Der hier vorgestellte Maschinentyp ba-siert auf einer Sprache, die in der Li-teratur gern als Goto-Sprache bezeich-net wird [95, 169, 181]. Andere Maschi-nenmodelle nutzen dagegen Instruktio-nen, die an die Assembler-Sprachen derfrühen Mikroprozessoren erinnern [51,95]. Das Eingabe- und Ausgabeverhaltenwird ebenfalls unterschiedlich gehand-habt. Einige Maschinentypen tauschen dieEingabe- und Ausgabewerte nicht, wiehier, über die Register, sondern über spe-zielle Speicherbänder aus [51, 95]. Es istein bedeutendes Ergebnis der Berechen-barkeitstheorie, dass sich die genanntenUnterschiede nicht auf die Berechnungs-stärke auswirken und es daher keine Rol-le spielt, welches dieser Modelle für dieUntersuchungen des Berechenbarkeitsbe-griffs verwendet wird.


5.1.2 Registermaschinen

In diesem Abschnitt werden wir mit der Registermaschine ein Berech-nungsmodell besprechen, das in Aufbau und Funktion dem realen Com-puter sehr ähnlich ist [99,126,127]. Anders als bei der Turing-Maschineist kein Band mehr vorhanden; stattdessen existieren mehrere Register,die natürliche Zahlen beliebiger Größe aufnehmen können und sich wiebei realen Computern über eine individuelle Speicheradresse direkt an-sprechen lassen (Abbildung 5.14). Das aufwendige Hin- und Herbewe-gen eines Schreib-Lese-Kopfs, wie wir es von der Turing-Maschine hergewöhnt sind, kann hierdurch vollständig entfallen. Gesteuert wird dieRegistermaschine über ein Programm, das aus einer nummerierten Listevon Instruktionen besteht.

Definition 5.4 (Registermaschine)

Eine Registermaschine ist ein Tupel (R, I). Sie besteht aus

� der endlichen Registermenge R = {R1, . . . ,Rr} und

� der endlichen Instruktionsmenge I = {L1, . . . ,Ll}.Jede Instruktion hat eine der folgenden Formen:

� Li : R j ← R j +1 � Li : goto Ln (n �= i+1)

� Li : R j ← R j−1 � Li : if R j = 0 goto Ln (n �= i+1)

� Li : stop � Li : if R j �= 0 goto Ln (n �= i+1)

Nach dem Start einer Registermaschine werden alle Register per De-finition mit dem Wert 0 initialisiert, und es wird mit der Ausführungder Instruktion L1 begonnen. Die Auswahl der Folgeinstruktion funk-tioniert so, wie wir es von imperativen Programmiersprachen gewöhntsind. Normalerweise folgt auf die Instruktion Li die Instruktion Li+1,es sein denn, der Kontrollfluss wird durch einen unbedingten Sprung(goto) oder einen bedingten Sprung (if goto) direkt beeinflusst oder dieBerechnung mit dem Befehl stop explizit beendet.

Registermaschinen verfügen über rudimentäre Arithmetikfähigkeiten,die im Vergleich zu realen Computern spartanisch wirken; außer derMöglichkeit, den Inhalt eines Registers um eins zu erniedrigen oder zuerhöhen, werden keine anderen Operationen unterstützt. Für die Sub-traktion existiert eine Sonderregel. Da Registermaschinen keine nega-tiven Zahlen verarbeiten können, wird die Subtraktion saturiert ausge-

L1 if R1 = 0 goto L20

L2 R2 ← R2 +1,R3 ← R3 +1L3 R1 ← R1−1L4 if R1 = 0 goto L16

L5 R1 ← R1−1L6 R4 ← R4 +1,R5 ← R5 +1L7 R3 ← R3−1L8 if R3 �= 0 goto L6

L9 R4 ← R4 +1,R2 ← R2−1L10 if R2 �= 0 goto L9

L11 R3 ← R3 +1,R4 ← R4−1L12 if R4 �= 0 goto L11

L13 R2 ← R2 +1,R5 ← R5−1L14 if R5 �= 0 goto L13

L15 if R1 �= 0 goto L5

L16 R3 ← R3−1L17 if R3 �= 0 goto L16

L18 R2 ← R2−1,R1 ← R1 +1L19 if R2 �= 0 goto L18

L20 stop

Abbildung 5.16: Registermaschinenpro-gramm aus [100]


1i Li

234

Programm

...5

Berechnende Maschine

i Ri

223

Speicher

...4

Inhalt von R1

Ein- und Ausgabe1

NeinJa Eingabe

akzeptiert?

1i Li

234

Programm

...5

Akzeptierende Maschine

1i

EingabeRi

234

Speicher

...5

Abbildung 5.15: Transduktoren und Akzeptoren im Vergleich

führt. Das bedeutet, dass die Berechnung 0− 1 nicht dem Wert −1,sondern den Wert 0 liefert.

Genau wie Turing-Maschinen lassen sich auch Registermaschinen aufzwei unterschiedliche Arten nutzen:

� Als berechnende Maschine (Abbildung 5.15 links)

In diesem Fall nimmt die Maschine in Register R1 die Eingabe entge-gen und legt dort auch das Ergebnis ab [100]. Alle anderen Registerstehen für die Speicherung von Zwischenergebnissen zur Verfügung.Eine berechnende Maschine wird auch als Transduktor bezeichnet.

� Als akzeptierende Maschine (Abbildung 5.15 rechts)

Anstatt einen konkreten Ergebniswert zu berechnen, liefert die Ma-schine in diesem Fall lediglich eine Ja-Nein-Antwort. Wir sagen, ei-ne Registermaschine akzeptiert die Eingabe in R1, wenn sie nachendlich vielen Schritten terminiert und zu diesem Zeitpunkt alle Re-gister den Wert 0 enthalten [99]. Andernfalls wird die Eingabe nichtakzeptiert. Wir sagen auch, die Eingabe wird zurückgewiesen oderverworfen.


R1 R2 R3 R4 R5 Befehl

0 2 0 0 0 0 L1 if R1 = 0 goto L20

1 2 0 0 0 0 L2 R2 ← R2 +1

R3 ← R3 +1

2 2 1 1 0 0 L3 R1 ← R1−1

3 1 1 1 0 0 L4 if R1 = 0 goto L16

4 1 1 1 0 0 L5 R1 ← R1−1

5 0 1 1 0 0 L6 R4 ← R4 +1

R5 ← R5 +1

6 0 1 1 1 1 L7 R3 ← R3−1

7 0 1 0 1 1 L8 if R3 �= 0 goto L5

8 0 1 0 1 1 L9 R4 ← R4 +1

R2 ← R2−1

9 0 0 0 2 1 L10 if R2 �= 0 goto L9

10 0 0 0 2 1 L11 R3 ← R3 +1

R4 ← R4−1

11 0 0 1 1 1 L12 if R4 �= 0 goto L11

R1 R2 R3 R4 R5 Befehl

12 0 0 1 1 1 L11 R3 ← R3 +1

R4 ← R4−1

13 0 0 2 0 1 L12 if R4 �= 0 goto L11

14 0 0 2 0 1 L13 R2 ← R2 +1

R5 ← R5−1

15 0 1 2 0 0 L14 if R5 �= 0 goto L13

16 0 1 2 0 0 L15 if R1 �= 0 goto L5

17 0 1 2 0 0 L16 R3 ← R3−1

18 0 1 1 0 0 L17 if R3 �= 0 goto L16

19 0 1 1 0 0 L16 R3 ← R3−1

20 0 1 0 0 0 L17 if R3 �= 0 goto L16

21 0 1 0 0 0 L18 R2 ← R2−1

R1 ← R1 +1

22 1 0 0 0 0 L19 if R2 �= 0 goto L18

23 1 0 0 0 0 L20 stop

Abbildung 5.17: Ablaufprotokoll für die Eingabe R1 = 2

Als Beispiel ist in Abbildung 5.16 das Registermaschinenprogrammaus der bekannten Arbeit „Proof of Recursive Unsolvability of Hil-bert’s Tenth Problem“ von James P. Jones und Juri Matijasevic aus demJahr 1991 abgedruckt [100]. Das Programm ist für einen Transduktor,d. h. für eine berechnende Maschine ausgelegt. Wird es mit der EingabeR1 = 2 gestartet, so werden nacheinander die in Abbildung 5.17 dar-gestellten Berechnungsschritte ausgeführt. Nach 23 Schritten hält dieMaschine an und hinterlässt in R1 den Ergebniswert 1.

Vielleicht ist Ihnen aufgefallen, dass Jones und Matijasevic geringfügigvon den getroffenen Vereinbarungen aus Definition 5.14 abgewichensind, da sie in den Zeilen L2, L6, L9, L11, L13 und L18 mehrere Einzel-instruktionen zu einem gemeinsamen Befehl zusammengefasst haben.Diese Verallgemeinerung stellt uns vor keinerlei Probleme, da wir zu-sammengefasste Befehle jederzeit auf mehrere Zeilen aufteilen können.

5.2 Die Church’sche These 287

199511Aug

190314Jun Viele Errungenschaften auf dem

Gebiet der Berechenbarkeitstheo-rie sind mit dem Namen AlonzoChurch verbunden. Geboren wurde

der amerikanische Logiker am 14. Juni 1903 in Washing-ton, D.C. Die Schule besuchte er in Ridgefield, Connecti-cut. Nach dem Studium und der Promotion an der PrincetonUniversity folgten Aufenthalte in Chicago, Harvard, Göt-tingen und Amsterdam. Nach seiner Rückkehr in die USAwurde er 1929 in Princeton zum Assistant Professor, 1939zum Associate Professor und 1947 zum Full Professor er-nannt. Church blieb Princeton lange treu. Erst nach seinerEmeritierung im Jahr 1967 wechselte er an die University ofCalifornia, Los Angeles, wo er weitere 23 Jahre lehrte undforschte. Drei Jahre nach seiner zweiten Emeritierung, am11. August 1995, starb Alonzo Church in Hudson, Ohio, imAlter von 92 Jahren.Zu seinen größten Leistungen gehört die Entdeckung des λ -Kalküls im Jahr 1930. Mit ihm wollte Church die Mathema-tik mit einem formalen Unterbau versehen, der frei von Para-doxien, aber weniger umständlich sein sollte als die konkur-rierende Typentheorie von Russell und Whitehead. Damals

war noch nicht abzusehen, dass die Zukunft des λ -Kalkülsnicht in der Mathematik, sondern in der Informatik liegenwürde. Im Laufe der Zeit wurde er zu einem wertvollenHilfsmittel für die formale Untersuchung von Programmier-sprachen und bildet heute den operativen Kern der funktio-nalen Programmiersprachen Lisp.Im Jahr 1936 gelang es Church, aus dem λ -Kalkül das glei-che Ergebnis abzuleiten, das Turing wenige Monate spätermithilfe der Turing-Maschine erzielte: die Unentscheidbar-keit der Prädikatenlogik erster Stufe [32]. Damit nahm er dasHauptresultat aus Turings berühmter Publikation zwar zeit-lich vorweg, sein Beweis besaß aber bei Weitem nicht dieKlarheit und Eleganz des Turing’schen Ansatzes. Ebenfallsaus dem Jahr 1936 stammt die berühmte Church’sche The-se [33], die wir in Abschnitt 5.2 diskutieren.Rückblickend dürfen wir Church als den geistigen Ziehva-ter einer neuen Logikergeneration bezeichnen. Unter seinen31 Doktoranden befinden sich mit Martin Davis, Leon Hen-kin, Stephen Kleene, Michael Oser Rabin, Barkley Rosser,Dana Scott, Raymond Smullyan und Alan Turing namhafteLogiker, von denen uns die meisten an anderer Stelle diesesBuchs schon begegnet sind oder noch begegnen werden.

5.2 Die Church’sche These

Mit der Turing-Maschine und der Registermaschine haben wir zwei Be-rechnungsmodelle kennen gelernt, die auf den ersten Blick sehr unter-schiedlich wirken. Aus der Ferne betrachtet scheint die Registermaschi-ne das leistungsfähigere Berechnungsmodell zu sein, da alle Registerfrei adressiert werden können und sich hierdurch viele Algorithmen oh-ne große Umwege in ein Registermaschinenprogramm übersetzen las-sen. Auf den ersten Blick wirkt auch ihr Speicher größer als der ei-ner Turing-Maschine. Anstelle eines einzelnen Bands existiert eine freiwählbare Anzahl von Registern, die beliebig große natürliche Zahlenspeichern können. Erst auf den zweiten Blick wird deutlich, dass diegroßzügige Gestaltung des Maschinenmodells zu keiner Steigerung derBerechnungsstärke führt. Jede Funktion, die mithilfe einer Registerma-schine berechnet werden kann, ist auch mithilfe einer Turing-Maschineberechenbar [127].

Lässt sich diese Beobachtung verallgemeinern? Um der Antwort näherzu kommen, werden wir kurz eine Reihe weiterer Berechnungsmodelleskizzieren. Anschließend werden wir klären, ob sich die Berechnungs-stärke der Turing-Maschine mit einem dieser Modelle überbieten lässt.

while x1 �= 0 do

x3 := x2;while x3 �= 0 do

x0 := succ(x0);x3 := pred(x3)

end;x1 := pred(x1)

end

x0 x1 x2 x3 Befehl

1 0 2 2 0 while x1 �= 0 do

2 0 2 2 0 x3 := x2

3 0 2 2 2 while x3 �= 0 do

4 0 2 2 2 x0 := succ(x0)

5 1 2 2 2 x3 := pred(x3)

6 1 2 2 1 while x3 �= 0 do

7 1 2 2 1 x0 := succ(x0)

8 2 2 2 1 x3 := pred(x3)

9 2 2 2 0 while x3 �= 0 do

10 2 2 2 0 x1 := pred(x1)

11 2 1 2 0 x3 := x2

12 2 1 2 2 while x3 �= 0 do

13 2 1 2 2 x0 := succ(x0)

14 3 1 2 2 x3 := pred(x3)

15 3 1 2 1 while x3 �= 0 do

16 3 1 2 1 x0 := succ(x0)

17 4 1 2 1 x3 := pred(x3)

18 4 1 2 0 while x3 �= 0 do

19 4 1 2 0 x1 := pred(x1)

20 4 0 2 0 while x1 �= 0 do

Abbildung 5.18: While-Programm für dieMultiplikation zweier natürlicher Zahlen x1und x2. Der Ablaufplan demonstriert dieProgrammausführung für den Fall x1 = 2und x2 = 2. Am Ende der Berechnung ent-hält das Register x0 den Ergebniswert 4.


� While-Programme (Abbildung 5.18)

Die While-Sprache ist eine fiktive Computersprache, die dem impe-rativen Programmierparadigma folgt. Ein While-Programm schöpftaus einem unendlichen Vorrat an Variablen xi, i ∈ N, von denenx1, . . . ,xn zur Übergabe der Eingabewerte verwendet werden. DasErgebnis wird in x0 gespeichert, und die restlichen Variablen dienenzur Ablage von Zwischenergebnissen.

Optisch erinnert die While-Sprache an klassische imperative Pro-grammiersprachen wie C oder Pascal, allerdings ist der Sprachschatzauf ein Minimum beschränkt. Er umfasst lediglich die beiden Opera-toren succ und pred, die Zuweisung ‚:=‘, den Kompositionsoperator‚;‘ und das Schleifenkonstrukt while do end.

� μ-rekursive Funktionen

Die Menge der μ-rekursiven Funktionen ist die kleinste Menge, diealle primitiv-rekursiven Funktionen enthält und außerdem unter derAnwendung des μ-Operators abgeschlossen ist. Mit diesem Opera-tor lässt sich eine n+ 1-stellige Funktion f : Nn+1 → N nach demfolgenden Schema auf eine n-stellige Funktion reduzieren:

(μ f )(x1, . . . ,xn) := min

⎧⎨⎩m

∣∣∣∣∣∣f (m,x1, . . . ,xn) = 0

und für alle k < m istf (k,x1, . . . ,xn) �=⊥

⎫⎬⎭ (5.3)

Das Symbol ‚⊥‘ steht stellvertretend für einen undefinierten Funkti-onswert. Degradiert die rechte Seite von Gleichung (5.3) zur leerenMenge, so ist kein minimales Element vorhanden und der Funkti-onswert undefiniert ((μ f )(x1, . . . ,xn) =⊥).

� Lambda-Kalkül (Abbildung 5.19)

Der Lambda-Kalkül (kurz λ -Kalkül) basiert auf der Idee, komplexemathematische Funktionen durch die Kombination allgemein gehal-tener Rechenvorschriften zu definieren. Die grundlegende Operationist die Anwendung einer Funktion f auf ein Argument x, geschrie-ben als ( f x). Ist z. B. add eine Funktion zur Addition zweier Zahlen,so berechnet ((add x) y) die Summe x+ y. Mithilfe des λ -Operatorslassen sich Variablen binden und damit aus bestehenden Funktio-nen neue erzeugen. Beispielsweise bezeichnet (λx.((add x) x)) einevon x abhängige Funktion, die den Wert 2 ·x berechnet. λ -Ausdrückelassen sich freizügig kombinieren. So kann eine Funktion beliebigeλ -Terme als Argumente erhalten und damit insbesondere auch aufFunktionen angewendet werden. Wie der Ausdruck ((λx.x)(λx.x))zeigt, kann sich eine Funktion sogar selbst als Argument entgegen-nehmen.

� Reduktionsregeln

(α) λξ .ϕμ �∈ϕ→ λ μ .ϕ[ξ ← μ]

(β ) ((λξ .ϕ)ψ) → ϕ[ξ ← ψ]

(η) λξ .ϕξ → ϕ

� Ableitung

((((λy.(λ z.(λx.((yz)x))))

(λw.(λx.(wx))))P)v)β⇒ (((λ z.(λx.(((λw.(λx.(wx)))z)x)))P)v)β⇒ ((λx.(((λw.(λx.(wx)))P)x))v)β⇒ (((λw.(λx.(wx)))P)v)β⇒ ((λx.(Px))v)β⇒ (Pv)

Abbildung 5.19: Ableitung im λ -Kalkül

� Produktionen

xI → xIU (Regel 1)

Mx → Mxx (Regel 2)

xIIIy → xUy (Regel 3)

xUUy → xy (Regel 4)

� Ableitung von MUIIU aus MI

MI ⇒ MII (Regel 2)

⇒ MIIII (Regel 2)

⇒ MUI (Regel 3)

⇒ MUIU (Regel 1)

⇒ MUIUUIU (Regel 2)

⇒ MUIIU (Regel 4)

Abbildung 5.20: MIU-System von DouglasHofstadter [96], hier formuliert als Termer-setzungssystem


� Termersetzungssysteme (Abbildung 5.20)

Ein Termersetzungssystem besteht aus einer Menge von Ersetzungs-regeln der Form l → r, den sogenannten Produktionen. Auf der lin-ken und der rechten Seite stehen Terme, die neben den Symbolen ei-ner Menge Σ auch Variablen enthalten dürfen. Die Ersetzungsregelnwerden verwendet, um ein vorgelegtes Eingabewort ω ∈ Σ∗ sukzes-sive umzuformen. Hierzu wird zunächst geprüft, ob sich ω und dielinke Seite einer Produktion l → r durch eine Substitution S anglei-chen lassen (lS= rS). In diesem Fall ist rS das Ergebnis. Termer-setzungssysteme existieren in vielen Variationen. Wichtige Vertre-ter sind die Phrasenstrukturgrammatiken (Typ-0-Grammatiken) [95]oder die Semi-Thue-Systeme, die der norwegische MathematikerAxel Thue im Jahr 1914 zur Untersuchung von Ableitungskalkülenersann [193].

Wir wissen heute, dass es keine Rolle spielt, welches der vorgestelltenModelle wir zur Begründung des Berechenbarkeitsbegriffs zu Rate zie-hen; trotz ihrer unübersehbaren äußerlichen Unterschiede besitzen alledie gleiche Ausdrucksstärke. Das bedeutet, dass der Berechenbarkeits-begriff stets derselbe bleibt, egal ob wir ihn über die Turing-Maschine,die Registermaschine, die While-Sprache, die Menge der μ-rekursivenFunktionen, den λ -Kalkül oder mithilfe von Termersetzungssystemendefinieren.

Für den amerikanischen Logiker Alonzo Church war dies die empiri-sche Bestätigung für die These, dass der intuitive Berechenbarkeitsbe-griff mit dem Begriff der Turing-Berechenbarkeit zusammenfällt. Ge-nau dies ist der Inhalt der berühmten Church’schen These:

Satz 5.1 (Church’sche These)

Die Klasse der Turing-berechenbaren Funktionen stimmt mit derKlasse der intuitiv berechenbaren Funktionen überein.

Der Begriff der intuitiv berechenbaren Funktion bedarf an dieser Stellebesonderer Aufmerksamkeit. Er bezeichnet eine Funktion, die von ei-nem Menschen – in welcher Form auch immer – ausgerechnet werdenkann. Damit besagt die Church’sche These nichts anderes, als dass je-de Funktion, die überhaupt in irgendeiner Weise berechenbar ist, auchdurch eine Turing-Maschine berechnet werden kann.

Die Church’sche These ist kein Satz im mathematisch präzisen Sinne,da der Begriff der intuitiv berechenbaren Funktion keine formale Defi-nition besitzt. Gäbe es diese, so hätten wir uns – bewusst oder unbewusst

� Entscheidbarkeit

NeinJa

in N ?

Entscheiderfür N

� Semi-Entscheidbarkeit

Ja

in N ?

Semi-Entscheiderfür N

Abbildung 5.21: Bildliche Darstellung derbeiden Entscheidbarkeitsbegriffe


– bereits auf ein konkretes Berechnungsmodell festgelegt und die ei-gentliche Bedeutung dieses Begriffs ad absurdum geführt. Folgerichtigwird es niemals möglich sein, die Church’sche These zu beweisen. Wirkönnen lediglich Indizien für ihre Gültigkeit sammeln, und genau diesist Forschern in der Vergangenheit vielfach gelungen. Alle bisher unter-nommenen Versuche, die Menge der berechenbaren Funktionen durchdie Angabe eines ausdrucksstärkeren Berechnungsmodells zu vergrö-ßern, waren bisher vergebens. Selbst so ausgefallene Konzepte wie derQuantenrechner [135] oder das DNA computing [5] konnten die Grenzedes maschinell Berechenbaren nicht verschieben.

Die Church’sche These ist die Legitimation für die folgende Definiti-on, die den bereits mehrfach bemühten Begriff der Berechenbarkeit nunendlich mit einem formalen Unterbau versieht:

Definition 5.5 (Berechenbarkeit)

Eine partielle Funktion f : Σ∗ → Σ∗ heißt berechenbar, wenn eineTuring-Maschine M mit der folgenden Eigenschaft existiert:

� Ist f (ω) �=⊥, so

beschreibt M bei Eingabe von ω das Band mit f (ω) und hält an.

� Ist f (ω) =⊥, so

rechnet M bei Eingabe von ω für immer weiter.

In dieser Definition ist Σ eine beliebige Menge, die als Bandalphabeteiner Turing-Maschine in Frage kommt. Von hier ist es nur noch einkleiner Schritt, um auch den Begriff der Entscheidbarkeit formal zu er-fassen:

Definition 5.6 (Entscheidbarkeit, Semi-Entscheidbarkeit)

Eine Menge N ⊆ Σ∗ heißt entscheidbar, falls die charakteristischeFunktion χN : Σ∗ → {0,1} berechenbar ist mit

χN(ω) :={

1 falls ω ∈ N0 falls ω �∈ N

Eine Menge N ⊆Σ∗ heißt semi-entscheidbar, falls die partielle cha-rakteristische Funktion χ ′N : Σ∗ → {1} berechenbar ist mit

χ ′N(ω) :={

1 falls ω ∈ N⊥ falls ω �∈ N

Ja

in N ?


Nein


Abbildung 5.22: Sind sowohl N als auchdas Komplement N semi-entscheidbar, solässt sich die Menge N entscheiden.


Im Kern dieser Definition steht der Begriff der charakteristischen Funk-tion. Sie ist das formale Bindeglied zwischen dem auf Funktionen aus-gelegten Berechenbarkeitsbegriff und dem für Mengen formuliertenEntscheidbarkeitskriterium.

Abbildung 5.21 demonstriert, wie sich die beiden Entscheidbarkeitsbe-griffe bildlich erfassen lassen. Ist eine Menge N entscheidbar, dann exis-tiert eine algorithmisch arbeitende Maschine, die ein Element ω ∈ Nin codierter Form entgegennimmt und die Frage beantwortet, ob ω zuN gehört oder nicht. In der bildlichen Darstellung werden die beidenmöglichen Antworten durch zwei separate Glühlampen symbolisiert,von denen genau eine nach endlicher Zeit aufleuchtet. Wann eine derLampen zu glühen beginnt, wissen wir nicht. Dennoch können wir unsdarauf verlassen, dass dies sowohl für den Fall ω ∈ N als auch für denFall ω �∈ N irgendwann der Fall sein wird. Um die Mengenzugehörig-keit zu entscheiden, müssen wir uns also lediglich in Geduld üben undlange genug warten.

Im Gegensatz zu einem Entscheider besitzt ein Semi-Entscheider nureine einzige Glühlampe. Wird er mit einem Element ω ∈N gestartet, sobeginnt die Lampe nach endlicher Zeit zu leuchten. Für ω �∈N lässt sichkeine verlässliche Aussage mehr treffen. Hier können wir niemals mitSicherheit sagen, ob sich die Maschine innerhalb einer Endlosschleifebefindet oder zu einem späteren Zeitpunkt doch noch eine positive Ant-wort liefern wird. Damit ist die Semi-Entscheidbarkeit gleichbedeutendmit einer Halbaussage. Die gestellte Frage „Ist ω ∈N?“ wird nur im po-sitiven Fall nach endlicher Zeit beantwortet. Fällt die Antwort negativaus, so zeigt die Maschine keinerlei Reaktion.

Ist eine Menge N entscheidbar, so ist es auch das Komplement N, unddaraus folgt, dass N und N dann erst recht semi-entscheidbar sind. Tat-sächlich gilt auch die Umkehrung: Ist neben N auch das KomplementN semi-entscheidbar, so reicht dies aus, um N zu entscheiden. Abbil-dung 5.22 zeigt auf grafische Weise, wie sich die Semi-Entscheider fürN und N zu einem Entscheider für N kombinieren lassen. Beide Semi-Entscheider werden gleichzeitig mit dem Eingabewort ω versorgt undparallel simuliert. Liegt ω in N, so reagiert der erste Semi-Entscheidernach einer endlichen Zeitspanne; ist ω nicht in N, so reagiert irgend-wann der zweite. In Satzform lautet unser Ergebnis folgendermaßen:

Satz 5.2

Für eine Menge N gilt:

N ist entscheidbar ⇔ N und N sind semi-entscheidbar

� Entscheidbarkeit

Entscheiderfür N

Ja

N

Entscheiderfür N

Nein

N

� Semi-Entscheidbarkeit


Ja

N


N

� Aufzählbarkeit

1, 2, 3, 4, 5, 6, ...

Aufzählerfür N

Abbildung 5.23: Entscheidbarkeit, Semi-Entscheidbarkeit und Aufzählbarkeit imVergleich


In derselben Weise wollen wir einen weiteren Begriff formal zementie-ren, den wir bereits des öfteren informell verwendet haben. Die Redeist von der Aufzählbarkeit von Mengen. Genau wie im Falle der Ent-scheidbarkeit können wir auch diesen Begriff auf die Berechenbarkeiteiner Funktion zurückführen:

Definition 5.7 (Aufzählbarkeit)

Eine Menge N heißt aufzählbar, wenn sie die leere Menge ist odereine surjektive und berechenbare Funktion f : N→ N existiert.

Aus dieser Definition geht erst auf den zweiten Blick hervor, dass hierjenes Konzept beschrieben wird, das die meisten von uns intuitiv mitdem Begriff der Aufzählbarkeit verbinden. Sehen wir also genauer hin!Ist eine Menge N aufzählbar, so existiert per Definition eine Turing-Maschine M, die unter der Eingabe einer natürlichen Zahl x den Funk-tionswert f (x) berechnet. M versetzt uns in die Lage, die Werte

f (0), f (1), f (2), f (3), . . .

nacheinander zu berechnen. Auf diese Weise entsteht eine immer län-ger werdende Liste von Elementen aus N. Wir wissen aber noch mehr.Da f per Definition surjektiv ist, wird jedes Element ω ∈N irgendwannin unserer Aufzählung erscheinen. Als Ergebnis erhalten wir eine algo-rithmisch arbeitende Maschine, die alle Elemente von N nacheinanderaufsagt (Abbildung 5.23). Beachten Sie, dass wir lediglich die Surjek-tivität und nicht die Bijektivität von f gefordert haben. Damit ist esexplizit erlaubt, dass die Elemente von N in der generierten Aufzählungmehrfach vorkommen dürfen.

Wir wollen versuchen, zwischen der Aufzählbarkeit, der Abzählbar-keit und der Semi-Entscheidbarkeit einen Zusammenhang herzustellen.Ganz offensichtlich ist jede aufzählbare Menge auch abzählbar, da wirjedes ihrer Elemente mit mindestens einer natürlichen Zahl in Bezugsetzen können. Auf der anderen Seite existieren zahlreiche abzählbareMengen N, für die keine Funktion f : N→ N existiert, die gleichzei-tig surjektiv und berechenbar ist. Ein prominentes Beispiel werden wirbald kennen lernen: die Menge aller wahren arithmetischen Formeln.

Zwischen der Aufzählbarkeit und der Semi-Entscheidbarkeit einerMenge besteht ebenfalls eine enge Verwandtschaft. Zunächst ist jedeaufzählbare Menge N auch semi-entscheidbar, schließlich können wiralle Elemente der Reihe nach aufsagen und genau dann stoppen, wennwir das gesuchte Element ω gefunden haben. Ist ω ∈ N, so werden wir

ausgeben

N ?


:= das i-te Element von *

( i , j ) := 1(n)n := n + 1

Abbruch nachj Schritten

n := 0

Ja

Abbildung 5.24: Durch den geschicktenEinsatz der Cantor’schen Paarungsfunktionist es möglich, die Elemente einer semi-entscheidbaren Menge der Reihe nach auf-zuzählen.


das Element nach endlich vielen Schritten antreffen. Ist ω �∈ N, so fah-ren wir für immer fort.

Es gilt sogar die umgekehrte Richtung: Jede semi-entscheidbare MengeN ist aufzählbar. Dies einzusehen, ist alles andere als trivial. Um dieElemente von N aufzuzählen, müssen wir den zur Verfügung stehendenSemi-Entscheider so ansteuern, dass er niemals in eine Endlosschleifegerät. Aber wie kann das gelingen? Zum Erfolg verhilft uns abermalsdie Cantor’sche Paarungsfunktion π , die eine Zuordnung zwischen derMenge aller Tupel (i, j) ∈ N2 und der Menge der natürlichen Zahlenherstellt. Durch geschickten Einsatz dieser Funktion ist es tatsächlichmöglich, die Elemente einer semi-entscheidbaren Menge nacheinanderaufzusagen. Abbildung 5.24 zeigt, wie dies möglich ist:

� In einer unendlichen Schleife werden nacheinander die Elemente

π−1(0),π−1(1),π−1(2),π−1(3), . . . (5.4)

berechnet. Als Ergebnis erhalten wir eine Folge, in der jedes Tupel(i, j) ∈ N2 irgendwann auftaucht.

� Für jedes Tupel (i, j) starten wir den Semi-Entscheider mit dem i-ten Element ω von Σ∗. Stellt er die Mengenzugehörigkeit innerhalbvon j Schritten fest, so gibt er ω aus. Ist der Semi-Entscheider nachj Schritten noch zu keinem Ergebnis gekommen, brechen wir dieBerechnung ab und fahren mit dem nächsten Tupel fort. Da für je-des ω ∈ N ein j ∈ N mit der Eigenschaft existiert, dass der Semi-Entscheider die Mengenzugehörigkeit in j Schritten positiv beant-wortet, werden nacheinander alle Elemente von N erzeugt.

Damit ist es uns gelungen, den folgenden Satz zu beweisen:

Satz 5.3 (Aufzählbarkeit und Semi-Entscheidbarkeit)

Für eine Menge N �= /0 gilt:

N ist aufzählbar ⇔ N ist semi-entscheidbar

Kombinieren wir die Aussagen der Sätze 5.2 und 5.3, so erhalten wirohne weiteres Zutun das folgende Ergebnis:

Korollar 5.1

Für eine Menge N �= /0 gilt:

N ist entscheidbar ⇔ N und N sind aufzählbar


5.3 Grenzen der Berechenbarkeit

In diesem Abschnitt werden wir die algorithmische Methode an ihreGrenzen führen. Wir beginnen unsere Diskussion mit verschiedenen Va-rianten des Halteproblems und werden die gewonnenen Erkenntnisseanschließend mit dem Satz von Rice verallgemeinern.

5.3.1 Das Halteproblem

Als Halteproblem werden mehrere Fragestellungen bezeichnet, die sichmit den Terminierungseigenschaften von Turing-Maschinen beschäfti-gen. Konkret geht es um die Frage, ob auf algorithmischem Wege ent-schieden werden kann, ob eine Turing-Maschine unter gewissen Ein-gaben terminiert oder für immer weiter rechnet. Wir beginnen mit derDefinition des allgemeinen Halteproblems:

Definition 5.8 (Allgemeines Halteproblem)

Das allgemeine Halteproblem lautet wie folgt:

� Gegeben: Turing-Maschine M und Eingabewort ω

� Gefragt: Terminiert M unter Eingabe von ω?

Tabelle 5.1: Ein einfaches Diagonalisie-rungsargument reicht aus, um die Unent-scheidbarkeit des Halteproblems zu be-weisen. In der nebenstehenden Tabellesind alle Eingaben auf der horizontalenAchse und alle Turing-Maschinen auf dervertikalen Achse aufgelistet. Der Tabel-leneintrag in der i-ten Zeile und der j-tenSpalte gibt an, ob die Maschine Mi un-ter Eingabe von ω j hält. Wäre das Hal-teproblem entscheidbar, so ließe sich ei-ne Turing-Maschine konstruieren, die denDiagonaleintrag (i, i) bestimmt und genaudann terminiert, wenn Mi unter Eingabevon ωi nicht hält. Diese Maschine kannnirgends in der Liste auftauchen, im Wi-derspruch zur Tabellenkonstruktion.

: Maschine terminiert: Maschine läuft für immer weiter

ω1 ω2 ω3 ω4 ω5 ω6 ω7 . . .

M1 . . .

M2 . . .

M3 . . .

M4 . . .

M5 . . .

M6 . . .

M7 . . ....

......

......

......

.... . .

„Hält Mi für i?

i

nein ja

Endlosschleife

Halte an

H

Turin

g-M

asch

ine H'

Mi

Abbildung 5.25: Gäbe es eine Turing-Maschine H, die das Halteproblem ent-scheidet, so könnten wir diese zu einer Ma-schine H ′ umbauen, die genau dann fürdas Eingabewort ωi terminiert, wenn dieTuring-Maschine Mi bei Eingabe von ωi un-endlich lange rechnet. Mithilfe des Diago-nalisierungsarguments können wir die Kon-struktion von H ′ als widersprüchlich entlar-ven und daraus schließen, dass die Maschi-ne H nicht existieren kann.

Behalten Sie stets im Auge,dass sich die Gültigkeit vonSatz 5.4 auf jedes Berech-nungsmodell überträgt, das

dieselbe Ausdrucksstärke besitzt wie dieTuring-Maschine. Hierunter fallen die Re-gistermaschine aus Abschnitt 5.1.2 sowiealle besprochenen Varianten der Turing-Maschine aus Abschnitt 5.1.1.1. Dort hat-ten wir mit der einseitig beschränkten Ma-schine, der Mehrspur-Maschine und derMehrband-Maschine drei Erweiterungendes Turing’schen Maschinenmodells ein-geführt, die allesamt die gleiche Aus-drucksstärke besitzen.

5.3 Grenzen der Berechenbarkeit 295

Für den Moment gehen wir davon aus, das Halteproblem sei entscheid-bar. Diese Annahme werden wir jetzt mit einem einfachen Diagonali-sierungsargument, das jenem aus Abschnitt 1.2.2 sehr ähnlich ist, zueinem Widerspruch führen.

Als Erstes konstruieren wir eine Matrix, wie sie in Tabelle 5.1 aus-schnittsweise dargestellt ist. Auf der vertikalen Achse sind alle Turing-Maschinen und auf der horizontalen Achse alle Eingabewörter ver-zeichnet. Die Reihenfolge spielt dabei keine Rolle; wichtig ist nur, dassjede Turing-Maschine und jedes Eingabewort auch wirklich in irgend-einer Zeile oder Spalte erscheinen. Die einzelnen Felder der Matrix ge-ben uns Auskunft über das Terminierungsverhalten unserer Maschinen.Hierzu ist in der i-ten Zeile und der j-ten Spalte verzeichnet, ob dieTuring-Maschine Mi unter Eingabe von ω j terminiert.

Wäre das Halteproblem entscheidbar, so würde eine Turing-MaschineH existieren, die ein Eingabewort ω und eine Turing-Maschine M in co-dierter Form entgegennimmt und stets korrekt bestimmt, ob M bei Ein-gabe von ω terminiert. Die fiktive Turing-Maschine H ist nichts ande-res als eine Maschine zur Berechnung der soeben konstruierten Matrix.Wie es in Abbildung 5.25 skizziert ist, können wir aus H eine zweiteMaschine H ′ konstruieren. Diese berechnet für das Eingabewort ωi dasMatrixelement (i, i) und verhält sich reziprok zu der erhaltenen Ant-wort. H ′ terminiert bei Eingabe von ωi genau dann, wenn Mi für immerweiter rechnen würde.

Da H ′ selbst eine Turing-Maschine ist, müssen wir sie in einer bestimm-ten Zeile der konstruierten Matrix wiederfinden können; der Aufbau derMatrix garantiert ja gerade, dass alle Maschinen der Reihe nach aufge-zählt werden. Doch egal, in welcher Zeile wir auch nachschauen: DieDiagonalkonstruktion führt immer einen Widerspruch herbei. Für allei ∈ N gilt H ′ �= Mi, da Mi die Eingabe ωi genau dann akzeptiert, wennsie von H ′ abgelehnt wird. Der Widerspruch macht deutlich, dass wirdie Annahme über die Existenz von H fallen lassen müssen und es keineMaschine geben kann, die das Halteproblem entscheidet.

Satz 5.4

Das allgemeine Halteproblem ist unentscheidbar.

Ein einfaches Diagonalisierungsargument hat ausgereicht, um eines derwichtigsten Ergebnisse der Berechenbarkeitstheorie zu beweisen. Wiebedeutend Satz 5.4 tatsächlich ist, werden die folgenden Betrachtungenjetzt nach und nach zum Vorschein bringen.

NeinJa

"Schreibe auf das Eingabeband und

simuliere M."

Hält M ?

Entscheider für dasHalteproblem auf

leerem Band

Ents

chei

der f

ür d

as a

llgem

eine

Hal

tepr

oble

m

, M

Konstruiere aus und M eine

neue Turing-Maschine M .

M

Abbildung 5.26: Reduktion des allgemei-nen Halteproblems auf das Halteproblemauf leerem Band. Wären wir in der Lage,das Halteproblem auf leerem Band zu lö-sen, so könnten wir einen Entscheider fürdas allgemeine Halteproblem konstruieren.Aus der Unentscheidbarkeit des allgemei-nen Halteproblems folgt unmittelbar, dassauch das Halteproblem auf leerem Bandnicht entschieden werden kann.


Halteproblem auf leerem Band

Neben dem allgemeinen Halteproblem existiert eine abgeschwächte Va-riante, die wie folgt definiert ist:

Definition 5.9 (Halteproblem auf leerem Band)

Das Halteproblem auf leerem Band lautet wie folgt:

� Gegeben: Turing-Maschine M

� Gefragt: Terminiert M unter Eingabe des leeren Worts ε?

Während das allgemeine Halteproblem fordert, dass wir die Terminie-rungseigenschaft für beliebige Turing-Maschinen und beliebige Einga-ben entscheiden können, betrachtet das spezielle Halteproblem nur denFall, dass die Berechnung auf einem leeren Band gestartet wird. Formalist die Eingabe dann das leere Wort, das gewöhnlich mit ε bezeichnetwird.

Das spezielle Halteproblem ist augenscheinlich einfacher zu lösen alsdas allgemeine. Dennoch lässt sich mit einem einfachen Reduktions-beweis zeigen, dass auch dieses Problem unentscheidbar ist. In einemsolchen Beweis wird gezeigt, dass aus der Entscheidbarkeit des Halte-problems auf leerem Band die Entscheidbarkeit des allgemeinen Halte-problems folgen würde. Wir sagen, das allgemeine Halteproblem wirdauf das Halteproblem auf leerem Band reduziert. Wie eine solche Re-duktion in unserem speziellen Fall durchgeführt werden kann, zeigt Ab-bildung 5.26.

Um zu entscheiden, ob eine Turing-Maschine für ein Eingabewort ωhält, wird zunächst eine Turing-Maschine Mω konstruiert, die alle Zei-chen von ω auf das Band schreibt und anschließend M simuliert. Mωwird mit einem leeren Band gestartet und terminiert genau dann, wenndie Originalmaschine M mit der Eingabe ω terminiert. Gäbe es alsoeine Turing-Maschine, die das Halteproblem auf leerem Band entschei-det, so wären wir auch in der Lage, das allgemeine Halteproblem zuentscheiden. Aus Satz 5.4 folgt jetzt sofort, dass auch das spezielle Hal-teproblem unentscheidbar sein muss.

Satz 5.5

Das Halteproblem auf leerem Band ist unentscheidbar.

� Erster Fall: M⊥ erfüllt E

M

ME

M terminiert

f ( )

Turin

g-M

asch

ine

H

� Zweiter Fall: M⊥ erfüllt E nicht

M

ME

M terminiert

f ( ) Tu

ring-

Mas

chin

e H

Abbildung 5.27: Kernstück des Beweisesfür den Satz von Rice. Über die dargestell-te Zusammenschaltung wird ein direkterZusammenhang zwischen der untersuchtenMaschineneigenschaft E und dem Halte-problem hergestellt.

5.3 Grenzen der Berechenbarkeit 297

5.3.2 Der Satz von Rice

Die Unentscheidbarkeit des Halteproblems hat uns gezeigt, dass Aus-sagen über Turing-Maschinen existieren, die sich einer maschinellenBeweisbarkeit entziehen. Kein algorithmisches Verfahren ist in der La-ge, die Terminierungseigenschaft für alle Turing-Maschinen Mi und al-le Eingabewörter ω j stets korrekt vorherzusagen. Durch eine geeigneteReduktion waren wir darüber hinaus in der Lage, auch das Haltepro-blem auf leerem Band als unentscheidbar zu identifizieren. In diesemAbschnitt wollen wir uns mit der Frage beschäftigen, ob noch weite-re Aussagen über Turing-Maschinen existieren, die nicht algorithmischentschieden werden können. So viel vorweg: Wir werden eine verblüf-fende Antwort erhalten.

Im Folgenden bezeichnet M eine beliebige Turing-Maschine, fM dievon M berechnete Funktion und E eine funktionale Eigenschaft von M(also eine Eigenschaft von fM). E soll nichttrivial sein, d. h., es gibtmindestens eine Maschine, die die untersuchte Eigenschaft besitzt, undmindestens eine Maschine, die sie nicht besitzt. Die folgende Aufzäh-lung enthält eine exemplarische Auswahl möglicher Eigenschaften. DerPhantasie sind an dieser Stelle keine Grenzen gesetzt:

� Es gibt eine Ausgabe von M, die das Symbol 0 enthält.

� Alle Ausgaben von M sind mindestens n Zeichen lang.

� M berechnet eine totale Funktion.

Wir wollen ausloten, welche Konsequenzen sich aus der Existenz einesEntscheidungsverfahrens für E ergeben. Hierzu führen wir zunächst dieTuring-Maschine M⊥ ein, die die überall undefinierte Funktion f (ω) =⊥ berechnet. M⊥ lässt sich sehr simpel konstruieren: Sie terminiert fürkeine Eingabe.

Für den Moment wollen wir annehmen, dass M⊥ die gewählte Eigen-schaft E erfüllt. Da E nichttrivial ist, existiert mindestens eine weitereMaschine ME , die E nicht erfüllt. Wir fassen zusammen:

M⊥ erfüllt die Eigenschaft E (5.5)ME erfüllt die Eigenschaft E nicht (5.6)

Die Maschinen M und ME vereinen wir nun zu einer gemeinsamen Ma-schine H. Wie der obere Teil von Abbildung 5.27 zeigt, wird innerhalbvon H zunächst die Maschine M mit dem leeren Eingabewort ε ge-startet. Hält diese nach endlich vielen Schritten an, so wendet H dieMaschine ME auf das Eingabewort ω an.

Die Tragweite des Satzesvon Rice ist enorm! In ei-nem Rundumschlag machter die Hoffnung zunichte, ir-gendeine nichttriviale funktionale Eigen-schaft über Turing-Maschinen algorith-misch entscheiden zu können. Die Gren-zen, die uns dieser Satz auferlegt, rei-chen tief in die Praxis der realen Software-Entwicklung hinein. So folgt daraus un-mittelbar, dass es keinen Algorithmus ge-ben kann, der für ein beliebiges Programmmaschinell verifiziert, ob es sich entspre-chend seiner Spezifikation verhält. Selbstso einfache Probleme wie die Frage nachder Existenz von Endlosschleifen entzie-hen sich einer algorithmischen Lösung.Seine Allgemeinheit macht den Satz vonRice zu einer der wertvollsten Aussagender Berechenbarkeitstheorie.


Um das Verhalten von H zu verstehen, unterscheiden wir zwei Fälle:

� M terminiert nicht: In diesem Fall ist H funktional identisch mit M⊥und erfüllt die Eigenschaft E.

� M terminiert: In diesem Fall ist H funktional identisch mit ME underfüllt die Eigenschaft E nicht.

Mit dieser Konstruktion ist es uns gelungen, einen direkten Zusammen-hang zwischen der Eigenschaft E und der Terminierung von M herzu-stellen. Würde ein Verfahren existieren, das E entscheidet, so könntenwir das Halteproblem für jede beliebige Maschine M lösen. Kurzum:Wir hätten ein Entscheidungsverfahren für das Halteproblem gefunden.

Beachten Sie, dass die obige Überlegung stets unter der Annahme stand,dass die gewählte Eigenschaft E auf M⊥ zutrifft. Sollte dies nicht derFall sein, so modifizieren wir die Maschine H wie in der unteren Hälftevon Abbildung 5.27 gezeigt. Anstelle von ME starten wir eine beliebigeMaschine ME , die E erfüllt. Die Fallunterscheidung liest sich jetzt wiefolgt:

� M terminiert nicht: In diesem Fall ist H funktional identisch mit M⊥und erfüllt die Eigenschaft E nicht.

� M terminiert: In diesem Fall ist H funktional identisch mit ME underfüllt die Eigenschaft E.

Wiederum ist es uns gelungen, einen Eins-zu-eins-Zusammenhang zwi-schen E und der Terminierung von M herzustellen. Gäbe es ein Ent-scheidungsverfahren für die Eigenschaft E, so könnten wir das Halte-problem ebenfalls lösen.

Die Unentscheidbarkeit des Halteproblems führt damit unweigerlich zuder Erkenntnis, dass ein Entscheidungsverfahren für E nicht existierenkann. Genau dies ist die Aussage des berühmten Satzes von Henry Gor-don Rice aus dem Jahr 1953.

Satz 5.6 (Satz von Rice)

Sei E sei eine nichttriviale funktionale Eigenschaft von Turing-Maschinen. Dann ist das folgende Problem unentscheidbar:

� Gegeben: Turing-Maschine M

� Gefragt: Besitzt M die Eigenschaft E?

Turing, 1936

NeinJa Hält M auf

leerem Band?

Prädikatenlogische Formel

Turing-maschineM

Reduktion

NeinJa Hält M auf

leerem Band?

Reduktion

Arithmetische Formel

Turing-maschineM

Abbildung 5.28: Gäbe es ein Entschei-dungsverfahren für die Prädikatenlogik er-ster Stufe (oben) oder einen korrektenund zugleich vollständigen Kalkül für diePeano-Arithmetik (unten), so ließe sich da-mit das Halteproblem entscheiden.

5.4 Folgen für die Mathematik 299

5.4 Folgen für die Mathematik

Zu Beginn dieses Kapitels haben wir den hohen Stellenwert der Bere-chenbarkeitstheorie unter anderem damit begründet, dass die Erkennt-nisse auf diesem Gebiet tief in die Mathematik hineinwirken. Wie eng-maschig die Berechenbarkeitstheorie auf der einen und die Beweistheo-rie auf der anderen Seite tatsächlich miteinander verwoben sind, werdenwir in diesem Abschnitt am Beispiel von drei prominenten Negativre-sultaten demonstrieren. Es sind dies keine Geringeren als

� die Unlösbarkeit des Hilbert’schen Entscheidungsproblems,

� die Unvollständigkeit der Arithmetik und

� die Unlösbarkeit des zehnten Hilbert’schen Problems.

Alle drei Negativresultate werden wir durch die Reduktion des Halte-problems beweisen. Konkret werden wir zeigen, dass sich die Lösungfür eines der drei Probleme dazu verwenden lässt, um die Terminierungvon Turing-Maschinen oder Registermaschinen zu entscheiden (Abbil-dungen 5.28 und 5.29). Wäre auch nur eines der drei Probleme lösbar,so wäre es auch das Halteproblem. Wir wissen aber bereits aus Ab-schnitt 5.3.1, dass das Halteproblem unentscheidbar ist.

Um den Blick auf das Große und Ganze zu wahren, wollen wir zunächstalle drei Reduktionen grob skizzieren. Im Anschluss daran liefern wirdie technischen Details in separaten Unterabschnitten nach.

� Unlösbarkeit des Hilbert’schen Entscheidungsproblems

In Abschnitt 5.4.1 werden wir demonstrieren, dass sich das Halte-problem auf leerem Band mithilfe eines Entscheidungsverfahrensfür die Prädikatenlogik erster Stufe lösen lässt. Im Kern des Bewei-ses steht die Idee, eine einseitig beschränkte Turing-Maschine M ineine prädikatenlogische Formel ϕM mit der folgenden Eigenschaftzu übersetzen:

M terminiert ⇔ ϕM ist allgemeingültig

Über die so hergestellte Beziehung lässt sich die Frage nach der Ter-minierung einer einseitig beschränkten Turing-Maschine mithilfe ei-nes prädikatenlogischen Entscheidungsverfahrens beantworten. Ausder Unentscheidbarkeit des Halteproblems können wir dann schlie-ßen, dass kein Entscheidungsverfahren für die Prädikatenlogik exis-tieren kann.

Entscheidungsverfahren für die Prädikatenlogik

erster Stufe

Korrekter und vollständiger Kalkül für die Peano-Arithmetik

NeinJa Hält R unter

Eingabe von x?

Jones, Matijasevi

1984Diophantische Gleichung

Register-maschine

R

Reduktion

Abbildung 5.29: Ein Lösungsverfahren fürdiophantische Gleichungen könnten wirverwenden, um das Halteproblem für Regi-stermaschinen zu entscheiden.


� Unvollständigkeit der Arithmetik

In Abschnitt 5.4.2 werden wir zeigen, dass sich das Halteproblemauf leeren Band auch mit einem Entscheidungsverfahren für diePeano-Arithmetik lösen lässt. Die Beweisidee ist wiederum die glei-che. Wir werden zeigen, dass sich eine Turing-Maschine M in einearithmetische Formel ϕM übersetzen lässt, für die gilt:

ϕM ist wahr ⇔ M terminiert

Über diese Beziehung können wir die Frage nach der Terminierungeiner Turing-Maschine mit einem Entscheidungsverfahren für PAbeantworten und daraus schließen, dass ein solches Verfahren nichtexistieren kann. In Kombination mit Satz 2.5 erhalten wir ein er-staunliches Ergebnis als Nebenprodukt frei Haus: die semantischeVariante des ersten Gödel’schen Unvollständigkeitssatzes.

� Unlösbarkeit des zehnten Hilbert’schen Problems

In Abschnitt 5.4.3 werden wir demonstrieren, dass sich das Halte-problem auch mit einem Entscheidungsverfahren für diophantischeGleichungen lösen lässt. Dieses Mal werden wir den Beweis abernicht mithilfe von Turing-Maschinen führen. Stattdessen werden wirzeigen, wie sich eine Registermaschine in eine diophantische Glei-chung ϕR = 0 mit der folgenden Eigenschaft übersetzen lässt:

ϕR = 0 hat eine Lösung ⇔ R terminiert

Über die so hergestellte Beziehung können wir die Frage nach derTerminierung einer Registermaschine mithilfe eines Lösungsverfah-rens für diophantische Gleichungen beantworten. Wiederum folgtaus der Unentscheidbarkeit des Halteproblems sofort, dass kein Lö-sungsverfahren für diophantische Gleichungen existieren kann.

Die Marschroute ist damit vorgezeichnet, und wir können uns ruhigenGewissens den Einzelheiten widmen. Für das Verständnis der weiterenKapitel werden die Details nicht benötigt, und es ist gefahrlos, sie beimersten Lesen zu überspringen.

5.4.1 Unentscheidbarkeit der PL1

In diesem Abschnitt werden wir herausarbeiten, wie sich eine einsei-tig beschränkte Turing-Maschine M in eine prädikatenlogische Formelübersetzen lässt, die genau dann allgemeingültig ist, wenn M unter Ein-gabe eines leeren Bands terminiert. Die Konstruktion dieser Formel ist

für diophantische Gleichungen

Lösungsverfahren

RS0(t,0)

RS2(t,1)

RS0(t,2)

RS0(t,3)

S2 ...1 2 30

I(t,0)

Kq2(t)

q2

Abbildung 5.30: In seiner Arbeit aus demJahr 1936 führte Turing mehrere Prädi-kate ein, mit denen sich die Konfigura-tionen von einseitig beschränkten Turing-Maschinen beschreiben lassen.


ein Schlüsselelement in Turings historischem Beweis und wird ausführ-lich in §11 seiner Arbeit beschrieben [195]. Auf den nächsten Seitenwerden wir den Kern seines Gedankengangs offenlegen.

Turing beginnt mit der Definition mehrere Prädikate, mit denen sichdie Konfigurationen von einseitig beschränkten Turing-Maschinen be-schreiben lassen (Abbildung 5.30):

I(t,y) : Zum Zeitpunkt t steht der Kopf über der Zelle y

RSj(t,y) : Zum Zeitpunkt t enthält die Zelle y das Symbol S j

Kqi(t) : Zum Zeitpunkt t ist die Maschine im Zustand qi

F(x,y) : x,y sind natürliche Zahlen mit y = x+1

Die angegebene Bedeutung der Prädikate ist deren intendierte Bedeu-tung. Damit die nachfolgende Konstruktion funktioniert, müssen wir si-cherstellen, dass die Symbole I, RSj , Kqi und F nur in dem gewünschtenSinne interpretiert werden können. Wie dies geschehen kann, werdenwir weiter unten diskutieren. Für den Moment gehen wir einfach davonaus, dass die Prädikate die gewünschte Bedeutung besitzen.

Unter den getroffenen Annahmen sind wir in der Lage, jede Instruk-tion in eine prädikatenlogische Formel ‚Inst‘ zu übersetzen, die denÜbergang von einer Konfiguration zur nächsten beschreibt. Als erstesbetrachten wir eine Instruktion der Form (qi,S j,Sk,L,ql). Der Konfigu-rationsübergang, der durch diese Instruktion ausgelöst wird, lässt sichwie folgt charakterisieren:

� Wenn in der Konfiguration zum Zeitpunkt t...

• die Zelle y das Zeichen S j enthält RSj(t,y)

• und der Schreib-Lese-Kopf über der Zelle y steht I(t,y)

• und sich die Maschine im Zustand qi befindet, Kqi(t)

� dann ist in der Konfiguration zum Zeitpunkt t +1...

• der Schreib-Lese-Kopf nach links gerückt I(t +1,y−1)

• und das Zeichen S j durch Sk ersetzt RSk(t +1,y)

• und der Folgezustand ql eingenommen. Kql(t +1)

Kombinieren wir die Teilformeln miteinander, so erhalten wir das fol-gende Zwischenergebnis:

∀ t ∀y ((RSj(t,y)∧ I(t,y)∧Kqi(t))

→ (I(t+1,y−1)∧RSk(t+1,y)∧Kql(t+1))) (5.7)

Die Formel (5.10) unterschei-det sich in zwei Punkten vonTurings eigener Formulierung. Zum einenwurde die in der Originalarbeit verwende-te Variable x in t umbenannt, um ihre in-haltliche Bedeutung hervorzuheben. t be-zeichnet einen Zeitpunkt – den t-ten Be-rechnungsschritt – und y eine Zellennum-mer. Zum anderen ist Turing in der letztenFormelzeile ein gravierender Fehler unter-laufen. Im Original lautet sie folgender-maßen:

∀z (F(y′,z)∨ (RSj(x,z)→ RSk(x′,z)))

Sinn ergibt diese Formel nicht, und siewurde von Turing auch schnell verbes-sert. Ein Jahr nach dem Erscheinen seinerOriginalarbeit publizierte er mehrere Kor-rekturen in einem Artikel mit dem Titel„On Computable Numbers, with an Ap-plication to the Entscheidungsproblem. ACorrection“ [196]. Dort hat er seine ur-sprüngliche Formel korrigiert und bis aufeinen vergessenen Allquantor in die kor-rekte Form gebracht.


Einen wichtigen Aspekt haben wir noch vergessen. Wir müssen sicher-stellen, dass der Bandinhalt an allen Stellen unverändert bleibt, überdenen sich der Schreib-Lese-Kopf nicht befindet:

∀z (z �= y→M∧

i=0

(RSi(t,z)→ RSi(t+1,z))) (5.8)

Die Formeln (5.7) und (5.8) fügen wir jetzt konjunktiv zusammen:

∀ t ∀y ((RSj(t,y)∧ I(t,y)∧Kqi(t))

→ (I(t+1,y−1)∧RSk(t+1,y)∧Kql(t+1)

∧ ∀z (z �= y→M∧

i=0

(RSi(t,z)→ RSi(t+1,z))))) (5.9)

Diese Formel ist noch keine Formel der Prädikatenlogik, da wir mit‚+‘ ein Funktionszeichen und mit ‚�=‘ ein Prädikatzeichen verwendethaben, das uns in der PL1 gar nicht zur Verfügung steht. Über das Prä-dikat F(x,y) können wir die Ausdrücke t+1, y−1 und z �= y aber ganzeinfach eliminieren:

Inst(qi,S j,Sk,L,ql) :=

∀ t ∀y ∀ t′ ∀y′ ((RSj(t,y)∧ I(t,y)∧Kqi(t)∧F(t, t′)∧F(y′,y))

→ (I(t′,y′)∧RSk(t′,y)∧Kql(t

′)

∧ ∀z (F(y′,z) ∨M∧

i=0

(RSi(t,z)→ RSi(t′,z))))) (5.10)

Jetzt ist klar, wie sich die anderen Instruktionstypen in eine prädika-tenlogische Formeln übersetzen lassen. Hierzu brauchen wir (5.10) nurgeringfügig umzuschreiben:

Inst(qi,S j,Sk,R,ql) :=

∀ t ∀y ∀ t′ ∀y′ ((RSj(t,y)∧ I(t,y)∧Kqi(t)∧F(t, t′)∧F(y,y′))

→ (I(t′,y′)∧RSk(t′,y)∧Kql(t

′)

∧ ∀z (F(z,y′) ∨M∧

i=0

(RSi(t,z)→ RSi(t′,z))))) (5.11)


Inst(qi,S j,Sk,N,ql) :=

∀ t ∀y ∀ t′ ∀y′ ((RSj(t,y)∧ I(t,y)∧Kqi(t)∧F(t, t′)∧F(y′,y))

→ (I(t′,y)∧RSk(t′,y)∧Kql(t

′)

∧ ∀z (F(y′,z) ∨M∧

i=0

(RSi(t,z)→ RSi(t′,z))))) (5.12)

Indem wir alle Instruktionen einer Turing-Maschine M auf die gezeigteWeise in Formeln übersetzen und diese anschließend konjunktiv mit-einander verknüpfen, können wir den kompletten Instruktionssatz vonM in eine einzige Formel hineincodieren. Für unsere Beispielmaschineaus Abbildung 5.1 sieht diese Formel folgendermaßen aus:

Des(M) = Inst(q1,S0,S1,R,q2) ∧ Inst(q2,S0,S0,R,q3) ∧Inst(q3,S0,S2,R,q4) ∧ Inst(q4,S0,S0,R,q1)

Die Bezeichnung Des(M) stammt von Turing und ist die Abkürzungfür „description of M“. Ausgeschrieben ergibt die Formel ein wahresMonstrum:

∀ t ∀y ∀ t′ ∀y′ ((RS0(t,y)∧ I(t,y)∧Kq1(t)∧F(t, t′)∧F(y,y′))→ (I(t′,y′)∧RS1(t

′,y)∧Kq2(t′)

∧ ∀z (F(z,y′)∨ ((RS0(t,z)→ RS0(t′,z)) ∧

(RS1(t,z)→ RS1(t′,z))∧ (RS2(t,z)→ RS2(t

′,z)))))) ∧∀ t ∀y ∀ t′ ∀y′ ((RS0(t,y)∧ I(t,y)∧Kq2(t)∧F(t, t′)∧F(y,y′))→ (I(t′,y′)∧RS0(t

′,y)∧Kq3(t′)

∧ ∀z (F(z,y′)∨ ((RS0(t,z)→ RS0(t′,z)) ∧



′,y)∧Kq4(t′)

∧ ∀z (F(z,y′)∨ ((RS0(t,z)→ RS0(t′,z)) ∧



′,y)∧Kq1(t′)

∧ ∀z (F(z,y′)∨ ((RS0(t,z)→ RS0(t′,z)) ∧


′,z))))))


Des(M) beschreibt den Übergang von einer Konfiguration in die nächs-te, sagt aber nichts darüber aus, in welcher Konfiguration die Maschinestartet.

Per Definition hatten wir vereinbart, dass zum Zeitpunkt 0

� der Schreib-Lese-Kopf über der Zelle 0 steht, I(0,0)

� der Startzustand q1 eingenommen ist und Kq1(0)

� ein leeres Band vorliegt. ∀y RS0(0,y)

Damit können wir das Gesamtverhalten von M folgendermaßen be-schreiben:

I(0,0)∧Kq1(0)∧∀y RS0(0,y)∧Des(M) (5.13)

Um diese Formel zu einer echten prädikatenlogischen Formel zu ma-chen, muss die 0 eliminiert werden. Turing nutzte aus, dass es keineRolle spielt, ob sich die Maschine zum Zeitpunkt 0 oder zu einem spä-teren Zeitpunkt u in dieser Konfiguration befindet. Damit lässt sich dasProblem lösen, indem die 0 durch ein existenziell quantifiziertes Kon-stantensymbol u ersetzt wird. Formel (5.13) wird dann zu

A(M) := ∃u (I(u,u)∧Kq1(u)∧∀y RS0(u,y))∧Des(M)

Zu guter Letzt wollen wir die Terminierung von M mithilfe einer For-mel Halt(M) beschreiben. Um den Aufbau dieser Formel zu verstehen,erinnern wir uns daran, dass eine Turing-Maschine genau dann wei-ter rechnet, wenn eine Instruktion angewendet werden kann. Betrachtenwir eine Instruktion der Gestalt (qi,S j,_,_), so ist sie genau dann an-wendbar, wenn

� sich die Maschine im Zustand qi befindet und Kqi(t)

� in der aktuell adressierten Zelle y I(t,y)

� das Bandzeichen S j gespeichert ist. RSj(t,y)

Damit können wir das Weiterrechnen einer Maschine mit einer FormelCont(M, t) beschreiben, indem wir für jede Instruktion (qi,S j,_,_) dieTeilformel

∃y (Kqi(t)∧ I(t,y)∧RSj(t,y))

In Turings historischer Arbeitaus dem Jahr 1936 werden

Sie die Definition der Formel Halt(M)nicht finden, genauso wenig wie das WortHalteproblem. In seinem ursprünglichenBeweis hatte Turing nämlich gar nicht dasHalteproblem reduziert, sondern gezeigt,dass sich mit einem Entscheidungsver-fahren für die Prädikatenlogik erster Stu-fe bestimmen lässt, ob eine Maschine ir-gendwann das Symbol S1 auf das Bandschreibt. Folgen wir dem Turing’schenWeg, so erhalten wir eine Formel, die so-gar noch einfacher ist als die hier konstru-ierte. Anstatt der vergleichsweise kompli-zierten Formel Halt(M) enthält sie denviel simpleren Ausdruck

∃t ∃y RS1(t,y)

Diese Formel besagt, dass die betrachte-te Maschine irgendwann eine Konfigura-tion erreicht, in der eine Zelle y das Band-symbol S1 enthält. Kurzum: Die Maschineschreibt irgendwann das Symbol S1.Genau wie das Halteproblem, ist auch dasProblem, ob eine Turing-Maschine ein be-stimmtes Symbol auf das Band schreibt,unentscheidbar; beide Formeln erfüllenalso den gleichen Zweck.


bilden und anschließend alle Teilformeln disjunktiv miteinander ver-knüpfen. Für unsere Beispielmaschine erhalten wir:

Cont(M, t) = ∃y (Kq1(t)∧ I(t,y)∧RS0(t,y))︸︷︷︸Instruktion (q1,S0,S1,R,q2)

∨

∃y (Kq2(t)∧ I(t,y)∧RS0(t,y))︸︷︷︸Instruktion (q2,S0,S0,R,q3)

∨


∨


Mithilfe der so erzeugten Formel können wir die Terminierung einerTuring-Maschine jetzt ohne Umwege beschreiben:

Halt(M) := ∃ t ¬Cont(M, t)

In Worten besagt die Formel, dass die Maschine irgendwann eine Kon-figuration erreicht, in der kein Weiterkommen mehr möglich ist.

Kombinieren wir die Teilformeln A(M) und Halt(M) zu

Un(M) := A(M)→ Halt(M)

so erhalten wir eine Formel mit der folgenden inhaltlichen Aussage:

„M terminiert auf leerem Band.“

Einen wichtigen Punkt dürfen wir an dieser Stelle nicht übergehen. DieFormel Un(M) steht nur dann für diese Aussage, wenn wir die ver-wendeten Prädikate entsprechend ihrer intendierten Bedeutung inter-pretieren. Bezeichnen wir diese Interpretation mit (U, I) so können wirden Zusammenhang zwischen Un(M) und der Terminierung von M wiefolgt präzisieren:

M terminiert ⇔ (U, I) |= Un(M)

Um das Hilbert’sche Entscheidungsproblem negativ zu beantworten,brauchen wir aber eine Formel, die genau dann allgemeingültig ist,wenn die Maschine M terminiert:

M terminiert ⇔ |= Un(M) (5.14)

Wir wollen uns nun mit der Frage beschäftigen, ob unsere FormelUn(M) diese Eigenschaft erfüllt. Die Richtung von rechts nach links

� G(z,x)xz ...

z < x

� ∨(G(x,y)∧F(y,z))x y z...

x < y∧ y+1 = z

� ∨(F(x,y)∧F(z,y))yx, z

x+1 = y∧ z+1 = y

⎫⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭

⇒¬F(x,z)x+1 �= z

Abbildung 5.31: Die Formel Q stellt un-ter anderem sicher, dass die Prädikate F undG die dargestellten Ordnungseigenschaftenerfüllen.

Die Formel Q werden Siein Turings Originalarbeit ausdem Jahr 1936 nicht finden. Dort hatteer noch versucht, die intendierte Bedeu-tung des Prädikatzeichens F folgenderma-ßen zu beschreiben:

N(u)∧∀x (N(x)→∃x′ F(x,x′)) ∧∀y ∀z (F(y,z)→ N(y)∧N(z))

In Turings Formel drückt N(ξ ) aus, dassdie Variable ξ einer natürlichen Zahl ent-spricht. Unter dieser Interpretation besagtder erste Formelbestandteil, dass u ∈ N

ist, der Mittelteil postuliert, dass jede Zahleinen Nachfolger hat, und der letzte For-melbestandteil drückt aus, dass aus y +1 = z stets y,z ∈ N folgt.Turing übersah, dass seine Formel nichtgarantiert, dass eine Zahl x einen eindeuti-gen Nachfolger besitzt. In seinem Beweisgreift er auf diese Eigenschaft aber expli-zit zurück. In den 1937 publizierten Kor-rekturen hat Turing den Fehler behobenund die Formel Q als Ersatz für den obengenannten Ausdruck eingeführt.


ist einfach. Ist Un(M) allgemeingültig, gilt also |= Un(M), so ist dieFormel unter jeder Interpretation wahr und damit auch unter jener In-terpretation, die alle verwendeten Prädikatzeichen mit ihrer intendier-ten Bedeutung versieht. Dann besagt die Formel Un(M) genau das Ge-wünschte: M wird irgendwann eine Konfiguration erreichen, in der keinWeiterkommen mehr möglich ist. Kurzum: M terminiert.

Gilt vielleicht sogar die Richtung von links nach rechts? Die Antwort istNein! Da wir die Allgemeingültigkeit einer Formel betrachten, müssenwir jetzt auch solche Interpretationen in Betracht ziehen, in denen dieverwendeten Prädikate ihre intendierte Bedeutung verlieren. Beispiels-weise sind wir bisher ohne Begründung davon ausgegangen, dass F(x,y)die Beziehung y = x+ 1 ausdrückt. Werden die Symbole mit einer an-deren Bedeutung versehen, dann kann Un(M) durchaus falsch sein,die Turing-Maschine M aber dennoch terminieren. Um die Beziehung(5.14) in beiden Richtungen sicherzustellen, müssen wir Un(M) um ei-ne Teilformel ergänzen, die F in seine intendierte Bedeutung zwingt.Genau dies leistet Turings Formel Q, die er in [196] folgendermaßenangibt:

Q = ∀x ∃w ∀y ∀z (F(x,w)∧ (F(x,y)→ G(x,y)) ∧(F(x,z)∧G(z,y)→ G(x,y)) ∧(G(z,x)∨ (G(x,y)∧F(y,z))∨ (F(x,y)∧F(z,y))→¬F(x,z)))

Mit G hat Turing ein neues Prädikatsymbol mit der folgenden intendier-ten Bedeutung eingeführt:

G(x,y) : x,y sind ganze Zahlen, und x ist kleiner als y

Die einzelnen Formelbestandteile von Q besagen dann das Folgende:

� Jede Zahl hat einen NachfolgerF(x,w)

� x+1 ist größer als xF(x,y)→ G(x,y)

� Ist x+1 < y, dann ist auch x < yF(x,z)∧G(z,y)→ G(x,y)

� F und G erfüllen die Ordnungseigenschaften aus Abbildung 5.31G(z,x)∨ (G(x,y)∧F(y,z))∨ (F(x,y)∧F(z,y))→¬F(x,z)

In seinen 1937 publizierten Korrekturen hat Turing gezeigt, dass dieFormel Q die intendierte Bedeutung unserer Prädikate tatsächlich hin-reichend beschreibt. Damit erhalten wir mit

(A(M)∧Q)→ Halt(M) (5.15)


die Formel, nach der wir gesucht haben; sie ist genau dann allgemein-gültig, wenn die beschriebene Turing-Maschine M auf leerem Band ter-miniert.

Den finalen Schluss in Turings Beweis haben wir weiter oben bereitsvorweggenommen. Gäbe es tatsächlich ein Entscheidungsverfahren fürdie Prädikatenlogik erster Stufe, so könnten wir damit das Halteproblementscheiden. Um festzustellen, ob eine einseitig beschränkte Turing-Maschine M auf leeren Band terminiert, müssten wir lediglich die For-mel (5.15) konstruieren und anschließend überprüfen, ob sie allgemein-gültig ist oder nicht. Im ersten Fall wüssten wir, dass M terminiert, imzweiten, dass M für immer weiterrechnet. Wir wissen aber bereits, dassdas Halteproblem unentscheidbar ist, und deshalb kann auch für dasHilbert’sche Entscheidungsproblem keine positive Lösung existieren:

Satz 5.7 (Turing, 1936)

Es gibt kein Entscheidungsverfahren für die Prädikatenlogik.

5.4.2 Unvollständigkeit der Arithmetik

In diesem Abschnitt werden wir eine alternative Codierung von Turing-Maschinen diskutieren. Anders als im vorangegangenen Abschnitt wirddas Ergebnis keine gewöhnliche Formel der PL1 mehr sein, sondern ei-ne Formel der Peano-Arithmetik. Konkret werden wir zeigen, wie sicheine Turing-Maschine M in eine arithmetische Formel übersetzen lässt,die genau dann wahr ist, wenn M terminiert. Der Begriff der Allgemein-gültigkeit wird keine Rolle mehr spielen, da wir uns nur noch dafür in-teressieren, ob die konstruierten Formeln unter der Standardinterpretati-on der Peano-Arithmetik wahr oder falsch sind. In dieser Interpretationsind die Grundelemente die natürlichen Zahlen, ‚+‘ entspricht der Ad-dition, ‚×‘ der Multiplikation und ‚s‘ der Nachfolgeroperation.

Die Konstruktion basiert auf der Idee, eine Folge von Konfigurations-übergängen in eine einzige natürliche Zahl hineinzucodieren und überdiese Zahl zu behaupten, dass sie eine terminierende Berechnungsse-quenz beschreibt.

Wir wollen unserem Ziel in mehreren Etappen entgegen gehen und zu-nächst überlegen, wie eine einzelne Konfiguration als natürliche Zahlcodiert werden kann. Im Allgemeinen hat eine Konfiguration die Form

(q, i,s0,s1, . . . ,sn) (5.16)

R0(x) = 0

R1(x) = 2

R2(x) = 0

S2 ......1 2 30

I(x) = 0

K(x) = 1

L(x) = 3

q1

Abbildung 5.32: Beschreibung von Turing-Maschinen-Konfigurationen mit den Funk-tionen I, Rj, K und L


wobei q den aktuellen Zustand, i die Position des Schreib-Lese-Kopfsund s0,s1, . . . ,sn den bis jetzt benutzten Bandabschnitt repräsentiert.Den aktuellen Zustand und die Bandzeichen stellen wir durch natürlicheZahlen dar und verwenden die Zahl n stellvertretend für den Zustand qnoder das Bandzeichen Sn. Somit können wir alle Komponenten einerKonfiguration ausnahmslos als natürliche Zahlen auffassen.

Um über die Komponenten einer Konfiguration innerhalb einer Formelsprechen zu können, führen wir mit I, Rj, K und L mehrere neue Funk-tionssymbole ein, die stellvertretend für die folgenden Funktionen ste-hen:

I : (q, i,s0, . . . ,sn) �→ i (Kopfposition)Rj : (q, i,s0, . . . ,sn) �→ s j (Symbol in der j-ten Zelle)K : (q, i,s0, . . . ,sn) �→ q (Zustand der Maschine)L : (q, i,s0, . . . ,sn) �→ n+1 (Anzahl benutzter Bandzellen)

Abbildung 5.32 zeigt, wie sich die Konfiguration einer Turing-Maschi-ne mit den definierten Funktionen beschreiben lässt.

Behalten Sie stets im Gedächtnis, dass wir eine Formel der Peano-Arithmetik suchen. Eine solche Formel darf neben ‚0‘, ‚s‘, ‚+‘ und ‚×‘keine weiteren Funktionszeichen und neben ‚=‘ keine weiteren Prädi-katzeichen enthalten. Wir kommen also nicht umhin, die neu eingeführ-ten Symbole irgendwann durch äquivalente arithmetische Ausdrücke zuersetzen. Für den Moment wollen wir uns an diesem Missstand nichtstören, doch schon jetzt sei angemerkt, dass sich die neu eingeführtenFunktionen durch äquivalente arithmetische Ausdrücke ersetzen lassen.Wie dies im Einzelnen gelingt, werden wir weiter unten klären.

Mit den neu eingeführten Funktionen werden wir jetzt zwei wichtigeTeilformeln definieren. Die erste ist die Formel ϕStart(x). Sie soll ge-nau dann wahr sein, wenn die Variable x die Startkonfiguration einerTuring-Maschine beschreibt. Weiter oben haben wir festgelegt, dass inder Startkonfiguration

� der Schreib-Lese-Kopf über der Zelle 0 steht, I(x) = 0

� der Startzustand q1 eingenommen ist K(x) = 1

� und ein leeres Band vorliegt. L(x) = 1∧R0(x) = 0

Die gesuchte Formel ϕStart(x) erhalten wir durch die konjunktive Ver-knüpfung der ermittelten Teilausdrücke:

ϕStart(x) := (I(x) = 0∧K(x) = 1∧L(x) = 1∧R0(x) = 0)

R0(x) = 0

R1(x) = 2

R2(x) = 0

S2 ......1 2 30

I(x) = 0

K(x) = 1

L(x) = 3

q1

(q1,S0,S1,N,q2)

R0(x) = 1

R1(x) = 2

R2(x) = 0

S2 ......

q2

1 2 30

I(x) = 0

K(x) = 2

L(x) = 3

S1

Abbildung 5.33: Ausführung einer Instruk-tion der Form (qi,S j,Sk,N,ql)


Die zweite ist die Formel ϕCont(x). Sie soll genau dann wahr sein, wenndie Maschine in der Konfiguration x nicht terminiert, wenn also eineInstruktion gefunden werden kann, die x in eine Folgekonfigurationüberführt. Die Formel können wir analog zur Formel Cont(M) aus Ab-schnitt 5.4.1 konstruieren. Für die dort betrachtete Maschine lautet siebeispielsweise so:

ϕCont(x) := ∃(y < L(x))(I(x) = y∧K(x) = 1∧Ry(x) = 0

)︸︷︷︸Instruktion (q1,S0,S1,R,q2)

∨

∃(y < L(x))(I(x) = y∧K(x) = 2∧Ry(x) = 0


∨

∃(y < L(x))(I(x) = y∧K(x) = 3∧Ry(x) = 0


∨

∃(y < L(x))(I(x) = y∧K(x) = 4∧Ry(x) = 0


Zusätzlich definieren wir für jede Instruktion I eine Formel ϕI(x,y),die den Übergang von der Konfiguration x in die Konfiguration y be-schreibt. Als erstes betrachten wir eine Instruktion (qi,S j,Sk,N,ql), dieden Schreib-Lese-Kopf nicht bewegt (Abbildung 5.33). Wird sie ausge-führt, so geht die Turing-Maschine von der Konfiguration x genau dannin die Konfiguration y über,

� wenn in der Ausgangskonfiguration x . . .

• n beschriebene Zellen codiert sind, L(x) = n

• der Zustand qi eingenommen ist, K(x) = i

• der Schreib-Lese-Kopf über der Zelle h steht I(x) = h

• und die Zelle h das Zeichen S j enthält Rh(x) = j

� und in der Folgekonfiguration y . . .

• n beschriebene Zellen codiert sind, L(y) = n

• der Zustand ql eingenommen ist, K(y) = l

• der Schreib-Lese-Kopf über der Zelle h steht I(y) = h

• und die Zelle h das Zeichen Sk enthält. Rh(y) = k

Ferner dürfen wir nicht vergessen, dass der Bandinhalt an allen Stellengleich bleibt, an denen der Schreib-Lesekopf nicht steht:

∀(h′ < n) (h′ �= h→∃s (Rh′(x) = s∧Rh′(y) = s))

R0(x) = 1

R1(x) = 2

R2(x) = 0

S2 ......

q2

1 2 30

I(x) = 0

K(x) = 2

L(x) = 3

S1

(q2,S1,S2,R,q3)

R0(x) = 2

R1(x) = 2

R2(x) = 0

S2 ......

q3

1 2 30

I(x) = 1

K(x) = 3

L(x) = 3

S2

Abbildung 5.34: Ausführung einer Instruk-tion der Form (qi,S j,Sk,R,ql)


Fügen wir alle Teilformeln zusammen, so erhalten wir das nachstehendeErgebnis:

� Instruktionstyp (qi,S j,Sk,N,ql)

ϕI(x,y) := ∃h ∃n (L(x) = n∧K(x) = i∧ I(x) = h∧Rh(x) = j ∧L(y) = n∧K(y) = l∧ I(y) = h∧Rh(y) = k ∧∀(h′ < n) (h′ �= h→∃s (Rh′(x) = s∧Rh′(y) = s)))

Für die anderen Instruktionstypen können wir ganz ähnlich verfahren,allerdings müssen wir ein wenig Mehrarbeit leisten, wenn der Schreib-Lese-Kopf auf der ersten oder der letzten Zelle der codierten Bandse-quenz positioniert ist. Der einfachere Fall ist die Rechtsbewegung (Ab-bildung 5.34). Bezeichnen wir mit n1 und n2 die Längen der in x bzw. ycodierten Bandabschnitte und mit h1 und h2 die Positionen des Schreib-Lese-Kopfs, so gilt:

� Steht der Schreib-Lese-Kopf nicht ganz rechts, h1+1 �= n1

• so codiert y genauso viele Zellen wie x. n1 = n2

� Steht der Schreib-Lese-Kopf ganz rechts, h1+1 = n1

• so ist in y eine Zelle mehr codiert als in x, n1+1 = n2

• und diese Zelle ist leer. Rn1(y) = 0

� In beiden Fällen rückt der Kopf nach rechts. h1+1 = h2

Die Formel ϕI(x,y) stellt sich dann folgendermaßen dar:

� Instruktionstyp (qi,S j,Sk,R,ql)

ϕI(x,y) := ∃h1 ∃h2 ∃n1 ∃n2(L(x) = n1∧K(x) = i∧ I(x) = h1∧Rh1(x) = j ∧L(y) = n2∧K(y) = l∧ I(y) = h2∧Rh1(y) = k ∧(h1+1 �= n1→ n1 = n2) ∧(h1+1 = n1→ (n1+1 = n2∧Rn1(y) = 0)) ∧h1+1 = h2 ∧∀(h< n1) (h �= h1→∃s (Rh(x) = s∧Rh(y) = s)))

Im Falle der Linksbewegung müssen wir noch wachsamer sein (Abbil-dungen 5.35 und 5.36). Steht der Schreib-Lese-Kopf bereits ganz links,ist also h1 = 0, so wird die Kopfbewegung simuliert, indem der gesamteBandinhalt eine Stelle nach rechts kopiert wird. Wir halten fest:

R0(x) = 2

R1(x) = 2

R2(x) = 0

S2 ......

q3

1 2 30

I(x) = 1

K(x) = 3

L(x) = 3

S2

(q3,S2,S3,L,q3)

R0(x) = 2

R1(x) = 3

R2(x) = 0

S3 ......

q3

1 2 30

I(x) = 0

K(x) = 3

L(x) = 3

S2

Abbildung 5.35: Ausführung einer Instruk-tion der Form (qi,S j,Sk,L,ql)


� Steht der Schreib-Lese-Kopf nicht ganz links, h1 �= 0

• so codiert y genauso viele Zellen wie x n1 = n2

• und der Schreib-Lese-Kopf rückt nach links. h1 = h2+1

� Steht der Schreib-Lese-Kopf ganz links, h1 = 0

• so ist in y eine Zelle mehr codiert als in x, n1+1= n2

• diese Zelle ist leer R0(y) = 0

• und der Schreib-Lese-Kopf bleibt wo er ist. h1 = h2

Das Umkopieren des Bandinhalts können wir mit der folgenden For-mel beschreiben:

∀(h< n1) (h �= 0→∃s (Rh(x) = s∧Rh+1(y) = s))

Insgesamt erhalten wir die folgende Formel:

� Instruktionstyp (qi,S j,Sk,L,ql)

ϕI(x,y) := ∃h1 ∃h2 ∃n1 ∃n2(L(x) = n1∧K(x) = i∧ I(x) = h1∧Rh1(x) = j ∧L(y) = n2∧K(y) = l∧ I(y) = h2 ∧(h1 �= 0→ (

n1 = n2∧h1 = h2+1∧Rh1(y) = k ∧∀(h< n1) (h �= h1→∃s (Rh(x) = s∧Rh(y) = s)))) ∧

(h1 = 0→ (

n1+1 = n2∧R0(y) = 0∧h1 = h2∧R1(y) = k ∧∀(h< n1) (h �= 0→∃s (Rh(x) = s∧Rh+1(y) = s)))))

Indem wir alle Instruktionsformeln disjunktiv miteinander verknüpfen,erhalten wir eine Formel, die genau dann wahr ist, wenn die Maschineeinen Übergang von der Konfiguration x in die Konfiguration y vollzie-hen kann:

ϕTrans(x,y) := ϕI1(x,y)∨ϕI2(x,y)∨ϕI3(x,y)∨ . . .∨ϕIK (x,y)

Als nächstes werden wir versuchen, beliebige Anfangsstücke einer Be-rechnungssequenz, d. h. eine endliche Folge von Konfigurationen κ0,κ1, κ2, . . . ,κm als natürliche Zahl zu codieren. Hierzu führen wir mitM ein einstelliges und mit C ein zweistelliges Funktionssymbol mit derfolgenden Bedeutung ein:

M : (κ0,κ1,κ2, . . . ,κm) �→ m (Anzahl Berechnungsschritte)C : (κ0,κ1,κ2, . . . ,κm),k �→ κk (k-te Konfiguration)

R0(x) = 2

R1(x) = 3

R2(x) = 0

S3 ......

q3

1 2 30

I(x) = 0

K(x) = 3

L(x) = 3

S2

(q3,S2,S3,L,q3)

K(x) = 3

S3

R0(x) = 0

R1(x) = 3

R2(x) = 3

S3 ......

q3

1 2 30

I(x) = 0

L(x) = 4 R3(x) = 0

Abbildung 5.36: Ausführung einer Instruk-tion der Form (qi,S j,Sk,L,ql). Im darge-stellten Fall steht der Schreib-Lese-Kopfbereits ganz links. Die Kopfbewegung wirdsimuliert, indem der gesamte Bandinhalt ei-ne Stelle nach rechts kopiert wird.


Mit den beiden neuen Funktionen können wir eine terminierende Be-rechnungssequenz ohne Umwege beschreiben. Hierzu brauchen wir unslediglich darauf zu besinnen, dass eine Turing-Maschine M nach n Be-rechnungsschritten terminiert, wenn sie

� in der Starkonfiguration beginnt ϕStart(C(z,0))

� und rechnet, n=M(z)∧∀(u< n) ϕTrans(C(z,u),C(z,s(u)))

� bis es kein Weiterkommen gibt. ¬ϕCont(C(z,n))

Zusammenfassend erhalten wir mit

ϕM := ∃z ∃n (ϕStart(C(z,0)) ∧ (5.17)n=M(z)∧∀(u< n) ϕTrans(C(z,u),C(z,s(u))) ∧¬ϕCont(C(z,n)))

jene Formel, nach der wir gesucht haben. ϕM ist genau dann wahr, wenndie Turing-Maschine M terminiert. Ihr einziger Makel: Sie ist keine For-mel der Peano-Arithmetik, da sie eine Reihe von Funktionszeichen ent-hält, die uns in PA nicht zur Verfügung stehen, und die Variable y in derFormel ϕCont zudem als Index eines Funktionszeichens vorkommt. Die-ses Umstands wollen wir uns jetzt annehmen und die Funktionszeichennacheinander eliminieren. Der Schlüssel für unser Vorhaben ist wiedereinmal die Gödel’sche β -Funktion

β (x,y,z) := x mod (1+ y ·(z+1))

mit der wir uns ausführlich in Abschnitt 4.2.3 beschäftigt haben. Dorthaben wir nachgewiesen, dass für jede Sequenz natürlicher Zahlena0, . . . ,an zwei Zahlen b und c existieren mit

β (b,c,0) = a0, β (b,c,1) = a1, β (b,c,2) = a2, . . .

Damit sind wir in der Lage, jede Konfiguration

x = (q, i,s0,s1, . . . ,sn)

mithilfe zweier Zahlen b und c zu repräsentieren. Diese Zahlen lassensich so wählen, dass die folgenden Eigenschaften erfüllt sind:

β (b,c,0) = n+1 (Anzahl der codierten Zellen, L(x))β (b,c,1) = q (Zustand der Maschine, K(x))β (b,c,2) = i (Kopfposition, I(x))β (b,c,3) = s0 (Inhalt der ersten Zelle, R0(x))

. . .

β (b,c,n+3) = sn (Inhalt der letzten Zelle, Rn(x))


Jetzt ist es nur noch eine Formsache, die Formeln ϕStart(x), ϕTrans(x) undϕCont(x) in Formeln der Peano-Arithmetik zu übersetzen. Beispielswei-se können wir die Formel

ϕStart(x) = (I(x) = 0∧K(x) = 1∧L(x) = 1∧R0(x) = 0)

wie folgt umschreiben:

ϕStart(b,c) := (β (b,c,2) = 0)∧ (β (b,c,1) = 1) ∧(β (b,c,0) = 1)∧ (β (b,c,3) = 0)

Ersetzen wir jetzt noch den Platzhalter β (b,c,n) durch den äquivalentenarithmetischen Ausdruck (4.7) aus Abschnitt 4.2.3, so erhalten wir eineechte PA-Formel:

ϕStart(b,c) := ∃d b= s(c× s(2))×d+0∧0< s(c× s(2)) ∧∃d b= s(c× s(1))×d+1∧1 < s(c× s(1)) ∧∃d b= s(c× s(0))×d+1∧1 < s(c× s(0)) ∧∃d b= s(c× s(3))×d+0∧0< s(c× s(3))

Auf die gleiche Weise können wir die Formeln ϕTrans(x) und ϕCont(x)in entsprechende Formeln ϕTrans(b1,c1,b2,c2) und ϕCont(b,c) transfor-mieren. Übersichtlich sind diese Formeln nicht, und deshalb wollen wirdarauf verzichten, sie in voller Gänze auszuschreiben. Auch den Platz-halter β (b,c,n) wollen wir ab jetzt nicht mehr eliminieren.

Nachdem wir es geschafft haben, einzelne Konfigurationen arithmetischzu codieren, wollen wir uns im nächsten Schritt davon überzeugen, dasssich endliche Berechnungssequenzen auf die gleiche Weise codierenlassen. Dies gelingt, indem wir die Gödel’sche β -Funktion ein zwei-tes Mal bemühen. Nach dem oben Gesagten können wir eine endlicheBerechnungssequenz

κ0,κ1,κ2, . . . ,κm

als eine Folge von jeweils zwei natürlichen Zahlen auffassen:

b0,c0,b1,c1, . . . ,bm,cm

Mithilfe der Gödel’schen β -Funktion können wir diese Folge in dergewohnten Weise auf zwei natürliche Zahlen b und c verdichten. Wirwissen, dass b und c so gewählt werden können, dass die folgendenEigenschaften gelten:

β (b,c,0) = m (Anzahl der Berechnungsschritte, M(z))β (b,c,2 · i+1) = bi (erste Komponente von C(z, i))β (b,c,2 · i+2) = ci (zweite Komponente von C(z, i))


Damit können wir Formel (5.17) folgendermaßen umschreiben:

ϕM =∃b ∃c ∃n (ϕStart(β (b,c,1),β (b,c,2)) ∧ (5.18)n= β (b,c,0) ∧∀(u< n) ϕTrans(β (b,c,2×u+1),β (b,c,2×u+2),

∀(u< n) ϕTrans(β (b,c,2×u+3),β (b,c,2×u+4)) ∧¬ϕCont(β (b,c,2×n+1),β (b,c,2×n+2)))

Jetzt sind wir am Ziel. Mit ϕM haben wir eine PA-Formel konstruiert,die genau dann wahr ist, wenn die codierte Turing-Maschine M termi-niert. Der Rest der Argumentation ist der gleiche wie im vorherigen Ab-schnitt. Gäbe es ein Entscheidungsverfahren für die Peano-Arithmetik,so könnten wir damit das Halteproblem lösen. Hierzu müssten wir le-diglich Formel (5.18) konstruieren und prüfen, ob sie wahr oder falschist. Aus der Unentscheidbarkeit des Halteproblems folgt nun sofort

Satz 5.8

Die semantische Variante des Entscheidungsproblems ist für diePeano-Arithmetik unlösbar.

Der Satz besagt, dass kein systematisches Verfahren existiert, das fürjede arithmetische Formel immer korrekt entscheidet, ob sie wahr oderfalsch ist. Daraus folgt unmittelbar, dass es auch kein formales Sys-tem für die Peano-Arithmetik geben kann, das korrekt und vollständigist. Gäbe es ein solches, so könnten wir nach Satz 2.6 die semantischeVariante des Entscheidungsproblems lösen. Aber genau dies ist nachSatz 5.8 unmöglich, und wir erhalten eines der bedeutendsten Ergebnis-se der Beweistheorie als Korollar: die semantische Variante des erstenGödel’schen Unvollständigkeitssatzes.

Korollar 5.2 (Erster Gödel’scher Unvollständigkeitssatz)

Jedes korrekte formale System, das stark genug ist, um die Peano-Arithmetik zu formalisieren, ist unvollständig.

Die Überlegungen in diesem Abschnitt haben gezeigt, dass wir die se-mantische Variante des ersten Gödel’schen Unvollständigkeitssatzes aufverblüffend einfache Weise herleiten können. Alles, was wir für sei-nen Beweis benötigen, sind das Wissen über die Unentscheidbarkeit desHalteproblems sowie die Erkenntnis, dass wir jede Turing-Maschine alsarithmetische Formel codieren können. Ein wunderbares Ergebnis.

1953 Davis:

„Jede semi-entscheidbareRelation lässt sich alsdiophantische Gleichungmit einer beschränktallquantifizierten Variablecodieren.“ [41]

1961 Davis, Putnam, Robinson:

„Jede semi-entscheidbareRelation lässt sich alsexponentiellediophantische Gleichungcodieren.“ [45]

1970 Matijasevic:

„Jede exponentiellediophantische Gleichunglässt sich in einegewöhnliche diophantischeGleichungübersetzen.“ [122]

⇒ Hilberts zehntes Problemist unlösbar!

1984 Jones, Matijasevic:

„Jede Registermaschinelässt sich exponentielldiophantischrepräsentieren.“ [99]

Abbildung 5.37: Sternstunden der Mathe-matik. Seit dem Jahr 1970 wissen wir, dassdas zehnte Hilbert’sche Problem keine Lö-sung besitzt, und seit 1984 haben wir eineneleganten Beweis dafür in Händen.


5.4.3 Hilberts zehntes Problem

In den beiden vorangegangenen Abschnitten haben wir durch die Re-duktion des Halteproblems elegante Beweise für die Unlösbarkeit desEntscheidungsproblems der Prädikatenlogik und für die Unvollständig-keit der Arithmetik erhalten. Auf die gleiche Weise werden wir jetztein weiteres bedeutendes Negativresultat herleiten: die Unlösbarkeit deszehnten Hilbert’schen Problems. Auf dem 2. internationalen Kongressder Mathematiker in Paris hatte David Hilbert das Problem mit den fol-genden Worten formuliert:

„Eine diophantische Gleichung mit irgend welchen Unbe-kannten und mit ganzen rationalen Zahlenkoeffizienten seivorgelegt: man soll ein Verfahren angeben, nach welchemsich mittelst einer endlichen Anzahl von Operationen ent-scheiden lässt, ob die Gleichung in ganzen rationalen Zah-len lösbar ist.“

David Hilbert, 1900 [90]

In Kapitel 1 haben wir vorweggenommen, dass sich Hilberts zehntesProblem nicht lösen lässt, d. h., dass es unmöglich ist, ein systematisch-es Verfahren anzugeben, das für jede diophantische Gleichung immerkorrekt entscheidet, ob sie lösbar ist oder nicht. Historisch wurde diesesErgebnis in mehreren Etappen erzielt (Abbildung 5.37):

� Im Jahr 1953 publizierte Martin Davis eine Arbeit mit dem Ti-tel „Arithmetical Problems and Recursively Enumerable Predica-tes“ [41]. Darin konnte er zeigen, dass sich jede semi-entscheidbareRelation R(a1, . . . ,an) in der Form

∃y ∀(z≤ y) ∃x1 . . .∃xm p(a1, . . . ,an,y,z,x1, . . . ,xm) = 0 (5.19)

darstellen lässt. Hierin ist p ein multivariables Polynom mit n+m+2Unbekannten. Mit dieser Gleichung hatte Davis den Fuß an denRand der Ziellinie gesetzt; lediglich der Quantor ∀(z ≤ y) hinderteihn daran, sie zu überschreiten. Wäre es Davis gelungen, den All-quantor zu eliminieren, so hätte er Hilberts zehntes Problem ent-schieden. In Worten würde Gleichung (5.19) dann besagen, dass fürjede semi-entscheidbare Relation R eine diophantische Gleichungkonstruiert werden kann, die für (a1, . . . ,an) ∈ R lösbar und für(a1, . . . ,an) �∈ R unlösbar ist. Aus der Tatsache, dass das Haltepro-blem semi-entscheidbar ist, ergäbe sich dann in der Tat die Unlös-barkeit des zehnten Hilbert’schen Problems. 1953 schien die Lösung

Reduktion

DiophantischeGleichung

Reduktion

Exponentiellediophantische

Gleichung

Jones, Matijasevi (1984)

Matijasevi (1970)

Registermaschine

Abbildung 5.38: Im Jahr 1984 zeigten Jo-nes und Matijasevic, wie sich Registerma-schinen exponentiell diophantisch repräsen-tieren lassen. Zusammen mit dem Ergeb-nis von Matijasevic aus dem Jahr 1970 er-gibt sich daraus ein eleganter Beweis fürdie Unlösbarkeit des zehnten Hilbert’schenProblems.


zum Greifen nahe. Dennoch blieben alle Versuche, den Allquantoraus Gleichung (5.19) zu eliminieren, zunächst ohne Erfolg.

� Im Jahr 1961 publizierten Martin Davis, Hilary Putnam und JuliaRobinson eine wegweisende Arbeit mit dem Titel „The DecisionProblem for Exponential Diophantine Equations“ [45]. In dieser Ar-beit bewiesen die Autoren einen Satz, der heute als Bounded quan-tifier theorem bekannt ist. Damit konnten sie den Davis’schen All-quantor tatsächlich eliminieren, doch der Preis dafür war hoch. Dieresultierende Gleichung hatte die Form

∃x1 . . .∃xm r(a1, . . . ,an,x1, . . . ,xm) = s(a1, . . . ,an,x1, . . . ,xm)

wobei r = s keine gewöhnliche diophantische Gleichung mehr war,sondern eine exponentielle. Im Gegensatz zu gewöhnlichen diophan-tischen Gleichungen dürfen Variablen hier auch als Exponent ver-wendet werden. Auch wenn das Ergebnis keinen direkten Rück-schluss auf Hilberts zehntes Problem zuließ, wurde dennoch einwichtiger Meilenstein erreicht: Davis, Putnam und Robinson hattenbewiesen, dass kein Entscheidungsverfahren für exponentielle dio-phantische Gleichungen existieren kann.

� Die Gewissheit, dass auch für gewöhnliche diophantische Gleichun-gen kein Entscheidungsverfahren existiert, haben wir seit 1970. Indiesem Jahr bewies Yuri Matijasevic, dass sich jede exponentiellediophantische Gleichung in eine gewöhnliche diophantische Glei-chungen übersetzen lässt (Abbildung 5.38 unten) [122]. Der Beweisist wenig anschaulich, und wir wollen ihn an dieser Stelle nicht füh-ren. Dennoch spielt er in unserer Argumentation eine wichtige Rolle.Nur mit ihm folgt aus der Unlösbarkeit des Entscheidungsproblemsfür exponentielle diophantische Gleichungen auch wirklich die Un-lösbarkeit des zehnten Hilbert’schen Problems.

� Obwohl das Rätsel im Jahr 1970 gelöst war, verebbte das Interessenicht. Der gefundene Beweis war zwar korrekt, dafür aber ungemeintechnisch und kompliziert. Im Jahr 1984 publizierten James Jonesund Yuri Matijasevic schließlich einen neuen Beweis für die Un-entscheidbarkeit exponentieller diophantischer Gleichungen (Abbil-dung 5.38 oben) [99]. Inhaltlich bewiesen sie das Gleiche wie Da-vis, Putnam und Robinson etliche Jahre zuvor, erzielten ihr Ergebnisaber auf verblüffend elegante Weise. Sie fanden heraus, wie sich Re-gistermaschinen exponentiell diophantisch codieren lassen. Dass eskein Entscheidungsverfahren für exponentielle diophantische Glei-chungen geben kann, folgt dann sofort aus der Unentscheidbarkeitdes Halteproblems.

� Reduktion von Z auf N

p(x1, . . . ,xm) = 0hat eine Lösung in Zm

⇓⇑p(p1−q1, . . . , pm−qm) = 0

hat eine Lösung in N2m

� Reduktion von N auf Z

p(x1, . . . ,xm) = 0hat eine Lösung in Nm

Lagrange1) ⇓⇑ Lagrange1)

p(w21 + x2

1 + y21 + z2

1, . . . ,w2m + x2

m + y2m + z2

m) = 0

hat eine Lösung in Z4m

Abbildung 5.39: Gegenseitige Reduktionder Entscheidungsprobleme diophantischerGleichungen

1)„Jede natürliche Zahl lässt sich alsSumme von vier Quadratzahlen

darstellen.“

Joseph Louis de Lagrange (1736 – 1813)

Abbildung 5.40: Im Jahr 1770 bewies derfranzösische Mathematiker Joseph Louis deLagrange eine von Bachet de Méziriac imJahr 1612 geäußerte Vermutung. Sie besagt,dass sich jede natürliche Zahl als Summevon vier Quadratzahlen darstellen lässt.


Der Beweis von Jones und Matijasevic besticht so sehr durch seine Klar-heit und Eleganz, dass er sich zur Untersuchung in diesem Buch gerade-zu aufzwingt. Um ihn im Detail verstehen zu können, müssen wir abernoch ein wenig Vorarbeit leisten. Zunächst wollen wir klären, wann wireine diophantische Gleichung als lösbar erachten. Anders als von Hil-bert gefordert, werden wir die Lösungen nicht in den ganzen Zahlen,sondern in den natürlichen Zahlen suchen. Auf den ersten Blick ma-chen wir hierdurch einen gewaltigen Fehler. Beispielsweise besitzt dieGleichung

(x+1)3 +(y+1)3 = (z+1)3 (5.20)

in den natürlichen Zahlen gar keine, in den ganzen Zahlen dagegen un-endlich viele Lösungen. Dass wir den Wertebereich dennoch bedenken-los wechseln dürfen, liegt daran, dass wir nicht an der Lösbarkeit ganzbestimmter Gleichungen, sondern an der Existenz von Entscheidungs-verfahren interessiert sind. Hier gilt, dass wir ein Verfahren für die Lös-barkeit in den ganzen Zahlen dazu verwenden können, um die Lösbar-keit in den natürlichen Zahlen zu entscheiden, und umgekehrt. Wie diejeweiligen Problemreduktionen aussehen, ist in Abbildung 5.39 darge-stellt. Eine der vier Schlussrichtungen ist nicht unmittelbar einsichtig.Um sie zu legitimieren, benötigen wir den berühmten Vier-Quadrate-Satz von Lagrange, der uns in Abschnitt 3.1.2 bereits begegnet ist. Erbesagt, dass sich jede natürliche Zahl als die Summe von vier Quadrat-zahlen darstellen lässt (Abbildung 5.40).

Bezogen auf die Beispielgleichung (5.20) bedeutet die Reduktion dasFolgende: Die Frage, ob sie in den ganzen Zahlen lösbar ist, ist äquiva-lent zur Frage, ob die Gleichung

(p1−q1 +1)3 +(p2−q2 +1)3 = (p3−q3 +1)3

eine Lösung in den natürlichen Zahlen hat. Analog gilt, dass (5.20) ge-nau dann in den natürlichen Zahlen lösbar ist, wenn es für die Gleichung

(w21 + x2

1 + y21 + z2

1 +1)3 +(w22 + x2

2 + y22 + z2

2 +1)3 =

(w23 + x2

3 + y23 + z2

3 +1)3

eine Lösung in den ganzen Zahlen gibt. Die Frage nach der Existenzeines Entscheidungsverfahrens ist damit unabhängig von der konkretenWahl des Wertebereichs. Würde ein Verfahren existieren, das für jedediophantische Gleichung immer korrekt entscheidet, ob sie in den na-türlichen Zahlen lösbar ist, so würde auch ein Entscheidungsverfahrenfür die Lösbarkeit in den ganzen Zahlen existieren und umgekehrt.


5.4.3.1 Diophantische Repräsentierbarkeit

In diesem Abschnitt wollen wir klären, wie sich Relationen diophan-tisch repräsentieren lassen. Die Idee, die wir hierbei verfolgen, ist jeneraus Abschnitt 4.2.1 sehr ähnlich. Dort haben wir gezeigt, wie sich Re-lationen arithmetisch repräsentieren lassen.

Definition 5.10 (Diophantisch repräsentierbare Relationen)

Sei R⊆ Nn. Die (exponentielle) diophantische Gleichung

p(a1, . . . ,an,x1, . . . ,xm) = 0

repräsentiert R, wenn sie die folgende Eigenschaft erfüllt:

(a1, . . . ,an) ∈ R ⇔ p(a1, . . . ,an,x1, . . . ,xm) = 0 hat eine Lösung

In Worten besagt die Definition das Folgende: Eine Relation R wirddurch die Gleichung p= 0 diophantisch repräsentiert, wenn wir für jedeKombination (a1, . . . ,an) ∈ R natürliche Zahlen x1, . . . ,xm finden kön-nen, mit p(a1, . . . ,an,x1, . . . ,xm) = 0. Gilt umgekehrt (a1, . . . ,an) �∈ R,so darf die Gleichung für keine Kombination von x1, . . . ,xm lösbar sein.In mathematischer Notation können wir den Sachverhalt so ausdrücken:

R(a1, . . . ,an) ⇔ ∃x1 . . .∃xm p(a1, . . . ,an,x1, . . . ,xm) = 0

Jetzt ist klar, wie wir Gleichung (5.19) zu lesen haben. Die von Davisverwendete Form ist bis auf den zusätzlichen Allquantor mit der hierpräsentierten identisch.

In Abbildung 5.41 sind mehrere diophantisch repräsentierbare Relatio-nen exemplarisch zusammengefasst. Auch wenn die meisten davon sehrsimpel sind, lässt das letzte aufgeführte Beispiel schon jetzt erahnen,dass auch komplexe Relationen diophantisch repräsentiert werden kön-nen. Es handelt sich um eine Gleichung mit 26 Unbekannten, die genaudann eine Lösung in den positiven natürlichen Zahlen besitzt, wenn dieZahl k+2 eine Primzahl ist. [101, 156, 205]

Das Primzahlbeispiel wollen wir nicht vorschnell übergehen. Vielleichtist Ihnen aufgefallen, dass sich die abgebildete Gleichung aus insgesamt14 Teilausdrücken zusammensetzt, die konjunktiv miteinander verbun-den sind. Streng genommen ist sie damit keine echte diophantischeGleichung mehr, da sie neben arithmetischen Verknüpfungen auch Lo-gikoperatoren enthält. Glücklicherweise lassen sich die Operatoren ‚∧‘


Auswahl diophantisch repräsentierbarer Relationen

� „x ist eine gerade natürliche Zahl“

x−2 ·y = 0

� „x ist eine Quadratzahl“

x− y2 = 0

� „x teilt y“

x ·z− y = 0

� „x ist größer oder gleich y“

y+ z− x = 0

� „x ist größer als y“

y+ z+1− x = 0

� „k+2 ist eine Primzahl“ wz+h+ j−q = 0 ∧(gk+2g+ k+1)(h+ j)+h− z = 0 ∧

16(k+1)3(k+2)(n+1)2 +1− f 2 = 0 ∧2n+ p+q+ z− e = 0 ∧

e3(e+2)(a+1)2 +1−o2 = 0 ∧(a2−1)y2 +1− x2 = 0 ∧

16r2y4(a2−1)+1−u2 = 0 ∧n+ l + v− y = 0 ∧

(a2−1)l2 +1−m2 = 0 ∧ai+ k+1− l− i = 0 ∧

((a+u2(u2−a))2−1)(n+4dy)2 +1− (x+ cu)2 = 0 ∧p+ l(a−n−1)+b(2an+2a−n2−2n−2)−m = 0 ∧q+ y(a− p−1)+ s(2ap+2a− p2−2p−2)− x = 0 ∧

z+ pl(a− p)+ t(2ap− p2−1)− pm = 0

Abbildung 5.41: Auswahl diophantischer repräsentierbarer Relationen. Auch die Menge aller Primzahlen lässt sich diophan-tisch repräsentieren [205]. Die Zahl k+2 ist genau dann eine Primzahl, wenn die rechts abgebildete Gleichung eine Lösung inden positiven natürlichen Zahlen besitzt.

und ‚∨‘ sehr einfach eliminieren, so dass wir sie bedenkenlos innerhalbvon diophantischen Gleichungen verwenden können. Es gelten die fol-genden Zusammenhänge:

p = 0 ∨ q = 0 ⇔ p ·q = 0 (5.21)

p = 0 ∧ q = 0 ⇔ p2 +q2 = 0 (5.22)

Als nächstes definieren wir mit der Maskierungsrelation ‚�‘ einen derProtagonisten im Beweis von Jones und Matijasevic:

Definition 5.11 (Maskierungsrelation ‚�‘)

r und s seien natürliche Zahlen mit den Binärdarstellungen

r =n

∑i=0

ri2i (0≤ ri ≤ 1), s =n

∑i=0

si2i (0≤ si ≤ 1)

Die Maskierungsrelation ‚�‘ ist wie folgt festgelegt:

r � s :⇔ ri ≤ si für alle i mit 0≤ i≤ n

s 2 1 0 t

r1,s . . . r1,2 r1,1 r1,0 R1

r2,s . . . r2,2 r2,1 r2,0 R2

r3,s . . . r3,2 r3,1 r3,0 R3

r4,s . . . r4,2 r4,1 r4,0 R4

......

......

s 2 1 0 t

l1,s . . . l1,2 l1,1 l1,0 L1

l2,s . . . l2,2 l2,1 l2,0 L2

l3,s . . . l3,2 l3,1 l3,0 L3

l4,s . . . l4,2 l4,1 l4,0 L4

......

......

Datenflussmatrix

Kontrollflussmatrix

Abbildung 5.42: Tabellarische Darstellungder Berechnungssequenz einer Registerma-schine. Die x-Achse ist die Zeitachse; hierhält die Tabelle für jeden Berechnungs-schritt eine separate Spalte vor. Für jedesRegister und jede Instruktion existiert ei-ne eigene Zeile. In den Zeilen der Daten-flussmatrix ist vermerkt, wie sich die Inhal-te der Register ändern. Die Zeileneinträgeder Kontrollflussmatrix enthalten entwederden Wert 1 oder 0. Eine 1 bedeutet, dass dieInstruktion ausgeführt wird.


In Worten drückt r � s aus, dass die i-te Binärstelle von r niemals grö-ßer ist als die i-te Binärstelle von s. Für den Moment wollen wir an-nehmen, dass auch die Maskierungsrelation diophantisch repräsentiertwerden kann. Weiter unten werden wir uns davon überzeugen, dass dieswirklich so ist.

Im Folgenden wird die Maskierungsrelation häufig im Zusammenhangmit einer speziellen Konstanten auftauchen, die Jones und Matijasevicmit I bezeichnen. Sie steht stellvertretend für die Zahl

I :=s

∑t=0

Qt = 111 . . .111︸︷︷︸s+1 Ziffern

Q (5.23)

Q ist die Basis von I und wird später passend gewählt werden.

Auf den ersten Blick ist die Bedeutung der Konstanten I schwer zu er-kennen, da ihr exakter Wert in unserer Betrachtung überhaupt keineRolle spielt. Benötigt wird sie ausschließlich aufgrund der speziellenStruktur ihrer Ziffernfolge; stellen wir I zur Basis Q dar, so entsprichtsie einer Folge von genau s+1 Einsen.

5.4.3.2 Codierung von Registermaschinen

Jetzt sind wir gewappnet, um die Berechnungssequenz einer Register-maschine mithilfe einer exponentiellen diophantischen Gleichung zucodieren. Das Verhalten der Maschine werden wir über die folgendenBezeichner erfassen:

r j,t = Inhalt von Register R j zum Zeitpunkt t

l j,t =

{1 zum Zeitpunkt t wird die Instruktion L j ausgeführt0 eine andere Instruktion wird ausgeführt

Die Berechnungssequenz einer Registermaschine können wir mit einerzweidimensionalen Matrix beschreiben, wie sie in Abbildung 5.42 ge-zeigt ist. Die horizontale Achse ist die Zeitachse und erstreckt sich vonrechts nach links. Vertikal besteht die Darstellung aus zwei Teilmatri-zen. Die Datenflussmatrix (oben) hält für jedes Register eine eigeneZeile vor und beschreibt, wie sich die Registerinhalte über die Zeit ver-ändern. In der Kontrollflussmatrix (unten) existiert für jede Instruktioneine eigene Zeile. Dort ist mit einer 1 bzw. einer 0 vermerkt, ob dieInstruktion gegenwärtig ausgeführt wird oder nicht.

In Abbildung 5.43 (oben) ist die vollständig ausgefüllte Daten- undKontrollflussmatrix für das Registermaschinenprogramm aus Abbil-dung 5.16 zu sehen. Die Maschine wird mit der Eingabe R1 = 2 gestartet


23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 t1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 2 2 R1 Registerinhalt0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 R2 Registerinhalt0 0 0 0 1 1 2 2 2 2 2 1 1 0 0 0 0 1 1 1 1 1 0 0 R3 Registerinhalt0 0 0 0 0 0 0 0 0 0 0 1 1 2 2 1 1 1 0 0 0 0 0 0 R4 Registerinhalt0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 R5 Registerinhalt

23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 t0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 L1 if R1 = 0 goto L20

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 L2 R2 ← R2 +1,R3 ← R3 +10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 L3 R1 ← R1−10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 L4 if R1 = 0 goto L16

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 L5 R1 ← R1−10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 L6 R4 ← R4 +1,R5 ← R5 +10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 L7 R3 ← R3−10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 L8 if R3 �= 0 goto L6

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 L9 R4 ← R4 +1,R2 ← R2−10 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 L10 if R2 �= 0 goto L9

0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 L11 R3 ← R3 +1,R4 ← R4−10 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 L12 if R4 �= 0 goto L11

0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 L13 R2 ← R2 +1,R5 ← R5−10 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 L14 if R5 �= 0 goto L13

0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 L15 if R1 �= 0 goto L5

0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 L16 R3 ← R3−10 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 L17 if R3 �= 0 goto L16

0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 L18 R2 ← R2−1,R1 ← R1 +10 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 L19 if R2 �= 0 goto L18

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 L20 stop

Q− 22+s+20 = 0 ∧ 1+(Q− 1) · I = Qs+1 ∧ Qs = L20 ∧ R1 � (Q/2− 1)I ∧ R2 � (Q/2− 1)I ∧ R3 � (Q/2− 1)I ∧R4 � (Q/2− 1)I ∧ R5 � (Q/2− 1)I ∧ R1 = QR1 +QL18−QL3−QL5 + 2− y ·Qs+1 ∧ R2 = QR2 +QL2 +QL13−QL9−QL18 ∧ R3 = QR3 +QL2 +QL11−QL7−QL16 ∧ R4 = QR4 +QL6 +QL9−QL11 ∧ R5 = QR5 +QL6−QL13∧ L1 � I ∧ L2 � I ∧ L3 � I ∧ L4 � I ∧ L5 � I ∧ L6 � I ∧ L7 � I ∧ L8 � I ∧ L9 � I ∧ L10 � I ∧ L11 � I ∧L12 � I ∧ L13 � I ∧ L14 � I ∧ L15 � I ∧ L16 � I ∧ L17 � I ∧ L18 � I ∧ L19 � I ∧ L20 � I ∧ I = L1 + L2 +L3 + L4 + L5 + L6 + L7 + L8 + L9 + L10 + L11 + L12 + L13 + L14 + L15 + L16 + L17 + L18 + L19 + L20 ∧ 1 � L1 ∧Q ·L1 � L20 +L2∧Q ·L1 � L2 +Q · I−2R1 ∧ Q ·L2 � L3 ∧ Q ·L3 � L4 ∧ Q ·L4 � L16 +L5∧Q ·L4 � L5 +Q · I−2R1∧ Q ·L5 � L6 ∧ Q ·L6 � L7 ∧ Q ·L7 � L8 ∧ Q ·L8 � L6 +L9 ∧Q ·L8 � L6 +Q · I− 2R3 ∧ Q ·L9 � L10 ∧ Q ·L10 �L9 +L11∧Q ·L10 � L9 +Q · I−2R2 ∧ Q ·L11 � L12 ∧ Q ·L12 � L11 +L13∧Q ·L12 � L11 +Q · I−2R4 ∧ Q ·L13 � L14∧ Q ·L14 � L13 +L15∧Q ·L14 � L13 +Q · I−2R5 ∧ Q ·L15 � L5 +L16∧Q ·L15 � L5 +Q · I−2R1 ∧ Q ·L16 � L17 ∧Q ·L17 � L16 +L18∧Q ·L17 � L16 +Q · I−2R3 ∧ Q ·L18 � L19 ∧ Q ·L19 � L18 +L20∧Q ·L19 � L18 +Q · I−2R2 ∧

Abbildung 5.43: Codierte Berechnungssequenz der hier besprochenen Beispielmaschine für die Eingabe R1 = 2

Registermaschine terminiertunter Eingabe von x

⇓⇑Es existiert eine Lösung für

2x+s+l (Basis)

p (Q, I, s, x, y, R1,..., Rr, L1,..., Ll ) = 0

111...111Q

Anzahl SchritteEingabe

DatenflussKontrollfluss

……

Ausgabe

Abbildung 5.44: Codierung von Register-maschinen mithilfe exponentieller diophan-tischer Gleichungen.


und terminiert nach 23 Schritten. Die so entstandene Berechnungsse-quenz kennen wir bereits; sie ist die gleiche, die wir in Abschnitt 5.1.2verwendet haben, um das Verhalten von Registermaschinen zu erklä-ren. Lediglich die Darstellung ist eine andere. In Abbildung 5.17 hattenwir das Verhalten noch mithilfe eines gewöhnlichen Ablaufprotokollsanalysiert.

Um die Berechnungssequenz einer Registermaschine diophantisch zucodieren, stellen wir zunächst jede Zeile der Datenflussmatrix und derKontrollflussmatrix durch eine Zahl zur Basis Q dar. Dabei verfolgenwir die Idee, den Eintrag in der t-ten Spalte in die t-te Ziffer hineinzu-codieren:

R j =s

∑t=0

r j,tQt , 0≤ r j,t <Q2

(5.24)

L j =s

∑t=0

l j,tQt , 0≤ l j,t ≤ 1 (5.25)

In diesen Gleichungen ist s die Anzahl der Berechnungsschritte, durch-geführt von einer Maschine mit den Registern R1, . . . ,Rr und den Code-Zeilen L1, . . . ,Ll . Damit die Codierung funktioniert, muss Q eine Zwei-erpotenz sein und so groß gewählt werden, dass alle darzustellendenWerte in eine einzige Ziffer hineinpassen. Insbesondere müssen wirauch darauf achten, dass bei der Verrechnung zweier Werte keine Über-läufe zwischen den einzelnen Ziffern generiert werden. Auf der siche-ren Seite sind wir, wenn der Wert von Q für eine Registermaschine mitr Registern, l Code-Zeilen und der Eingabe x folgendermaßen gewähltwird [99]:

Q = 2x+s+l (5.26)

Die Forderung, dass die Ziffern r j,t nicht den vollen Bereich 0 bis Q−1,sondern nur den Bereich 0 bis Q

2 − 1 ausschöpfen dürfen, wird weiterunten wichtig werden. Wir benötigen sie, damit die Modellierung derbedingten Verzweigungsbefehle korrekt funktioniert.

Wir werden nun daran gehen, die gesuchte diophantische Gleichungaufzustellen. Wie in Abbildung 5.44 gezeigt, wird sie die Variablen

Q, I,s,x,y,R1, . . . ,Rr,L1, . . . ,Ll

enthalten und für einen festgelegten Wert von x genau dann lösbar sein,wenn die codierte Registermaschine unter Eingabe von x terminiert. Esgilt sogar noch mehr: Haben wir eine konkrete Lösung in Händen, sokönnen wir daraus die vollständige Berechnungssequenz rekonstruie-ren. In diesem Fall gilt:

Q2 Q1 Q0

I = 0 0 0 0 0 1 0 0 1

⇓⇑Q2 Q1 Q0

1= 0 0 0 0 0 0 0 0 1

+(Q−1)I= 0 0 0 1 1 1 1 1 1

= Qs+1= 0 0 1 0 0 0 0 0 0

Abbildung 5.45: Visualisierung der Glei-chung (5.27) für den Fall Q = 8 und s = 1.Die einzelnen Ziffern sind hier im Binär-system dargestellt. Die Ziffernwerte liegenzwischen 0 und 7 und sind deshalb 3 Bitsbreit.

Q2 Q1 Q0

Q : 0 0 0 0 0 1 0 0 0

Q2 Q1 Q0

Q2 : 0 0 0 0 0 0 1 0 0

Q2 Q1 Q0

Q2 −1 : 0 0 0 0 0 0 0 1 1

Q2 Q1 Q0

(Q2 −1) · I : 0 1 1 0 1 1 0 1 1

R j � (Q2 −1)I

Q2 Q1 Q0

R j : 0 ? ? 0 ? ? 0 ? ?︸︷︷︸r j,2

︸︷︷︸r j,1

︸︷︷︸r j,0

Abbildung 5.46: R j � (Q2 − 1)I stellt si-

cher, dass in jeder Ziffer r j,t das höchstwer-tige Bit gleich 0 ist.


� I und Q besitzen die in (5.23) und (5.26) angegebenen Werte,

� die Registermaschine terminiert nach s Schritten,

� im Ausgaberegister R1 steht am Ende der Berechnung der Wert y,

� R j codiert den Datenfluss, wie er in (5.24) festgelegt ist,

� L j codiert den Kontrollfluss, wie er in (5.25) festgelegt ist.

Wir werden nun eine Reihe von diophantischen Gleichungen formulie-ren, mit denen sich die genannten Eigenschaften erzwingen lassen:

� Dass Q und I die gewünschten Werte erhalten, können wir folgen-dermaßen sicherstellen:

Q−2x+s+l = 0 ∧ 1+(Q−1) · I = Qs+1 (5.27)

Abbildung 5.45 demonstriert an einem konkreten Beispiel, auf wel-che Weise Gleichung (5.27) den gewünschten Wert von I erzwingt.

� Um die Terminierung der Registermaschine zu beschreiben, fordernwir, dass nach s Berechnungsschritten die Instruktion stop ausge-führt wird. Hierzu verwenden wir eine Gleichung der Form

Qs = ∑k

Lk,

wobei die Summe über alle Zeilen der Form Lk : stop iteriert.

� Um den Datenfluss adäquat zu beschreiben, fordern wir zunächst,dass die Variablen R j die in (5.24) vereinbarte Form besitzen. Mit-hilfe der Maskierungsrelation gelingt dies folgendermaßen (Abbil-dung 5.46):

R j � (Q2−1)I

Ferner fügen wir für jedes Register eine eigene Registergleichung(register equation) hinzu, die beschreibt, wie sich der Registerinhaltüber die Zeit verändert. Diese Gleichungen lauten folgendermaßen:

R1 = QR1 +∑k

QLk−∑i

QLi + x− y ·Qs+1 (5.28)

R j = QR j +∑k

QLk−∑i

QLi (2≤ j ≤ r) (5.29)

Die erste Summe iteriert über alle Zeilen der Form Lk : R j ← R j +1und die zweite Summe über alle Zeilen der Form Li : R j ← R j− 1.

� Li : R j ← R j +1, Li : R j ← R j−1Q2 Q1 Q0

Li : 0 0 0 0 0 1 0 0 0︸︷︷︸li,2

︸︷︷︸li,1

︸︷︷︸li,0

Q2 Q1 Q0

Q ·Li : 0 0 1 0 0 0 0 0 0︸︷︷︸li,1

︸︷︷︸li,0

Q ·Li � Li+1

Q2 Q1 Q0

Li+1 : ? ? 1 ? ? ? ? ? ?︸︷︷︸li+1,2

︸︷︷︸li+1,1

︸︷︷︸li+1,0

� Li : goto Ln

Q2 Q1 Q0

Li : 0 0 0 0 0 1 0 0 0︸︷︷︸li,2

︸︷︷︸li,1

︸︷︷︸li,0

Q2 Q1 Q0

Q ·Li : 0 0 1 0 0 0 0 0 0︸︷︷︸li,1

︸︷︷︸li,0

Q ·Li � Ln

Q2 Q1 Q0

Ln : ? ? 1 ? ? ? ? ? ?︸︷︷︸ln,2

︸︷︷︸ln,1

︸︷︷︸ln,0

Abbildung 5.47: Modellierung des Kon-trollflusses mithilfe der Maskierungsrelati-on ‚�‘


Erstere führen zu einer Erhöhung des j-ten Registers und letztere zueiner Erniedrigung. Die Gleichungen codieren zudem die Start- unddie Endkonfiguration. Sie sind so angelegt, dass die am weitestenrechts stehende Ziffer in R1 gleich x und in R2, . . . ,Rr gleich 0 ist.Ferner muss die Ziffer an der Position s+ 1 in R1 gleich y und inR2, . . . ,Rr gleich 0 sein.

� Um den Programmablauf korrekt zu beschreiben, fordern wir, dassdie Elemente der Kontrollflussmatrix ausschließlich die Werte 0 und1 annehmen können und die Programmausführung mit der Instruk-tion L1 beginnt:

L1 � I ∧ . . . ∧ Ll � I ∧ 1 � L1

Darüber hinaus müssen wir sicherstellen, dass zu jedem Zeitpunktgenau eine Instruktion ausgeführt wird. Dies ist genau dann der Fall,wenn in jeder Spalte der Kontrollflussmatrix genau eine 1 vorhandenist:

I =l

∑i=1

Li

Zusätzlich müssen wir mehrere Gleichungen formulieren, die denÜbergang von einer Konfiguration in die nächste festlegen. Fürnichtverzweigende Instruktionstypen lassen sie sich recht einfachniederschreiben (Abbildung 5.47):

Li : R j ← R j +1 : Q ·Li � Li+1

Li : R j ← R j−1 : Q ·Li � Li+1

Li : goto Ln : Q ·Li � Ln

Die Sprungbefehle Li : if R j = 0 goto Ln und Li : if R j �= 0 goto Ln er-fordern mehr Aufmerksamkeit. Dass die Programmausführung ent-weder in Zeile n oder in Zeile i+1 fortgesetzt wird, können wir nochvergleichsweise einfach formulieren:

Q ·Li � Ln +Li+1

Jetzt müssen wir noch sicherstellen, dass immer die korrekte Folge-instruktion ausgeführt wird. Um zu sehen, wie dies gelingen kann,betrachten wir den Ausdruck

Q · I−2 ·R j

Abbildung 5.48 zeigt, welches Bitmuster entsteht, wenn wir die Sub-traktion im Binärsystem durchführen. Wichtig an dieser Stelle ist,


� Schema

0 0 0 1 0 0 0 1 0 0 0 0Q I

- 2Rj ? ? ? 0 ? ? ? 0

=

? ? ? ? ? ? ? ? ?

??

und der Multiplikation mit 2 sind diese Bits gleich 0.

0 falls ri, t-1 = 01 falls ri, t-1 0

= 1 falls ri, t-1 = 00 falls ri, t-1 0

0 0 0 0

=

(Übertrag)(Übertrag)

Q 0Q 1Q 2

Wegen ri, t < Q2

� Beispiel 1: r j,3 = 2,r j,2 = 1,r j,1 = 2,r j,0 = 1

Q · I 0001 0001 0001 0001 0000−2R j 0100 0010 0100 0010

0001 1001 1101 1001 110= 0000 1100 1110 1100 1110


Q · I 0001 0001 0001 0001 0000−2R j 0100 0010 0000 0000

1 1001 1100 0000 000= 0000 1100 1111 0001 0000


Q · I 0001 0001 0001 0001 0000−2R j 0000 0000 0010 0100

0000 0001 1101 10= 0001 0001 0000 1110 1100

Abbildung 5.48: Die Bedeutung der Formel Q · I−2 ·R j. Das am weitesten rechts stehende Bit der t-ten Ziffer zeigt an, ob derRegisterinhalt R j zum Zeitpunkt t−1 gleich oder ungleich 0 ist.

dass wir in Gleichung (5.24) gefordert haben, dass die Ziffern r j,t

allesamt die Bedingung r j,t <Q2 erfüllen. Das hat zur Folge, dass

wir den Wert R j mit 2 multiplizieren können, ohne zwischen denZiffern Überläufe zu generieren. Somit sind alle Ziffern von 2 ·R jgerade, oder anders formuliert: In allen Ziffern von 2 ·R j ist das amweitesten rechts stehende Bit gleich 0. Dies wiederum hat zur Fol-ge, dass die Subtraktion Q · I − 2 ·R j genau dann ein Übertragsbitvon einem Binärpaket auf das nächste generiert, wenn das Regis-ter R j einen Wert �= 0 enthält. Das bedeutet, dass wir am Bitmustervon Q · I−2 ·R j ablesen können, ob der Inhalt von Register R j zumZeitpunkt t gleich oder ungleich 0 ist. Hierzu müssen wir lediglichdie Ziffer mit der Wertigkeit Qt+1 betrachten. Ist das am weitestenrechts stehende Bit dieser Ziffer gleich 1, so ist r j,t = 0, ansonstenist r j,t �= 0.

Damit können wir das Verhalten der bedingten Sprungbefehle wiefolgt charakterisieren:

Li : if R j = 0 goto Ln : Q ·Li � Ln +Li+1 ∧Q ·Li � Li+1 +Q · I−2R j


r = 0

s = 0 r � s r = 1

s = 1 r � s r � s r = 2

s = 2 r � s r �� s r � s r = 3

s = 3 r � s r � s r � s r � s r = 4

s = 4 r � s r �� s r �� s r �� s r � s r = 5

s = 5 r � s r � s r �� s r �� s r � s r � s r = 6

s = 6 r � s r �� s r � s r �� s r � s r �� s r � s r = 7

s = 7 r � s r � s r � s r � s r � s r � s r � s r � s r = 8

s = 8 r � s r �� s r �� s r �� s r �� s r �� s r �� s r �� s r � s r = 9

s = 9 r � s r � s r �� s r �� s r �� s r �� s r �� s r �� s r � s r � s r = 10

s = 10 r � s r �� s r � s r �� s r �� s r �� s r �� s r �� s r � s r �� s r � s r = 11

s = 11 r � s r � s r � s r � s r �� s r �� s r �� s r �� s r � s r � s r � s r � s r = 12

s = 12 r � s r �� s r �� s r �� s r � s r �� s r �� s r �� s r � s r �� s r �� s r �� s r � s r = 13

s = 13 r � s r � s r �� s r �� s r � s r � s r �� s r �� s r � s r � s r �� s r �� s r � s r � s r = 14

s = 14 r � s r �� s r � s r �� s r � s r �� s r � s r �� s r � s r �� s r � s r �� s r � s r �� s r � s r = 15

s = 15 r � s r � s r � s r � s r � s r � s r � s r � s r � s r � s r � s r � s r � s r � s r � s r � s

Abbildung 5.49: Ordnen wir die Kombinationen von r und s mit r � s zweidimensional an, so entsteht die fraktale Strukturdes Sierpinski-Dreiecks. Die Werte von s sind zeilenweise aufgetragen. Die Werte von r befinden sich auf den nach unten linksverlaufenden Diagonalen.

Li : if R j �= 0 goto Ln : Q ·Li � Ln +Li+1 ∧Q ·Li � Ln +Q · I−2R j

Fügen wir alle Bausteine zusammen, so haben wir die Ziellinie fast er-reicht. Wir erhalten eine diophantische Gleichung, die genau dann eineLösung in den natürlichen Zahlen besitzt, wenn die codierte Register-maschine für die gewählte Eingabe terminiert. Wie die Formel für un-sere konkrete Beispielmaschine aussieht, ist im unteren Teil von Abbil-dung 5.43 zu sehen.

Nur noch ein einziges Puzzle-Stück fehlt in unserem Beweis. Wir sindbisher davon ausgegangen, dass sich die Maskierungsrelation ‚�‘ dio-phantisch repräsentieren lässt, haben dafür aber noch keine Begründunggeliefert. Dies wollen wir jetzt nachholen.

Wacław Sierpinski (1882 – 1969)

Abbildung 5.50: Im Jahr 1915 beschriebder polnische Mathematiker Wacław Sier-pinski jenes Fraktal, das wie heute alsSierpinski-Dreieck bezeichnen [171]. ImBereich der fraktalen Geometrie wird esgerne dazu verwendet, um den Begriff derSelbstähnlichkeit zu erklären.


Als erstes wollen wir klären, für welche konkreten Werte von r und sdie Beziehung r � s erfüllt ist und für welche nicht. Wir unterscheidenzwei Fälle:

� 1. Fall: r > s: An mindestens einer Bitstelle hat r den Wert 1 und san der gleichen Bitstelle den Wert 0. Es gilt daher immer r �� s.

� 2. Fall: r≤ s: Für manche Kombinationen gilt r � s, für andere nicht.Die genaue Verteilung ist in Abbildung 5.49 dargestellt.

Die Struktur aus Abbildung 5.49 ist in der Mathematik keine Unbekann-te. Wir haben das sogenannte Sierpinski-Dreieck vor uns, benannt nachdem polnischen Mathematiker Wacław Sierpinski (Abbildung 5.50). ImBereich der fraktalen Geometrie wird das Dreieck gern verwendet, umdas Prinzip der Selbstähnlichkeit zu demonstrieren. Grob gesprochenist ein Objekt genau dann selbstähnlich, wenn es als Ganzes die gleicheStruktur aufweist wie seine Teile. Am Beispiel des Sierpinski-Dreieckslässt sich die Eigenschaft gut erkennen. Trennen wir eines der drei Teil-dreiecke heraus, so erhalten wir erneut ein Sierpinski-Dreieck, das inseiner Struktur dem ursprünglichen gleicht.

Das Sierpinski-Dreieck ist eng mit dem Pascal’schen Dreieck verwandt,das in der oberen Hälfte von Abbildung 5.51 dargestellt ist. Die Einträgedes Pascal’schen Dreiecks lassen sich auf einfache Weise berechnen,indem die Randzellen zunächst mit dem Wert 1 gefüllt werden. DerWert einer inneren Zelle entspricht dann ganz einfach der Summe derbeiden darüber liegenden Werte.

Das Pascal’sche Dreieck hat eine ganz praktische Bedeutung. Die Zellein Zeile s und Spalte r enthält den Wert des Binomialkoeffizienten(

sr

)Diese Eigenschaft folgt sofort aus der vereinbarten Konstruktionsvor-schrift und der bekannten Gleichung(

s+1r+1

)=

(sr

)+

(s

r+1

)Für unsere Zwecke wird das Pascal’sche Dreieck interessant, wenn wirseine Einträge modulo 2 betrachten. Jede gerade Zahl wird dann zu ei-ner 0 und jede ungerade Zahl zu einer 1. Die untere Hälfte von Ab-bildung 5.51 zeigt, dass wir auf diese Weise genau jene Struktur er-halten, nach der wir suchen; wir erhalten das Sierpinski-Dreieck aus


r = 0

s = 0 1 r = 1

s = 1 1 1 r = 2

s = 2 1 2 1 r = 3

s = 3 1 3 3 1 r = 4

s = 4 1 4 6 4 1 r = 5

s = 5 1 5 10 10 5 1 r = 6

s = 6 1 6 15 20 15 6 1 r = 7

s = 7 1 7 21 35 35 21 7 1 r = 8

s = 8 1 8 28 56 70 56 28 8 1 r = 9

s = 9 1 9 36 84 126 126 84 36 9 1 r = 10

s = 10 1 10 45 120 210 252 210 120 45 10 1 r = 11

s = 11 1 11 55 165 330 462 462 330 165 55 11 1 r = 12

s = 12 1 12 66 220 495 792 924 792 495 220 66 12 1 r = 13

s = 13 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 r = 14

s = 14 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 r = 15

s = 15 1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1

r = 0

s = 0 1 r = 1

s = 1 1 1 r = 2

s = 2 1 0 1 r = 3

s = 3 1 1 1 1 r = 4

s = 4 1 0 0 0 1 r = 5

s = 5 1 1 0 0 1 1 r = 6

s = 6 1 0 1 0 1 0 1 r = 7

s = 7 1 1 1 1 1 1 1 1 r = 8

s = 8 1 0 0 0 0 0 0 0 1 r = 9

s = 9 1 1 0 0 0 0 0 0 1 1 r = 10

s = 10 1 0 1 0 0 0 0 0 1 0 1 r = 11

s = 11 1 1 1 1 0 0 0 0 1 1 1 1 r = 12

s = 12 1 0 0 0 1 0 0 0 1 0 0 0 1 r = 13

s = 13 1 1 0 0 1 1 0 0 1 1 0 0 1 1 r = 14

s = 14 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 r = 15

s = 15 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Abbildung 5.51: Berechnen wir alle Koeffizienten modulo 2, so entsteht aus dem Pascal’schen Dreieck das Sierpinski-Dreieck.


� Darstellung zur Basis 10

(10+1)0 = 1 ·100

(10+1)1 = 1 ·101 + 1 ·102

(10+1)2 = 1 ·102 + 2 ·101 + 1 ·100

(10+1)3 = 1 ·103 + 3 ·102 + 3 ·101 + 1 ·100

(10+1)4 = 1 ·104 + 4 ·103 + 6 ·102 + 4 ·101 + 1 ·100

Ab (10+1)5 ist die Basis 10 zu klein. Es entstehen Ziffernüberläufe.

� Darstellung zur Basis 16

(16+1)0 = 1 ·160

(16+1)1 = 1 ·161 + 1 ·162

(16+1)2 = 1 ·162 + 2 ·161 + 1 ·160

(16+1)3 = 1 ·163 + 3 ·162 + 3 ·161 + 1 ·160

(16+1)4 = 1 ·164 + 4 ·163 + 6 ·162 + 4 ·161 + 1 ·160

(16+1)5 = 1 ·165 + 5 ·164 + 10 ·163 + 10 ·162 + 5 ·161 + 1 ·160

Ab (16+1)6 ist die Basis 16 zu klein. Es entstehen Ziffernüberläufe.

Abbildung 5.52: Jede Zeile des Pas-cal’schen Dreiecks können wir als dieZiffernfolge der Zahl (u+ 1)s auffassen,wenn wir die Basis u hinreichend großwählen. Die beiden nebenstehenden Bei-spiele zeigen, dass die Basis 10 ausreicht,um die ersten 5 Zeilen zu beschreiben; erstin der sechsten Zeile entstehen Überläu-fe. Gehen wir zur Basis 16 über, so wirdauch die sechste Zeile korrekt dargestellt.Wollen wir zusätzlich auch die siebte Zei-le erfassen, so müssen wir die Basis erneutvergrößern.

Abbildung 5.49. Damit haben wir es geschafft, einen elementaren Zu-sammenhang zwischen der Eigenschaft r � s und den Elementen desPascal’schen Dreiecks herzustellen: r � s gilt genau dann, wenn dasPascal’sche Dreieck in Zeile s und Spalte r eine ungerade Zahl enthält:

r � s ⇔(

sr

)ist eine ungerade Zahl (5.30)

Nun gilt nach dem binomischen Lehrsatz das Folgende:

(u+1)s =s

∑r=0

(sr

)ur

Das bedeutet, dass wir jede Zeile des Pascal’schen Dreiecks als die Zif-fernfolge der Zahl (u+ 1)s betrachten können, wenn wir die Basis uhinreichend groß wählen (Abbildung 5.52). Da die Binomialkoeffizien-ten die bekannte Beziehung

s

∑r=0

(sr

)= 2s


erfüllen, sind wir auf der sicheren Seite, wenn wir für u den Wert 2s +1wählen.

Damit sind wir in der Lage, die Binomialkoeffizienten exponentiell dio-phantisch zu erfassen. Es gilt:

m =

(sr

)⇔ u = 2s +1 und m ist die r-te Ziffer von (u+1)s

⇔

⎧⎪⎪⎨⎪⎪⎩∃u ∃w ∃v u = 2s +1 ∧

(u+1)s = vur+1 +mur +w ∧w < ur ∧m < u

(5.31)

Jetzt können wir auch die Beziehung (5.30) problemlos umschreiben.Hierzu müssen wir (5.31) nur geringfügig ergänzen:

r � s ⇔

⎧⎪⎪⎪⎪⎨⎪⎪⎪⎪⎩∃m ∃z ∃u ∃w ∃v u = 2s +1 ∧(u+1)s = vur+1 +mur +w ∧

w < ur ∧m < u ∧

m = 2z+1

(5.32)

Voilà: Die Maskierungsrelation ‚�‘ ist exponentiell diophantisch re-präsentierbar. Damit ist die letzte Beweislücke geschlossen; wir wis-sen nun, dass sich jede Berechnungssequenz einer Registermaschine alsexponentielle diophantische Gleichung codieren lässt. Aus der Unent-scheidbarkeit des Halteproblems folgt jetzt unmittelbar

Satz 5.9 (Jones, Matijasevic, 1984)

Es gibt kein Entscheidungsverfahren für exponentielle diophanti-sche Gleichungen.

Kombinieren wir den Satz mit dem Ergebnis von Matijasevic aus demJahr 1970, so erhalten wir das, was wir in diesem Abschnitt gesuchthaben: Die Antwort auf Hilberts zehntes Problem.

Korollar 5.3

Das zehnte Hilbert’sche Problem hat keine Lösung.

5.5 Übungsaufgaben 331

5.5 Übungsaufgaben

Die Instruktionsmengen zweier Turing-Maschinen M1 und M2 seien wie folgt gegeben: Aufgabe 5.1��

Webcode5089

I1 := {(q1,S0,S1,R,q2),(q2,S0,S0,R,q3),(q3,S0,S2,R,q1)}I2 := {(q1,S0,S1,R,q2),(q2,S0,S0,R,q3),(q3,S0,S2,R,q1),(q4,S0,S0,R,q1)}

a) Erzeugen Sie die Standardbeschreibungen von M1 und M2.

b) Analysieren Sie das Verhalten der Maschinen. Welche Unterschiede fallen Ihnen auf?

In Abbildung 5.12 ist die Instruktionstabelle von Turings historischer universal machine Aufgabe 5.2��

Webcode5743

dargestellt. Unter anderem wird dort die folgende Teilmaschine definiert:

con(C,α)

⎧⎨⎩ Not A R,R con(C,α)

A L,Pα,R con1(C,α)

con1(C,α)

⎧⎪⎪⎪⎨⎪⎪⎪⎩A R,Pα,R con1(C,α)

D R,Pα,R con2(C,α)

None PD,R,Pα,R,R,R C

con2(C,α)

⎧⎨⎩ C R,Pα,R con2(C,α)

Not C R,R C

Wird die Maschine in der Konfiguration

; D... A D D C R D A A

gestartet, so terminiert sie nach 10 Berechnungsschritten, und der Schreib-Lese-Kopf stehtan der folgenden Bandposition:

...

a) Tragen Sie den produzierten Bandinhalt in die Abbildung ein.

b) Welche Teilaufgabe könnte die Maschine in Turings Gesamtkonstruktion erfüllen?


Damit eine Turing-Maschine von einer universellen Maschine simuliert werden kann, mussAufgabe 5.3��Webcode5272

sie in geeigneter Weise codiert werden. In dieser Aufgabe geht es um die Codierung, dieTuring in seiner Arbeit aus dem Jahr 1936 vorgeschlagen hat.

Bewerten Sie die folgenden Aussagen: wahr falsch

� Jede natürliche Zahl ist die Gödelnummer einer Maschine.

� Die Codierung ist injektiv.

� Die Codierung ist surjektiv.

� Die Codierung ist bijektiv.

Wir haben gezeigt, dass sich eine Turing-Maschine oder eine Registermaschine auf zweiAufgabe 5.4��Webcode5543

Arten nutzen lässt: als Transduktor oder als Akzeptor. Für eine Funktion f : N→ N bedeutetdies das Folgende: Als Transduktor nimmt die Registermaschine x als Eingabe entgegen undproduziert y als Ausgabe. Als Akzeptor nimmt sie das Tupel (x,y) entgegen und akzeptiertdie Eingabe genau dann, wenn x und y die Beziehung f (x) = y erfüllen.

Ziel dieser Aufgabe ist es, einen Zusammenhang zwischen diesen Begriffen herzustellen.

a) Kann eine berechnende Maschine eine akzeptierende Maschine simulieren?

b) Kann eine akzeptierende Maschine eine berechnende Maschine simulieren?

In Abschnitt 5.1.2 haben Sie eine Registermaschine kennen gelernt, die von James P. JonesAufgabe 5.5��Webcode5781

und Yuri Matijasevic im Jahr 1991 entworfen wurde [100]. Hierbei handelte es sich um einenTransduktor, der in Register R1 die Eingabe x entgegennimmt und dort auch die Ausgabef (x) ablegt. Anhand des Ablaufprotokolls aus Abbildung 5.17 konnten Sie einen Eindruckgewinnen, wie sich die Maschine für den Fall R1 = 2 verhält. Nach 23 Schritten hielt sie anund hinterließ in R1 den Ergebniswert 1.

a) Vervollständigen Sie die nachstehende Liste, indem Sie den Ablauf für weitere Eingabensimulieren:

f (0) = , f (1) = , f (2) = 1 , f (3) = , f (4) = , f (5) =

b) Welche bekannte Zahlenfolge wird durch die Registermaschine berechnet?


Alle diskutierten Registermaschinen waren mit drei Sprungbefehlen ausgestattet: Aufgabe 5.6��

Webcode5696

� Li : goto Ln � Li : if R j = 0 goto Ln � Li : if R j �= 0 goto Ln

a) Ist es möglich, damit den folgenden erweiterten Sprungbefehl zu implementieren?

Li : if R j = 0 goto Ln else goto Lm

b) Ändert sich die Ausdrucksstärke des Maschinenmodells, wenn wir uns auf den Sprungbe-fehl Li : if R j = 0 goto Ln beschränken?

In dieser Aufgabe sollen Sie sich mit dem zellulären Automaten beschäftigen, der über das Aufgabe 5.7��

Webcode5742

folgende Regelschema definiert ist:

Zustand

LinkerNachbar

RechterNachbar

Folgezustand

Regel 1 Regel 2 Regel 3 Regel 4

Regel 5 Regel 6 Regel 7 Regel 8

Welche Ihnen bekannte Struktur wird durch diesen Automaten erzeugt? Vervollständigen Siezur Beantwortung dieser Frage das folgende Diagramm. Die ersten drei Zeilen sind bereitsausgefüllt.


In dieser Aufgabe geht es um die folgende Turing-Maschine:Aufgabe 5.8��Webcode5911

Q = {q1,q2,q3,q4,q5,q6}S = {0,1}I = {(q1,0,1,R,q2),(q2,0,1,R,q3),(q3,0,1,R,q4),(q4,0,1,L,q1),(q5,0,1,R,q6),

(q1,1,1,L,q3),(q2,1,1,R,q2),(q3,1,0,L,q5),(q4,1,1,L,q4),(q5,1,0,L,q1)}

a) Vervollständigen Sie den nachstehend abgedruckten Simulationslauf.

0 0 0 0 0 0 0 0 0 0

〈q1〉

0 0 0 0 1 0 0 0 0 0

〈q2〉

0 0 0 0 1 1 0 0 0 0

〈q3〉

〈__〉

〈__〉

〈__〉

〈__〉

〈__〉

〈__〉

〈__〉

〈__〉

〈__〉

〈__〉

〈__〉

〈__〉

〈__〉

〈__〉

〈__〉b) Recherchieren Sie, welche bekannte Turing-Maschine wir hier vor uns haben. Wird die

Maschine irgendwann terminieren?


In Definition 5.7 haben wir vereinbart, dass eine Menge N genau dann aufzählbar ist, wenn Aufgabe 5.9��

Webcode5800

eine surjektive und berechenbare Funktion f : N → N existiert. Welche Konsequenzenergeben sich, wenn wir die Forderung nach der Surjektivität durch die Forderung nach derBijektivität ersetzen?

In Abschnitt 5.3.2 haben Sie den Satz von Rice kennen gelernt. In einem Rundumschlag Aufgabe 5.10��

Webcode5932

macht er die Hoffnung zunichte, irgendeine nichttriviale Eigenschaft von Turing-Maschinenalgorithmisch zu entscheiden. Doch ist das wirklich so? Als Beispiel betrachten wir dieEigenschaft einer Maschine, exakt 5 Zustände zu besitzen. Mit einem Blick auf die In-struktionstabelle können wir diese Eigenschaft für jede vorgelegte Maschine immer korrektentscheiden. Aber genau dies dürfte nach dem Satz von Rice nicht möglich sein, odervielleicht doch?

In dieser Aufgabe betrachten wir die Formel Inst(qi,S j,Sk,L,ql) aus Abschnitt 5.4.1. Mit Aufgabe 5.11��

Webcode5193

ihr hat Turing in seiner Arbeit aus dem Jahr 1936 die Linksbewegung einer einseitigbeschränkten Turing-Maschine beschrieben:

Inst(qi,S j,Sk,L,ql) :=

∀ t ∀y ∀ t′ ∀y′ ((RSj(t,y)∧ I(t,y)∧Kqi(t)∧F(t, t′)∧F(y′,y))→ (I(t′,y′)∧RSk(t

′,y)∧Kql(t′)

∧ ∀z (F(y′,z) ∨M∧

i=0

(RSi(t,z)→ RSi(t′,z)))))

Auf Seite 274 haben wir festgelegt, wie sich eine solche Maschine verhält, wenn der Schreib-Lese-Kopf ganz links steht:

„Der Schreib-Lese-Kopf einer einseitig beschränkten Turing-Maschine kann sich nicht über das Bandende hinausbewegen.Eine angeforderte Linksbewegung wird in diesem Fall ignoriert,und der Schreib-Lese-Kopf verharrt in seiner Position.“

Offenbar ist die verbale Beschreibung in der Formel ϕI(x,y) überhaupt nicht umgesetzt.

a) Ist der Turing’sche Beweis etwa unvollständig?

b) Wie schwierig wäre es, die verbale Beschreibung in die Formel ϕI(x,y) zu integrieren?


In Abschnitt 5.4.2 haben wir herausgearbeitet, wie sich Turing-Maschinen arithmetisierenAufgabe 5.12��Webcode5892

lassen. In diesem Zusammenhang haben wir die PA-Formel ϕI(x,y) eingeführt, die den Über-gang von einer Konfiguration x in eine Konfiguration y beschreibt. Für die Linksbewegunglautetet sie beispielsweise so:

ϕI(x,y) := ∃h1 ∃h2 ∃n1 ∃n2(L(x) = n1∧K(x) = i∧ I(x) = h1∧Rh1(x) = j ∧L(y) = n2∧K(y) = l∧ I(y) = h2 ∧(h1 �= 0→ (

n1 = n2∧h1 = h2+1∧Rh1(y) = k ∧∀(h< n1) (h �= h1→∃s (Rh(x) = s∧Rh(y) = s)))) ∧

(h1 = 0→ (

n1+1 = n2∧R0(y) = 0∧h1 = h2∧R1(y) = k ∧∀(h< n1) (h �= 0→∃s (Rh(x) = s∧Rh+1(y) = s)))))

Wir hätten den Beweis vereinfachen können, indem wir ihn für einseitig beschränkte Turing-Maschinen führen. Wie würde die Formel dann aussehen?

Am Beispiel der diophantischen GleichungAufgabe 5.13��Webcode5970

(x+1)3 +(y+1)3 = (z+1)3

haben wir in Abschnitt 5.4.3 argumentiert, dass es einen Unterschied darstellt, ob wir nachLösungen in den ganzen Zahlen oder in den natürlichen Zahlen suchen.

a) Zeigen Sie, dass die Gleichung in den ganzen Zahlen unendlich viele Lösungen hat.

b) Warum ist die Gleichung in den natürlichen Zahlen unlösbar?

In Abschnitt 5.4.3 haben wir erarbeitet, wie sich diophantische Gleichungen konjunktiv oderAufgabe 5.14��Webcode5100

disjunktiv zusammenfassen lassen.

a) Welche Relationen werden durch die folgenden beiden Gleichungen repräsentiert?

a+ x+1−b = 0 ∨ b+ y+1−a = 0a+ x−b = 0 ∧ b+ y−a = 0

b) Formen Sie die Ausdrücke in gewöhnliche diophantische Gleichungen um.


R und S seien zwei diophantisch repräsentierbare Relationen. Aufgabe 5.15��

Webcode5651

a) Ist die Relation R∪S diophantisch repräsentierbar?

b) Ist die Relation R∩S diophantisch repräsentierbar?

In Abbildung 5.41 ist eine diophantische Gleichung mit 26 Unbekannten aufgeführt, die Aufgabe 5.16��

Webcode5999

genau dann eine Lösung in den positiven natürlichen Zahlen besitzt, wenn k + 2 einePrimzahl ist.

a) Kann diese Gleichung dazu verwendet werden, alle Primzahlen aufzuzählen?

b) Lässt sich die Menge aller Primzahlzwillinge ebenfalls diophantisch repräsentieren?

Das nachstehende Registermaschinenprogramm stammt aus der mehrfach zitierten Arbeit Aufgabe 5.17��

Webcode5156

von Jones und Matijasevic aus dem Jahr 1984 [99]:

L0 R2 ← R2 +1L1 R2 ← R2 +1L2 if R3 = 0 goto L5

L3 R3 ← R3−1L4 goto L2

L5 R3 ← R3 +1R4 ← R4 +1

R2 ← R2−1L6 if 0 < R2 goto L5

L7 R2 ← R2 +1R4 ← R4−1

L8 if 0 < R4 goto L7

L9 if R3 < R1 goto L5



L12 R1 ← R1−1R2 ← R2−1R3 ← R3−1

L13 if 0 < R1 goto L12

L14 stop

a) Mit Ri < R j wird eine Operation verwendet, die unser Registermaschinenmodell nicht vonHause aus unterstützt. Zeigen Sie, dass sich die Operationen mit den nativen Sprachele-menten nachbilden lassen.

b) Führen Sie das Programm für die Eingabe R1 = 2 händisch aus und erstellen Sie einAblaufdiagramm, das ähnlich aussieht wie jenes aus Abbildung 5.17. Beachten Sie, dassdie Programmausführung in Zeile L0 beginnt und nicht, wie bisher, in Zeile L1.

c) Stellen Sie für diese Berechnungssequenz die Daten- und Kontrollflussmatrix auf. Wieeine solche Matrix aussieht, wurde in Abbildung 5.43 gezeigt.

d) Wenn Sie die Registermaschine für verschiedene Eingabewerte starten, werden Sie fest-stellen, dass sie in manchen Fällen hält und in anderen für immer weiter rechnet. Versu-chen Sie, einen Zusammenhang zwischen dem Eingabewert und der Terminierungseigen-schaft herzustellen.


In Abschnitt 5.4.3.2 haben wir gezeigt, wie sich Registermaschinen diophantisch codierenAufgabe 5.18��Webcode5548

lassen. Die von uns konstruierte Gleichung enthielt unter anderem den Teilausdruck

L1 � I ∧ . . . ∧ Ll � I (5.33)

Er stellt sicher, dass L1, . . . ,Ll ausschließlich aus den Ziffern 0 und 1 besteht. Darüber hinaushatten wir über den Teilausdruck

I =l

∑i=1

Li (5.34)

erzwungen, dass in jeder Spalte der Kontrollflussmatrix höchstens eine 1 vorkommt. Aufden ersten Blick scheinen wir (5.33) gar nicht zu benötigen, da deren inhaltliche Aussageaugenscheinlich aus (5.34) folgt. Beweisen oder widerlegen Sie diese Vermutung.

Documents

Grenzen der Mathematik || Berechenbarkeitstheorie