Sei
[img]http://mokrates.de/cgi-bin/texstring?G_0%0A[/img] die Menge aller Funktionen die von GOTO-Programmen berechnet werden koennen, die nur Vorwaertspruenge enthalten.
Zeigen oder widerlegen Sie: Es gibt eine totale und berechenbare Funktion, die nicht in
[img]http://mokrates.de/cgi-bin/texstring?G_0[/img] liegt.

OK ich weiss es gibt eine, aber wie sieht der formale Beweis aus?

Zur Idee: Ich hab bereits gezeigt, dass man mit GOTO-Programmen die 1 Rückwaertssprung enthalten duerfen jede berechenbare Funktion hinbekommt:

Jede GOTO-berechenbare Funktion ist WHILE-berechenbar.
Jedes WHILE-Programm kann dargestellt werden als WHILE-Programm mit nur einer WHILE-Schleife.
Und WHILE-Programme koennen durch GOTO-Programme ersetzt werden mit einem RUeckwaertssprung pro WHILE-Schleife.

Ausgehend von der Definition im Schöning würde ich das so machen:

Wenn nur Vorwärtssprünge erlaubt sind, lässt sich die
Laufzeit des Programms durch die Programmlänge nach oben
abschätzen. Außerdem kann bei jeder Anweisung das Maximum
über alle Variableninhalte und Konstanten höchstens
verdoppelt werden (denn es sind nur Additionen und
Subtraktionen erlaubt). Wenn also P ein Programm der Länge
k ist, ist bei Eingabe n (für großes n, das alle Konstanten
in P und k übersteigt) das maximale Ergebnis n*2^k. Das
Ergebnis ist also kleiner als n*2^n. Also kann die Funktion
n*2^n nicht berechnet werden.