Turing Machine

Es ist der Ur-Vater aller Computer. Aber es ist kein echtes Gerät, sondern ein Gedankenexperiment von Alan Turing (1936). Stell dir ein unendlich langes Papierband vor. Darüber schwebt ein kleiner Schreibkopf. Der Kopf kann nur:

Lesen, was auf dem Feld steht (0 oder 1).
Schreiben (0 oder 1).
Einen Schritt nach links oder rechts gehen. Turing hat bewiesen: Mit diesem simplen Mechanismus kann man alles berechnen, was berechenbar ist. Dein Laptop, dein Smartphone, ein Supercomputer – im Kern ist alles nur eine schnelle Turing-Maschine.

Merksatz: Ein theoretisches Modell eines Computers, das aus einem unendlichen Speicherband und einem Lese-/Schreibkopf besteht und die Grenzen der Berechenbarkeit definiert.

Du baust keine Turing-Maschinen. Aber du nutzt das Konzept der Turing-Vollständigkeit. Eine Programmiersprache (Python, Java) ist "Turing-vollständig", wenn sie theoretisch alles berechnen kann, was eine Turing-Maschine kann. HTML ist nicht Turing-vollständig (es kann nicht rechnen, keine Schleifen). CSS ist (überraschenderweise) Turing-vollständig (mit Hacks).

1. Das Halte-Problem

Turing hat damit bewiesen, dass Computer nicht allmächtig sind. Frage: "Gibt es ein Programm, das prüfen kann, ob ein anderes Programm jemals fertig wird oder in einer Endlosschleife hängt?" Antwort: Nein. Das ist das Halte-Problem. Es ist logisch unmöglich, so einen perfekten "Bug-Checker" zu schreiben.

2. Deterministisch vs. Nicht-Deterministisch

DTM (Deterministisch): Der nächste Schritt ist immer eindeutig definiert. (Normale Computer).
NTM (Nicht-Deterministisch): Die Maschine kann "raten" und mehrere Wege gleichzeitig gehen. (Theoretisches Modell für Komplexitätsklassen wie NP). Ein Quantencomputer kommt dem nahe.

1. Die Church-Turing-These

Alonzo Church (Lambda-Kalkül) und Alan Turing (Turing-Maschine) haben unabhängig voneinander das Gleiche bewiesen. Die Church-Turing-These besagt: "Alles, was intuitiv berechenbar ist, kann durch eine Turing-Maschine berechnet werden." Das ist kein mathematisches Theorem (weil "intuitiv" schwer zu definieren ist), sondern ein physikalisches Gesetz unserer Welt. Es bedeutet, dass wir keine "Super-Computer" bauen können, die logisch überlegen sind. Ein Quantencomputer ist zwar schneller bei bestimmten Problemen (Shor-Algorithmus), aber er kann nichts berechnen, was eine Turing-Maschine theoretisch nicht auch könnte (wenn sie genug Zeit hätte).

2. Universal Turing Machine (UTM)

Turing ging einen Schritt weiter: Die Universelle Turingmaschine. Er erkannte, dass man die Beschreibung einer Turingmaschine (ihre Regeln) selbst als Daten auf das Band schreiben kann. Dann baut man eine "Master-Maschine", die diese Regeln liest und so tut, als wäre sie die beschriebene Maschine. Das ist die Erfindung der Software! Vor Turing waren Rechner (wie Webstühle) fest für eine Aufgabe gebaut. Turing sagte: "Wir brauchen nur eine Hardware, die Software liest."

3. P vs. NP und Turingmaschinen

In der Komplexitätstheorie nutzt man Turingmaschinen, um Klassen zu definieren:

P (Polynomial): Probleme, die eine deterministische Turingmaschine (DTM) in vernünftiger Zeit lösen kann.
NP (Nondeterministic Polynomial): Probleme, die eine nicht-deterministische Turingmaschine (NTM) in vernünftiger Zeit lösen könnte. Da wir keine echten NTMs bauen können, versuchen wir seit 50 Jahren zu beweisen, ob $P = NP$. Würde man beweisen, dass eine DTM alles kann, was eine NTM kann, würde die gesamte moderne Kryptografie (RSA) sofort in sich zusammenbrechen.