Turing-Vollständigkeit - Turing completeness

In der Berechenbarkeitstheorie wird ein System von Datenmanipulationsregeln (wie der Befehlssatz eines Computers , eine Programmiersprache oder ein zellulärer Automat ) als Turing-vollständig oder rechnerisch universell bezeichnet, wenn es zur Simulation einer Turing-Maschine verwendet werden kann . Dies bedeutet, dass dieses System in der Lage ist, andere Regelwerke zur Datenmanipulation zu erkennen oder zu entscheiden. Turing-Vollständigkeit wird verwendet, um die Leistungsfähigkeit eines solchen Regelsatzes zur Datenmanipulation auszudrücken. Praktisch alle Programmiersprachen sind heute Turing-vollständig. Das Konzept ist nach dem englischen Mathematiker und Informatiker Alan Turing benannt .

Ein verwandtes Konzept ist das der Turing-Äquivalenz  – zwei Computer P und Q heißen äquivalent, wenn P Q simulieren und Q P simulieren kann. Die Church-Turing-These vermutet, dass jede Funktion, deren Werte durch einen Algorithmus berechnet werden können, durch a . berechnet werden kann Turing-Maschine, und wenn daher ein realer Computer eine Turing-Maschine simulieren kann, ist er Turing-Äquivalent zu einer Turing-Maschine. Eine universelle Turing-Maschine kann verwendet werden, um jede Turing-Maschine und damit die rechnerischen Aspekte jedes möglichen realen Computers zu simulieren.

Um zu zeigen, dass etwas Turing-vollständig ist, reicht es zu zeigen, dass es verwendet werden kann, um ein Turing-vollständiges System zu simulieren. Zum Beispiel kann eine imperative Sprache ist Turing-vollständig , wenn es hat bedingte Verzweigungen (zB „wenn“ und „goto“ Anweisungen oder einen „Zweig , wenn Null“ Anweisung, siehe one-Instruction Set Computer ) und die Möglichkeit , eine beliebige zu ändern Menge an Speicher (zB die Fähigkeit , eine beliebige Anzahl von Datenelementen aufrecht zu erhalten). Natürlich kann kein physikalisches System unendlichen Speicher haben; aber wenn die Begrenzung des endlichen Speichers ignoriert wird, sind die meisten Programmiersprachen ansonsten Turing-vollständig.

Nicht-mathematische Verwendung

Im umgangssprachlichen Gebrauch werden die Begriffe "Turing-vollständig" und "Turing-äquivalent" verwendet, um zu bedeuten, dass jeder reale Allzweckcomputer oder jede Computersprache die rechnerischen Aspekte eines anderen realen Allzweckcomputers annähernd simulieren kann oder Computer Sprache.

Bisher konstruierte reale Computer können wie eine Single-Tape-Turing-Maschine (das "Tape" entsprechend ihrem Speicher) funktional analysiert werden; daher kann die zugehörige Mathematik angewendet werden, indem ihre Operation weit genug abstrahiert wird. Reale Computer haben jedoch begrenzte physische Ressourcen, so dass sie nur linear begrenzte Automaten sind . Im Gegensatz dazu ist ein Universalcomputer als Gerät mit einem Turing-vollständigen Befehlssatz, unendlichem Speicher und unendlicher verfügbarer Zeit definiert.

Formale Definitionen

In der Berechenbarkeitstheorie werden mehrere eng verwandte Begriffe verwendet, um die Rechenleistung eines Rechensystems (wie einer abstrakten Maschine oder Programmiersprache ) zu beschreiben:

