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

Aus Wikiversity



Entscheidbarkeit und Berechenbarkeit

In der letzten Vorlesung haben wir verschiedene mathematische Operationen (wie Addition und Multiplikation) durch Registerprogramme berechnet und ebenso mathematische Prädikate (etwa das Prädikat, eine Primzahl zu sein) durch Registerprogramme charakterisiert. Die Fähigkeit eines Registerprogramms, bestimmte Funktionen bzw. Prädikate zu berechnen bzw. zu charakterisieren, führt zu den folgenden Begriffen.


Definition  

Eine - stellige Funktion

heißt -berechenbar (oder Register-berechenbar), wenn es ein Programm für eine Registermaschine gibt, die bei jeder Eingabe (in den ersten Registern) anhält und als (einzige) Ausgabe besitzt.


Definition  

Es sei eine Teilmenge der natürlichen Zahlen. Man sagt, dass diese Menge -entscheidbar (oder Register-entscheidbar) ist, wenn es ein Programm für eine Registermaschine gibt, die bei jeder Eingabe anhält und für die die Äquivalenz

gilt.

Eine Teilmenge ist genau dann -entscheidbar, wenn die zugehörige Indikatorfunktion -berechenbar ist.



Die Churchsche These

Wir haben in der letzten Vorlesung für einige recht einfache Aufgaben Registerprogramme angegeben, die diese Aufgabe lösen. Diese Beispiele vermitteln eine Vorstellung davon, was alles mit Registermaschinen berechnet werden kann. Zur Tragweite von algorithmischer Berechenbarkeit überhaupt ist die sogenannte Churchsche These von Bedeutung.

Bemerkung  

