loop-berechenbare Funktionen

Cuculli

Hi,

Ich habe leider keinen Anfang und kein Ende, darum bitte ich um Hilfe.

Aufagbe

a) Zeigen Sie, dass jede loop-berechenbare-Funktion auch durch ein loop'-Programm berechent werden kann, bei dem die Wertzuweisung x_i:=x_j+1 und x_i:=x_j-1 durch die Wertzuweisung x_i:=x_i+1 und x_i:=x_iersetzt wurden.

b) Zeigen Sie (zum Beispiel mit Hilfe einer strukturellen Induktion), dass nicht jede loop-berechenbare Funktion durch ein loop''-Programm berechnet werden kann, bei dem die Wertzuwesiung x_i:=x_j+1 durch die Wertzuweisung x_i:=x_j ersetzt wurde.

Gruß Cuculli

CStoll

(vorweg: Bist du dir sicher, daß die Indizes richtig gesetzt sind? "x_i:=x_i" wäre eine noop.)

@a: Du mußt die Dekrement-Operation durch Inkrement und Zuweisung realisieren, z.B. so:

y=0;
while(y+1!=x)
  y=y+1;

@b: Du mußt beweisen, daß du die Inkrement-Operation NICHT durch die vorhandenen Sprachmittel (und Zuweisung) ausdrücken kannst.

PS: Und wie bei deinem Kollegen gilt - die korrekte Syntax mußt du aus deinem Skript abschreiben.

Jester

CStoll schrieb:

PS: Und wie bei deinem Kollegen gilt - die korrekte Syntax mußt du aus deinem Skript abschreiben.

Dabei ist allerdings ein bißchen problematisch, daß Du immer while-Programme schreibst. while-Programme lassen sich aber nicht immer als loop-Programme umschreiben. Das ist hier also keine rein syntaktische Frage. Ich denke einfacher wäre es, würdest Du for-Schleifen schreiben.

CStoll

So weit ist mir die Loop-Programmierung nicht im Gedächtnis geblieben

OK, dann ein Versuch mit for:

y=0;
for(z=0;z!=x;z=z+1)
  y=z;

(wenn mich mein Gedächtnis nicht komplett täuscht, gilt damit am Ende y==x-1)