Turing-Vollständigkeit
Ein Rechensystem, das jede Turing- berechenbare Funktion berechnen kann, wird Turing-vollständig (oder Turing-mächtig) genannt. Alternativ kann ein solches System eine universelle Turingmaschine simulieren .
Turing-Äquivalenz
Ein Turing-vollständiges System heißt Turing-äquivalent, wenn jede Funktion, die es berechnen kann, auch Turing-berechenbar ist; dh es berechnet genau dieselbe Klasse von Funktionen wie Turing-Maschinen . Alternativ ist ein Turing-äquivalentes System eines, das eine universelle Turing-Maschine simulieren und von dieser simuliert werden kann. (Alle bekannten physikalisch implementierbaren Turing-vollständigen Systeme sind Turing-äquivalent, was die Church-Turing-These unterstützt .)
(Computer-) Universalität
Ein System heißt universell in Bezug auf eine Klasse von Systemen, wenn es jede Funktion berechnen kann, die von Systemen dieser Klasse berechenbar ist (oder jedes dieser Systeme simulieren kann). Typischerweise wird der Begriff Universalität stillschweigend in Bezug auf eine Turing-vollständige Klasse von Systemen verwendet. Der Begriff "schwach universell" wird manchmal verwendet, um ein System (zB einen zellularen Automaten ) zu unterscheiden, dessen Universalität nur durch Modifizieren der Standarddefinition der Turing-Maschine erreicht wird , um Eingabeströme mit unendlich vielen Einsen einzuschließen.

Geschichte

Die Turing-Vollständigkeit ist insofern von Bedeutung, als jeder reale Entwurf für ein Computergerä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 jeder andere programmierbare Computer kann. Dies sagt nichts über den Aufwand aus, der erforderlich ist, um das Programm zu schreiben , oder die Zeit, die die Maschine für die Berechnung benötigt, oder über Fähigkeiten der Maschine, die nichts mit der Berechnung zu tun haben.

Charles Babbage ‚s Analytical Engine (1830er Jahre) wäre die erste Turing-complete Maschine gewesen , wenn es zu der Zeit gebaut worden war es konzipiert wurde. Babbage schätzte, dass die Maschine zu großen Rechenleistungen fähig war, einschließlich primitiver logischer Überlegungen, aber er wusste nicht, dass keine andere Maschine bessere Leistungen erbringen konnte. Von den 1830er bis in die 1940er Jahre wurden mechanische Rechenmaschinen wie Addierer und Multiplikatoren gebaut und verbessert, aber sie konnten keine bedingte Verzweigung durchführen und waren daher nicht Turing-vollständig.

Im späten 19. Jahrhundert formulierte Leopold Kronecker Begriffe der Berechenbarkeit und definierte primitive rekursive Funktionen . Diese Funktionen können auswendig berechnet werden, aber sie reichen nicht aus, um einen universellen Computer zu erstellen, da die Anweisungen, die sie berechnen, keine Endlosschleife zulassen. Im frühen 20. Jahrhundert leitete David Hilbert ein Programm zur Axiomatisierung der gesamten Mathematik mit präzisen Axiomen und präzisen logischen Deduktionsregeln, die von einer Maschine ausgeführt werden konnten. Bald wurde klar, dass ein kleiner Satz von Deduktionsregeln ausreicht, um die Konsequenzen eines Satzes von Axiomen zu erzeugen. Diese Regeln wurden 1930 von Kurt Gödel als ausreichend bewiesen , um jeden Satz zu erstellen.

Der eigentliche Begriff der Berechnung wurde bald darauf isoliert, beginnend mit dem Unvollständigkeitssatz von Gödel . Dieses Theorem zeigte, dass Axiomensysteme begrenzt waren, wenn es um die Berechnungen ging, die ihre Theoreme herleiten. Church und Turing demonstrierten unabhängig voneinander, dass Hilberts Entscheidungsproblem (Entscheidungsproblem) unlösbar war, und identifizierten damit den Rechenkern des Unvollständigkeitssatzes. Diese Arbeit, zusammen mit Gödels Arbeit über allgemeine rekursive Funktionen , stellte fest, dass es Sätze einfacher Anweisungen gibt, die, wenn sie zusammengesetzt sind, in der Lage sind, jede Berechnung zu erzeugen. Die Arbeit von Gödel hat gezeigt, dass der Begriff der Berechnung im Wesentlichen einzigartig ist.

1941 stellte Konrad Zuse den Z3- Computer fertig . Zuse war damals mit Turings Arbeiten zur Berechenbarkeit nicht vertraut. Insbesondere fehlten dem Z3 spezielle Einrichtungen für einen bedingten Sprung, was ihn daran hinderte, Turing-Complete zu sein. 1998 zeigte Rojas jedoch, dass der Z3 in der Lage ist, bedingte Sprünge und damit Turing abzuschließen, indem er einige seiner Funktionen unbeabsichtigt nutzt.

