Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012)/Vorlesung 8

Wir kehren nun zur Ausgangsfrage dieses Kurses zurück, ob es eine Maschine geben kann, die mathematische Probleme (etwa aus der Zahlentheorie) löst. In den vorhergehenden Vorlesungen haben wir eine formale Sprache entwickelt, in der man solche nichttrivialen Probleme präzise formulieren kann. Ferner haben wir gesehen, wie ein formaler Beweis (eine Ableitung im Prädikatenkalkül) in dieser Sprache aussieht, und dass es nach dem Vollständigkeitssatz für jeden mathematisch beweisbaren Ausdruck der Sprache auch einen formalen Beweis gibt.

In dem vorgestellten Ableitungskalkül der Prädikatenlogik sind die Starttautologien und die Ableitungsregeln übersichtlich strukturiert. Zwar nehmen die Starttautologien häufig Bezug auf beliebige Ausdrücke (und Variablen) der Sprache, doch da die Ausdrücke prinzipiell auflistbar sind, gilt dies auch für die Starttautologien. Daher kann man sich auch einen Algorithmus vorstellen, der nach und nach alle formalen Beweise und somit auch alle formal-beweisbaren Ausdrücke ausgibt. Ein andersgelagertes Problem ist die Fragestellung, ob es ein Entscheidungsverfahren für die Prädikatenlogik gibt, ob es also ein algorithmisches Verfahren gibt, dass zu einem gegebenen Ausdruck überprüfen kann, ob es dafür einen formalen Beweis gibt oder nicht.

Wenn wir bisher von Algorithmen gesprochen haben, so haben wir dabei immer an intuitiv durchführbare Algorithmen gedacht, ohne ein konkretes Durchführungsmodell vor Augen zu haben. In dieser Vorlesung stellen wir die Arbeitsweise einer konkreten algorithmischen Maschine vor, der Registermaschine, die wir von nun an als mechanische Realisierung unserer intuitiven Vorstellung von Algorithmen auffassen wollen.

Registermaschinen

Statue von Alan Turing (1912-1954).

Es gibt verschiedene Möglichkeiten, eine deterministisch arbeitende Maschine zu modellieren. Wir arbeiten hier mit Registermaschinen, da diese einem wirklichen Computer ziemlich nahe kommen und daher etwas vertrauter sind als Turingmaschinen oder rekursive Funktionen (wobei letztere vom mathematischen Standpunkt her eleganter sind).

Definition

Unter einer Registermaschine versteht man eine endliche Folge von Registern ${}R_{1},R_{2},\ldots ,R_{m}$ (oder Speichern), deren Inhalt jeweils eine natürliche Zahl ist, die durch eine endliche (eventuell leere) Folge von Strichen repräsentiert wird.

Ein Programm für eine Registermaschine ist eine endliche durchnummerierte Folge von Befehlen ${}B_{1},B_{2},\ldots ,B_{h}$, wobei es für die einzelnen Befehle ${}B_{j}$ die folgenden Möglichkeiten gibt.

1. ${}i+$ (erhöhe den Inhalt des Registers ${}R_{i}$ um ${}1$, d.h. um einen Strich).
2. ${}i-$ (reduziere den Inhalt des Registers ${}R_{i}$ um ${}1$, d.h. ziehe einen Strich ab; wenn der Inhalt leer ist, so lasse ihn leer).
3. ${}C(ij)$ (wenn das ${}i$-te Register leer ist, so gehe zum Befehl ${}B_{j}$, andernfalls zum nächsten Befehl).
4. Drucke (drucke den Inhalt des ersten Registers).
5. Halte an.

Dabei muss ${}i\leq m$ für alle in einer Programmzeile adressierten Register und ${}j\leq h$ für alle adressierten Befehlszeilen gelten. Die letzte Befehlszeile ${}B_{h}$ ist ein Haltebefehl und sonst gibt es keinen Haltebefehl.

Die beiden ersten Befehle nennt man Inkrementierung bzw. Dekrementierung. Der dritte Befehl ist der Abfragebefehl oder die (bedingte) Sprunganweisung. Es folgen Druckbefehl und Haltebefehl.

Ein Programm für eine Registermaschine arbeitet die Befehle der Reihe nach ab und zwar unter den jeweiligen zum Bearbeitungszeitpunkt vorgefundenen Registerbelegungen. Wenn die aktuelle Programmzeile ein bedingter Sprungbefehl ${}C(ij)$ ist, so wird, falls die Bedingung zu diesem Zeitpunkt erfüllt ist (also falls das Register ${}R_{i}$ leer ist), zur Programmzeile ${}B_{j}$ gewechselt. Wenn die Endzeile ${}B_{h}$, also der Haltebefehl erreicht wird, so ist die Bearbeitung beendet.

