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