Turing Complete
Turing-Vollständigkeit bedeutet, dass ein Rechensystem eine Turing-Maschine simulieren und jede berechenbare Funktion berechnen kann — der Maßstab universeller Rechenleistung.
Zweck
Die Leistungsobergrenze einer Sprache/eines Systems beurteilen und die Grenzen der Berechenbarkeit verstehen.
Mechanismus
Erfordert: bedingte Verzweigung + beliebige Schleifen/Rekursion + Lese-Schreib-Speicher. Die meisten Programmiersprachen sind turingvollständig. HTML+CSS (umstritten), SQL (rekursive CTEs) und Regex (Backreferences) liegen an der Grenze. Das Halteproblem ist unentscheidbar.
Anwendungsfälle
- Theorie der Berechenbarkeit
- Sprachmächtigkeit
- Berechenbarkeit