Die Belegung (oder der Inhalt) des Registers ${}R_{i}$, die sich im Laufe des Programmdurchlaufs mehrfach ändern kann, werden wir häufig mit ${}r_{i}$ bezeichnen. Dies ist stets eine natürliche Zahl. Wenn das Register ${}R_{i}$ leer ist, so ist sein Inhalt ${}r_{i}=0$.

Die Möglichkeiten einer Registermaschine scheinen auf den ersten Blick recht bescheiden zu sein. Man sieht aber recht schnell, dass man aus diesen wenigen Befehlen Programmabschnitte zusammensetzen kann, die zunehmend komplexere Befehle ausführen. Komplexe Befehle, von denen schon gezeigt wurde, dass sie sich mit Hilfe der Grundbefehle realisieren lassen, werden ohne weiteren Kommentar weiterverwendet.

Man sagt, dass ein Programm korrekt ist, wenn es das tut, was es tun soll. Wenn beispielsweise gesagt wird, dass ein Programm zwei Zahlen addiert, so wird die Korrektheit dadurch bewiesen, dass man eben durch Analyse des Programmcodes nachweist, dass bei beliebiger Belegung der beiden Register, deren Inhalte addiert werden sollen, das Programm schließlich anhält und in einem weiteren Register wirklich die Summe der beiden Zahlen gespeichert ist. Ein Korrektheitsnachweis ist häufig eine mühevolle Kleinarbeit mit aufwändigen Fallunterscheidungen, in den natürlich auch mathematische Überlegungen eingehen, wie z.B. bei der Addition die Eigenschaft, dass ${}s+t=s+(t-1)+1$ ist, was einen induktiven Korrektheitsbeweis ermöglicht. Wir werden diese Korrektheitsüberlegungen häufig abkürzen.

Programmbeispiele

Wir beschreiben nun einige Programme bzw. Programmabschnitte für Registermaschinen. Wenn man Programme aus schon entwickelten Programmabschnitte zusammensetzt, so ändern sich natürlich die absoluten Befehlsnummern im Programm, was wir aber ignorieren werden.

Beispiel

Einen unbedingten Sprung (ein „Go to-Befehl“) zu einer bestimmten Programmzeile, der also nicht von einer Abfrage abhängt, kann man dadurch realisieren, dass man ein neues Register ${}R_{k}$ hinzunimmt, das von keiner anderen Programmzeile adressiert wird und dessen Inhalt auf ${}0$ gesetzt wird. Dann bewirkt der Befehl ${}C(kj)$, dass zur ${}j$-ten Programmzeile gewechselt wird, da der Inhalt des Registers ${}R_{k}$ im gesamten Programmverlauf gleich ${}0$ bleibt.

Beispiel

Ein Programm soll sämtliche natürlichen Zahlen der Reihe nach ausdrucken. Dazu brauchen wir eine Registermaschine mit zwei Registern ${}R_{1}$ und ${}R_{2}$, die zum Start beide leer sind. Das zweite Register bleibt unverändert und wird nur für den unbedingten Sprungbefehl verwendet. Die Haltezeile wird nie erreicht.

1. Drucke
2. ${}1+$
3. Gehe zu ${}1$
4. Halte an

Beispiel

Das Register ${}R_{i}$ soll geleert werden. Dies geschieht durch das folgende Programm.

1. ${}C(i,4)$
2. ${}i-$
3. Gehe zu ${}1$
4. Halte an

Bemerkung  

Wir erlauben, dass bei einer Registermaschine die Anfangsbelegung der Register von außen festgelegt wird. Man könnte aber auch festlegen, dass die Anfangsbelegung stets die Nullbelegung ist, ohne die Berechnungsmöglichkeiten der Registermaschine einzuschränken. Dann kann man die eigentlich gewünschte Anfangsbelegung dadurch erreichen, dass man dem Programm ein „Belegungsprogramm“ voranstellt, das den einzelnen Registern ${}R_{i}$ durch die ${}s_{i}$ Befehle ${}i+,\ldots ,i+$ die gewünschte Belegung ${}s_{i}$ zuweist.

Man könnte auch erstmal ein „Entleerungsprogramm“ vorschalten, das alle Register leert und daran anschließend die Belegung durchführt, doch muss man für den Entleerungsvorgang, der nach Beispiel 8.4 einen unbedingten Sprungbefehl verwendet, zumindest ein leeres Register zur Verfügung haben.

