[ Impressum ] [ Datenschutzerklärung ] [ Kontakt ]

[

]

Turing-Maschine

Keine Grundlagen-Vorlesung der Informatik kommt ohne eine Erwähnung der Turing-Maschine aus.

Martín Ugarte hat einen sehr schönen programmierbaren Simulator für Turing-Maschinen geschrieben, der Studenten einen ganz praktischen Zugang zu diesem ansonsten eher theoretischen Thema ermöglicht.

Falls Sie die Vorlesung "Grundlagen der Informatik" an der HFT Stuttgart hören, finden Sie hier neben den dort bereits erläuterten Beispielen weitere Programme zur Vertiefung der Thematik und für eigene Experimente.

Eine Anleitung erklärt Ihnen die Bedienung der Seiten in diesem Web-Auftritt, in den Einstellungen können Sie deren Verhalten anpassen.

Programmierung

Ein Programm für den Turing-Simulator besteht aus einem Vorspann und einer Serie von Definitionen für die Zustandsübergänge der Turing-Maschine.

Der Vorspann definiert den Progammnamen sowie die Namen des Initialzustandes und der "akzeptablen" Endzustände. Befindet sich die Turing-Maschine am Ende eines Programmes (d.h., wenn kein passender Zustandsübergang mehr gefunden werden kann) in einem der genannten Endzustände, gilt das Programm als "akzeptiert" (d.h. fehlerfrei durchgelaufen) - ansonsten ist ein Fehler aufgetreten.

name: Programmname
init: Name des Initialzustandes
accept: Name eines Endzustandes, ..., evtl. weitere Namen

Die Definition eines Zustandsüberganges besteht aus jeweils zwei Zeilen:

die erste Zeile definiert den Namen des Zustandes und das Symbol, das vom Speicherband gelesen werden muss, damit der gerade zu definierende Zustandsübergang stattfinden kann
die zweite Zeile legt den Namen des Zielzustandes fest, gibt das in die aktuelle Zelle des Speicherbandes zu schreibende Symbol vor und definiert, in welche Richtung der Schreib-/Lesekopf anschließend zu bewegen ist

Name des aktuellen Zustandes,zu lesendes Symbol (oder _ für eine leere Zelle)
Name des Zielzustandes,zu schreibendes Symbol,Bewegung des Schreib-/Lesekopfes

Folgende Bewegungen kann der Schreib-/Lesekopf ausführen

< - ein Feld nach links
> - ein Feld nach rechts
- - Verharren auf demselben Feld

Zeilen, die mit einem doppelten Schrägstrich beginnen, gelten als Kommentarzeilen und werden ignoriert. Leerzeilen werden ebenfalls übersprungen:

// Kommentarzeile

Vorgehensweise

Im einfachsten Fall wird der Programm-Quelltext in das Eingabefeld des Turing-Simulators eingetippt (oder dort hinein kopiert) und mit einem Klick auf die grüne "Compile"-Taste übersetzt.

Nach einer erfolgreichen Übersetzung erscheint die Bedienoberfläche des Simulators oberhalb des Eingabefeldes - anderenfalls wird dort der erste gefundene Übersetzungsfehler angezeigt.

Über die Bedienoberfläche lässt sich das Speicherband vorbelegen (mit je einem Zeichen pro Feld, wie links von "Load" eingegeben) und der Simulator steuern.

Nota bene: Sie müssen "Load" auch anklicken, wenn Sie das Speicherband nicht vorbelegen, sondern leer lassen wollen

und so sieht es aus

Abb. 1: Bedienoberfläche des Turing-Simulators

Ein paar Beispiele für Turing-Programme

Zunächst sind die Beispiele noch trivial, werden jedoch sukzessive komplizierter. Spätere Beispiele bauen meist auf vorangehenden (einfacheren) auf.

ein (fast) leeres Programm (um Übersetzer und Simulator zu testen)

Quelltext

name: just an (almost) empty program
init: qInit
accept: qAccept

qInit,_
qAccept,_,-

Überspringen einer einzelnen "0"
Das Überspringen von Feldern auf dem Speicherband gehört zu den häufigsten Aktionen in Turing-Programmen
Quelltext
```
name: skip a single zero
init: q0
accept: q1

q0,0
q1,0,>
```
Zustandsdiagramm

Abb. 2: Zustandsdiagramm

Überspringen aller folgenden "0"
Quelltext
```
name: skip all zeros
init: q0
accept: q0

q0,0
q0,0,>
```
Zustandsdiagramm

Abb. 3: Zustandsdiagramm

Überspringen eines einzelnen Bit
Ein "Bit" sei hier ein Feld auf dem Speicherband mit dem Inhalt "0" oder "1"
Quelltext
```
name: skip a single bit
init: q0
accept: q1

q0,0
q1,0,>

q0,1
q1,1,>
```
Zustandsdiagramm

Abb. 4: Zustandsdiagramm

Überspringen aller folgenden Bits
Quelltext
```
name: skip all bits
init: q0
accept: q0

q0,0
q0,0,>

q0,1
q0,1,>
```
Zustandsdiagramm

Abb. 5: Zustandsdiagramm

