powered by 
Ein Band, ein Kopf, der darauf liest und schreibt, und eine kleine Tabelle: Mehr braucht man nicht, um alles zu berechnen, was dein Computer berechnen kann. Du baust in Ruby oder Python Turingmaschinen, die Binärzahlen hochzählen, addieren und Wörter wie aaabbbccc prüfen, zählst ihre Schritte und findest mit einem Gedankenexperiment eine Frage, die kein Programm der Welt beantworten kann.
Bevor es um Begriffe geht, sieh einer Turingmaschine bei der Arbeit zu. Auf ihrem Band steht 1011, eine Zahl im Binärsystem. Schalte Schritt für Schritt weiter und achte darauf, wohin der violette Rahmen, ihr Kopf, auf dem Band wandert und was er hineinschreibt. Oben steht in jedem Schritt, was die Maschine liest (read), was sie schreibt (write) und wohin der Kopf geht (move): L heißt links, R rechts.
Schalte die Maschine oben bis zum Ende durch. 1011 ist im Binärsystem
die Zahl 11. Was macht die Maschine mit der Zahl auf ihrem Band?
Rechne aus, welche Zahl am Ende auf dem Band steht. Im Binärsystem sind die Stellen von rechts 1, 2, 4 und 8 wert.
Ein endlicher Automat merkt sich nur seinen Zustand. Ein Kellerautomat hat dazu einen Stack, aber auch er sieht immer nur dessen oberstes Zeichen. Wörter wie aaabbbccc, mit gleich vielen a, b und c, prüft darum keiner von beiden: Hat ein Kellerautomat beim Zählen der a seinen Stack gefüllt und beim Vergleichen mit den b wieder geleert, weiß er nicht mehr, wie viele c kommen müssen.
1936 fragte sich der britische Mathematiker Alan Turing, was »berechnen« überhaupt heißt. Seine Antwort war eine Maschine wie die, die du eben gesehen hast. Sie arbeitet wie ein Mensch mit Bleistift und Papier: Sie sieht auf ein Feld, schreibt etwas hinein, geht ein Feld weiter und merkt sich dabei nur, an welcher Stelle ihres Verfahrens sie gerade ist. Heute heißt sie Turingmaschine.
Alan Turing (1912–1954), britischer Mathematiker. Was einem endlichen Automaten fehlt, gab er 1936 seiner Turingmaschine: ein Band ohne Ende, auf dem sie lesen und schreiben kann. Was ein Computer berechnen kann, kann auch sie, und er bewies, dass es Fragen gibt, die keine Maschine beantworten kann.
Im Zweiten Weltkrieg half er in Bletchley Park, die verschlüsselten Funksprüche der deutschen Wehrmacht zu entziffern. Der wichtigste Preis der Informatik heißt nach ihm Turing Award.
Foto: um 1928, gemeinfrei, zugeschnitten (Wikimedia Commons)
Lege im Terminal (StrgJ) einen Ordner an und öffne ihn mit StrgK StrgO:
mkdir /workspace/turingmaschine
Alle Dateien dieser Aktivität kommen in diesen Ordner. Ein Programm startest du im Terminal mit ruby und dem Namen der Datei.
Alle Dateien dieser Aktivität kommen in diesen Ordner. Ein Programm startest du im Terminal mit python3 und dem Namen der Datei.
Die Maschine vom Anfang der Seite hat drei Teile. Ihr Band besteht aus Feldern und geht nach links und rechts ohne Ende weiter. In jedem Feld steht ein Zeichen; ein leeres Feld schreiben wir als _, wie die Felder links und rechts von 1011. Am Anfang steht die Eingabe auf dem Band, und der Kopf, der violette Rahmen, steht auf ihrem ersten Zeichen. Außerdem ist die Maschine in einem Zustand, am Anfang in q0, dem Kreis mit dem violetten Ring.
In jedem Schritt liest der Kopf das Zeichen unter sich. Zu ihrem Zustand und diesem Zeichen schlägt die Maschine in ihrer Tabelle nach, und dort stehen drei Angaben: welches Zeichen sie in das Feld schreibt, ob der Kopf ein Feld nach links (L) oder nach rechts (R) geht, und ihr neuer Zustand. Erreicht sie den Zustand qH, hält sie an, und was dann auf dem Band steht, ist ihr Ergebnis.
Die Maschine vom Anfang zählt 1 zu einer Binärzahl dazu. Im Bild steht an jedem Pfeil das gelesene Zeichen, hinter dem Schrägstrich das geschriebene und die Richtung; im Schritt-für-Schritt-Bild oben ist die Zeile violett, die gerade benutzt wird:
Lege plus_one.rb an:
# Eine Turingmaschine zählt 1 zu einer Binärzahl dazu. Sie hat ein Band aus # Feldern, einen Kopf, der auf einem Feld steht, und einen Zustand. _ ist # ein leeres Feld; das Band geht nach beiden Seiten ohne Ende weiter. START = 'q0' HALT = 'qH' # [Zustand, gelesenes Zeichen] => [was sie schreibt, wohin der Kopf geht # (L links, R rechts), neuer Zustand] TRANSITIONS = { # q0: nach rechts bis hinter die letzte Ziffer ['q0', '0'] => ['0', 'R', 'q0'], ['q0', '1'] => ['1', 'R', 'q0'], ['q0', '_'] => ['_', 'L', 'q1'], # q1: von hinten 1 dazu, mit Übertrag ['q1', '1'] => ['0', 'L', 'q1'], ['q1', '0'] => ['1', 'L', HALT], ['q1', '_'] => ['1', 'L', HALT], } # Das Band ab dem ersten bis zum letzten beschriebenen Feld, der Kopf in [ ] def show(tape, head) used = tape.keys.reject { |i| tape[i] == '_' } + [head] (used.min..used.max).map { |i| i == head ? "[#{tape[i]}]" : tape[i] }.join end def run(input, trace: false, max_steps: 1000) tape = Hash.new('_') input.each_char.with_index { |symbol, i| tape[i] = symbol } head = 0 state = START steps = 0 puts "#{state.ljust(3)} #{show(tape, head)}" if trace until state == HALT raise "Nach #{max_steps} Schritten hat die Maschine nicht angehalten." if steps == max_steps write, move, state = TRANSITIONS.fetch([state, tape[head]]) tape[head] = write head += move == 'R' ? 1 : -1 steps += 1 puts "#{state.ljust(3)} #{show(tape, head)}" if trace end used = tape.keys.reject { |i| tape[i] == '_' } used.empty? ? '' : (used.min..used.max).map { |i| tape[i] }.join end run('1011', trace: true) ['0', '1', '1011', '111'].each do |word| puts "#{word} → #{run(word)}" end
Das Band ist ein Hash von der Nummer des Feldes zum Zeichen darin. Hash.new('_') gibt für jedes Feld, in das noch nie etwas geschrieben wurde, _ zurück; so ist das Band ohne Ende, auch nach links, wo die Nummern negativ werden. run macht Schritte, bis die Maschine in HALT ist, und gibt dann das Band ohne die leeren Felder am Rand zurück. Mit trace: true zeigt es nach jedem Schritt den Zustand und das Band, den Kopf in eckigen Klammern. Nach max_steps Schritten gibt run auf.
Lege plus_one.py an:
# Eine Turingmaschine zählt 1 zu einer Binärzahl dazu. Sie hat ein Band aus # Feldern, einen Kopf, der auf einem Feld steht, und einen Zustand. _ ist # ein leeres Feld; das Band geht nach beiden Seiten ohne Ende weiter. START = 'q0' HALT = 'qH' # (Zustand, gelesenes Zeichen) -> (was sie schreibt, wohin der Kopf geht # (L links, R rechts), neuer Zustand) TRANSITIONS = { # q0: nach rechts bis hinter die letzte Ziffer ('q0', '0'): ('0', 'R', 'q0'), ('q0', '1'): ('1', 'R', 'q0'), ('q0', '_'): ('_', 'L', 'q1'), # q1: von hinten 1 dazu, mit Übertrag ('q1', '1'): ('0', 'L', 'q1'), ('q1', '0'): ('1', 'L', HALT), ('q1', '_'): ('1', 'L', HALT), } # Das Band ab dem ersten bis zum letzten beschriebenen Feld, der Kopf in [ ] def show(tape, head): used = [i for i in tape if tape[i] != '_'] + [head] return ''.join(f'[{tape.get(i, "_")}]' if i == head else tape.get(i, '_') for i in range(min(used), max(used) + 1)) def run(word, trace=False, max_steps=1000): tape = dict(enumerate(word)) head = 0 state = START steps = 0 if trace: print(f'{state:<3} {show(tape, head)}') while state != HALT: if steps == max_steps: raise RuntimeError(f'Nach {max_steps} Schritten hat die Maschine nicht angehalten.') write, move, state = TRANSITIONS[(state, tape.get(head, '_'))] tape[head] = write head += 1 if move == 'R' else -1 steps += 1 if trace: print(f'{state:<3} {show(tape, head)}') used = [i for i in tape if tape[i] != '_'] return ''.join(tape.get(i, '_') for i in range(min(used), max(used) + 1)) if used else '' run('1011', trace=True) for word in ['0', '1', '1011', '111']: print(f'{word} → {run(word)}')
Das Band ist ein dict von der Nummer des Feldes zum Zeichen darin. tape.get(i, '_') gibt für jedes Feld, in das noch nie etwas geschrieben wurde, _ zurück; so ist das Band ohne Ende, auch nach links, wo die Nummern negativ werden. run macht Schritte, bis die Maschine in HALT ist, und gibt dann das Band ohne die leeren Felder am Rand zurück. Mit trace=True zeigt es nach jedem Schritt den Zustand und das Band, den Kopf in eckigen Klammern. Nach max_steps Schritten gibt run auf.
Bevor du es startest: Die letzte Zeile lässt die Maschine auch auf 111 los.
Spiel die Maschine für 111 im Kopf durch, bevor du sie startest: Was
steht auf dem Band, wenn sie in qH angehalten hat?
q0 läuft nach rechts bis hinter die letzte Ziffer. Dann ist q1 dran, von rechts nach links: Jede 1 wird zu 0, und der Kopf geht weiter nach links.
Hier geht es weiter, sobald du deine Antwort oben abgegeben hast.
Starte es mit ruby plus_one.rb:
Starte es mit python3 plus_one.py:
q0 [1]011 q0 1[0]11 q0 10[1]1 q0 101[1] q0 1011[_] q1 101[1] q1 10[1]0 q1 1[0]00 qH [1]100 0 → 1 1 → 10 1011 → 1100 111 → 1000
In q0 läuft der Kopf nach rechts, ohne etwas zu ändern, bis er auf dem leeren Feld hinter der Zahl steht. Dann rechnet q1 von hinten, wie du schriftlich addierst: Aus einer 1 wird 0 mit Übertrag, und der Kopf geht weiter nach links; die erste 0 wird zu 1, und die Maschine hält. Bei 111 gibt es keine 0, und die 1 landet auf dem leeren Feld vor der Zahl.
trace auf 0111 laufen statt auf 1011. Achte darauf, auf welchem Feld sie die 1 schreibt und ob die Zahl danach länger ist als vorher.
Kopiere plus_one.rb nach minus_one.rb und ändere die Übergänge so,
dass die Maschine 1 von einer Binärzahl abzieht, die größer als 0 ist:
Aus 1100 wird 1011. Eine 0 vorne darf stehen bleiben, aus 1000 darf
0111 werden. Die Prüfung ruft run mit eigenen Zahlen auf.
Zieh von Hand ab, wie in der Schule: 1100 − 1. Von hinten gelesen, was
passiert mit jeder 0, und was mit der ersten 1?
q0 bleibt, wie es ist: Er läuft zum Ende der Zahl. Nur die Zeilen von q1 ändern sich. Eine 0 wird zu 1, und der Kopf geht weiter nach links; eine 1 wird zu 0, und die Maschine hält. Ein leeres Feld erreicht sie bei einer Zahl größer als 0 nie.
Ein Gerüst für q1:
['q1', '0'] => ['1', 'L', ...], ['q1', '1'] => ['0', 'L', ...],
Kopiere plus_one.py nach minus_one.py und ändere die Übergänge so,
dass die Maschine 1 von einer Binärzahl abzieht, die größer als 0 ist:
Aus 1100 wird 1011. Eine 0 vorne darf stehen bleiben, aus 1000 darf
0111 werden. Die Prüfung ruft run mit eigenen Zahlen auf.
Zieh von Hand ab, wie in der Schule: 1100 − 1. Von hinten gelesen, was
passiert mit jeder 0, und was mit der ersten 1?
q0 bleibt, wie es ist: Er läuft zum Ende der Zahl. Nur die Zeilen von q1 ändern sich. Eine 0 wird zu 1, und der Kopf geht weiter nach links; eine 1 wird zu 0, und die Maschine hält. Ein leeres Feld erreicht sie bei einer Zahl größer als 0 nie.
Ein Gerüst für q1:
('q1', '0'): ('1', 'L', ...), ('q1', '1'): ('0', 'L', ...),
Turingmaschinen rechnen nicht nur mit Binärzahlen. Am einfachsten ist es mit Strichlisten, wie beim Zählen von Stimmen an der Tafel: 111 ist 3. Schreibt man zwei davon mit einem + dazwischen auf das Band, kann eine Maschine sie addieren.
Eine Zahl als Strichliste ist eine Reihe von 1: 111 ist 3, 11 ist 2.
Kopiere plus_one.rb nach add.rb und schreib neue Übergänge: Auf dem
Band stehen zwei Strichlisten mit + dazwischen, am Ende steht nur noch
ihre Summe als Strichliste. Aus 111+11 wird 11111. Die Prüfung ruft
run auf, auch mit +11 und 11+, wo eine Zahl 0 ist.
Was muss sich auf dem Band ändern, damit aus 111+11 die Strichliste
11111 wird? Es sind genau zwei Felder.
Das + wird zu einer 1. Dann ist eine 1 zu viel da, und die letzte 1
ganz rechts wird zu _. Dafür läuft die Maschine bis hinter das Ende,
geht einen Schritt zurück und löscht.
Ein Gerüst; zwei Zeilen fehlen:
TRANSITIONS = { # q0: über die erste Zahl, das + wird zu 1 ['q0', '1'] => ['1', 'R', 'q0'], ['q0', '+'] => ..., # q1: über die zweite Zahl bis hinter das Ende ['q1', '1'] => ['1', 'R', 'q1'], ['q1', '_'] => ['_', 'L', 'q2'], # q2: die letzte 1 löschen ['q2', '1'] => ..., }
Eine Zahl als Strichliste ist eine Reihe von 1: 111 ist 3, 11 ist 2.
Kopiere plus_one.py nach add.py und schreib neue Übergänge: Auf dem
Band stehen zwei Strichlisten mit + dazwischen, am Ende steht nur noch
ihre Summe als Strichliste. Aus 111+11 wird 11111. Die Prüfung ruft
run auf, auch mit +11 und 11+, wo eine Zahl 0 ist.
Was muss sich auf dem Band ändern, damit aus 111+11 die Strichliste
11111 wird? Es sind genau zwei Felder.
Das + wird zu einer 1. Dann ist eine 1 zu viel da, und die letzte 1
ganz rechts wird zu _. Dafür läuft die Maschine bis hinter das Ende,
geht einen Schritt zurück und löscht.
Ein Gerüst; zwei Zeilen fehlen:
TRANSITIONS = { # q0: über die erste Zahl, das + wird zu 1 ('q0', '1'): ('1', 'R', 'q0'), ('q0', '+'): ..., # q1: über die zweite Zahl bis hinter das Ende ('q1', '1'): ('1', 'R', 'q1'), ('q1', '_'): ('_', 'L', 'q2'), # q2: die letzte 1 löschen ('q2', '1'): ..., }
Die Sprache anbncn, alle Wörter aus einer Reihe a, gleich vielen b und gleich vielen c, prüft kein Kellerautomat. Eine Turingmaschine kann es, weil sie auf ihr Band schreiben und darauf hin und her laufen kann. Sie streicht in jeder Runde ein a, ein b und ein c durch, indem sie X, Y und Z darüber schreibt, und läuft zurück zum Anfang. Ist kein a mehr übrig, darf auch kein b und kein c mehr übrig sein.
Diese Maschine hält auf zwei Arten an: im Zustand qJ (»ja«), wenn sie das Wort annimmt, oder wenn es für ihren Zustand und das gelesene Zeichen keinen Übergang gibt; dann lehnt sie es ab.
Lege anbncn.rb an. show ist dasselbe wie in plus_one.rb:
# Eine Turingmaschine prüft a^n b^n c^n: erst n-mal a, dann n-mal b, dann # n-mal c. In jeder Runde streicht sie ein a, ein b und ein c durch (X, Y, # Z). Steht kein a mehr da, prüft sie, dass auch nichts anderes übrig ist. START = 'q0' ACCEPT = 'qJ' TRANSITIONS = { # q0: das nächste a durchstreichen; keins mehr: zur Prüfung ['q0', 'a'] => ['X', 'R', 'q1'], ['q0', 'Y'] => ['Y', 'R', 'q4'], ['q0', '_'] => ['_', 'R', ACCEPT], # q1: nach rechts zum ersten b, durchstreichen ['q1', 'a'] => ['a', 'R', 'q1'], ['q1', 'Y'] => ['Y', 'R', 'q1'], ['q1', 'b'] => ['Y', 'R', 'q2'], # q2: weiter zum ersten c, durchstreichen ['q2', 'b'] => ['b', 'R', 'q2'], ['q2', 'Z'] => ['Z', 'R', 'q2'], ['q2', 'c'] => ['Z', 'L', 'q3'], # q3: zurück bis hinter das letzte X ['q3', 'a'] => ['a', 'L', 'q3'], ['q3', 'b'] => ['b', 'L', 'q3'], ['q3', 'Y'] => ['Y', 'L', 'q3'], ['q3', 'Z'] => ['Z', 'L', 'q3'], ['q3', 'X'] => ['X', 'R', 'q0'], # q4: hinter den a nur noch Y und Z ['q4', 'Y'] => ['Y', 'R', 'q4'], ['q4', 'Z'] => ['Z', 'R', 'q4'], ['q4', '_'] => ['_', 'L', ACCEPT], } # Das Band ab dem ersten bis zum letzten beschriebenen Feld, der Kopf in [ ] def show(tape, head) used = tape.keys.reject { |i| tape[i] == '_' } + [head] (used.min..used.max).map { |i| i == head ? "[#{tape[i]}]" : tape[i] }.join end # Nimmt die Maschine das Wort an? Ohne passenden Übergang hält sie und # lehnt ab. steps zählt die Schritte bis dahin. def accepts(word, trace: false) tape = Hash.new('_') word.each_char.with_index { |symbol, i| tape[i] = symbol } head = 0 state = START steps = 0 puts "#{state} #{show(tape, head)}" if trace while state != ACCEPT move = TRANSITIONS[[state, tape[head]]] break if move.nil? write, direction, state = move tape[head] = write head += direction == 'R' ? 1 : -1 steps += 1 puts "#{state} #{show(tape, head)}" if trace end puts "#{steps} Schritte" if trace state == ACCEPT end accepts('aabbcc', trace: true) ['abc', 'aabbcc', 'aabbc', 'abcabc', ''].each do |word| puts "#{word.inspect} #{accepts(word)}" end
Lege anbncn.py an. show ist dasselbe wie in plus_one.py:
# Eine Turingmaschine prüft a^n b^n c^n: erst n-mal a, dann n-mal b, dann # n-mal c. In jeder Runde streicht sie ein a, ein b und ein c durch (X, Y, # Z). Steht kein a mehr da, prüft sie, dass auch nichts anderes übrig ist. START = 'q0' ACCEPT = 'qJ' TRANSITIONS = { # q0: das nächste a durchstreichen; keins mehr: zur Prüfung ('q0', 'a'): ('X', 'R', 'q1'), ('q0', 'Y'): ('Y', 'R', 'q4'), ('q0', '_'): ('_', 'R', ACCEPT), # q1: nach rechts zum ersten b, durchstreichen ('q1', 'a'): ('a', 'R', 'q1'), ('q1', 'Y'): ('Y', 'R', 'q1'), ('q1', 'b'): ('Y', 'R', 'q2'), # q2: weiter zum ersten c, durchstreichen ('q2', 'b'): ('b', 'R', 'q2'), ('q2', 'Z'): ('Z', 'R', 'q2'), ('q2', 'c'): ('Z', 'L', 'q3'), # q3: zurück bis hinter das letzte X ('q3', 'a'): ('a', 'L', 'q3'), ('q3', 'b'): ('b', 'L', 'q3'), ('q3', 'Y'): ('Y', 'L', 'q3'), ('q3', 'Z'): ('Z', 'L', 'q3'), ('q3', 'X'): ('X', 'R', 'q0'), # q4: hinter den a nur noch Y und Z ('q4', 'Y'): ('Y', 'R', 'q4'), ('q4', 'Z'): ('Z', 'R', 'q4'), ('q4', '_'): ('_', 'L', ACCEPT), } # Das Band ab dem ersten bis zum letzten beschriebenen Feld, der Kopf in [ ] def show(tape, head): used = [i for i in tape if tape[i] != '_'] + [head] return ''.join(f'[{tape.get(i, "_")}]' if i == head else tape.get(i, '_') for i in range(min(used), max(used) + 1)) # Nimmt die Maschine das Wort an? Ohne passenden Übergang hält sie und # lehnt ab. steps zählt die Schritte bis dahin. def accepts(word, trace=False): tape = dict(enumerate(word)) head = 0 state = START steps = 0 if trace: print(state, show(tape, head)) while state != ACCEPT: move = TRANSITIONS.get((state, tape.get(head, '_'))) if move is None: break write, direction, state = move tape[head] = write head += 1 if direction == 'R' else -1 steps += 1 if trace: print(state, show(tape, head)) if trace: print(steps, 'Schritte') return state == ACCEPT accepts('aabbcc', trace=True) for word in ['abc', 'aabbcc', 'aabbc', 'abcabc', '']: print(repr(word), accepts(word))
Starte es und lies die Spur mit: Wo steht der Kopf, wenn ein b durchgestrichen wird, und wie weit läuft er danach zurück? Am Ende der Spur steht, wie viele Schritte die Maschine für aabbcc gebraucht hat: 23.
trace auf aabbbcc laufen, mit einem b zu viel. Achte darauf, in welchem Zustand und auf welchem Zeichen sie stehen bleibt, und such in TRANSITIONS, warum es dafür keinen Übergang gibt.
Für aabbcc braucht die Maschine 23 Schritte. Wie viele braucht sie
ungefähr für aaaabbbbcccc, das doppelt so lang ist?
Hier geht es weiter, sobald du deine Antwort oben abgegeben hast.
Jede Runde streicht ein a durch, also gibt es so viele Runden, wie a da sind. In jeder Runde läuft der Kopf vom durchgestrichenen a bis zum nächsten c und zurück, und dieser Weg wird mit dem Wort länger. Doppelt so viele Runden, jede etwa doppelt so lang: Für aaaabbbbcccc sind es 77 Schritte, gut dreimal so viele, und je länger das Wort, desto näher kommt das Verhältnis an viermal. Turingmaschinen sind nicht schnell, und darum geht es auch nicht. Es geht darum, ob sie etwas überhaupt können.
Wie viele Schritte braucht die Maschine für aaabbbccc? Lass sie es dir
sagen.
Eine Turingmaschine ist sehr einfach: ein Band, ein Kopf, eine Tabelle. Trotzdem kann man mit ihr alles berechnen, was dein Computer berechnen kann. Man kann sogar eine einzige Turingmaschine bauen, die die Tabelle einer anderen Maschine vom Band liest und dann tut, was diese tun würde. Turing nannte sie die universelle Maschine. Dein Computer, der jedes Programm ausführt, das man ihm gibt, folgt derselben Idee: Das Programm ist für ihn nur ein Text im Speicher.
Fast gleichzeitig mit Turing beschrieb der amerikanische Mathematiker Alonzo Church das Berechnen auf eine ganz andere Art, nur mit Funktionen (dem Lambda-Kalkül), und beide Wege können genau dasselbe. Dass jedes Verfahren, das man überhaupt Schritt für Schritt ausführen kann, auch eine Turingmaschine ausführen kann, heißt Church-Turing-These: Beweisen kann man sie nicht, weil »Verfahren« kein mathematischer Begriff ist, aber jedes Modell vom Rechnen, das seitdem jemand erfunden hat, kann nicht mehr als eine Turingmaschine.
On Computable Numbers, with an Application to the Entscheidungsproblem, Alan Turing, Proceedings of the London Mathematical Society, 1936. Der Aufsatz, in dem Turing seine Maschine beschreibt, die universelle Maschine baut und zeigt, dass manche Fragen keine Maschine beantworten kann; die ersten Seiten lesen sich gut, ab der Mitte wird es Mathematik: bei der London Mathematical Society, als PDF.
Alle Maschinen bisher hielten irgendwann an. Das muss nicht so sein.
Angenommen, in plus_one führt der Übergang für q0 und _
nicht mehr nach links in q1, sondern zu '_', 'R', 'q0': Auf
einem leeren Feld geht die Maschine nach rechts und bleibt in
q0. Was passiert bei run('1')?
Hier geht es weiter, sobald du deine Antwort oben abgegeben hast.
Probier es aus: Ändere den Übergang in deiner plus_one-Datei und starte sie. Die Maschine läuft über leere Felder nach rechts, Schritt für Schritt, ohne Ende. Dass run nach 1000 Schritten aufgibt, ist keine Antwort auf die Frage, ob sie je anhält: Vielleicht hätte sie nach 1001 Schritten angehalten. Setz den Übergang danach wieder auf L und q1.
Ein Programm, das sich aufhängt, ist ärgerlich. Wäre es nicht praktisch, wenn ein Werkzeug vorher sagen könnte, ob ein Programm anhält? Stell dir vor, jemand hätte es geschrieben: eine Funktion halts(program), die jedes Programm ansieht, ohne es zu starten, und immer richtig true oder false antwortet, je nachdem, ob es anhält. Mit ihr schreibst du dieses Programm:
def paradox if halts(method(:paradox)) loop {} # ohne Ende end end
def paradox(): if halts(paradox): while True: # ohne Ende pass
paradox fragt halts über sich selbst und tut dann das Gegenteil von dem, was halts sagt.
Angenommen, es gäbe halts(program), die für jedes Programm richtig
sagt, ob es anhält. Was antwortet halts(paradox)?
Hier geht es weiter, sobald du deine Antwort oben abgegeben hast.
Was auch immer halts über paradox sagt, paradox macht es falsch. Also kann es halts nicht geben, egal wie klug man es programmiert. Das ist das Halteproblem, und es war Turings Antwort auf eine Frage seiner Zeit: Es gibt Fragen, die genau gestellt sind und eine Antwort Ja oder Nein haben, die aber kein Verfahren für jede Eingabe beantworten kann. Werkzeuge, die vor Endlosschleifen warnen, gibt es trotzdem; sie finden manche, aber nie alle.
