Hallo dewdeded,
TL; DR: Es gibt keine
(un-)vollständige Turing-Vollständigkeit! Turingvollständigkeit kann auch für real existierende Systeme gelten und ist in der Praxis durch das
"One-Size-Fits-All"-Schema in der Computerchip-Branche eher die Regel als die Ausnahme.
Genau, denn vollständige Turing-Vollständigkeit in einer Kryptowährung führt ja mindestens zu folgenden Sicherheitsgefahren:
Hast du Gyrsurs Beitrag überhaupt gelesen?
http://de.wikipedia.org/wiki/Turing-Vollst%C3%A4ndigkeitExakt ausgedrückt bezeichnet Turing-Vollständigkeit in der Berechenbarkeitstheorie die Eigenschaft einer Programmiersprache oder eines anderen logischen Systems, sämtliche Funktionen berechnen zu können, die eine universelle Turingmaschine berechnen kann. Anders ausgedrückt, das System und eine universelle Turingmaschine können sich gegenseitig emulieren.
Auch wenn ich kein Freund von der deutschen Wikipedia bin, so ist der von ihm zitierte Abschnitt bereits die Antwort. Deshalb dachte ich eigentlich, dass das allgemein verstanden wäre.
Wenn du also von einer
"vollständigen Turing-Vollständigkeit" schreibst, dann musst du dir auch die folgende Frage gefallen lassen: Was ist
unvollständige Turing-Vollständigkeit?
Vorsicht, das ist eine Fangfrage! Die Antwort ist einfach die, dass es keine (un-)vollständige Turing-Vollständigkeit gibt! Es gibt Turing-Vollständigkeit. Aber es gibt keine Abstufung dazu.
Die Turingvollständigkeit (engl. turing completeness) ist auch unter dem Namen
Turingmächtigkeit (engl. turing powerful) bekannt, was hoffentlich etwas weniger verwirrend klingt. Es geht darum, dass die betrachtete Turingmaschine genügend
Macht (im Sinne von
Möglichkeiten) besitzt, um eine andere Turingmaschine zu simulieren. Auf den Zusammenhang kommt es an: Wenn eine Turingmaschine eine beliebige andere Turingmaschine simulieren kann, dann ist sie universell genug, um jedes
denkbare und als Algorithmus formulierbare Problem zu lösen. Das ist das ausschlaggebende Argument für praktische Anwendungen und notwendige Bedingung für die Klassifikation als
turingmächtiges System.
Der Schnickschnack mit dem unendlichen Band ist nur ein Kunstgriff, damit man nicht mit so schwammigen Begriffen wie "genügend großes Band" arbeiten muss und dann beim Beweisen mit der begrenzten Kapazität zu kämpfen hat. Hier haben sich also die Theoretiker verständlicherweise das Leben leichter gemacht. Es geht aber insbesondere in der praktischen Betrachtung nur darum, ob man ein System mit einem anderen System simulieren oder emulieren kann. Mehr nicht.
Falls nämlich das unendliche Band ausschlaggebend wäre, dann gäbe es in der Praxis keine turingmächtigen Systeme und dementsprechend hätte diese Klasse nur noch theoretische aber keine praktische Relevanz mehr.
Jedoch werden gängige Programmiersprachen wie z.B. Java, C/C++, C# und PHP als turingmächtige Programmiersprachen gehandelt (man kann z.B. einen Java-Bytecode-Compiler in C schreiben und umgekehrt; außerdem ist z.B. C mächtig genug um einen Interpreter für Java-Bytecode zu implementieren: die JVM).
Außerdem gibt es auch klar ersichtliche Anwendungen, welche turingmächtig sein müssen: Betriebssysteme, virtuelle Maschinen und Emulatoren. Im Allgemeinen ist es also bereits hinreichend (aber
nicht notwendig!), wenn man auf Loopmächtigkeit prüft und bei negativem Resultat von einer Einstufung als
"Turingmächtig" ausgeht. Ein guter Test ist halt die Implementierung des Klassikers: die
Ackermann-Funktion. Ist also die Ackermann-Funktion implementierbar, so ist das System
mächtiger als loopmächtig, was im praktischen Bereich bereits hinreichend für die begründete Annahme eines turingmächtigen Systems ist.
Insofern ist der Wikipedia-Artikel nicht ganz optimal geschrieben, auch wenn dieser eigentlich genau das oben Geschilderte ausdrückt:
http://de.wikipedia.org/wiki/Turing-Vollst%C3%A4ndigkeitObwohl solche Maschinen physikalisch unmöglich sind, da sie unbegrenzten Speicherplatz besitzen müssten, werden gängige Programmiersprachen und Computer, die universell wären, wenn sie unbegrenzten Speicher besäßen, als Turing-vollständig bezeichnet.
Gruss,
Bill
Tante
Edith mal wieder: TL; DR war zu schwammig gehalten.