Invertieren eines einzelnen Bit
Quelltext
```
name: invert a single bit
init: q0
accept: q1

q0,0
q1,1,>

q0,1
q1,0,>
```
Zustandsdiagramm

Abb. 6: Zustandsdiagramm

Invertieren aller folgenden Bits
Laden Sie das Speicherband mit einer Bitfolge (d.h. einer Folge von "0" und "1") und sehen Sie der Turing-Maschine dabei zu, wie sie diese Bit für Bit invertiert
Quelltext
```
name: invert all bits
init: q0
accept: q0

q0,0
q0,1,>

q0,1
q0,0,>
```
Zustandsdiagramm

Abb. 7: Zustandsdiagramm

Schreiben eines Paritätsbits
Dies ist das Beispiel aus der Vorlesung: laden Sie das Speicherband mit einer Bitfolge (d.h. einer Folge von "0" und "1") und sehen Sie der Turing-Maschine dabei zu, wie sie ein Paritätsbit hinzufügt
Quelltext
```
name: Parity Bit Generator
init: qEvenParity
accept: qAccept

qEvenParity,0
qEvenParity,0,>

qEvenParity,1
qOddParity,1,>

qEvenParity,_
qAccept,0,-

qOddParity,0
qOddParity,0,>

qOddParity,1
qEvenParity,1,>

qOddParity,_
qAccept,1,-
```

Rechts-Schieben eines einzelnen Bit

Quelltext

name: shift a single bit to the right
init: q0
accept: q3

q0,0
q1,_,>

q1,_
q3,0,>

q0,1
q2,_,>

q2,_
q3,1,>

Zustandsdiagramm

Abb. 8: Zustandsdiagramm

Rechts-Schieben aller folgenden Bits

Quelltext

name: shift all bits to the right
init: q0
accept: q3

q0,0
q1,_,>

q0,1
q2,_,>

q1,0
q1,0,>

q1,1
q2,0,>

q1,_
q3,0,>

q2,0
q1,1,>

q2,1
q2,1,>

q2,_
q3,1,>

Zustandsdiagramm

Abb. 9: Zustandsdiagramm

Links-Schieben eines einzelnen Bit

Quelltext

name: shift a single bit to the left
init: q0
accept: q3

q0,0
q1,_,<

q1,_
q3,0,<

q0,1
q2,_,<

q2,_
q3,1,<

Zustandsdiagramm

Abb. 10: Zustandsdiagramm

Links-Schieben aller folgenden Bits
Dieses Beispiel ist keine spiegelbildliche Kopie des Programmes für ein Verschieben mehrerer Bits nach rechts, sondern arbeitet die Bitfolge ebenfalls von links nach rechts ab
Quelltext
```
name: shift all bits to the left
init: q0
accept: q0

q0,0
q1,_,<

q0,1
q3,_,<

q1,_
q2,0,>

q2,_
q0,_,>

q3,_
q2,1,>
```
Zustandsdiagramm

Abb. 11: Zustandsdiagramm

Inkrementieren einer einstelligen Binärzahl
Laden Sie das Speicherband mit einer einzelnen "0" oder "1", das Programm wird dieses Binärzahl um 1 erhöhen
Quelltext
```
name: increment a single bit
init: q0
accept: q1

q0,0
q1,1,<

q0,1
q2,0,<

q2,_
q1,1,<
```
Zustandsdiagramm

Abb. 12: Zustandsdiagramm

Inkrementieren einer mehrstelligen Binärzahl
Dieses Programm inkrementiert eine beliebige, auf das Speicherband geschriebene Binärzahl
Quelltext
```
name: increment a binary number
init: q0
accept: q3

q0,0
q0,0,>

q0,1
q0,1,>

q0,_
q1,_,<

q1,0
q2,1,<

q1,1
q1,0,<

q1,_
q3,1,<

q2,0
q2,0,<

q2,1
q2,1,<

q2,_
q3,_,-
```
Zustandsdiagramm

Abb. 13: Zustandsdiagramm

Bilden des 2er-Komplementes für eine gegebene Binärzahl
Laden Sie das Speicherband mit einer beliebigen Binärzahl und verfolgen Sie, wie die Turing-Maschine das 2er-Komplement dieser Zahl bildet
Quelltext
```
name: compute 2th complement
init: q0
accept: q1,q2

q0,0
q0,1,>

q0,1
q0,0,>

q0,_
q1,_,<

q1,0
q2,1,<

q1,1
q1,0,<

q2,0
q2,0,<

q2,1
q2,1,<
```
Zustandsdiagramm

Abb. 14: Zustandsdiagramm