Wenn der Registerinhalt ${}r_{i}$ um eine natürliche Zahl ${}k$ erhöht werden soll, also ${}k$-fach direkt hintereinander inkrementiert werden soll, so schreiben wir dafür auch ${}i+\cdots +$ mit ${}k$ Pluszeichen.

Beispiel

Es soll mit einer Registermaschine festgestellt werden, ob der Inhalt ${}r_{i}$ des Registers ${}R_{i}$ größer oder gleich dem Inhalt ${}r_{j}$ des Registers ${}R_{j}$ ist. Dazu reserviert man das leere Register ${}R_{k}$ (${}i,j,k$ seien paarweise verschieden) und baut einen Programmabschnitt der folgenden Art.

1. ${}C(j,6)$
2. ${}j-$
3. ${}C(i,7)$
4. ${}i-$
5. Gehe zu ${}1$
6. ${}k+$
7. Halte an

Wenn dieser Programmabschnitt abgelaufen ist, so steht im Register ${}R_{k}$ der Wert ${}r_{k}=1$ oder ${}r_{k}=0$, je nachdem, ob ${}r_{i}\geq r_{j}$ ist oder nicht, und zwar unabhängig davon, ob man damit die Eingangsdaten oder Zwischendaten, wenn das Programm den ersten Befehl abarbeitet, meint. Die Korrektheit dieses Programms beruht darauf, dass ${}r\geq s$ genau dann gilt, wenn ${}r-1\geq s-1$ ist. Dies ermöglicht einen Induktionsbeweis.

Beispiel

Wir wollen überprüfen, ob die Inhalte von zwei Registern ${}R_{i}$ und ${}R_{j}$ übereinstimmen. Dazu kann man das Programm aus Beispiel 8.5 einfach abändern zu

1. ${}C(j,6)$
2. ${}j-$
3. ${}C(i,9)$
4. ${}i-$
5. Gehe zu ${}1$
6. ${}C(i,8)$
7. Gehe zu ${}9$
8. ${}k+$
9. Halte an

Bei Gleichheit erhält man ${}r_{k}=1$, bei Ungleichheit ${}r_{k}=0$.

In den obigen beiden Beispielen wurde die Antwort im Register ${}R_{k}$ (in der Form ${}0$ oder ${}1$ abgespeichert). Der Druckbefehl nimmt aber immer Bezug auf ${}R_{1}$. Daher ist es nötig, Registerinhalte in andere Register zu verschieben.

Beispiel

Wir wollen den Registerinhalt ${}r_{i}$ des Registers ${}R_{i}$ in das Register ${}R_{j}$ übertragen (unabhängig von dessen Inhalt). Dies leistet das folgende Programm.

1. Leere ${}R_{j}$
2. ${}C(i,6)$
3. ${}i-$
4. ${}j+$
5. Gehe zu ${}2$
6. Halte an

Bei diesem Programm wird im Laufe der Durchführung der Ausgangsregister der Übertragung leer gemacht. Dies ist nicht immer erwünscht, häufig möchte man den Inhalt eines Registers kopieren und sich den Inhalt zugleich merken.

Beispiel

Wir wollen den Registerinhalt ${}r_{i}$ des Registers ${}R_{i}$ in das Register ${}R_{j}$ übertragen (unabhängig von dessen Inhalt), ohne ${}R_{i}$ zu leeren. Dazu brauchen wir ein drittes Register ${}R_{k}$ und das folgende Programm.

1. Leere ${}R_{j}$
2. Leere ${}R_{k}$
3. ${}C(i,8)$
4. ${}i-$
5. ${}j+$
6. ${}k+$
7. Gehe zu ${}3$
8. Übertrage den Inhalt von ${}R_{k}$ nach ${}R_{i}$
9. Halte an

Hier wird zwar im Laufe des Programms der Inhalt von ${}R_{i}$ verändert, zum Schluss wird der ursprüngliche Inhalt aber wieder hergestellt.

Beispiel

Die beiden Registerinhalte ${}r_{i}$ (von ${}R_{i}$) und ${}r_{j}$ (von ${}R_{j}$) sollen addiert werden, wobei die Summe zum Schluss in ${}R_{k}$ stehen soll (es seien $i,j,k$ paarweise verschieden). Dies leistet das folgende Programm.

1. Leere ${}R_{k}$
2. Übertrage ${}r_{i}$ nach ${}R_{k}$
3. ${}C(j,7)$
4. ${}j-$
5. ${}k+$
6. Gehe zu ${}3$
7. Halte an

