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

Aus Wikiversity

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

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 (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 , wobei es für die einzelnen Befehle die folgenden Möglichkeiten gibt.

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

Dabei muss für alle in einer Programmzeile adressierten Register und für alle adressierten Befehlszeilen gelten. Die letzte Befehlszeile 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 ist, so wird, falls die Bedingung zu diesem Zeitpunkt erfüllt ist (also falls das Register leer ist), zur Programmzeile gewechselt. Wenn die Endzeile , also der Haltebefehl erreicht wird, so ist die Bearbeitung beendet.

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

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 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 hinzunimmt, das von keiner anderen Programmzeile adressiert wird und dessen Inhalt auf gesetzt wird. Dann bewirkt der Befehl , dass zur -ten Programmzeile gewechselt wird, da der Inhalt des Registers im gesamten Programmverlauf gleich bleibt.



Beispiel  

Ein Programm soll sämtliche natürlichen Zahlen der Reihe nach ausdrucken. Dazu brauchen wir eine Registermaschine mit zwei Registern und , 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. Gehe zu
  3. Halte an


Beispiel  

Das Register soll geleert werden. Dies geschieht durch das folgende Programm.

  1. Gehe zu
  2. 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 durch die Befehle die gewünschte Belegung 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 um eine natürliche Zahl erhöht werden soll, also -fach direkt hintereinander inkrementiert werden soll, so schreiben wir dafür auch mit Pluszeichen.


Beispiel  

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

  1. Gehe zu
  2. Halte an

Wenn dieser Programmabschnitt abgelaufen ist, so steht im Register der Wert oder , je nachdem, ob 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 genau dann gilt, wenn ist. Dies ermöglicht einen Induktionsbeweis.



Beispiel  

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

  1. Gehe zu
  2. Gehe zu
  3. Halte an

Bei Gleichheit erhält man , bei Ungleichheit .


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


Beispiel  

Wir wollen den Registerinhalt des Registers in das Register übertragen (unabhängig von dessen Inhalt). Dies leistet das folgende Programm.

  1. Leere
  2. Gehe zu
  3. 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 des Registers in das Register übertragen (unabhängig von dessen Inhalt), ohne zu leeren. Dazu brauchen wir ein drittes Register und das folgende Programm.

  1. Leere
  2. Leere
  3. Gehe zu
  4. Übertrage den Inhalt von nach
  5. Halte an

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



Beispiel  

Die beiden Registerinhalte (von ) und (von ) sollen addiert werden, wobei die Summe zum Schluss in stehen soll (es seien paarweise verschieden). Dies leistet das folgende Programm.

  1. Leere
  2. Übertrage nach
  3. Gehe zu
  4. 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 (von ) und (von ) sollen multipliziert werden, wobei das Produkt zum Schluss in stehen soll (es seien paarweise verschieden). Dies leistet das folgende Programm mit dem Hilfsregister .

  1. Leere
  2. Übertrage den Inhalt von nach ohne zu leeren
  3. Addiere den Inhalt von zu hinzu
  4. Gehe zu
  5. Halte an

Die Korrektheit dieses Programms beruht auf ; für das Produkt muss man -mal mit sich selbst addieren.



Beispiel  

Es soll überprüft werden, ob der Registerinhalt (von ) den Registerinhalt (von ) teilt. Falls ja soll das Programm ausgeben, andernfalls . Dies leistet das folgende Programm mit den Hilfsregistern und (für Teilprogramme braucht man noch weitere Hilfsregister). Das Ausgaberegister soll zu Beginn leer sein.

  1. Leere
  2. Berechne und schreibe das Ergebnis in (ohne zu verändern)
  3. Bei gehe zu 8
  4. Bei gehe zu 7
  5. Gehe zu 2
  6. Drucke
  7. Halte an


Beispiel  

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

  1. Leere
  2. Wenn , so gehe zu 8
  3. Wenn , so gehe zu 9[1]
  4. Wenn von geteilt wird, so gehe zu 9
  5. Gehe zu 3
  6. Drucke
  7. Halte an


Beispiel  

Es sollen die geraden Zahlen 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 machen, falls ein Gegenbeispiel gefunden wurde. Dies leistet das folgende Programm mit den Registern , und , die alle zu Beginn auf gesetzt seien. Auch das Ausgaberegister soll zu Beginn leer sein. Wir testen ab , um uns auf ungerade Primzahlen als Summanden beschränken zu können.

  1. Leere
  2. Wenn , so gehe zu 12
  3. Wenn eine Primzahl ist, so gehe zu 9
  4. Gehe zu 5
  5. Berechne , schreibe das Ergebnis in
  6. Wenn eine Primzahl ist, so gehe zu 2
  7. Gehe zu 5
  8. Drucke
  9. Halte an



Fußnoten
  1. Die Programmzeile (5) ist nur für von Bedeutung.



<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)