Bitweise konjunktive Verknüpfung zweier Bitfolgen
Laden Sie das Speicherband mit zwei beliebigen (aber gleich langen) Bitfolgen und lassen Sie dazwischen genau ein Feld frei - im Turing-Simulator erreichen Sie dies durch einen Unterstrich ("_"), ein Leerzeichen wird als Eingabe nicht akzeptiert. Die Turing-Maschine wird hinter der zweiten Bitfolge eine bitweise konjunktive Verknüpfung Ihrer Eingaben auf das Band schreiben.
Quelltext
```
name: compute conjunction of two bit sequences
init: q0
accept: q0

q0,0
q1,.,>

q0,1
q5,.,>

q1,0
q1,0,>

q1,1
q1,1,>

q1,_
q2,_,>

q2,.
q2,.,>

q2,0
q3,.,>

q2,1
q3,.,>

q3,0
q3,0,>

q3,1
q3,1,>

q3,_
q4,_,>

q4,0
q4,0,>

q4,1
q4,1,>

q4,_
q9,0,<

q5,0
q5,0,>

q5,1
q5,1,>

q5,_
q6,_,>

q6,.
q6,.,>

q6,0
q3,.,>

q6,1
q7,.,>

q7,0
q7,0,>

q7,1
q7,1,>

q7,_
q8,_,>

q8,0
q8,0,>

q8,1
q8,1,>

q8,_
q9,1,<

q9,0
q9,0,<

q9,1
q9,1,<

q9,_
q10,_,<

q10,0
q10,0,<

q10,1
q10,1,<

q10,.
q10,.,<

q10,_
q11,_,<

q11,0
q11,0,<

q11,1
q11,1,<

q11,.
q0,.,>
```
Zustandsdiagramm

Abb. 15: Zustandsdiagramm

Bitweise disjunktive Verknüpfung zweier Bitfolgen
Laden Sie das Speicherband mit zwei beliebigen (aber gleich langen) Bitfolgen und lassen Sie dazwischen genau ein Feld frei - im Turing-Simulator erreichen Sie dies durch einen Unterstrich ("_"), ein Leerzeichen wird als Eingabe nicht akzeptiert. Die Turing-Maschine wird hinter der zweiten Bitfolge eine bitweise disjunktive Verknüpfung Ihrer Eingaben auf das Band schreiben.
Quelltext
```
name: compute disjunction of two bit sequences
init: q0
accept: q0

q0,1
q1,.,>

q0,0
q5,.,>

q1,0
q1,0,>

q1,1
q1,1,>

q1,_
q2,_,>

q2,.
q2,.,>

q2,0
q3,.,>

q2,1
q3,.,>

q3,0
q3,0,>

q3,1
q3,1,>

q3,_
q4,_,>

q4,0
q4,0,>

q4,1
q4,1,>

q4,_
q9,1,<

q5,0
q5,0,>

q5,1
q5,1,>

q5,_
q6,_,>

q6,.
q6,.,>

q6,1
q3,.,>

q6,0
q7,.,>

q7,0
q7,0,>

q7,1
q7,1,>

q7,_
q8,_,>

q8,0
q8,0,>

q8,1
q8,1,>

q8,_
q9,0,<

q9,0
q9,0,<

q9,1
q9,1,<

q9,_
q10,_,<

q10,0
q10,0,<

q10,1
q10,1,<

q10,.
q10,.,<

q10,_
q11,_,<

q11,0
q11,0,<

q11,1
q11,1,<

q11,.
q0,.,>
```
Zustandsdiagramm

Abb. 16: Zustandsdiagramm

Addition zweier vorzeichenloser Binärzahlen
Laden Sie das Speicherband mit zwei beliebigen (aber gleich langen) vorzeichenlosen Binärzahlen und lassen Sie dazwischen genau ein Feld frei - im Turing-Simulator erreichen Sie dies durch einen Unterstrich ("_"), ein Leerzeichen wird als Eingabe nicht akzeptiert. Die Turing-Maschine wird die Summe Ihrer Eingaben hinter der zweiten Zahl auf das Band schreiben - sofern die Anzahl der von Ihnen vorgegebenen Bits dafür ausreicht.
Das Programm geht dabei etwas anders vor als Sie es von der Vorlesung her gewohnt sind: die beiden Zahlen werden bitweise von links nach rechts aufsummiert und evtl. Stellenüberträge sofort eingepflegt - auf diese Weise kann ein finaler Überlauf u.U. schon recht früh während der Berechnung erkannt werden.
Quelltext
```
name: compute the sum of two binary numbers
init: q0
accept: q0

q0,0
q1,.,>

q0,1
q8,.,>

q1,0
q1,0,>

q1,1
q1,1,>

q1,_
q2,_,>

q2,.
q2,.,>

q2,0
q3,.,>

q2,1
q10,.,>

q3,0
q3,0,>

q3,1
q3,1,>

q3,_
q4,_,>

q4,0
q4,0,>

q4,1
q4,1,>

q4,_
q5,0,<

q5,0
q5,0,<

q5,1
q5,1,<

q5,_
q6,_,<

q6,0
q6,0,<

q6,1
q6,1,<

q6,.
q6,.,<

q6,_
q7,_,<

q7,0
q7,0,<

q7,1
q7,1,<

q7,.
q0,.,>

q8,0
q8,0,>

q8,1
q8,1,>

q8,_
q9,_,>

q9,.
q9,.,>

q9,0
q10,.,>

q9,1
q12,.,>

q10,0
q10,0,>

q10,1
q10,1,>

q10,_
q11,_,>

q11,0
q11,0,>

q11,1
q11,1,>

q11,_
q5,1,<

q12,0
q12,0,>

q12,1
q12,1,>

q12,_
q13,_,>

q13,0
q13,0,>

q13,1
q13,1,>

q13,_
q14,0,<

q14,0
q5,1,<

q14,1
q14,0,<
```
Zustandsdiagramm

