nicht angemeldet
Turingvollständigkeit vielleicht?
Über eine ähnliche Frage habe ich neulich woanders diskutiert. Ich habe kritisiert, dass Programmiersprachen in aller Regel Turing-vollständig sind, ohne dass die Vor- und Nachteile jemals gegeneinander abgewogen worden wären.
Im Alltag werden Programmierer:innen praktisch nie mit Problemen konfrontiert, die die volle Ausdrucksstärke einer Turing-Maschine benötigen. Man muss schon sehr kreativ werden, um Probleme zu konstruieren, die rekursiv aber nicht primitiv-rekursiv sind. Ein pathologisches Beispiel ist die sogenannte Ackermann-Funktion, aber selbst sie kann mit primitiv rekursiven Systemen und Funktionen höherer Ordnung berechnet werden.
Umgekehrt erkauft man mit Turing-Vollständigkeit enorm viele Probleme. Alle unerwarteten Laufzeitfehler, die nicht durch physische Grenzen (zu wenig Speicher, abgebrochene Netzwerk-Verbindungen etc.) ausgelöst werden und ausnahmslos alle ungewollten Endlosschleifen sind auf Turing-Vollständigkeit zurückzuführen.
So viel zu den praktischen Auswirkungen. In der Theorie hat Turing-Vollständigkeit noch viel weitreichendere Implikationen. Alonzo Church, der Erfinder des Lambda-Kalküls, war erschüttert als er erfahren hat, dass sein Kalkül genauso mächtig ist wie eine Turing-Maschine. Denn Church war Logiker, und er wollte mit seinem Kalkül die Logik mechanisieren. Turing-Vollständigkeit bedeutete für Church, dass sein Kalkül inkonsistent ist. Das heißt, mit seinem System ließen sich widersprüchliche Aussagen ableiten und demzufolge konnte man damit jede Aussage ableiten, die man wollte. Church hat den Rest seines Lebens damit verbracht diesen Makel zu beseitigen. Mit Erfolg.
TS
Der Martin
Rolf B