RAM-Berechenbarkeit

Aufgabe

Zeigen Sie, dass die Multiplikationsfunktion für natürliche Zahlen RAM-berechenbar ist.

Lösung

GOTO-Interpreter

Aufgabe

Verwenden Sie VCC aus AtoCC, um einen Interpreter für GOTO-Programme zu entwickeln.

Lösung

Ein GOTO-Programm besteht aus Marken M_i denen jeweils eine Anweisung A_i getrennt durch einen Doppelpunkt (:). Marken, auf die kein GOTO-Befehl verweist, können weggelassen werden.

M_1 : A_1; M_2 : A_2; ...; M_k : A_k

Es stehen 5 verschiedene Anweisungen zur Auswahl:

• Wertzuweisungen: X_i := X_j \pm C (X_i := 0. wenn X_j - C < 0)
• unbedingter Sprung: GOTO M_i
• bedingter Sprung: IF X_i = C THEN GOTO M_i
• Stop: HALT

X ist eine Variable, C ist eine Konstante (i, j, k, C \in \mathbb{N}_0)

So könnte ein GOTO-Programm zur