Abb. 17: Zustandsdiagramm

Addition zweier vorzeichenloser Binärzahlen (nach Coors)
Falls Sie meine Vorlesung "Grundlagen der Informatik" hören, finden Sie in den Folien von Prof. Coors ein anderes Turing-Programm zur Addition von Binärzahlen.
1. Wandeln Sie das Zustandsdiagramm aus den Folien von Prof. Coors in ein Programm für den Simulator um
  Nota bene: das Programm von Prof. Coors startet die Addition mitten auf dem Speicherband (was im Allgemeinen vollkommen zulässig ist). Damit der Simulator damit jedoch etwas anfangen kann, muss der Schreib-/Lesekopf durch folgende Anfangszeilen erst an diese Position bewegt werden:
```
qPre,0
qPre,0,>

qPre,1
qPre,1,>

qPre,_
q1,_,>
```
  Der neue Anfangszustand ist also nicht mehr q0, sondern qPre
  Quelltext (zur Kontrolle)
```
name: compute the sum of two binary numbers
init: qPre
accept: q8

qPre,0
qPre,0,>

qPre,1
qPre,1,>

qPre,_
q1,_,>

q0,_
q1,_,>

q1,0
q1,0,>

q1,1
q2,1,>

q1,_
q3,_,<

q2,0
q2,0,>

q2,1
q2,1,>

q2,_
q4,_,<

q3,0
q3,_,<

q3,_
q8,_,<

q4,0
q4,1,<

q4,1
q5,0,<

q5,0
q5,0,<

q5,1
q5,1,<

q5,_
q6,_,<

q6,0
q7,1,>

q6,1
q6,0,<

q6,_
q7,1,>

q7,0
q7,0,>

q7,1
q7,1,>

q7,_
q1,_,>
```
2. Testen Sie das Programm mit der Eingabe "1001_100"
  (wie führt das Programm die Addition durch?)

Fleissige Biber

Turing-Maschinen werden vor allem für theoretische Betrachtungen genutzt - in der Praxis haben sie keinerlei Bedeutung.

Eine bekannte Fragestellung lautet: wieviele "1" kann eine Turing-Maschine mit n Zuständen maximal auf ein anfangs mit lauter "0" gefülltes Speicherband schreiben und anschließend anhalten(!)?

Turing-Programme, die diese Bedingung erfüllen, heißen "fleissige Biber".

Die Lösung für ein Turing-Programm mit nur einem Zustand ist offensichtlich:

Abb. 18: Zustandsdiagramm für einen "fleissigen Biber" mit einem Zustand

Nachstehend finden Sie die Beispiele für "fleissige Biber" mit bis zu sechs Zuständen. Die beiden letzten Programme gelten nur als "Kandidaten" für einen "fleissigen Biber", weil sie aufgrund ihrer immensen Laufzeit nicht mehr praktisch getestet werden können.

Die ersten vier Beispiele lassen sich jedoch auch im Simulator noch gut ausprobieren.

"fleissiger Biber" mit einem Zustand

Quelltext

name: busy beaver with one state
init: q0
accept: q1

q0,_
q1,1,>

"fleissiger Biber" mit zwei Zuständen

Quelltext

name: busy beaver with two states
init: q0
accept: q2

q0,_
q1,1,>

q0,1
q1,1,<

q1,_
q0,1,<

q1,1
q2,1,>

"fleissiger Biber" mit drei Zuständen

Quelltext

name: busy beaver with three states
init: q0
accept: q3

q0,_
q1,1,>

q0,1
q3,1,>

q1,_
q2,_,>

q1,1
q1,1,>

q2,_
q2,1,<

q2,1
q0,1,<

"fleissiger Biber" mit vier Zuständen

Quelltext

name: busy beaver with four states
init: q0
accept: q4

q0,_
q1,1,>

q0,1
q1,1,<

q1,_
q0,1,<

q1,1
q2,_,<

q2,_
q4,1,>

q2,1
q3,1,<

q3,_
q3,1,>

q3,1
q0,_,>

Kandidat für einen "fleissigen Biber" mit fünf Zuständen

Quelltext

name: busy beaver with five states
init: q0
accept: q5

q0,_
q1,1,>

q0,1
q2,1,<

q1,_
q2,1,>

q1,1
q1,1,>

q2,_
q3,1,>

q2,1
q4,_,<

q3,_
q0,1,<

q3,1
q3,1,<

q4,_
q5,1,>

q4,1
q0,_,<

Kandidat für einen "fleissigen Biber" mit sechs Zuständen

Quelltext

name: busy beaver with six states
init: q0
accept: q6

q0,_
q1,1,>

q0,1
q4,1,<

q1,_
q2,1,>

q1,1
q5,1,>

q2,_
q3,1,<

q2,1
q1,_,>

q3,_
q4,1,>

q3,1
q2,_,<

q4,_
q0,1,<

q4,1
q3,_,>

q5,_
q6,1,<

q5,1
q2,1,>

Universelle Turing-Maschine

Eine "universelle Turing-Maschine" ist eine Turing-Maschine, die eine andere Turing-Maschine simulieren kann.