Berechenbarkeitstheorie

Die Berechenbarkeitstheorie verwendet Berechnungsmodelle , um Probleme zu analysieren und zu bestimmen, ob sie berechenbar sind und unter welchen Umständen. Das erste Ergebnis der Berechenbarkeitstheorie ist, dass es Probleme gibt, für die es unmöglich ist, vorherzusagen, was ein (Turing-vollständiges) System über einen beliebig langen Zeitraum tun wird.

Das klassische Beispiel ist das Halteproblem : Erstellen Sie einen Algorithmus, der ein Programm in einer Turing-vollständigen Sprache und einige Daten, die diesem Programm zugeführt werden sollen, als Eingabe verwendet und bestimmt, ob das Programm, das auf die Eingabe reagiert, irgendwann stoppt oder fortfährt bis in alle Ewigkeit. Es ist trivial, einen Algorithmus zu erstellen, der dies für einige Eingaben tun kann , aber im Allgemeinen unmöglich. Für irgendein Merkmal der eventuellen Ausgabe des Programms ist es unmöglich zu bestimmen, ob dieses Merkmal zutrifft.

Diese Unmöglichkeit wirft Probleme bei der Analyse von Computerprogrammen der realen Welt auf. Zum Beispiel kann man kein Werkzeug schreiben, das Programmierer vollständig davor schützt, Endlosschleifen zu schreiben, oder Benutzer davor schützt, Eingaben bereitzustellen, die Endlosschleifen verursachen würden.

Stattdessen kann man ein Programm darauf beschränken, nur für einen festen Zeitraum ( timeout ) ausgeführt zu werden oder die Leistung von Flusssteuerungsanweisungen zu begrenzen (zum Beispiel nur Schleifen bereitstellen, die über die Elemente eines vorhandenen Arrays iterieren). Ein anderes Theorem zeigt jedoch, dass es Probleme gibt, die von Turing-vollständigen Sprachen lösbar sind, die von keiner Sprache mit nur endlichen Schleifenfähigkeiten gelöst werden können (dh jede Sprache, die garantiert, dass jedes Programm irgendwann zum Stillstand kommt). Eine solche Sprache ist also nicht Turing-vollständig. Zum Beispiel kann eine Sprache, in der Programme garantiert abgeschlossen und angehalten werden, nicht die berechenbare Funktion berechnen, die durch das Diagonalargument von Cantor für alle berechenbaren Funktionen in dieser Sprache erzeugt wird.

Turing-Orakel

Ein Computer mit Zugriff auf ein unendliches Datenband kann leistungsfähiger sein als eine Turing-Maschine: Das Band kann beispielsweise die Lösung des Halteproblems oder eines anderen Turing-unentscheidbaren Problems enthalten. Ein solches unendliches Datenband wird Turing-Orakel genannt . Auch ein Turing-Orakel mit Zufallsdaten ist nicht berechenbar ( mit Wahrscheinlichkeit 1 ), da es nur abzählbar viele Berechnungen, aber unzählbar viele Orakel gibt. Ein Computer mit einem zufälligen Turing-Orakel kann also Dinge berechnen, die eine Turing-Maschine nicht kann.

Digitale Physik

Alle bekannten physikalischen Gesetze haben Konsequenzen, die durch eine Reihe von Näherungen auf einem digitalen Computer berechenbar sind. Eine Hypothese namens digitale Physik besagt, dass dies kein Zufall ist, da das Universum selbst auf einer universellen Turing-Maschine berechenbar ist. Dies würde bedeuten, dass kein leistungsfähigerer Computer als eine universelle Turing-Maschine physikalisch gebaut werden kann.

Beispiele

Die als Turing-vollständigen Systeme diskutierten Rechensysteme (Algebren, Kalküle) sind für das Studium der theoretischen Informatik bestimmt . Sie sollen so einfach wie möglich sein, um die Grenzen der Berechnung besser zu verstehen. Hier sind ein paar:

