Kurs:Einführung in die mathematische Logik (Osnabrück 2021)/Vorlesung 20/kontrolle

Arithmetische Repräsentierbarkeit

Wir möchten die Wirkungsweise von Registerprogrammen arithmetisch repräsentieren, um so aus der Unentscheidbarkeit des Halteproblems auf die Unentscheidbarkeit der Arithmetik zu schließen. Im Folgenden arbeiten wir mit dem arithmetischen Alphabet ${}{\rm {Ar}}=\{0,1,+,\cdot \}$ und der Standardinterpretation in ${}\mathbb {N}$.

Definition Referenznummer erstellen

Eine Abbildung

$F\colon \mathbb {N} ^{r}\longrightarrow \mathbb {N} ^{s}$

heißt arithmetisch repräsentierbar , wenn es einen ${}L^{\rm {Ar}}$-Ausdruck ${}\psi$ in ${}r+s$ freien Variablen derart gibt, dass für alle ${}(r+s)$-Tupel ${}(n_{1},\ldots ,n_{r+s})\in \mathbb {N} ^{r+s}$ die Äquivalenz ${}F(n_{1},\ldots ,n_{r})=(n_{r+1},\ldots ,n_{r+s})$ genau dann, wenn ${}\mathbb {N} \vDash \psi (n_{1},\ldots ,n_{r+s})$ gilt.

Definition Referenznummer erstellen

Eine Relation ${}R\subseteq \mathbb {N} ^{r}$ heißt arithmetisch repräsentierbar , wenn es einen ${}L^{\rm {Ar}}$-Ausdruck ${}\psi$ in ${}r$ freien Variablen derart gibt, dass für alle ${}r$-Tupel ${}(n_{1},\ldots ,n_{r})\in \mathbb {N} ^{r}$ die Äquivalenz ${}(n_{1},\ldots ,n_{r})\in R$ genau dann, wenn ${}\mathbb {N} \vDash \psi (n_{1},\ldots ,n_{r})$ gilt.

Die Schreibweise ${}\psi (n_{1},\ldots ,n_{r+s})$ bedeutet, dass die ${}r+s$ nicht namentlich aufgeführten freien Variablen durch die ${}n_{1},\ldots ,n_{r+s}$ ersetzt werden, wobei die natürlichen Zahlen ${}n_{j}$ als Terme durch die ${}n_{j}$-fache Summe ${}1+\cdots +1$ (streng genommen mit einer fixierten Klammerung) wiedergegeben werden. Da die repräsentierenden Ausdrücke genau ${}r+s$ bzw. ${}r$ freie Variablen besitzen, entsteht durch Substitution der freien Variablen durch die Terme eine Aussage ohne freie Variablen. Diese sind bei Interpretation über den natürlichen Zahlen wahr oder falsch. Aufgrund des Substitutionslemmas ist die Gültigkeit ${}\mathbb {N} \vDash \psi (n_{1},\ldots ,n_{r+s})$ äquivalent zur Gültigkeit ${}\mathbb {N} {\frac {n_{1},\ldots ,n_{r+s}}{x_{1},\ldots ,x_{r+s}}}\vDash \psi$. Polynomfunktionen

$\mathbb {N} ^{r}\longrightarrow \mathbb {N}$

mit natürlichzahligen Koeffizienten sind unmittelbar arithmetisch präsentierbar, siehe Aufgabe 20.6.

Wir wollen zeigen, dass Registerprogramme, oder besser gesagt die durch ein Registerprogramm festgelegte Programmabbildung, arithmetisch repräsentierbar sind.

Registerprogramme als Abbildungen

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.

Bei ${}B_{\ell }=i+$ ist

$\varphi (\ell ,n_{1},\ldots ,n_{m})=(\ell +1,n_{1},\ldots ,n_{i-1},n_{i}+1,n_{i+1},\ldots ,n_{m})\,.$

Bei ${}B_{\ell }=i-$ ist

$\varphi (\ell ,n_{1},\ldots ,n_{m})=(\ell +1,n_{1},\ldots ,n_{i-1},n_{i}-1,n_{i+1},\ldots ,n_{m})\,$

bei ${}n_{i}\geq 1$ und

$\varphi (\ell ,n_{1},\ldots ,n_{m})=(\ell +1,n_{1},\ldots ,n_{i-1},n_{i},n_{i+1},\ldots ,n_{m})\,$

bei ${}n_{i}=0$. Bei ${}B_{\ell }=C(ij)$ ist