Während bei einer einfachen Turing-Maschine das "Programm" (genauer: die Menge aller Zustände und Zustandsübergänge) fest vorgegeben und für die Maschine selbst nicht erreichbar ist, liegen bei einer universellen Turing-Maschine sowohl die Daten (d.h. der Inhalt des Speicherbandes) als auch der Zustandsautomat der zu simulierenden Turing-Maschine auf dem Speicherband - fest vorgegeben ist lediglich die Fähigkeit der universellen Turing-Maschine zur Simulation.

Eine universelle Turing-Maschine ist damit ein einfaches Modell für einen universellen Computer.

Nota bene: die Materialien, die Sie zur Durchführung der Experimente in diesem und im folgenden Kapitel benötigen, finden Sie sowohl auf dieser Web-Seite als auch auf Github.

Universelle Turing-Maschine von Marvin Minsky

Es gibt inzwischen eine ganze Reihe von Beispielen für universelle Turing-Maschinen, die bekannteste darunter ist vermutlich die von Marvin Minsky entwickelte Maschine für binäre Datenaus dem Jahr 1967.

Abb. 19: vereinfachtes Zustandsdiagramm für die universelle Turing-Maschine von Marvin Minsky

(Quelle: Minsky, M.L. Computation: Finite and Infinite Machines. Englewood Cliffs, N.J.: Prentice-Hall, 1967, p. 142.)

Das gezeigte Zustandsdiagramm wurde von Marvin Minsky der Übersichtlichkeit halber stark vereinfacht: er setzte voraus, dass seine universelle Turing-Maschine in jedem Zustand Symbole, die im Diagramm nicht explizit erwähnt wurden, einfach überspringen sollte (ein Detail, das uns weiter unten noch beschäftigen wird).

Quelltext für den Turing-Simulator

name: Universal Turing Machine (by Marvin Minsky)
// see https://github.com/intrinsic-propensity/turing-machine
init: p0
accept: q0

  p0,0
  p0,0,>

  p0,1
  p0,1,>

  p0,A
  p0,A,>

  p0,B
  p0,B,>

  p0,M
  p0,M,>

  p0,S
  p0,S,>

  p0,Y
  p0,Y,>

  p0,X
  p0,X,>

  p0,_
  p1,_,<

  p1,0
  p1,0,<

  p1,Y
  p2,Y,<

  p2,0
  p2,0,<

  p2,1
  p2,1,<

  p2,X
  p2,X,<

  p2,Y
  p3,Y,>

  p3,0
  p3,0,>

  p3,1
  p3,1,>

  p3,X
  q6,X,<

// transitions mentioned in the diagram

  q1,0
  q3,A,<

  q1,1
  q4,B,>

  q2,A
  q1,0,>

  q2,B
  q5,1,>

  q2,X
  q7,X,>

  q3,Y
  q2,Y,>

  q4,X
  q6,X,<

  q4,Y
  q0,Y,-

  q5,0
  q4,A,>

  q5,1
  q3,B,<

  q6,0
  q6,A,<

  q6,1
  q6,B,<

  q6,Y
  q2,Y,>

  q7,0
  q9,A,<

  q7,1
  q8,B,<

  q8,Y
  q10,Y,>

  q9,Y
  q11,Y,>

  q10,0
  q12,B,>

  q10,1
  q12,B,>

  q10,X
  q13,X,<

  q11,0
  q12,A,>

  q11,1
  q12,A,>

  q11,X
  q14,X,<

  q12,X
  q7,X,>

  q13,M
  q15,B,>

  q14,M
  q15,A,>

  q15,A
  q15,0,>

  q15,B
  q15,1,>

  q15,X
  q16,X,>

  q16,0
  q17,0,<

  q16,1
  q17,1,<

  q17,0
  q22,S,<

  q17,1
  q23,S,<

  q17,A
  q17,0,<

  q17,B
  q17,1,<

  q18,S
  q6,A,<

  q19,S
  q6,B,<

  q20,0
  q18,M,>

  q20,1
  q19,M,>

  q21,0
  q18,M,>

  q21,1
  q19,M,>

  q22,A
  q21,0,<

  q22,B
  q20,1,>

  q23,A
  q21,1,<

  q23,B
  q20,1,>

