spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Also aus den oben gegebenen Definitionen ergibt sich ja eine relativ simple Konstruktion dieser endrekursiven Funktion. Die rekursive Funktion r(x) terminiert fuer alle x in endlicher Zeit. Ich kann also in endlicher Zeit fuer alle x die B(x) erfuellen das r(x) berechnen, solange auch dies endlich ist. Damit kann ich dann z(x) konstruieren, schlimmstenfalls als abschnittsweise definiert (praktisch wäre das also eine LUT). Damit lässt sich meiner Meinung nach die Existenz eines B(x) und z(x) zeigen. Wenn ich das aber innerhalb einer beschraenkten Zeit t machen muss, dann ist dies nur moeglich wenn ich ein B(x) so waehlen kann, das ich alle r(x) innerhalb von t berechnen kann. D.h. aber umgekehrt das ich fuer jede beschraenkte Zeit t eine Funktion r'(x) konstruieren kann, die für jedes x nach endlicher Zeit hält, aber jeweils erst nach t, indem ich r'(x) = r(x) + s(x) definiere, wenn s(x) fuer jedes x eine Berechnungsdauer von mindestens t benötigt.

Theoretisch könnte man doch den gesamten Zustand einer Turingmaschine im Funktionsparameter x kodieren, dann kann man jede beliebige berechenbare Funktion "endrekursiv" angeben:

• Die Funktion y(x) führt einen Schritt auf der Turingmaschine aus und liefert deren neuen Zustand.
• Die Funktion z(x) liest die Ausgabe der Turingmaschine vom Band.
• Die Abbruchbedingung B(x) ist genau dann wahr, wenn die Turingmaschine angehalten hat, also sich in einem Endzustand befindet.

Einziger Haken: Man muss "von außen" erst einmal den initialen Parameter x konstruieren, d.h. die Kodierung der gewünschten Turingmaschine inkl. Daten auf ihrem Band.

Zitat von »David Scherfgen«

Theoretisch könnte man doch den gesamten Zustand einer Turingmaschine im Funktionsparameter x kodieren

Ja, genau da liegt auch schon der Knackpunkt. Selbst wenn das theoretisch moeglich ist, praktisch dauert allein die Angabe dieser Kodierung schon wieder länger als jede beliebige endliche Zeit t.