Turingmaschinen

Die Turingmaschine ist ein abstraktes Gerät mit einer endlichen Steuerung und einem unbegrenzten Band, das den intuitiven Begriff eines Algorithmus erfasst und als Standardreferenzmodell für das dient, was berechenbar ist.

Definition

Eine Turingmaschine besteht aus einer endlichen Menge von Zuständen und einem zweiseitig unendlichen Band von Zellen; bei jedem Schritt liest sie das Symbol unter ihrem Kopf, schreibt ein Symbol, bewegt sich nach links oder rechts und ändert den Zustand gemäß einer Übergangsfunktion, wobei sie anhält, wenn sie einen akzeptierenden oder ablehnenden Zustand erreicht.

Scope

Dieses Thema behandelt die Definition und Funktionsweise von Turingmaschinen, Konfigurationen und Berechnungen, die Robustheit des Modells unter Varianten wie Mehrband- und Nichtdeterminismus, die universelle Turingmaschine, die jede andere simulieren kann, und die Kodierung von Maschinen als Daten, die Selbstreferenz und Unentscheidbarkeitsargumente ermöglicht.

Core questions

• Wie erfasst ein einfaches Lese-Schreib-Bewegungs-Gerät den vollständigen Begriff des Algorithmus?
• Warum berechnen viele Varianten des Modells genau die gleichen Funktionen?
• Was ist eine universelle Maschine, und warum ist ihre Existenz bedeutsam?
• Wie ermöglicht die Kodierung von Maschinen als Zeichenketten Beweise über ihr eigenes Verhalten?

Key theories

Universalität

Es gibt eine einzige universelle Turingmaschine, die, gegeben eine Kodierung einer beliebigen Maschine und ihrer Eingabe, die Berechnung dieser Maschine simuliert, was den speicherprogrammierbaren Computer vorwegnimmt, bei dem Programme selbst Daten sind.

Robustheit des Modells

Das Hinzufügen von Bändern, mehreren Köpfen, zweidimensionalen Bändern oder Nichtdeterminismus ändert die Klasse der berechenbaren Funktionen nicht, sodass die Turingmaschine einen Berechnungsbegriff erfasst, der gegenüber solchen Details unempfindlich ist.

Clinical relevance

Die Turingmaschine ist der Maßstab, an dem die Leistungsfähigkeit von Programmiersprachen und Computerarchitekturen gemessen wird, und die universelle Maschine ist der konzeptionelle Vorläufer des Allzweck-Speicherprogrammscomputers, auf dem die gesamte moderne Datenverarbeitung beruht.

History

Turing führte seine Maschinen 1936 ein, um präzise zu definieren, was es bedeutet, dass eine Zahl berechenbar ist, und um Hilberts Entscheidungsproblem zu lösen. Die Idee einer universellen Maschine, bei der eine gespeicherte Beschreibung ein allgemeines Gerät steuert, beeinflusste von Neumanns Entwurf des speicherprogrammierbaren Computers ein Jahrzehnt später.

Key figures

• Alan Turing
• Emil Post
• John von Neumann

Seminal works

• turing1937
• sipser2013

Frequently asked questions

Ist eine Turingmaschine ein echter Computer?

Nein, sie ist eine mathematische Abstraktion mit unbegrenztem Band und ohne Berücksichtigung von Geschwindigkeit oder Speicherkosten. Ihr Wert ist konzeptionell: Sie legt genau fest, was prinzipiell berechnet werden kann, und jede Aufgabe, die ein echter Computer ausführen kann, kann eine Turingmaschine auch ausführen, wenn genügend Band und Zeit zur Verfügung stehen.

Warum ist die universelle Turingmaschine wichtig?

Sie zeigt, dass eine feste Maschine das Verhalten jeder anderen ausführen kann, wenn ihr die Beschreibung dieser Maschine als Eingabe gegeben wird. Dies ist die theoretische Grundlage des Allzweck-Programmiercomputers, bei dem Software Daten sind, die einem einzigen interpretierenden Gerät zugeführt werden, anstatt für jede Aufgabe neu verdrahtet zu werden.