Registerprogramm/Abbildung/Einführung/Textabschnitt

Wir möchten ein Registerprogramm ${}P$ , das aus ${}h$ Programmzeilen besteht und ${}m$ Register anspricht, als eine Abbildung auffassen. Die Wirkungsweise einer jeden Programmzeile hängt dabei nur von den Belegungen der Register zu dem Zeitpunkt ab, an dem diese Zeile aufgerufen wird. Sie ist geschichtsunabhängig, d.h. unabhängig von dem bisherigen Verlauf des Programmes. Man kann daher ein Programm vollständig durch die Abbildung

\varphi \colon \{1,2,\ldots ,h\}\times \mathbb {N} ^{m}\longrightarrow \{1,2,\ldots ,h\}\times \mathbb {N} ^{m},\,(\ell ,n_{1},\ldots ,n_{m})\longmapsto \varphi (\ell ,n_{1},\ldots ,n_{m}),

erfassen. Diese Abbildung nennen wir die Programmabbildung ${}\varphi =\varphi _{P}$ . Dabei steht ${}\ell$ für die Programmzeilennummer und ${}n_{j}$ steht für den Inhalt des Registers ${}R_{j}$ (von denen es ja ${}m$ Stück gibt). Dem Tupel ${}(\ell ,n_{1},\ldots ,n_{m})$ wird dasjenige Tupel ${}\varphi (\ell ,n_{1},\ldots ,n_{m})$ zugeordnet, das bei Abruf des in der ${}\ell$ -ten Programmzeile stehenden Befehls ${}B_{\ell }$ bei der Registerbelegung ${}(n_{1},\ldots ,n_{m})$ entsteht. Die Abbildung ${}\varphi$ besteht dabei aus den ${}m+1$ Komponentenfunktionen ${}\varphi _{0},\varphi _{1},\ldots ,\varphi _{m}$ , wobei ${}\varphi _{0}$ die Wirkungsweise auf die Programmzeilennummer und die ${}\varphi _{j}$ , ${}1\leq j\leq m$ , die Wirkungsweise auf das ${}j$ -te Register beschreibt. Die Wirkung der einzelnen Befehle sieht folgendermaßen aus.