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

Repräsentierbarkeit des Halteproblems

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

derart, dass

$\mathbb {N} \vDash \psi _{P}(e_{1},\ldots ,e_{m},a_{1},\ldots ,a_{m})$

genau dann gilt, wenn das Programm bei Eingabe von ${}(1,e_{1},\ldots ,e_{m})$ nach endlich vielen Schritten bei der Konfiguration ${}(h,a_{1},\ldots ,a_{m})$ anlangt

(und insbesondere anhält).

Zum Beweis, Alternativen Beweis erstellen