Eine Eigenschaft eines Rechensystems, die anzeigt, dass es jede universelle programmierbare Maschine simulieren kann und damit jede Berechnung ausführen kann, die eine solche ideale Maschine leisten kann, vorausgesetzt unbeschränkte Zeit und Speicher.

Prinzip

Universalität durch Simulation: Kann ein System die Zustandsübergänge einer idealen programmierbaren Maschine emulieren, so erreicht es dieselbe Klasse berechenbarer Verhaltensweisen unter idealisierten Ressourcen.

Demonstration

Eine minimale imperative Sprache mit bedingter Verzweigung und unbeschränktem Ganzzahlspeicher kann eine universelle Maschine simulieren und ist damit Turing-vollständig; das zelluläre Automat Regel 110 ist ein klassisches konstruktives Beispiel.

Fehlanwendung

Turing-Vollständigkeit mit praktischer Nutzbarkeit, Effizienz, Entscheidbarkeit oder garantierter Terminierung gleichzusetzen, ist falsch; Vollständigkeit betrifft nur formale Universalisierbarkeit unter idealisierten Ressourcen.

Konsequenz

Ist ein System Turing-vollständig, so lassen sich darin beliebige algorithmische Verfahren kodieren, gleichzeitig gelten dann auch klassische Unentscheidbarkeits- und Nichtterminierungsresultate für Programme in diesem System.

Umkehrung

Ein Turing-inkomplettes System kann keine universellen Berechnungen beliebiger Art simulieren und kann somit nicht jeden algorithmischen Prozess ausdrücken, es kann jedoch entscheidbar oder voraussagbarer sein.

Abgrenzung

Beruht auf Idealisierungen wie unbeschränktem Speicher und präziser Zustandskontrolle; Modelle mit begrenztem Speicher, eingeschränktem Kontrollfluss oder nicht programmierbaren Primitiven gehören nicht dazu.

Semantische Spannung

Unterscheidet sich von informellen Vorstellungen von Ausdruckskraft oder Benutzerfreundlichkeit: Eine Sprache kann für Anwender sehr ausdrucksstark sein, ohne Turing-vollständig zu sein, und umgekehrt; Vollständigkeit ist eine formale Simulationseigenschaft, kein Gebrauchswertmaß.

Synthese

Turing-Vollständigkeit klassifiziert Systeme nach ihrer Fähigkeit, eine universelle programmierbare Maschine unter idealisierten Ressourcen zu emulieren, was sowohl maximale Repräsentationskraft als auch das Eintreten von Unentscheidbarkeitsphänomenen impliziert.