// important transitions not mentioned in the diagram but implicitly being
// part of Marvin Minsky's implementation

  q1,A
  q1,A,>

  q1,B
  q1,B,>

  q1,X
  q1,X,>

  q2,0
  q2,0,>

  q2,1
  q2,1,>

  q3,0
  q3,0,<

  q3,1
  q3,1,<

  q3,A
  q3,A,<

  q3,B
  q3,B,<

  q3,X
  q3,X,<

  q4,0
  q4,0,>

  q4,1
  q4,1,>

  q5,A
  q5,A,>

  q5,B
  q5,B,>

  q5,X
  q5,X,>

  q6,A
  q6,A,<

  q6,B
  q6,B,<

  q6,X
  q6,X,<

  q7,A
  q7,A,>

  q7,B
  q7,B,>

  q7,X
  q7,X,>

  q8,0
  q8,0,<

  q8,1
  q8,1,<

  q8,A
  q8,A,<

  q8,B
  q8,B,<

  q8,X
  q8,X,<

  q9,0
  q9,0,<

  q9,1
  q9,1,<

  q9,A
  q9,A,<

  q9,B
  q9,B,<

  q9,X
  q9,X,<

  q10,A
  q10,A,>

  q10,B
  q10,B,>

  q11,A
  q11,A,>

  q11,B
  q11,B,>

  q12,0
  q12,0,>

  q12,1
  q12,1,>

  q13,0
  q13,0,<

  q13,1
  q13,1,<

  q13,A
  q13,A,<

  q13,B
  q13,B,<

  q13,Y
  q13,Y,<

  q14,0
  q14,0,<

  q14,1
  q14,1,<

  q14,A
  q14,A,<

  q14,B
  q14,B,<

  q14,Y
  q14,Y,<

  q15,0
  q15,0,>

  q15,1
  q15,1,>

  q15,Y
  q15,Y,>

  q16,A
  q16,A,>

  q16,B
  q16,B,>

  q16,X
  q16,X,>

  q16,Y
  q16,Y,>

  q17,X
  q17,X,<

  q17,Y
  q17,Y,<

  q18,0
  q18,0,>

  q18,1
  q18,1,>

  q18,Y
  q18,Y,>

  q19,0
  q19,0,>

  q19,1
  q19,1,>

  q19,Y
  q19,Y,>

  q22,0
  q22,0,<

  q22,1
  q22,1,<

  q22,Y
  q22,Y,<

  q23,0
  q23,0,<

  q23,1
  q23,1,<

  q23,Y
  q23,Y,<

// dangerous transitions not mentioned in the diagram but implicitly being
// part of Marvin Minsky's implementation

  q2,M
  q2,M,>

  q3,M
  q3,M,<

  q6,M
  q6,M,<

  q7,Y
  q7,Y,>

  q8,S
  q8,S,<

  q9,M
  q9,M,<

  q9,S
  q9,S,<

  q10,S
  q10,S,>

  q11,M
  q11,M,>

  q11,S
  q11,S,>

  q12,S
  q12,S,>

  q13,X
  q13,X,<

  q13,S
  q13,S,<

  q14,X
  q14,X,<

  q14,S
  q14,S,<

  q16,S
  q16,S,>

  q17,S
  q17,S,<

  q18,A
  q18,A,>

  q18,B
  q18,B,>

  q18,X
  q18,X,>

  q19,A
  q19,A,>

  q19,B
  q19,B,>

  q19,X
  q19,X,>

  q20,A
  q20,A,>

  q20,B
  q20,B,>

  q20,S
  q20,S,>

  q20,X
  q20,X,>

  q20,Y
  q20,Y,>

  q21,A
  q21,A,<

  q21,S
  q21,S,<

  q21,B
  q21,B,<

  q21,X
  q21,X,<

  q21,Y
  q21,Y,<

Nota bene: Bedingt durch das Verhalten des hier eingesetzten Turing-Simulators (der Schreib-/Lesekopf wird darin stets auf dem linken Ende des Speicherbandes plaziert), muss der im Diagramm gezeigten universellen Turing-Maschine eine "Präambel" vorangestellt werden, die den Schreib-/Lesekopf dorthin bewegt, wo sie Marvin Minsky's Implementierung anfänglich erwartet.

Beladen der universellen Turing-Maschine

Um eine Turing-Maschine zu simulieren, muss eine Beschreibung ihres Zustandsautomaten zusammen mit ihrem initialen Zustand auf das Speicherband der universellen Turing-Maschine geschrieben werden.

Die Zustände der zu simulierenden Maschine werden dazu durchnumeriert. Da die Daten in Binärform vorliegen müssen, werden die Zustandsnummern als Dualzahlen fester Länge angegeben - die Mindestanzahl der benötigten Stellen (Bits) ergibt sich aus der Gesamtzahl verwendeter Zustände (z.B. 3 für bis zu 8 Zustände 0...7). Wie wir noch sehen werden, dürfen (auf Kosten der Simulationsgeschwindigkeit) durchaus auch mehr Stellen verwendet, die Mindestanzahl jedoch nicht unterschritten werden.

Der Inhalt ist dabei (von links nach rechts) wie folgt zusammengesetzt:

der Inhalt des zu simulierenden Speicherbandes, wobei die Stelle, an der sich der simulierte Schreib-/Lesekopf befindet, durch ein "M" markiert wird,
ein "Y"
die Nummer des Startzustandes für die simulierte Turing-Maschine, gefolgt vom Wert des simulierten Speicherbandes an der Position des simulierten Schreib-/Lesekopfes (diese Zelle wurde ja mit einem "M" überschrieben)
als nächstes folgen die Zustandsübergänge der simulierten Maschine in beliebiger Reihenfolge. Jeder Übergang wird wie folgt kodiert:
- ein "X"
- gefolgt von der Nummer des Ausgangszustandes und dem erwarteten Wert an der Stelle des simulierten Schreib-/Lesekopfes
- gefolgt von der Nummer des Zielzustandes und dem auf das simulierte Speicherband zu schreibenden Wert
- gefolgt von der gewünschten Bewegungsrichtung des simulierten Schreib-/Lesekopfes ("0" steht für links, "1" für rechts)
auf das Ende dieser Liste folgt noch ein "Y0"