$\varphi (\ell ,n_{1},\ldots ,n_{m})={\begin{cases}(j,n_{1},\ldots ,n_{m}),{\text{ falls }}n_{i}=0\,,\\(\ell +1,n_{1},\ldots ,n_{m}){\text{ sonst}}\,.\end{cases}}$

Bei ${}B_{\ell }=H$ (also bei $\ell =h$) ist

${}\varphi (h,n_{1},\ldots ,n_{m})=(h,n_{1},\ldots ,n_{m})\,,$

die Abbildung wirkt dort also wie die Identität. Der Druckbefehl ist für den Programmablauf nicht relevant und wird hier ignoriert.

In manchen Situationen möchte man eine auf ganz ${}\mathbb {N} \times \mathbb {N} ^{m}$ definierte Programmabbildung haben. Um dies zu erreichen setzt man für ${}\ell >h$ einfach

${}\varphi (\ell ,n_{1},\ldots ,n_{m})=(\ell ,n_{1},\ldots ,n_{m})\,.$

Repräsentierbarkeit der Registerbefehle

Ein Registerprogramm kann also in eine Abbildung übersetzt werden, die die Wirkungsweise des Programms widerspiegelt. Die dabei auftretenden Abbildungen sind prinzipiell einfach beschreibbar, auch wenn dafür eine lange Abbildungsdefinition und tief verschachtelte Fallunterscheidungen nötig sind.

Der Ablauf eines Programms ${}P$ zur Anfangseingabe (Anfangskonfiguration) ${}e=(1,e_{1},\ldots ,e_{m})$ (die Anfangszeile besitzt die Zeilennummer ${}1$!) wird durch die Hintereinanderschaltung der Programmabbildung ${}\varphi =\varphi _{P}$ mit sich selbst beschrieben. Nach dem ersten Programmschritt, bei dem der Befehl in der ersten Programmzeile aufgerufen wird, erhält man die Folgekonfiguration ${}\varphi (e)$. Die nullte Komponente von ${}\varphi (e)$ gibt an, mit welcher Programmzeile weitergearbeitet wird. Dies ist aber alles in ${}\varphi$ kodiert, so dass das Ergebnis nach dem nächsten Schritt einfach ${}\varphi (\varphi (e))$ ist. Das Ergebnis nach dem ${}s$-ten Rechenschritt (Befehlszeilenwechsel) ist also

$\varphi (\ldots (\varphi (\varphi (e)))\ldots ),$

wobei ${}s$-mal ${}\varphi$ angewendet wird. Dafür schreiben wir auch ${}\varphi ^{s}(e)$. Die aktuelle Zeilennummer ist dabei stets als nullte Komponente von ${}\varphi ^{s}(e)$ ablesbar, wofür wir ${}(\varphi ^{s}(e))_{0}$ schreiben.

Wie wirkt sich nun die Eigenschaft eines Programms, anzuhalten oder nicht, auf diese Iterationen von ${}\varphi$ aus? Das Programm hält genau dann an, wenn es bei Eingabe von ${}e$ ein ${}s$ mit ${}(\varphi ^{s}(e))_{0}=h$ gibt.

Wir möchten die Wirkungsweise von Programmen in der Sprache der Arithmetik selbst repräsentieren, um dort das Halteproblem (und seine Unentscheidbarkeit) nachbilden zu können. Dafür müssen wir zunächst die einzelnen Programmschritte arithmetisch erfassen.

Definition Definition 20.3 ändern

Den Programmzeilen ${}B_{1},\ldots ,B_{h}$ eines Registerprogramms mit ${}m$ Registern werden die folgenden arithmetischen Ausdrücke ${}A_{1},\ldots ,A_{h}$ in den freien Variablen ${}z,r_{1},\ldots ,r_{m},z',r'_{1},\ldots ,r'_{m}$ zugeordnet.

1. Bei ${}B_{\ell }=i+$ setzt man

   $A_{\ell }:=(z=\ell )\rightarrow (z'=z+1)\wedge (r_{1}'=r_{1})\wedge \ldots \wedge (r_{i-1}'=r_{i-1})\wedge (r_{i}'=r_{i}+1)\wedge (r_{i+1}'=r_{i+1})\wedge \ldots \wedge (r_{m}'=r_{m}).$

