Unentscheidbarkeit der Arithmetik/Registermaschine/Fakt/Beweis

Beweis

Nach Fakt gibt es zu jedem Programm ${}P$ (mit ${}h$ Befehlen und ${}m$ Registern) einen arithmetischen Ausdruck ${}\psi _{P}$ in ${}2m$ freien Variablen ${}x_{1},\ldots ,x_{m},y_{1},\ldots ,y_{m}$, der bei der Belegung mit ${}e_{1},\ldots ,e_{m},a_{1},\ldots ,a_{m}\in \mathbb {N}$ genau dann wahr ist, wenn das Programm, angesetzt auf ${}(1,e_{1},\ldots ,e_{m})$, schließlich mit der Konfiguration ${}(h,a_{1},\ldots ,a_{m})$ anhält. Der Ausdruck

${}\varphi _{P}=\psi _{P}(0,0,\ldots ,0,y_{1},\ldots ,y_{m})\,$

besagt daher, dass das Programm bei Nulleingabe mit der Registerbelegung ${}(y_{1},\ldots ,y_{m})$ anhält und der Ausdruck (ohne freie Variablen)

${}\theta _{P}=\exists y_{1}\exists y_{2}\ldots \exists y_{m}\varphi _{P}\,$

besagt, dass das Programm überhaupt anhält. Es gilt also

$\mathbb {N} \vDash \theta _{P}$

genau dann, wenn ${}P$ bei Nulleingabe anhält. Man beachte, dass die Abbildung, die einem jeden Programm ${}P$ dieses ${}\theta _{P}$ zuordnet, effektiv durch eine Registermaschine durchführbar ist.

Wenn es ein Entscheidungsverfahren für arithmetische Sätze geben würde, so könnte man insbesondere auch die Richtigkeit von ${}\mathbb {N} \vDash \theta _{P}$ entscheiden. Doch dann würde es ein Entscheidungsverfahren für das Halteproblem im Widerspruch zu Fakt geben.

Zur bewiesenen Aussage