Ein konkreter Zielzustand lässt sich nicht vorgeben. Stattdessen bleibt die universelle Turing-Maschine (in den meisten Fällen) einfach stehen, sobald sie für den aktuellen Zustand der simulierten Maschine keinen passenden Zustandsübergang mehr finden kann.

Ein einfaches Beispiel

An einem einfachen Beispiel lässt sich das Beladen leicht demonstrieren.

Zu simulieren sei eine Turing-Maschine, die wiederholt eine vom Speicherband gelesene "0" in eine "1" umwandelt und anschließend den Schreib-/Lesekopf nach rechts bewegt - solange, bis sie auf dem Band auf eine "1" trifft.

In der Notation des hier verwendeten Simulators lautet der zugehörige Zustandsautomat:

  q0,0
  q0,1,>

Wenn das simulierte Speicherband anfangs zwei Nullen und eine Eins enthalten und der simulierte Schreib-/Lesekopf auf der ersten Null stehen soll, muss das Band der universellen Turing-Maschine wie folgt beladen werden:

M zur Markierung der simulierten Kopfposition
01 für die zweite Null und die darauffolgende Eins
Y
0 weil der Initialzustand die Nummer 0 hat
0 weil das M auf dem simulierten Speicherband die erste Null überdeckt
X
0 um einen Übergang aus Zustand Nummer 0 zu definieren
0 weil auf dem Band eine Null erwartet wird
0 weil auch der Zielzustand die Nummer 0 hat
1 weil eine Eins geschrieben werden soll
1 weil der Kopf nach rechts bewegt werden soll
Y0 weil dies das Ende de Definition ist,

zusammen also M01Y00X00011Y0

Programmieren Sie den Turing-Maschinen-Simulator mit dem oben gezeigten Quelltext für die universelle Turing-Maschine (Compile nicht vergessen!) und beladen Sie das Speicherband mit der gezeigten Zeichenfolge M01Y00X00011Y0.

Wenn Sie jetzt auf die Starttaste drücken, beginnt der Turing-Simulator mit der Simulation einer universellen Turing-Maschine, die ihrerseits eine einfache Turing-Maschine simuliert.

Nota bene: Leider kann man im Turing-Maschinen-Simulator die Anzeige des Speicherbandes nicht verschieben. Da die universelle Turing-Maschine oftmals so anhält, dass das simulierte Speicherband nicht zur Gänze einsehbar ist, empfiehlt sich am Ende ein Anklicken von "show output" rechts oben neben "rejected". Dadurch öffnet sich eine Anzeige, die den vollständigen Inhalt des Speicherbandes in Textform ausgibt.

Verwundbarkeit universeller Turing-Maschinen

Ein Artikel von Pontus Johnson hat gezeigt, dass selbst so einfache Systeme wie universelle Turing-Maschinen nicht gegen Angriffe von außen gefeit sind.

Im konkreten Fall wurde die universelle Turing-Maschine von Marvin Minsky derart geschickt beladen, dass sie nicht die eigentlich beschriebene Turing-Maschine simuliert, sondern Code ausführt, der eigentlich in den "Daten" (d.h. auf dem simulierten Speicherband) versteckt ist.

Der Grund für die Verwundbarkeit liegt in Marvin Minsky's "Vereinfachung" bzw. der Voraussetzung, dass jeder Zustand im Diagramm nicht explizit erwähnte Symbole beim Einlesen überspringen sollte.

Eigentlich zu simulieren: ein Binärzähler

Dem konkreten Beispiel für einen solchen Angriff liegt als eigentlich zu simulierende Turing-Maschine ein Binärzähler zugrunde.

In der Notation des hier verwendeten Simulators lautet der Zustandsautomat für diesen Binärzähler:

name: binary counter
init: q0
accept: q2

q0,0
q0,0,>

q0,1
q1,1,<

q1,0
q0,1,>

q1,1
q1,0,<

Quelltext

name: binary counter
init: q0
accept: q2

q0,0
q0,0,>

q0,1
q1,1,<

q1,0
q0,1,>

q1,1
q1,0,<

Binärzähler für die universelle Turing-Maschine

Um diesen Zähler laufen zu lassen, muss das Speicherband mit einer Folge von Nullen und einer Eins am Ende beladen werden. Die Anzahl der führenden Nullen bestimmt die Anzahl der Bits, die dem Zähler zur Verfügung stehen - die Turing-Maschine bricht ab, sobald der Zähler einen Überlauf generiert, die Anzahl der verfügbaren Bits also nicht mehr ausreicht.

Zweckmäßigerweise beschränkt man sich beim Testen im Simulator deshalb auf zwei Nullen, belädt das Speicherband also mit 001.

Aus dem Anfangswert für das Speicherband, dem Initialzustand q0 und der Liste der Zustandsübergänge ergibt sich somit folgender Inhalt für das Speicherband der oben gezeigten universellen Turing-Maschine:

M01
Y
00
X 00 00 1
X 01 11 0
X 10 01 1
X 11 10 0
Y0

oder zusammengefasst M01Y00X00001X01110X10011X11100Y0.

