# Repräsentierbarkeit von Registerprogrammen/Über p-adische beta Funktion/Textabschnitt

Ein Durchlauf eines Registerprogramms $P$ (das auf $m$ Register Bezug nimmt) bis zum Rechenschritt $t$ wird am einfachsten durch die Folge der Programmkonfigurationen $K_{s}$, $1\leq s\leq t$, dokumentiert, wobei jede Programmkonfiguration $K_{s}$ aus der Nummer der im Rechenschritt $s$ abzuarbeitenden Programmzeile und der Folge der Registerinhalte (zu diesem Zeitpunkt) besteht. Wenn man diese Konfigurationen einfach hintereinander schreibt, so erhält man eine Folge von $t(m+1)$ Zahlen. Wenn umgekehrt eine solche Zahlenfolge gegeben ist, so kann man einfach überprüfen, ob sie den Durchlauf des Programms bis zum Schritt $t$ korrekt dokumentiert. Man muss sicherstellen, dass sich jeder Abschnitt zu den Indizes $(s+1)(m+1)+1,\ldots ,(s+1)(m+1)+m+1$ aus dem Vorgängerabschnitt zu den Indizes $s(m+1)+1,\ldots ,s(m+1)+m+1$ ergibt, wenn die Programmzeile zu $s(m+1)+1$ angewendet wird (der Abschnitt muss also durch die Programmabbildung aus dem Vorgängerabschnitt hervorgehen).

## Lemma

Für ein Programm $P$ für eine Registermaschine
gibt es einen arithmetischen Ausdruck $\psi _{P}$, der genau dann (bei der Standardinterpretation in den natürlichen Zahlen) gilt, wenn das Programm anhält.
Genauer gesagt: Wenn das Programm $h$ Programmzeilen besitzt und $m$ Register verwendet, so gibt es einen arithmetischen Ausdruck $\psi _{P}$ in $2m$ freien Variablen
    $\mathbb {N} \vDash \psi _{P}(e_{1},\ldots ,e_{m},a_{1},\ldots ,a_{m})$
$(1,e_{1},\ldots ,e_{m})$
$(h,a_{1},\ldots ,a_{m})$
(und insbesondere anhält).

### Beweis

Es sei $A_{P}$ der das Programm repräsentierende Ausdruck im Sinne von Fakt in den Variablen $r_{0},\ldots ,r_{m},r_{0}',\ldots ,r_{m}'$ (zur Notationsvereinfachung schreiben wir also $r_{0}$ statt $z$ und $r_{0}'$ statt $z'$.). Es sei $\vartheta$ der Ausdruck (in den vier freien Variablen $p,n,i,r$), der die $\beta$-Funktion arithmetisch repräsentiert. Der Ausdruck
    $\vartheta (p,n,i,r)$
ist also genau dann wahr in $\mathbb {N}$, wenn $\beta (p,n,i)=r$ ist. Diese Beziehung verwenden wir für $i=s(m+1)+j$ (bzw. $i=(s+1)(m+1)+j$) und $r=r_{j}$ (bzw. $r=r'_{j}$) und $j=0,\ldots ,m$. Daher ist der Ausdruck (in den freien Variablen $p,n,s,r_{j},r_{j}'$)
    $T(p,n,s):=\vartheta (p,n,s(m+1),r_{0})\wedge \ldots \wedge \vartheta (p,n,s(m+1)+m,r_{m})\wedge \vartheta (p,n,(s+1)(m+1),r'_{0})\wedge \ldots \wedge \vartheta (p,n,(s+1)(m+1)+m,r'_{m})\,$
bei Interpretation in $\mathbb {N}$ genau dann wahr, wenn die $\beta$-Funktion $\beta (p,n,-)$ für die $m+1$ aufeinander folgenden Zahlen (eingesetzt in die dritte Komponente der $\beta$-Funktion) $s(m+1),s(m+1)+1,\ldots ,s(m+1)+m$ gleich $r_{0},r_{1},\ldots ,r_{m}$ und für die $m+1$ aufeinander folgenden Zahlen $(s+1)(m+1),(s+1)(m+1)+1,\ldots ,(s+1)(m+1)+m$ gleich $r'_{0},r'_{1},\ldots ,r'_{m}$ ist. An der mit $s(m+1)+j$ bezeichneten Stelle in $T(p,n,s)$ steht die $(m+1)$-fache Addition der Variablen $s$ mit sich selbst plus die $j$-fache Addition der $1$.
Mit diesem Ausdruck soll der Konfigurationsübergang beim $s$-ten Rechenschritt beschrieben werden. Da man die Registerbelegung beim $s$-ten Rechenschritt nicht von vornherein kennt, muss man den Übergang mit Allquantoren ansetzen. Der Ausdruck
    $E(p,n,s):=\forall r_{0}\forall r_{1}\ldots \forall r_{m}\forall r_{0}'\forall r'_{1}\ldots \forall r'_{m}(T(p,n,s)\rightarrow A_{P})\,$
besagt, dass der durch $p,n,s$ über die $\beta$-Funktion kodierte Konfigurationsübergang durch das Programm bewirkt wird.
In analoger Weise ist der Ausdruck (in den $m+2$ freien Variablen $p,n,x_{1},\ldots ,x_{m}$)
    $D(p,n)(x_{1},\ldots ,x_{m}):=\vartheta (p,n,0,1)\wedge \vartheta (p,n,1,x_{1})\wedge \ldots \wedge \vartheta (p,n,m,x_{m})\,$
(bei inhaltlicher Interpretation) genau dann wahr, wenn $\beta (p,n,0)=1$ und $\beta (p,n,j)=x_{j}$ für $j=1,\ldots ,m$ ist. Der Ausdruck (in den $m+3$ freien Variablen $p,n,t,y_{1},\ldots ,y_{m}$)
    $F(p,n,t)(y_{1},\ldots ,y_{m}):=\vartheta (p,n,t(m+1),h)\wedge \vartheta (p,n,t(m+1)+1,y_{1})\wedge \ldots \wedge \vartheta (p,n,t(m+1)+m,y_{m})\,$
ist genau dann wahr, wenn $\beta (p,n,t(m+1))=h$ und $\beta (p,n,t(m+1)+j)=y_{j}$ für $j=1,\ldots ,m$ ist.
Somit besagt der Ausdruck
    $\psi _{P}=\exists p\exists n\exists t{\left(D(p,n)(x_{1},\ldots ,x_{m})\wedge \forall s(1\leq s<t\rightarrow E(p,n,s))\wedge F(p,n,t)(y_{1},\ldots ,y_{m})\right)}\,,$
dass das Programm mit der Startkonfiguration $(1,x_{1},\ldots ,x_{m})$ anhält und dabei die Konfiguration $(h,y_{1},\ldots ,y_{m})$ erreicht.
$\Box$