Ich habe mal etwas nachgedacht.
>>7345>Zwei verschiedene Implementierungen können inkompatibel sein, was sie z.B. im Hinblick auf maximale Objektzahl auch sind.
Korrekt. Das widerspricht dem vorherigen aber nicht. Bloß weil man sagt, C sei die Menge aller möglichen C-Sprachimplementierungen, heißt es nicht, dass zwei C-Sprachimplementierungen zueinander kompatibel sind. Das widerspricht auch nicht:
>Und so ist C turing-vollständig, weil C die Menge aller möglichen C-Sprachimplementierungen ist.
Denn die Frage ist, was überhaupt der Bedeutungsinhalt von "C ist nicht turing-vollständig, da mit Pointern nur endlich viel Speicher adressiert werden kann" sein soll.
Ich mache mal ein Beispiel: Wenn man die (offensichtlich nicht turing-vollständige) Programmiersprachen L_k = "Schreibe k-viele Einsen aufs Band" definiert, hat man mit L_1, L_2, ... eine Menge an Sprachen. Nun kann man sagen, L = {L_1, L_2, ...} ist die Menge der Sprachen. D.h. L_5 ist eine L-Sprache.
Und so hat man auch bei C eine Menge an Sprachen. Was ist also C? Eine Menge an Sprachen oder nicht? Was meint man, wenn man von C spricht? Eine spezifische Sprache mit z.B. Pointergröße 32 oder 64 Bits - und der Rest ist dann keine C-Sprache? Oder die gesamte Menge aller möglichen Sprachen? Ich sage: C_32 ist eine C-Sprache.
D.h. das obige "C ist (nicht) turing-vollständig" ist nicht spezifisch genug. Spezifischer genug wären:
1. "Gegeben ein bestimmtes Programm und eine bestimmte C-Sprache, lässt sich das Programm in dieser C-Sprache umsetzen?"
2. "Gegeben eine bestimmte C-Sprache, lassen sich alle Programme in dieser C-Sprache umsetzen?"
3. "Gegeben ein bestimmtes Programm, lässt sich das Programm in einer C-Sprache umsetzen?"
Die Antworten sind:
1. Hängt vom Programm und der C-Sprache ab.
2. Nein.
3. Ja.
Wenn man also "C ist turing-vollständig" im Sinne von 3. versteht, so ist das korrekt. Wenn man "C ist nicht turing-vollständig" im Sinne von 2. versteht, so ist das korrekt. Man muss nur mal in der Frage genau genug werden, dann lösen sich die Probleme in Wohlgefallen auf.
>>7347>>Dann wird die Turingmaschine weggeschmissen und eine neue, identische (mit leerem Band) hingestellt.
>Und wer macht das, der Weihnachtsmann? Das kann ja nur durch eine andere Turing-Maschine geschehen, also ist deine Server-Implementation nicht vollständig.
Eine Turing-Maschine funktioniert klassisch so: Eine TM kriegt eine Eingabe, berechnet das Programm, und (wenn sie hält) hat dann eine bestimmte Ausgabe auf dem Band. Sollte die TM einmal in einem akzeptierenden Zustand sein, kriegt man die dort nie wieder raus, da es keine Übergänge aus einem akzeptierenden Zustand heraus gibt.
Deshalb erst mal zu:
>>Die restlichen Eingaben, d.h. die, auf denen das Programm nicht hält, sind wurst.
>Ein Server ist ein Programm, dass idealerweise nicht hält.
Das Problem und die Ursache der Konfusion ist, dass da von zwei unterschiedlichen "halten" die Rede ist, und zwar nennen wir es einmal das TM-Halten und das Computerprogramm-Halten. Im ursprünglichen Zitat verwendete ich "halten" im Sinne von TM-Halten.
Zum TM-Halten: Bei einer klassischen TM ist es so, dass man eine Eingabe hat, und nur einmal eine Funktion für diese Eingabe berechnen will, und dann fertig ist. Bevor die TM nicht gehalten hat, ist das Band nicht die Ausgabe der TM, da die TM schließlich noch in späteren Schritten etwas auf das Band schreiben könnte. Wenn die TM nicht gehalten hat, gibt es auch keine Ausgabe. Bei einer Turing-Maschine gibt es auch nur eine endlich lange Eingabe.
Zum Computerprogramm-Halten: Natürlich kann da ein Programm eine Ausgabe liefern, bevor es hält. Ob ein Programm eine unendlich lange Eingabe erhalten kann, darüber lässt sich streiten.
Jetzt zu:
>Und wer macht das, der Weihnachtsmann? Das kann ja nur durch eine andere Turing-Maschine geschehen, also ist deine Server-Implementation nicht vollständig.
Natürlich macht das eine Turing-Maschine. Man nimmt die Server-TM, führt diese bis zum TM-Halt aus (d.h. die Antwort für den Client steht auf dem Band, und M hält dann), löscht das Band (maximale Länge des Bandinhalts kann von der TM berechnet werden) und führt dann wieder die Server-TM aus, usw. Das Problem ist dabei, dass man die gesamte Eingabe, d.h alle Client-Anfragen, im Voraus kennen muss. Wie kann man das lösen? Wie kann der Server die Client-Anfragen antizipieren?
Der Trick, ein Client-Server-System als TM zu bauen, liegt darin, nicht Clients und Server zu trennen, sondern das alles als eine einzige TM zu pressen, d.h. alle Clients und der Server in einer TM. Eingabe an die TM sind die Eingaben an die Clients vom Nutzer (endlich), Ausgabe sind die Ausgaben der Clients an den Nutzer (endlich). So kann man das als eine einzige TM bauen, ohne das Wekschmeißen und Neuanfangen mit leerem Band wie in einem vorherigen Pfosten.
Alles, was die Nutzer vom Client-Server-System berechnet haben wollen, können sie so von der TM berechnet bekommen.
>>TM-Programme sind immer pure Funktionen.
>Dann wäre jede Implementierung, die nicht-reine Funktionen unterstützt, mächtiger als eine Turing-Maschine. Das glaube ich nicht, Tim.
Man kann nicht-reine Funktionen durch reine Funktionen ersetzen, die den gesamten Status als zusätzlichen Parameter haben, und den gesamten (eventuell geänderten) Status mit zurückgeben. Klappte ähnlich in C++ schon mit dem versteckten
this
-Pointer als ersten Parameter der Funktion. :3