Was bedeutet "Turing vollständig"?
3 Antworten
Wenn du dich damit tiefgründig beschäftigen willst, musst du sehr viel Informatik lernen...
Praktisch gesehen heißt es aber: mit einer solchen Programmiersprache kann man jeden erdenklichen Algorithmus implementieren.
Ich glaube für die Praxis hat das keine echte Bedeutung; es handelt sich um einen theoretischen Begriff aus der informatik.
Dass es in der Praxis kaum eine Bedeutung hat, hängt m. E. damit zusammen, dass nur ein paar Nischenprogrammiersprachen nicht Turing-vollständig sind. (Ich hatte mal mit so einer Makro-Programmiersprache zu tun, die keine Schleifen kannte, bei der die Anzahl der Durchläufe nicht schon am Anfang bekannt war. War nicht nett.)
In der Berechenbarkeitstheorie gibt es die universelle Turingmaschine. Und Turingvollständig oder turingmächtig sagt man zu logischen Systemen (z.B. Computer oder Programmiersprachen), wenn sie alles berechnen können, was eine universelle Turing-Maschine auch berechnen kann. Hierbei fiel in einer anderen Antwort auch der Begriff universell programmierbar.
Die universelle Programmierbarkeit.