Die meisten Programmiersprachen (ihre abstrakten Modelle, vielleicht mit einigen besonderen Konstrukten, die davon ausgehen, dass endlicher Speicher weggelassen wird), konventionelle und unkonventionelle, sind Turing-vollständig. Das beinhaltet:

Einige Rewrite-Systeme sind Turing-komplett.

Turing-Vollständigkeit ist eine abstrakte Aussage über die Fähigkeit und keine Vorschrift spezifischer Sprachmerkmale, die verwendet werden, um diese Fähigkeit zu implementieren. Die zum Erreichen der Turing-Vollständigkeit verwendeten Funktionen können sehr unterschiedlich sein; Fortran- Systeme würden Schleifenkonstrukte oder möglicherweise sogar goto- Anweisungen verwenden, um Wiederholung zu erreichen; Haskell und Prolog, denen die 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-vollständig. Auch reine funktionale Sprachen sind Turing-vollständig.

Turing-Vollständigkeit in deklarativem SQL wird durch rekursive allgemeine Tabellenausdrücke implementiert . Es überrascht nicht, dass prozedurale Erweiterungen von SQL ( PLSQL , etc.) ebenfalls Turing-vollständig sind. Dies illustriert einen Grund, warum relativ mächtige nicht-Turing-vollständige Sprachen selten sind: Je mächtiger die Sprache zunächst ist, desto komplexer sind die Aufgaben, auf die sie angewendet wird, und desto eher wird ihre mangelnde Vollständigkeit als Nachteil wahrgenommen, was ihre Erweiterung, bis es Turing-vollständig ist.

Der untypisierte Lambda-Kalkül ist Turing-vollständig, aber viele typisierte Lambda-Kalküle, einschließlich System F , sind es nicht. Der Wert typisierter Systeme beruht auf ihrer Fähigkeit, die meisten typischen Computerprogramme darzustellen und gleichzeitig mehr Fehler zu erkennen.

Rule 110 und Conways Game of Life , beides zellulare Automaten , sind Turing-vollständig.

Unbeabsichtigte Turing-Vollständigkeit

Einige Spiele und andere Software sind zufällig Turing-komplett, dh nicht von Natur aus.

Software:

Videospiele:

Sozialen Medien:

Kartenspiele:

Zero-Person-Spiele (Simulationen):

Computersprachen:

Computerhardware:

  • x86-MOV-Anweisung

Biologie:

Nicht-Turing-vollständige Sprachen

Es gibt viele Computersprachen, die nicht Turing-vollständig sind. Ein solches Beispiel ist die Menge der regulären Sprachen , die von regulären Ausdrücken erzeugt und von endlichen Automaten erkannt werden . Eine leistungsfähigere , aber immer noch nicht Turing-vollständige Erweiterung des endlichen Automaten ist die Kategorie der Kellerautomaten und kontextfreien Grammatiken , die Parse - Bäume in einem Anfangsstadium des Programms zu erzeugen häufig verwendet werden , Compilierung . Weitere Beispiele sind einige der frühen Versionen der Pixel-Shader-Sprachen, die in Direct3D- und OpenGL- Erweiterungen eingebettet sind .

In total funktionalen Programmiersprachen wie Charity und Epigram sind alle Funktionen total und müssen beendet werden. Charity verwendet ein Typensystem und Kontrollkonstrukte basierend auf der Kategorietheorie , 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 berechnen echte 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 im Gegensatz zu Turing-Maschinen auch keine Algorithmen für rekursiv aufzählbare Mengen in diesen Sprachen geschrieben werden.

Obwohl der (untypisierte) Lambda-Kalkül Turing-vollständig ist, ist der einfach typisierte Lambda-Kalkül nicht.

Datensprachen

Der Begriff der Turing-Vollständigkeit gilt nicht für Sprachen wie XML , HTML , JSON und YAML , da sie normalerweise zur Darstellung strukturierter Daten und nicht zur Beschreibung von Berechnungen verwendet werden. Diese werden manchmal als Auszeichnungssprachen oder besser als "Containersprachen" oder "Datenbeschreibungssprachen" bezeichnet.

Siehe auch

Anmerkungen

Verweise

Weiterlesen

Externe Links