Turing-Vollständigkeit
In der Theorie der Berechenbarkeit wird ein System von Datenmanipulationsregeln (wie z. B. der Befehlssatz eines Computers, eine Programmiersprache oder ein zellulärer Automat) als Turing-komplett oder rechnerisch universell bezeichnet, wenn es dazu verwendet werden kann, eine beliebige Turing-Maschine zu simulieren (die vom englischen Mathematiker und Informatiker Alan Turing entwickelt wurde). Das bedeutet, dass dieses System in der Lage ist, andere Regelsätze für die Datenmanipulation zu erkennen oder zu entscheiden. Die Turing-Vollständigkeit wird verwendet, um die Mächtigkeit eines solchen Regelsatzes für die Datenmanipulation auszudrücken. Praktisch alle heutigen Programmiersprachen sind Turing-komplett. ⓘ
Ein verwandtes Konzept ist das der Turing-Äquivalenz - zwei Computer P und Q werden als äquivalent bezeichnet, wenn P Q simulieren kann und Q P simulieren kann. Die Church-Turing-These besagt, dass jede Funktion, deren Werte durch einen Algorithmus berechnet werden können, von einer Turing-Maschine berechnet werden kann, und dass daher jeder Computer der realen Welt, der eine Turing-Maschine simulieren kann, einer Turing-Maschine äquivalent ist. Eine universelle Turing-Maschine kann dazu verwendet werden, jede Turing-Maschine zu simulieren und damit die rechnerischen Aspekte eines jeden möglichen realen Computers. ⓘ
Um zu zeigen, dass etwas Turing-komplett ist, reicht es, zu zeigen, dass es zur Simulation eines Turing-kompletten Systems verwendet werden kann. Kein physikalisches System kann unendlichen Speicher haben, aber wenn man die Beschränkung des endlichen Speichers ignoriert, sind die meisten Programmiersprachen ansonsten Turing-komplett. ⓘ
Nicht-mathematische Verwendung
In der Umgangssprache werden die Begriffe "Turing-komplett" und "Turing-äquivalent" verwendet, um zu sagen, dass jeder reale Allzweckcomputer oder jede reale Computersprache die rechnerischen Aspekte jedes anderen realen Allzweckcomputers oder jeder anderen realen Computersprache annähernd simulieren kann. Im wirklichen Leben führte dies zu den praktischen Konzepten der Computervirtualisierung und -emulation. ⓘ
Bisher konstruierte reale Computer können funktional wie eine Einband-Turing-Maschine (das "Band" entspricht ihrem Speicher) analysiert werden; daher kann die zugehörige Mathematik angewendet werden, wenn man ihre Funktionsweise weit genug abstrahiert. Allerdings haben reale Computer nur begrenzte physikalische Ressourcen, so dass sie nur als linear begrenzte Automaten vollständig sind. Im Gegensatz dazu ist ein universeller Computer definiert als ein Gerät mit einem vollständigen Turing-Befehlssatz, unendlichem Speicher und unendlicher verfügbarer Zeit. ⓘ
Formale Definitionen
In der Berechenbarkeitstheorie werden mehrere eng verwandte Begriffe verwendet, um die Rechenleistung eines Rechensystems (z. B. einer abstrakten Maschine oder Programmiersprache) zu beschreiben:
- Turing-Vollständigkeit
- Ein Rechensystem, das jede Turing-berechenbare Funktion berechnen kann, wird als Turing-vollständig (oder Turing-mächtig) bezeichnet. Alternativ ist ein solches System eines, das eine universelle Turing-Maschine simulieren kann.
- Turing-Äquivalenz
- Ein Turing-komplettes System heißt Turing-äquivalent, wenn jede Funktion, die es berechnen kann, auch Turing-berechenbar ist, d.h. es berechnet genau die gleiche Klasse von Funktionen wie Turing-Maschinen. Alternativ dazu ist ein Turing-äquivalentes System ein System, das eine universelle Turing-Maschine simulieren kann und von ihr simuliert werden kann. (Alle bekannten physikalisch implementierbaren Turing-kompletten Systeme sind Turing-äquivalent, was die Church-Turing-These stützt).
- (Rechnerische) Universalität
- Ein System wird in Bezug auf eine Klasse von Systemen als universell bezeichnet, wenn es jede Funktion berechnen kann, die von Systemen dieser Klasse berechnet werden kann (oder jedes dieser Systeme simulieren kann). Normalerweise wird der Begriff "Universalität" stillschweigend in Bezug auf eine Turing-komplette Klasse von Systemen verwendet. Der Begriff "schwach universell" wird manchmal verwendet, um ein System (z. B. einen zellulären Automaten) zu unterscheiden, dessen Universalität nur durch eine Änderung der Standarddefinition der Turing-Maschine erreicht wird, um Eingabeströme mit unendlich vielen 1en einzuschließen. ⓘ
Geschichte
Die Turing-Vollständigkeit ist insofern von Bedeutung, als jedes reale Design für ein Rechengerät durch eine universelle Turing-Maschine simuliert werden kann. Die Church-Turing-These besagt, dass dies ein Gesetz der Mathematik ist - dass eine universelle Turing-Maschine im Prinzip jede Berechnung durchführen kann, die auch jeder andere programmierbare Computer durchführen kann. Dies sagt nichts über den Aufwand aus, der erforderlich ist, um das Programm zu schreiben, oder über die Zeit, die die Maschine zur Durchführung der Berechnung benötigt, oder über irgendwelche Fähigkeiten, die die Maschine besitzen könnte, die nichts mit der Berechnung zu tun haben. ⓘ
Charles Babbage's analytische Maschine (1830er Jahre) wäre die erste Turing-komplette Maschine gewesen, wenn sie zum Zeitpunkt ihrer Entwicklung gebaut worden wäre. Babbage erkannte, dass die Maschine zu großen Rechenleistungen fähig war, einschließlich primitiver logischer Schlussfolgerungen, aber er erkannte nicht, dass keine andere Maschine besser war. Von den 1830er bis in die 1940er Jahre wurden mechanische Rechenmaschinen wie Addierer und Multiplizierer gebaut und verbessert, aber sie konnten keine bedingten Verzweigungen ausführen und waren daher nicht Turing-komplett. ⓘ
Im späten 19. Jahrhundert formulierte Leopold Kronecker Begriffe der Berechenbarkeit und definierte primitive rekursive Funktionen. Diese Funktionen können durch Auswendigrechnen berechnet werden, reichen aber nicht aus, um einen Universalcomputer zu bauen, da die Anweisungen, mit denen sie berechnet werden, keine Endlosschleife zulassen. Anfang des 20. Jahrhunderts führte David Hilbert ein Programm zur Axiomatisierung der gesamten Mathematik mit präzisen Axiomen und genauen logischen Deduktionsregeln an, die von einer Maschine ausgeführt werden konnten. Bald wurde klar, dass ein kleiner Satz von Deduktionsregeln ausreicht, um die Konsequenzen eines beliebigen Satzes von Axiomen zu erzeugen. Kurt Gödel bewies 1930, dass diese Regeln ausreichen, um jedes Theorem zu erzeugen. ⓘ
Der eigentliche Begriff des Rechnens wurde bald darauf isoliert, beginnend mit Gödels Unvollständigkeitstheorem. Dieses Theorem zeigte, dass Axiomensysteme begrenzt sind, wenn man über die Berechnung nachdenkt, die ihre Theoreme herleitet. Church und Turing wiesen unabhängig voneinander nach, dass Hilberts Entscheidungsproblem unlösbar ist, und identifizierten damit den rechnerischen Kern des Unvollständigkeitssatzes. Zusammen mit Gödels Arbeit über allgemeine rekursive Funktionen hat diese Arbeit gezeigt, dass es einfache Anweisungen gibt, die, wenn sie zusammengesetzt werden, eine beliebige Berechnung ermöglichen. Die Arbeit von Gödel zeigte, dass der Begriff der Berechnung im Wesentlichen eindeutig ist. ⓘ
1941 stellte Konrad Zuse den Z3-Computer fertig. Zuse war zu dieser Zeit nicht mit Turings Arbeit über Berechenbarkeit vertraut. Insbesondere fehlte der Z3 eine spezielle Einrichtung für einen bedingten Sprung, so dass sie nicht als vollständig nach Turing gelten konnte. Im Jahr 1998 zeigte Rojas jedoch, dass das Z3 in der Lage ist, bedingte Sprünge zu simulieren, und daher theoretisch vollständig ist. Dazu müsste sein Bandprogramm lang genug sein, um jeden möglichen Pfad durch beide Seiten jeder Verzweigung auszuführen. ⓘ
Der erste Computer, der in der Praxis bedingte Verzweigungen simulieren konnte und damit in der Praxis Turing-vollständig war, war der ENIAC im Jahr 1946. Der Z4-Computer von Zuse wurde 1945 in Betrieb genommen, unterstützte aber erst 1950 bedingte Verzweigungen. ⓘ
Berechenbarkeitstheorie
Die Berechenbarkeitstheorie verwendet Rechenmodelle, um Probleme zu analysieren und festzustellen, ob und unter welchen Umständen sie berechenbar sind. Das erste Ergebnis der Berechenbarkeitstheorie ist, dass es Probleme gibt, bei denen es unmöglich ist, vorherzusagen, was ein (Turing-komplettes) System über einen beliebig langen Zeitraum tun wird. ⓘ
Das klassische Beispiel ist das Halteproblem: Erstelle einen Algorithmus, der als Eingabe ein Programm in einer Turing-kompletten Sprache und einige Daten, die in dieses Programm eingespeist werden sollen, annimmt und feststellt, ob das Programm, das mit der Eingabe arbeitet, schließlich aufhört oder für immer weiterläuft. Es ist trivial, einen Algorithmus zu entwickeln, der dies für einige Eingaben tun kann, aber es ist unmöglich, dies im Allgemeinen zu tun. Für jede beliebige Eigenschaft der möglichen Ausgabe des Programms ist es unmöglich zu bestimmen, ob diese Eigenschaft bestehen bleibt. ⓘ
Diese Unmöglichkeit wirft Probleme bei der Analyse von Computerprogrammen in der realen Welt auf. Man kann zum Beispiel kein Tool schreiben, das Programmierer vollständig davor schützt, Endlosschleifen zu schreiben, oder Benutzer davor schützt, Eingaben zu machen, die Endlosschleifen verursachen würden. ⓘ
Stattdessen kann man die Ausführung eines Programms auf eine bestimmte Zeitspanne beschränken (Timeout) oder die Leistung von Anweisungen zur Flusskontrolle einschränken (z. B. indem man nur Schleifen bereitstellt, die über die Elemente eines bestehenden Arrays iterieren). Ein anderes Theorem zeigt jedoch, dass es Probleme gibt, die von Turing-kompletten Sprachen gelöst werden können, die aber von keiner Sprache mit endlichen Schleifenfähigkeiten gelöst werden können (d.h. von keiner Sprache, die garantiert, dass jedes Programm irgendwann zum Stillstand kommt). Eine solche Sprache ist also nicht Turing-komplett. Zum Beispiel kann eine Sprache, in der Programme garantiert zum Stillstand kommen, nicht die berechenbare Funktion berechnen, die durch das Cantorsche Diagonalargument für alle berechenbaren Funktionen in dieser Sprache erzeugt wird. ⓘ
Turing-Orakel
Ein Computer, der Zugang zu einem unendlichen Datenband hat, kann leistungsfähiger sein als eine Turing-Maschine: Das Band könnte zum Beispiel die Lösung des Halteproblems oder eines anderen unentscheidbaren Turing-Problems enthalten. Ein solches unendliches Datenband nennt man ein Turing-Orakel. Selbst ein Turing-Orakel mit zufälligen Daten ist nicht berechenbar (mit Wahrscheinlichkeit 1), da es nur abzählbar viele Berechnungen, aber nicht abzählbar viele Orakel gibt. Ein Computer mit einem Turing-Zufallsorakel kann also Dinge berechnen, die eine Turing-Maschine nicht berechnen kann. ⓘ
Digitale Physik
Alle bekannten physikalischen Gesetze haben Konsequenzen, die durch eine Reihe von Näherungen auf einem digitalen Computer berechenbar sind. Eine als digitale Physik bezeichnete Hypothese besagt, dass dies kein Zufall ist, weil das Universum selbst auf einer universellen Turing-Maschine berechenbar ist. Dies würde bedeuten, dass kein Computer gebaut werden kann, der leistungsfähiger ist als eine universelle Turing-Maschine. ⓘ
Beispiele
Die Rechensysteme (Algebren, Kalküle), die als Turing-komplette Systeme diskutiert werden, sind für das Studium der theoretischen Informatik bestimmt. Sie sollen so einfach wie möglich sein, damit man die Grenzen des Rechnens besser verstehen kann. Hier sind einige davon:
- Automatentheorie
- Formale Grammatik (Sprachgeneratoren)
- Formale Sprache (Spracherkenner)
- Lambda-Kalkül
- Post-Turing-Maschinen
- Prozess-Kalkül ⓘ
Die meisten Programmiersprachen (ihre abstrakten Modelle, vielleicht mit einigen speziellen Konstrukten, die endlichen Speicher voraussetzen), konventionelle und unkonventionelle, sind Turing-komplett. Dies schließt ein:
- Alle weit verbreiteten Allzwecksprachen.
- Die meisten Sprachen, die weniger verbreitete Paradigmen verwenden:
- Funktionale Sprachen wie Lisp und Haskell.
- Logische Programmiersprachen wie Prolog.
- Allzweck-Makroprozessoren wie m4.
- Deklarative Sprachen wie XSLT.
- VHDL und andere Hardwarebeschreibungssprachen.
- TeX, ein Schriftsatzsystem.
- Esoterische Programmiersprachen, eine Form der mathematischen Freizeitgestaltung, bei der Programmierer herausfinden, wie man grundlegende Programmierkonstrukte in einer extrem schwierigen, aber mathematisch Turing-äquivalenten Sprache erreichen kann. ⓘ
Einige Umschreibesysteme sind Turing-komplett. ⓘ
Die Turing-Vollständigkeit ist eine abstrakte Aussage über die Fähigkeit, und nicht eine Vorschrift über spezifische Sprachmerkmale, die zur Umsetzung dieser Fähigkeit verwendet werden. Die Eigenschaften, die zur Erreichung der Turing-Vollständigkeit verwendet werden, können recht unterschiedlich sein; Fortran-Systeme würden Schleifenkonstrukte oder möglicherweise sogar goto-Anweisungen verwenden, um eine Wiederholung zu erreichen; Haskell und Prolog, denen Schleifen fast vollständig fehlen, würden Rekursion verwenden. Die meisten Programmiersprachen beschreiben Berechnungen auf von-Neumann-Architekturen, die über Speicher (RAM und Register) und eine Steuereinheit verfügen. Diese beiden Elemente machen diese Architektur Turing-komplett. Auch reine funktionale Sprachen sind Turing-komplett. ⓘ
Turing-Vollständigkeit in deklarativem SQL wird durch rekursive gemeinsame Tabellenausdrücke implementiert. Es überrascht nicht, dass prozedurale Erweiterungen von SQL (PLSQL usw.) ebenfalls Turing-vollständig sind. Dies veranschaulicht einen Grund, warum relativ mächtige Sprachen, die nicht Turing-komplett sind, selten sind: Je mächtiger die Sprache anfangs ist, desto komplexer sind die Aufgaben, auf die sie angewandt wird, und desto eher wird ihre Unvollständigkeit als Nachteil empfunden, was ihre Erweiterung fördert, bis sie Turing-komplett ist. ⓘ
Das untypisierte Lambda-Kalkül ist Turing-komplett, aber viele typisierte Lambda-Kalküle, einschließlich System F, sind es nicht. Der Wert typisierter Systeme liegt in ihrer Fähigkeit, die meisten typischen Computerprogramme darzustellen und dabei mehr Fehler zu erkennen. ⓘ
Regel 110 und Conway's Game of Life, beides zelluläre Automaten, sind Turing-komplett. ⓘ
Unbeabsichtigte Turing-Vollständigkeit
Einige Spiele und andere Software sind zufällig, d. h. nicht absichtlich, Turing-komplett. ⓘ
Software:
- Microsoft Excel
- Microsoft PowerPoint ⓘ
Videospiele:
- Dwarf Fortress
- Städte: Skylines
- Opus Magnum ⓘ
Soziale Medien:
- Habbo Hotel ⓘ
Computersprachen:
- C++-Vorlagen ⓘ
Computer-Hardware:
- x86 MOV-Befehl ⓘ
Biologie:
- Chemische Reaktionsnetzwerke und enzymbasierte DNA-Computer sind nachweislich Turing-äquivalent ⓘ
Nicht-Turing-komplette Sprachen
Es gibt viele Rechensprachen, die nicht Turing-komplett sind. Ein solches Beispiel ist die Menge der regulären Sprachen, die durch reguläre Ausdrücke erzeugt und von endlichen Automaten erkannt werden. Eine leistungsfähigere, aber immer noch nicht Turing-komplette Erweiterung der endlichen Automaten ist die Kategorie der Pushdown-Automaten und kontextfreien Grammatiken, die üblicherweise zur Erzeugung von Parse-Bäumen in einer ersten Phase der Programmkompilierung verwendet werden. Weitere Beispiele sind einige der frühen Versionen der in Direct3D und OpenGL-Erweiterungen eingebetteten Pixel-Shader-Sprachen. ⓘ
In total funktionalen Programmiersprachen wie Charity und Epigram sind alle Funktionen total und müssen beendet werden. Charity verwendet ein Typsystem und Kontrollkonstrukte, die auf der Kategorientheorie basieren, während Epigram abhängige Typen verwendet. Die LOOP-Sprache ist so konzipiert, dass sie nur die Funktionen berechnet, die primitiv rekursiv sind. Alle diese Sprachen berechnen geeignete Teilmengen der gesamten berechenbaren Funktionen, da die vollständige Menge der gesamten berechenbaren Funktionen nicht berechenbar aufzählbar ist. Da alle Funktionen in diesen Sprachen total sind, können in diesen Sprachen auch keine Algorithmen für rekursiv aufzählbare Mengen geschrieben werden, im Gegensatz zu Turingmaschinen. ⓘ
Obwohl das (untypisierte) Lambda-Kalkül Turing-komplett ist, ist das einfach typisierte Lambda-Kalkül es nicht. ⓘ