Es sei P {\displaystyle {}P} ein Registerprogramm mit den Programmzeilen B 1 , … , B h {\displaystyle {}B_{1},\ldots ,B_{h}} und m {\displaystyle {}m} Registern mit den zugehörigen arithmetischen Ausdrücken A 1 , … , A h {\displaystyle {}A_{1},\ldots ,A_{h}} in den freien Variablen z , r 1 , … , r m , z ′ , r 1 ′ , … , r m ′ {\displaystyle {}z,r_{1},\ldots ,r_{m},z',r'_{1},\ldots ,r'_{m}} . Es sei A P = A 1 ∧ … ∧ A h ∧ A h + 1 {\displaystyle {}A_{P}=A_{1}\wedge \ldots \wedge A_{h}\wedge A_{h+1}} .
Dann ist A P {\displaystyle {}A_{P}} eine arithmetische Repräsentierung der Programmabbildung φ P {\displaystyle {}\varphi _{P}} .