Registermaschine/Überprüfung des Programmcodes/Bemerkung

Aus Wikiversity

Es ist algorithmisch überprüfbar, ob eine als Strichfolge gegebene natürliche Zahl ein Code für ein Registerprogramm ist. Dazu muss zuerst die Zahl in ihre Ziffernentwicklung (im Neunersystem) übersetzt werden. Da der Trennstrich, der die einzelnen Befehle trennt, durch eine bestimmte Ziffer codiert wird, muss die Ziffernfolge zwischen zwei Trennstrichziffern einen Befehl codieren. Die syntaktische Korrektheit dieser einzelnen Befehlsziffernfolgen muss dann der Reihe nach überprüft werden. Dazu muss man für jeden der Einzelbefehle einen Algorithmus entwerfen. Wenn beispielsweise die Anfangsziffer einer Befehlsziffernfolge eine (also ein ) ist, so muss es sich um einen Inkrementierungsbefehl handeln und alle nachfolgenden Ziffern (bis zum nächsten Trennstrich) müssen Striche sein.