Mit der Addition und der Kopie von Inhalten kann man auch den Inhalt eines Registers zu einem anderen Register dazuaddieren. Dies kann man natürlich auch einfach direkt realisieren.

Beispiel

Die beiden Registerinhalte ${}r_{i}$ (von ${}R_{i}$) und ${}r_{j}$ (von ${}R_{j}$) sollen multipliziert werden, wobei das Produkt zum Schluss in ${}R_{k}$ stehen soll (es seien $i,j,k$ paarweise verschieden). Dies leistet das folgende Programm mit dem Hilfsregister ${}R_{\ell }$.

1. Leere ${}R_{k}$
2. Übertrage den Inhalt von ${}R_{i}$ nach ${}R_{\ell }$ ohne ${}R_{i}$ zu leeren
3. ${}C(j,7)$
4. Addiere den Inhalt von ${}R_{\ell }$ zu ${}R_{k}$ hinzu
5. ${}j-$
6. Gehe zu ${}2$
7. Halte an

Die Korrektheit dieses Programms beruht auf ${}r\cdot s=(r-1)s+s$; für das Produkt ${}rs$ muss man ${}r$-mal ${}s$ mit sich selbst addieren.

Beispiel

Es soll überprüft werden, ob der Registerinhalt ${}r_{t}$ (von ${}R_{t}$) den Registerinhalt ${}r_{j}$ (von ${}R_{j}$) teilt. Falls ja soll das Programm ${}1$ ausgeben, andernfalls ${}0$. Dies leistet das folgende Programm mit den Hilfsregistern ${}R_{k}$ und ${}R_{\ell }$ (für Teilprogramme braucht man noch weitere Hilfsregister). Das Ausgaberegister ${}R_{1}$ soll zu Beginn leer sein.

1. Leere ${}R_{\ell }$
2. Berechne ${}r_{t}\cdot r_{\ell }$ und schreibe das Ergebnis in ${}R_{k}$ (ohne ${}r_{t},r_{\ell }$ zu verändern)
3. Bei ${}r_{k}>r_{j}$ gehe zu 8
4. Bei ${}r_{k}=r_{j}$ gehe zu 7
5. ${}\ell +$
6. Gehe zu 2
7. ${}1+$
8. Drucke
9. Halte an

Beispiel

Es soll überprüft werden, ob der Registerinhalt ${}r_{j}$ (von ${}R_{j}$) eine Primzahl ist. Falls ja soll das Programm ${}1$ ausgeben, andernfalls ${}0$. Dies leistet das folgende Programm mit dem Hilfsregister ${}R_{t}$ (für Teilprogramme braucht man noch weitere Hilfsregister). Das Ausgaberegister ${}R_{1}$ soll zu Beginn leer sein.

1. Leere ${}R_{t}$
2. ${}t+$
3. ${}t+$
4. Wenn ${}r_{t}=r_{j}$, so gehe zu 8
5. Wenn ${}r_{t}\geq r_{j}$, so gehe zu 9
6. Wenn ${}r_{j}$ von ${}r_{t}$ geteilt wird, so gehe zu 9
7. Gehe zu 3
8. ${}1+$
9. Drucke
10. Halte an

Beispiel

Es sollen die geraden Zahlen ${}\geq 4$ daraufhin überprüft werden, ob sie die Eigenschaft in der Goldbachvermutung erfüllen, also ob sie die Summe von zwei Primzahlen sind. Das Programm soll die Ausgabe ${}0$ machen, falls ein Gegenbeispiel gefunden wurde. Dies leistet das folgende Programm mit den Registern ${}R_{n}$, ${}R_{k}$ und ${}R_{i}$, die alle zu Beginn auf ${}0$ gesetzt seien. Auch das Ausgaberegister ${}R_{1}$ soll zu Beginn leer sein. Wir testen ab ${}6$, um uns auf ungerade Primzahlen als Summanden beschränken zu können.

1. ${}n++++$
2. ${}n++$
3. Leere ${}R_{k}$
4. ${}k+$
5. ${}k++$
6. Wenn ${}r_{k}\geq r_{n}$, so gehe zu 12
7. Wenn ${}r_{k}$ eine Primzahl ist, so gehe zu 9
8. Gehe zu 5
9. Berechne ${}r_{n}-r_{k}$, schreibe das Ergebnis in ${}R_{i}$
10. Wenn ${}r_{i}$ eine Primzahl ist, so gehe zu 2
11. Gehe zu 5
12. Drucke
13. Halte an

Fußnoten

<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012) | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)