Lassen Sie im Turing-Simulator den Binärzähler (mit maximaler Geschwindigkeit) von der universellen Turing-Maschine simulieren und prüfen Sie am Ende (nach 1333 Ausführungsschritten) mittels "show output" den Inhalt des simulierten Speicherbandes.

Tatsächlich ausgeführt: ein Löschprogramm

Das Ziel des Angriffes ist der Einfachheit halber ein Löschen des simulierten Speicherbandes (anstelle der Zählerausführung).

Dies gelingt mit einem einfachen Programm

  q0,0
  q0,0,<

  q0,1
  q0,0,<

oder in der Notation der universellen Turing-Maschine geschrieben:

  X00000X01000

Gemäß der in der oben genannten Veröffentlichung beschriebenen Anleitung ergibt sich für den Angriff somit die Form

  1111YBAXAAAAAXABAAAS

Damit die Attacke funktioniert, muss der Anfangszustand für den Binärzahler so gewählt werden, dass

der Schreib-/Lesekopf der zu simulierenden Maschine am linken Ende seines Speicherbandes steht und eine "1" unter sich sieht und
in Verbindung mit dem anfänglichen Zustand auf einen Zustandsübergang (des Binärzählers) gezeigt wird, der eine "1" schreibt und den Schreib-/Lesekopf nach links bewegt

Außerdem darf das Schreib-/Leseband für den Zähler nicht zu kurz sein (und sollte mindestens 4 Zellen umfassen)

Alles zusammen ergibt:

  1111YBAXAAAAAXABAAASM000Y01X00001X01110X10011X11100Y0

Der Angriff

Mit der soeben konstruierten anfänglichen Belegung für das Speicherband der universellen Turing-Maschine

  1111YBAXAAAAAXABAAASM000Y01X00001X01110X10011X11100Y0

lässt sich der Angriff im Simulator durchführen.

Sobald Sie die Ausführung starten, wird die Turing-Maschine angegriffen und anstelle des Binärzählers läuft der Code, der die linke Seite des Speicherbandes (binnen 1413 Schritten) löscht bzw. mit Nullen überschreibt.

Begründung und Abhärtung

Die Ursache für die Angreifbarkeit der universellen Turing-Maschine sind eine Reihe von nicht explizit erwähnten, sondern implizit vorausgesetzten Zustandsübergängen - von denen viele für das korrekte Funktionieren der universellen Turing-Maschine zwingend erforderlich sind. Andere implizite Zustandsübergänge veranlassen die Turing-Maschine hingegen, eigentlich fehlerhafte Daten auf dem Speicherband einfach zu überspringen - obwohl ein Abbruch der Simulation das einzig richtige Verhalten wäre.

Im Quelltext der universellen Turing-Maschine für den hier verwendeten Turing-Maschinen-Simulator finden Sie diese Zustandsübergänge im Abschnitt "dangerous transitions".

Werden diese Übergänge entfernt, bleibt die Turing-Maschine voll funktionsfähig, ist jedoch nicht mehr angreifbar.

Die von Marvin Minsky veröffentlichte Fassung seiner universellen Turing-Maschine geht also davon aus, dass die Eingabedaten korrekt und nur "für den bestimmungsgemäßen Gebrauch" gedacht sind und verzichtet der Einfachheit halber auf eine (implizite oder explizite) Überprüfung.

Vergleichbare Probleme hat auch der größte Teil der heutigen Software: aus Faulheit oder um den Quelltext kurz zu halten, verzichten viele Programmierer auf eine Validierung von Eingabedaten - und dies, obwohl das Ausnutzen solcher Lücken einen großen Teil der tatsächlichen Angriffe in der realen Welt ausmacht.

Nota bene: Im Sinne des EVA-Prinzips ist der Begriff "Eingabe" dabei nicht auf Benutzereingaben i.e.S beschränkt. Vielmehr handelt es sich bei "Eingaben" um alle Arten von Daten, die einem Programm von außen zugeführt werden.

Im Umkehrschluss bedeutet dies aber auch, dass Software durch (ggfs. nachträgliches) Hinzufügen von Eingabevalidierungen auf recht einfache Weise "gehärtet" werden kann.

An dieser Stelle möchte sich der Autor ausdrücklich bei Pontus Johnson (dem Entdecker der beschriebenen Sicherheitslücke) für seine Unterstützung bei der Portierung von Marvin Minsky's universeller Turing-Maschine und der Durchführung des gezeigten Angriffes bedanken.

Danksagungen

Diese Web-Seite verwendet die folgenden Drittanbieter-Bibliotheken oder -Materialien bzw. StackOverflow-Antworten:

Font Awesome Free 4.7.0
Lizenz: SIL Open Font License (OFL)
Antwort auf die StackOverflow-Frage How to get the global object in JavaScript?
beigetragen von Christian C. Salvadó
Lizenz: CC BY-SA 2.5
jQuery - jQuery JavaScript Library
Copyright OpenJS Foundation and other contributors, https://openjsf.org/
Lizenz: MIT License

Der Autor dankt den Entwicklern und Autoren der genannten Beiträge für ihre Mühe und die Bereitschaft, ihre Werke der Allgemeinheit zur Verfügung zu stellen.

https://www.rozek.de/Turing-Machine/index_de.html

24.05.2021