In der Informatik ist die Turing-Vollständigkeit eine Klassifizierung für ein Regelsystem, das Daten manipuliert. Es ist nach dem Informatiker Alan Turing, dem Erfinder der Turing-Maschine, benannt.
Beispielsweise sind Programmiersprachen und CPU-Befehlssätze Beispiele für formale Regelsysteme, die auf Daten zugreifen und diese modifizieren. Wenn die Regeln Turings hypothetische Rechenmaschine simulieren können, werden die Regeln als „Turing vollständig“ bezeichnet. Es kann mathematisch nachgewiesen werden, dass ein Turing-vollständiges System in der Lage ist, alle möglichen Berechnungen oder Computerprogramme auszuführen.
Ein Beispiel für ein vollständiges Turing-System ist der Lambda-Kalkül, der von Alonzo Church, dem Professor von Alan Turing, entwickelt wurde.
Beispiele für Turing-Komplettsysteme
- Viele prozedurale Programmiersprachen, einschließlich C und Pascal.
- Die meisten objektorientierten Programmiersprachen wie Java und C++.
- Logik-Programmiersprachen wie Prolog.
- Viele endliche Automatensysteme, wie Conways Game of Life.
Informatik, Lambda-Kalkül, Programmierbegriffe