Die Churchsche These (nach Alonzo Church, manchmal auch Church-Turing-These) behauptet, dass die intuitiv berechenbaren Funktionen (bzw. die intuitiv entscheidbaren Prädikate) mit den Register-berechenbaren Funktionen übereinstimmt. Da es sich bei „intuitiv berechenbar“ um einen nicht präzisen Begriff handelt, lässt sich diese These nicht beweisen. Sie ist dennoch weitgehend akzeptiert, wobei die folgenden Gründe angeführt werden.

    • Alle Präzisierungen des Berechenbarkeitsbegriffs, nämlich durch Registermaschine, Turingmaschine, -rekursive Funktionen, -Kalkül, führen zu einer übereinstimmenden Klasse von berechenbaren Funktionen. Dies beruht darauf, dass man diese algorithmischen Verfahren wechselseitig simulieren kann.
    • Konkrete, intuitiv berechenbare Funktionen lassen sich stets durch ein Registerprogramm realisieren.

    In der Praxis ist die Churchsche These vor allem eine Erleichterung, da man aufgrund eines häufig naheliegenden intuitiven Algorithmus auf die Existenz eines Registerprogramms schließen kann, und so die oft mühevolle „Programmier-Arbeit“ umgeht.




    Das Halteproblem

    Nicht jedes Programm hält an. Ein einfaches Beispiel mit zwei Registern und leerer Belegung für ist

    1. Halte an

    Im Allgemeinen wird es sehr schnell schwierig, zu einem gegebenen konkreten Programm zur Eingabe zu entscheiden, ob es den Haltebefehl schließlich erreicht oder nicht. Ebenso ist es schwierig zu entscheiden, für welche Eingabedaten in (den Input) das konkrete Programm stoppt.

    Ein qualitativ anderes Problem ist allerdings die Frage, ob es ein Verfahren gibt, mit dem man für jedes Programm (bzw. jedes Programm und jede Eingabe) entscheiden kann, ob es anhält oder nicht.

    Hier deutet sich eine selbstbezügliche Fragestellung an: Gibt es ein Programm, das Aussagen über alle Programme machen kann? Welche Aussage macht dann dieses Programm über sich selbst?

    Um einen solchen Ansatz präzise machen zu können, müssen wir Programme als Eingabe für ein Programm interpretieren können. Das Programm einer Registermaschine erlaubt nur die Eingabe einer Zahl. Daher müssen wir ein Programm durch eine Zahl kodieren. Dies geschieht in zwei Schritten.

    Zuerst führen wir für die erlaubten Befehle abkürzende Schreibweisen ein. Wir arbeiten mit dem Alphabet

    Die einzelnen Befehle werden folgendermaßen notiert

    1. Inkrementierung von : (mit Strichen).
    2. Dekrementierung von : (mit Strichen).
    3. Sprunganweisung : (mit Strichen vor dem Komma und Strichen nach dem Komma).
    4. Druckanweisung: .
    5. Halteanweisung: .

    Das Symbol wird also benutzt, um sowohl die Registernummern als auch die Zeilennummern (in der Sprunganweisung) auszudrücken. Da in jeder Befehlszeile eines konkreten Programmes konkrete Register bzw. Zeilen adressiert werden, stehen da jeweils natürliche Zahlen (keine Variablen), die problemlos durch eine Strichfolge ausgedrückt werden können.

    Ein Programm, das aus den durchnummerierten Befehlszeilen besteht, wird dann insgesamt durch die Zeichenfolge

    wiedergegeben, wobei die die soeben angeführte Kodierung der -ten Befehlszeile ist. Das Zeichen wird also verwendet, um die Zeilen voneinander zu trennen. Das Mitschleppen der Zeilennummern ist nicht nötig, da sich die Nummer aus der Reihenfolge rekonstruieren lässt.

    Das oben angegebene Programm hätte demnach die symbolische Kodierung

    In einem zweiten Schritt ersetzen wir diese symbolische Kodierung durch eine numerische Kodierung. Dafür gibt es verschiedene Möglichkeiten. Da unser Alphabet, mit dem wir jedes Programm schreiben können, Symbole verwendet, liegt eine Repräsentierung im Achtersystem nahe. Da die als Anfangsnummer etwas problematisch ist, arbeiten wir lieber im Neunersystem (man kann die folgenden Zahlen genau so gut im Zehnersystem auffassen) und ordnen den Symbolen von oben in der obigen Reihenfolge die Ziffern

    zu. Das Programm von oben wird dann zur Ziffernfolge

    Die einem jeden Programm auf diese Weise zugeordnete Zahl (also der Zahlwert, nicht die Ziffernfolge) nennen wir . Man spricht von der Gödelnummer des Programms.

    Bemerkung  

    Es ist algorithmisch überprüfbar, ob eine als Strichfolge gegebene natürliche Zahl ein Code für ein Registerprogramm ist. Dazu muss zuerst die Zahl in ihre Ziffernentwicklung (im Neunersystem) übersetzt werden. Da der Trennstrich, der die einzelnen Befehle trennt, durch eine bestimmte Ziffer codiert wird, muss die Ziffernfolge zwischen zwei Trennstrichziffern einen Befehl codieren. Die syntaktische Korrektheit dieser einzelnen Befehlsziffernfolgen muss dann der Reihe nach überprüft werden. Dazu muss man für jeden der Einzelbefehle einen Algorithmus entwerfen. Wenn beispielsweise die Anfangsziffer einer Befehlsziffernfolge eine (also ein ) ist, so muss es sich um einen Inkrementierungsbefehl handeln und alle nachfolgenden Ziffern (bis zum nächsten Trennstrich) müssen Striche sein.


    Für ein Registerprogramm und eine natürliche Zahl verstehen wir unter das Programm angesetzt auf im ersten Register (und leeren anderen Registern).



    Lemma  

    Die Menge

    ist nicht - entscheidbar.

    Beweis  

    Wir nehmen an, dass es ein Programm gibt, das diese Menge entscheidet (der erste Teilaspekt, ob es sich überhaupt um ein valides Programm handelt, ist entscheidbar). Wir ändern dieses Programm zu einem Programm ab, indem wir den letzten Befehl von (also den Haltebefehl) durch den Programmabschnitt (mit der relativen Nummerierung und einem neuen Register )

    1. Gehe zu
    2. Halte an

    ersetzen. Dies bedeutet, dass das Programm genau dann in eine Endlosschleife hineinkommt und nicht anhält, wenn das Programm die Ausgabe hat. Daher gilt die Äquivalenz, dass ein Programm bei Eingabe der eigenen Programmnummer genau dann anhält, wenn bei Eingabe der Programmnummer von nicht anhält. Diese Äquivalenz ergibt bei Anwendung auf das Programm einen Widerspruch.



    Satz  

    Die Menge

    ist nicht - entscheidbar.

    Beweis  

    Wir nehmen an, dass es ein Registerprogramm gibt, dass die in Frage stehende Menge entscheidet, also stets anhält und angesetzt auf eine Zahl genau dann die Ausgabe liefert, wenn für ein Programm ist (also wenn die Programmnummer eines Registerprogramms ist) und wenn dieses Programm , angesetzt auf , anhält. Wir entwickeln aus ein Programm , das genau dann die Ausgabe hat, wenn für ein Programm ist und wenn , angesetzt auf , anhält. Dies ergibt einen Widerspruch zu Lemma 9.5.

    Dazu wird folgendermaßen konstruiert: Wenn keine Programmnummer ist, so hält das Programm mit der Ausgabe an (hier gibt es also keinen Unterschied zu ). Wenn eine Programmnummer ist, so wird das Programm aufgestellt, das dem Programm die -fache Inkrementierung des ersten Registers voranstellt und dessen (in einem bedingten Sprungbefehl in einer Befehlszeile) adressierte Befehlszeilennummern sich um erhöhen. Für die Programmnummer wird nun mittels überprüft, welche Ausgabe , angesetzt auf , besitzt. Aufgrund der Konstruktion von besitzt bei Eingabe die Ausgabe genau dann, wenn bei Eingabe von die Ausgabe besitzt.




    Aufzählbarkeit von Programmen

    Wir führen einen weiteren Berechenbarkeitsbegriff ein.


    Definition  

    Es sei eine Teilmenge der natürlichen Zahlen. Man sagt, dass diese Menge -aufzählbar (oder Register-aufzählbar) ist, wenn es ein Programm für eine Registermaschine gibt, die bei Eingabe von nach und nach genau die Zahlen aus ausdruckt (dabei dürfen Zahlen aus auch mehrfach ausgedruckt werden).

    Zwischen Entscheidbarkeit und Aufzählbarkeit besteht der folgende Zusammenhang.


    Lemma  

    Es sei eine Teilmenge der natürlichen Zahlen.

    Dann ist genau dann - entscheidbar, wenn sowohl als auch das Komplement - aufzählbar ist.

    Beweis  

    Wenn ein Programm ist, das entscheidet, so kann man einfach ein aufzählendes Programm konstruieren. Man lässt der Reihe nach jede natürliche Zahl mittels auf ihre Zugehörigkeit zu überprüfen und druckt sie aus, falls sie dazu gehört (dazu muss man den Haltebefehl von zu einer Druckausgabe modifizieren). Entsprechend konstruiert man ein Aufzählungsprogramm für das Komplement.

    Es seien nun als auch aufzählbar, und es seien und Programme, die dies leisten. Dann liefert die folgende Kombination der beiden Programme ein Entscheidungsverfahren: Man schreibt die Programme und hintereinander (wobei man natürlich die adressierten Register und Programmzeilen umnummerieren muss) und lässt sie abwechselnd bis zu einer Druckausgabe laufen. Sobald eine Druckausgabe eines Programmteils mit der zu überprüfenden Zahl übereinstimmt, weiß man, ob zu gehört oder nicht. Da entweder zu oder zum Komplement gehört, muss einer dieser Fälle eintreten.



    Lemma  

    Die Menge der Programmnummern von Registerprogrammen, die angesetzt auf anhalten, ist - aufzählbar.

    Beweis  

    Die Idee für ein algorithmisches Aufzählverfahren geht so: Zu jeder natürlichen Zahl berechnet man sämtliche Programme mit . Jedes dieser Programme lässt man, angesetzt auf , Schritte (also Befehlszeilenwechsel) lang laufen. Wenn anhält, so druckt man aus. Wenn all diese Programme Schritte gelaufen sind, so erhöht man auf . Da ein jedes anhaltendes Programm nach einer gewissen Laufzeit anhält, wird es bei als anhaltendes Programm erfasst.


    Daraus folgt insbesondere, dass die nicht haltenden Programme nicht aufzählbar sind.


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

    PDF-Version dieser Vorlesung

    Arbeitsblatt zur Vorlesung (PDF)