Was ist Turing-Vollständigkeit?
Turing-Vollständigkeit liegt vor, wenn eine Programmiersprache die Funktionen einer Turing-Maschine ausführen kann. Dies ist ein Konzept für einen sehr einfachen mechanischen Computer, der manchmal als die einfachste Maschine bezeichnet wird, die als Computer betrachtet werden kann. Praktisch alle heute verwendeten Programmiersprachen und theoretisch die Computer, auf denen sie ausgeführt werden, sind vollständig.
Das Konzept der Vollständigkeit von Turing stammt von Alan Turing, einem britischen Informatiker, der im Zweiten Weltkrieg unter anderem verschlüsselte Nachrichten entschlüsselt hat. Zu seinen Arbeiten am Computer gehörte die Entwicklung einer Philosophie darüber, was ein Computer tatsächlich leisten kann. Dies beinhaltete das Konzept, dass Computer einfach durch Ausführen von Algorithmen funktionieren. Das heißt, sie befolgen ein festes Regelwerk, um Daten zu verarbeiten und Probleme zu lösen. Dies bedeutet, dass ein Computer nicht so "denkt" oder Entscheidungen trifft, wie es eine Person kann.
Um das Konzept zu veranschaulichen, beschrieb Turing eine hypothetische Maschine, die er eine "A-Maschine" nannte, wobei das "A" für automatisch steht; andere nannten es später die Turingmaschine. Die Maschine verarbeitete eine Bandspule, die sich vorwärts oder rückwärts bewegen konnte und eine Reihe von Symbolen enthielt. Die Maschine kann jederzeit ein Symbol verarbeiten und gegebenenfalls ändern. Für die Zwecke des Konzepts kann die Bandspule unendlich lang sein, was bedeutet, dass der Arbeitsspeicher des Computers nicht von Natur aus eingeschränkt ist. Dies ist eine Analogie zu der Vorstellung, dass, sobald ein Computer eine Reihe von Anweisungen befolgt, die Datenmenge, auf die er diese Anweisungen anwenden kann, nur physischen Grenzen unterliegt.
Ironischerweise sind die meisten Computer heutzutage nicht vollständig. Dies liegt daran, dass sie Einschränkungen hinsichtlich des verfügbaren Speicherplatzes und damit der Daten haben, die sie verarbeiten können. Sie haben auch körperliche Einschränkungen, vor allem, dass sie sich irgendwann abnutzen. Tatsächlich ist es die Programmiersprache, die Turing-Vollständigkeit besitzt. Aus diesem Grund ist ein Computer, auf dem ein solches Programm ausgeführt wird, kein Turing-Computer, sondern kann zur Simulation eines solchen Computers verwendet werden.
Die Turing-Vollständigkeit darf nicht mit dem Turing-Test verwechselt werden. Dies war ein Experiment, das von Turing entwickelt wurde, um festzustellen, ob Computer sich in natürlicher Sprache unterhalten können. Das Prinzip des Tests ist, dass der Computer den Test besteht, wenn ein Mensch den Unterschied zwischen einer Nur-Text-Konversation mit dem Computer und einem anderen Menschen nicht erkennen kann. Während einige Computer den Test bestanden haben, wenn der Bereich der Gesprächsthemen eingeschränkt ist, hat dies keiner in einem uneingeschränkten Gespräch getan.