Turing Complete

Als Turing Complete wird ein System mit einer universellen Programmierbarkeit beschrieben und bezeichnet die Eigenschaft einer Programmiersprache, sämtliche Funktionen berechnen zu können, welche eine universelle Turingmaschine berechnen kann. Das Konzept ist benannt nach dem englischen Mathematiker Alan Turing.

Eine imperative Programmiersprache ist Turing Complete wenn sie bedingtes Verzweigungen hat (if, goto, etc.) und die Fähigkeit eine beliebige Menge an Speicher zu verändern (eine beliebige Anzahl Variablen zu verwalten). Da dies fast immer der Fall ist, sind die meisten, wenn nicht alle imperativen Sprachen Turing Complete, sofern die Einschränkungen des begrenzten Speichers ignoriert werden.

Die rechnerischen Systeme (Algebren, Kalküle), die als Turing Complete diskutiert werden, sind für das Studium der theoretischen Informatik gedacht. Sie sollen so einfach wie möglich sein, damit die Grenzen der Berechnung leichter zu verstehen sind. Hier sind ein paar:

Die meisten Programmiersprachen, konventionell und unkonventionell, sind Turing Complete. Das beinhaltet:

Alle General Purpose Sprachen:

  • Prozedurale Sprachen wie
    • C
    • Pascal
  • Objekt-orientierte Sprachen wie
    • Java
    • SmallTalk
    • C#
    • Objective-C
  • Multi-paradigm Sprachen wie
    • Ada
    • C++
    • Python
    • R
    • Swift

Die meisten Sprachen weniger geläufige Paradigmen:

  • Funktionelle Sprachen
    • Lisp
    • Haskell
  • Logische Sprachen
    • Prolog
  • Deklarative Sprachen
    • PHP

Turing Complete ist eine abstrakte Aussage über Fähigkeit statt einer Beschreibung bestimmter Sprachmerkmale, die verwendet werden, um diese Fähigkeit zu implementieren. Die verwendeten Features um Turing Complete zu erreichen sind sehr verschieden: Fortran würde Loop Konstrukte oder möglicherweise goto Anweisungen verwenden um die Wiederholungen zu erzielen; Haskell und Prolog, die fast keine Schleife mehr haben, würden Rekursion benutzen. Die meisten Programmiersprachen beschreiben Berechnungen auf von Neumann-Architekturen, die Speicher (RAM und Register) und eine Steuereinheit (CPU) aufweisen. Diese beiden Elemente machen diese Architektur Turing Complete. Sogar reine funktionale Sprachen sind Turing Complete.

Es existieren viele rechnerische Sprachen, die nicht Turing Complete sind. Ein solches Beispiel ist die Menge der regulären Sprachen, die durch reguläre Ausdrücke generiert werden. Obwohl (nicht typisierter) Lambda Calculus Turing Complete ist, ist einfach typisierte Lambda Calculus nicht.

Der Begriff Turing Complete bezieht sich nicht auf Sprachen wie XML, HTML, JSON und YAML, da sie typischerweise zur Darstellung von strukturierten Daten und nicht zur Berechnungen verwendet werden.

Diese werden manchmal als Markup-Sprachen „Containersprachen“ oder „Datenbeschreibungssprachen“ bezeichnet. Rule110, ein Turing Complete Zellautomaten, wurde jedoch erfolgreich in CSS3 implementiert, was in gewissem Masse seine Turing Complete beweist.