2. Bei ${}B_{\ell }=i-$ setzt man

   $A_{\ell }:=(z=\ell )\rightarrow (z'=z+1)\wedge (r_{1}'=r_{1})\wedge \ldots \wedge (r_{i-1}'=r_{i-1})\wedge ((r_{i}=0)\rightarrow (r'_{i}=r_{i}))\wedge (\neg (r_{i}=0)\rightarrow (r_{i}'+1=r_{i}))\wedge (r_{i+1}'=r_{i+1})\wedge \ldots \wedge (r_{m}'=r_{m}).$

3. Bei ${}B_{\ell }=C(ij)$ setzt man

   $A_{\ell }:=(z=\ell )\rightarrow ((r_{i}=0)\rightarrow (z'=j))\wedge (\neg (r_{i}=0)\rightarrow (z'=z+1))\wedge (r_{1}'=r_{1})\wedge \ldots \wedge (r_{m}'=r_{m}).$

4. Bei ${}B_{\ell }=B_{h}=H$ setzt man

   $A_{h}:=(z=h)\rightarrow (z'=z)\wedge (r_{1}'=r_{1})\wedge \ldots \wedge (r_{m}'=r_{m}).$

Hierbei werden die natürlichen Zahlen ${}\ell$ und ${}j$ in den arithmetischen Ausdrücken durch die entsprechenden Summen ${}1+\cdots +1$ repräsentiert, die Abfrage am ${}i$-ten Register schlägt sich in der Variablenbezeichnung nieder.

Wie bei der Programmabbildung ist es sinnvoll, für alle Programmzeilennummern (also auch für $\ell >h$) einen arithmetischen Ausdruck zu haben. Dazu setzen wir

$A_{h+1}:=(z\geq h+1)\rightarrow (z'=z)\wedge (r_{1}'=r_{1})\wedge \ldots \wedge (r_{m}'=r_{m})$

(wobei $z\geq h+1$ eine Abkürzung ist). Zu einem gegebenen Programm bestehend aus den Programmzeilen ${}B_{1},\ldots ,B_{h}$ betrachtet man die Konjunktion der soeben eingeführten zugehörigen arithmetischen Repräsentierungen, also ${}A_{P}=A_{1}\wedge A_{2}\wedge \ldots \wedge A_{h}\wedge A_{h+1}$. Dieser Ausdruck repräsentiert die Programmabbildung.

Lemma Lemma 20.4 ändern

Es sei ${}P$ ein Registerprogramm mit den Programmzeilen ${}B_{1},\ldots ,B_{h}$ und ${}m$ Registern mit den zugehörigen arithmetischen Ausdrücken ${}A_{1},\ldots ,A_{h}$ in den freien Variablen ${}z,r_{1},\ldots ,r_{m},z',r'_{1},\ldots ,r'_{m}$. Es sei ${}A_{P}=A_{1}\wedge \ldots \wedge A_{h}\wedge A_{h+1}$.

Dann ist ${}A_{P}$ eine arithmetische Repräsentierung der Programmabbildung ${}\varphi _{P}$.

Beweis

Die Variablen ${}z,z',r_{j},r_{j}'$ seien durch die natürlichen Zahlen ${}\ell ,\ell ',n_{j},n_{j}'$ belegt. Wir müssen zeigen, dass die Gleichheit

${}\varphi _{P}(\ell ,n_{1},\ldots ,n_{m})=(\ell ',n'_{1},\ldots ,n'_{m})\,$

genau dann gilt, wenn

$\mathbb {N} \vDash A_{P}(\ell ,\ell ',n_{1},\ldots ,n_{m},n'_{1},\ldots ,n'_{m})$

gilt. Der Ausdruck ${}A_{P}$ gilt genau dann, wenn sämtliche Ausdrücke ${}A_{1},A_{2},\ldots ,A_{h},A_{h+1}$ gelten. Es sei ${}\ell$ fixiert. Dann gelten sämtliche ${}A_{k}$, ${}k\neq \ell$, automatisch, da für diese Ausdrücke der Vordersatz nicht gilt. Die Gültigkeit von ${}A_{P}$ bei dieser Belegung bedeutet also, dass der Nachsatz in ${}A_{\ell }$ gelten muss. Sowohl ${}\varphi (\ell ,-)$ als auch der Nachsatz von ${}A_{\ell }$ drücken die Wirkungsweise des Befehls ${}B_{\ell }$ aus, daher gilt die Abbildungsgleichheit genau dann, wenn ${}A_{\ell }$ wahr ist.

$\Box$

Die ${}\beta$-Funktion

Das Halteproblem führte zu der Existenzaussage, dass es eine Iteration der Programmabbildung gibt, für die die ${}0$-te Komponente gleich der Haltezeilennummer ist. Die arithmetische Repräsentierung dieser Existenzaussage bedarf einiger Vorbereitungen.

Eine natürliche Zahl ${}n$ lässt sich bekanntlich im Zehnersystem als

${}n=a_{0}1+a_{1}10+a_{2}10^{2}+\cdots +a_{k}10^{k}\,$

schreiben, wobei die ${}a_{i}$ zwischen ${}0$ und ${}9$ liegen. Umgekehrt definiert eine endliche Ziffernfolge ${}(a_{0},a_{1},\ldots ,a_{k})$ (bzw. in alltäglicher Schreibweise $a_{k}a_{k-1}\ldots a_{1}a_{0}$) eine natürliche Zahl. Anstatt der Basis ${}10$ kann man jede natürliche Zahl ${}p\geq 2$ als Basis nehmen (für viele Zwecke ist auch die Basis ${}1$ erlaubt, eine Zahl ${}n$ wird dann einfach durch das ${}n$-fache Hintereinanderschreiben der ${}1$ repräsentiert). Man spricht dann von der ${}p$-adischen Entwicklung (oder Darstellung) der Zahl. Die ${}p$-adische Entwicklung einer natürlichen Zahl ist eindeutig.

Sei ${}p\geq 2$ fixiert. Wie berechnet man die Ziffernfolge einer gegebenen Zahl ${}n$? Zuerst betrachten wir die Ziffer (die Einerziffer) ${}a_{0}(n)=a(n,0)$. Es gilt die rekursive Beziehung

${}a(n,0)={\begin{cases}n,{\text{falls }}n<p\,,\\a(n-p,0){\text{ sonst}}\,.\end{cases}}\,$

Dies beruht einfach darauf, dass bei ${}n\geq p$ das Abziehen von ${}p$ die Ziffer zu ${}p^{0}$ nicht ändert. Man beachte, dass sowohl die Abfrage, die die Fallunterscheidung in dieser Definition konstituiert, als auch die Subtraktion im Fall ${}2$ mit einer Registermaschine durchführbar sind, und dass dadurch eine ${}R$-berechenbare Funktion vorliegt.

Auch die Definition der anderen Ziffern geschieht rekursiv. Wenn man von ${}n$ die (schon berechnete) Ziffer zu ${}p^{0}$ abzieht, so erhält man eine durch ${}p$ teilbare Zahl. Zwischen der Ziffernentwicklung von ${}n$ und von ${}m={\frac {n-a(n,0)}{p}}$ besteht ein direkter Zusammenhang, die Ziffer ${}a_{i+1}$ von ${}n$ ist einfach die Ziffer ${}a_{i}$ von ${}m$. Daher ist für ${}i\geq 0$

${}a(n,i+1)={\begin{cases}0,{\text{falls }}n<p^{i+1}\,,\\a{\left({\frac {n-a(n,0)}{p}},i\right)}{\text{ sonst}}\,.\end{cases}}\,$

Damit ist die Berechnung der ${}(i+1)$-ten Ziffer auf die Berechnung der ${}i$-ten Ziffer einer kleineren Zahl rekursiv zurückgeführt. Die Bedingung in der Abfrage und die Subtraktion und die Division in der Definition sind durch eine Registermaschine durchführbar. Diese Funktionsvorschrift berechnet nicht nur die „benötigten“ Ziffern, sondern auch alle höheren, wobei natürlich für alle unbenötigten ${}0$ herauskommt.

Wir führen nun die ${}\beta$-Funktion ein. Der Hauptzweck dieser Funktion soll sein, endliche Folgen von natürlichen Zahlen unterschiedlicher Länge durch drei Zahlen zu kodieren. Die Grundidee ist, dies über die ${}p$-adische Entwicklung zu tun, wobei die drei Eingabezahlen einen Zahlwert, eine Basis und eine Ziffernstelle repräsentieren, und die Ausgabe die Ziffernfolge ist. Zugleich soll diese Funktion arithmetisch repräsentierbar sein, sodass die folgende Funktion etwas komplizierter aussieht. Wir folgen weitgehend dem Zugang von Ebbinghaus, Flum, Thomas.

Definition Referenznummer erstellen

Unter der Funktion versteht man die Abbildung

$\mathbb {N} ^{3}\longrightarrow \mathbb {N} ,\,(p,n,i)\longmapsto \beta (p,n,i),$

die folgendermaßen festgelegt ist. ${}\beta (p,n,i)$ ist die kleinste Zahl ${}a\in \mathbb {N}$, die die Bedingung erfüllt, dass es natürliche Zahlen ${}b_{0},b_{1},b_{2}$ gibt, die die folgenden Eigenschaften erfüllen:

1. ${}n=b_{0}+b_{1}{\left((i+1)+ap+b_{2}p^{2}\right)}$.
2. ${}a<p$.
3. ${}b_{0}<b_{1}$.
4. ${}b_{1}$ ist eine Quadratzahl.
5. Alle Teiler ${}d\neq 1$ von ${}b_{1}$ sind ein Vielfaches von ${}p$.

Wenn kein solches ${}a$ existiert, so ist ${}\beta (p,n,i)=0$.

Zunächst ist klar, dass diese Funktion arithmetisch repräsentierbar ist. Wenn ${}p$ eine Primzahl ist, so bedeutet Teil (5), dass ${}b_{1}$ eine Primzahlpotenz ist, und Teil (4), dass der Exponent geradzahlig ist. Das folgende Lemma sichert die gewünschte Eigenschaft der ${}\beta$-Funktion, nämlich die Eigenschaft, endliche Folgen zu repräsentieren.

Lemma Referenznummer erstellen

Zu jeder endlichen Folge ${}(a_{0},\ldots ,a_{s})$ aus ${}\mathbb {N}$

gibt es natürliche Zahlen ${}p,n$ derart, dass ${}\beta (p,n,i)=a_{i}$ für ${}i\leq s$ ist.

Beweis

Es sei die endliche Folge ${}(a_{0},a_{1},\ldots ,a_{s})$ vorgegeben. Wir wählen eine Primzahl ${}p$, die größer als alle ${}a_{i}$ und größer als ${}s+1$ ist. Es sei

${}{\begin{aligned}n&:=1\cdot p^{0}+a_{0}p^{1}+2p^{2}+a_{1}p^{3}+\cdots +(s+1)p^{2s}+a_{s}p^{2s+1}\\&=\sum _{i=0}^{s}a_{i}p^{2i+1}+\sum _{i=0}^{s}(i+1)p^{2i}\\&=\sum _{i=0}^{s}(i+1+a_{i}p)p^{2i}.\end{aligned}}$

Die vorgegebene Folge ist also die Folge der Ziffern der ungeraden Stellen in der ${}p$-adischen Ziffernentwicklung von ${}n$. Wir behaupten ${}\beta (p,n,k)=a_{k}$ für ${}k\leq s$. Zunächst erfüllt ${}a_{k}$ die in der Definition der ${}\beta$-Funktion formulierten Eigenschaften, und zwar mit

$b_{0}=1p^{0}+a_{0}p^{1}+2p^{2}+a_{1}p^{3}+\cdots +kp^{2k-2}+a_{k-1}p^{2k-1}\,,$

${}b_{1}=p^{2k}\,,$

$b_{2}=(k+2)+a_{k+1}p+(k+3)p^{2}+\cdots +(s+1)p^{2(s-k)-2}+a_{s}p^{2(s-k)-1}\,.$

Die erste Eigenschaft ergibt sich aus

${}{\begin{aligned}n&=\sum _{i=0}^{s}a_{i}p^{2i+1}+\sum _{i=0}^{s}(i+1)p^{2i}\\&=\sum _{i=0}^{k-1}a_{i}p^{2i+1}+\sum _{i=0}^{k-1}(i+1)p^{2i}+\sum _{i=k}^{s}a_{i}p^{2i+1}+\sum _{i=k}^{s}(i+1)p^{2i}\\&=b_{0}+p^{2k}{\left(\sum _{i=0}^{s-k}a_{k+i}p^{2i+1}+\sum _{i=0}^{s-k}(k+i+1)p^{2i}\right)}\\&=b_{0}+p^{2k}{\left(k+1+a_{k}p+\sum _{i=1}^{s-k}a_{k+i}p^{2i+1}+\sum _{i=1}^{s-k}(k+i+1)p^{2i}\right)}\\&=b_{0}+b_{1}{\left(k+1+a_{k}p+b_{2}p^{2}\right)},\end{aligned}}$

die anderen sind klar. Wenn umgekehrt ein ${}a$ die Bedingungen erfüllt (mit $c_{0},c_{1},c_{2}$), wobei ${}c_{1}=p^{2\ell }$ ist, so ist

${}{\begin{aligned}n&=b_{0}+(k+1)p^{2k}+a_{k}p^{2k+1}+b_{2}p^{2k+2}\\&=c_{0}+(k+1)p^{2\ell }+ap^{2\ell +1}+c_{2}p^{2\ell +2}.\end{aligned}}$

Da die ${}p$-adische Entwicklung von ${}n$ eindeutig ist, folgen daraus und aus den weiteren Bedingungen die Gleichheiten ${}\ell =k$ und ${}a=a_{k}$.

$\Box$