Kurs:Einführung in die mathematische Logik (Osnabrück 2014)/Vorlesung 19/latex
\setcounter{section}{19}
\zwischenueberschrift{Entscheidbarkeit und Berechenbarkeit}
In der letzten Vorlesung haben wir verschiedene mathematische Operationen \zusatzklammer {wie Addition und Multiplikation} {} {} durch Registerprogramme berechnet und ebenso mathematische Prädikate \zusatzklammer {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.
\inputdefinition
{}
{
Eine
$k$-\definitionsverweis {stellige Funktion}{}{}
\maabbdisp {F} {\N^k} {\N
} {}
heißt
\definitionswortpraemath {R}{ berechenbar }{}
\zusatzklammer {oder
\definitionswort {Register-berechenbar}{}} {} {,}
wenn es ein Programm $P$ für eine Registermaschine gibt, die bei jeder Eingabe
\mathl{(r_1 , \ldots , r_k)}{}
\zusatzklammer {in den ersten $k$ Registern} {} {}
anhält und
\mathl{F(r_1 , \ldots , r_k)}{} als
\zusatzklammer {einzige} {} {}
Ausgabe besitzt.
}
\inputdefinition
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Teilmenge der natürlichen Zahlen. Man sagt, dass diese Menge
\definitionswortpraemath {R}{ entscheidbar }{}
\zusatzklammer {oder \definitionswort {Register-entscheidbar}{}} {} {}
ist, wenn es ein Programm $P$ für eine Registermaschine gibt, die bei jeder Eingabe anhält und für die die Äquivalenz
\mathdisp {n \in T \text{ genau dann, wenn } P(n) \text{ die Ausgabe } 0 \text{ besitzt}} { }
gilt.
}
Eine Teilmenge
\mathl{T \subseteq \N}{} ist genau dann $R$-entscheidbar, wenn die zugehörige
\definitionsverweis {Indikatorfunktion}{}{} $R$-berechenbar ist.
\zwischenueberschrift{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 \stichwort {Churchsche These} {} von Bedeutung.
\inputbemerkung
{}
{
Die \stichwort {Churchsche These} {} \zusatzklammer {nach Alonzo Church, manchmal auch \stichwort {Church-Turing-These} {}} {} {} behauptet, dass die intuitiv berechenbaren Funktionen \zusatzklammer {bzw. die intuitiv entscheidbaren Prädikate} {} {} mit den \definitionsverweis {Register-berechenbaren}{}{} Funktionen übereinstimmt. Da es sich bei \anfuehrung{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. \auflistungzwei{Alle Präzisierungen des Berechenbarkeitsbegriffs, nämlich durch Registermaschine, Turingmaschine, $\mu$-rekursive Funktionen, $\lambda$-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 \anfuehrung{Programmier-Arbeit}{} umgeht.
}
\zwischenueberschrift{Das Halteproblem}
Nicht jedes Programm hält an. Ein einfaches Beispiel mit zwei Registern
\mathl{R_1,R_2}{} und leerer Belegung für $R_2$ ist
\aufzaehlungdrei{$1+$
}{
\mathl{C(2,1)}{}
}{Halte an
}
Im Allgemeinen wird es sehr schnell schwierig, zu einem gegebenen konkreten Programm zur Eingabe
\mavergleichskette
{\vergleichskette
{r_1
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
zu entscheiden, ob es den Haltebefehl schließlich erreicht oder nicht. Ebenso ist es schwierig zu entscheiden, für welche Eingabedaten in
\mathl{R_1}{}
\zusatzklammer {den \stichwort {Input} {}} {} {}
das konkrete Programm stoppt. Wenn man das Programm bei einer bestimmten Eingabe laufen lässt und es nach einer gewissen Zeit anhält, so kann man dies natürlich unmittelbar als einen Beweis für die Halteeigenschaft des Programms verstehen. Wenn das Programm nicht die Halteeigenschaft hat, so kann man dies aus dem Programmablauf nicht erschließen. Das Programm läuft einfach weiter und man weiß nicht, ob es einfach noch nicht angehalten hat oder ob es niemals anhalten wird. Mit einer aufwändigen Analyse des Programms wird man im Allgemeinen erkennen können, ob das Programm anhält oder nicht.
Ein qualitativ anderes Problem ist allerdings die Frage, ob es ein deterministisches Verfahren gibt, mit dem man für jedes Programm \zusatzklammer {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
\mathdisp {\prime \,-\,I\,D\,C\,P\,H \, ,} { }
Die einzelnen Befehle werden folgendermaßen notiert
\aufzaehlungfuenf{Inkrementierung von $R_i$
\mathl{I \prime \prime \cdots \prime}{} \zusatzklammer {mit $i$ Strichen} {} {.}
}{Dekrementierung von $R_i$
\mathl{D \prime \prime \cdots \prime}{} \zusatzklammer {mit $i$ Strichen} {} {.}
}{Sprunganweisung $C(i,j)$
\mathl{C \prime \prime \cdots \prime , \prime \prime \cdots \prime}{} \zusatzklammer {mit $i$ Strichen vor dem Komma und $j$ Strichen nach dem Komma} {} {.}
}{Druckanweisung: $P$. }{Halteanweisung: $H$. } Das Symbol $\prime$ wird also benutzt, um sowohl die Registernummern als auch die Zeilennummern \zusatzklammer {in der Sprunganweisung} {} {} auszudrücken. Da in jeder Befehlszeile eines konkreten Programmes konkrete Register bzw. Zeilen adressiert werden, stehen da jeweils natürliche Zahlen \zusatzklammer {keine Variablen} {} {,} die problemlos durch eine Strichfolge ausgedrückt werden können.
Ein Programm, das aus den durchnummerierten Befehlszeilen
\mathl{B_1,B_2 , \ldots , B_h}{} besteht, wird dann insgesamt durch die Zeichenfolge
\mathdisp {b_1-b_2- \ldots -b_h} { }
wiedergegeben, wobei $b_j$ die soeben angeführte Kodierung der $j$-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
\mathdisp {I \prime -C \prime \prime , \prime -H} { }
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, $8$ Symbole verwendet, liegt eine Repräsentierung im Achtersystem nahe. Da die $0$ als Anfangsnummer etwas problematisch ist, arbeiten wir lieber im Neunersystem
\zusatzklammer {man kann die folgenden Zahlen genauso gut im Zehnersystem auffassen} {} {}
und ordnen den Symbolen von oben in der obigen Reihenfolge die Ziffern
\mathdisp {1,2,3,4,5,6,7,8} { }
zu. Das Programm von oben wird dann zur Ziffernfolge
\mathdisp {3125118127} { . }
Die einem jeden Programm $P$ auf diese Weise zugeordnete Zahl
\zusatzklammer {also der Zahlwert, nicht die Ziffernfolge} {} {}
nennen wir
\mathl{c(P)}{.} Man spricht von der \stichwort {Gödelnummer} {} des Programms.
\inputbemerkung
{}
{
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 \zusatzklammer {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 $3$ \zusatzklammer {also ein $I$} {} {} ist, so muss es sich um einen Inkrementierungsbefehl handeln und alle nachfolgenden Ziffern \zusatzklammer {bis zum nächsten Trennstrich} {} {} müssen Striche sein.
}
Für ein Registerprogramm $P$ und eine natürliche Zahl $n$ verstehen wir unter
\mathl{P(n)}{} das Programm angesetzt auf $n$ im ersten Register
\zusatzklammer {und leeren anderen Registern} {} {.}
\inputfaktbeweis
{Halteproblem/Registermaschine/Eingabe der Programmnummer/Unentscheidbarkeit/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktfolgerung {Die Menge
\mathdisp {{ \left\{ n \in \N \mid n \text { ist die Nummer eines Registerprogramms } P \text{ und } P(n) \text{ hält an} \right\} }} { }
ist nicht
$R$-\definitionsverweis {entscheidbar}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Wir nehmen an, dass es ein Programm $U$ gibt, das diese Menge entscheidet
\zusatzklammer {der erste Teilaspekt, ob es sich überhaupt um ein valides Programm handelt, ist entscheidbar} {} {.}
Wir ändern dieses Programm zu einem Programm $U^\prime$ ab, indem wir den letzten Befehl von $U$
\zusatzklammer {also den Haltebefehl} {} {}
durch den Programmabschnitt
\zusatzklammer {mit der relativen Nummerierung und einem neuen Register
$R_i$} {} {}
\aufzaehlungfuenf{
\mathl{C(1,3)}{}
}{Gehe zu $5$
}{$i+$
}{
\mathl{C(1,3)}{}
}{Halte an
}
ersetzen. Dies bedeutet, dass das Programm $U'$ genau dann in eine Endlosschleife hineinkommt und nicht anhält, wenn das Programm $U$ die Ausgabe $0$ hat. Daher gilt die Äquivalenz, dass ein Programm $P$ bei Eingabe der eigenen Programmnummer
\mathl{c(P)}{} genau dann anhält, wenn $U'$ bei Eingabe der Programmnummer
\mathl{c(P)}{} von $P$ nicht anhält. Diese Äquivalenz ergibt bei Anwendung auf das Programm
\mavergleichskette
{\vergleichskette
{P
}
{ = }{U'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
einen Widerspruch.
\inputfaktbeweis
{Halteproblem/Registermaschine/Unentscheidbarkeit/Fakt}
{Satz}
{}
{
\faktsituation {}
\faktfolgerung {Die Menge
\mathdisp {{ \left\{ n \in \N \mid n \text { ist die Nummer eines Registerprogramms } P \text{ und } P(0) \text{ hält an} \right\} }} { }
ist nicht
$R$-\definitionsverweis {entscheidbar}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Wir nehmen an, dass es ein Registerprogramm $V$ gibt, dass die in Frage stehende Menge entscheidet, also stets anhält und angesetzt auf eine Zahl $n$ genau dann die Ausgabe $0$ liefert, wenn
\mavergleichskette
{\vergleichskette
{n
}
{ = }{ c(P)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für ein Programm $P$ ist
\zusatzklammer {also wenn $n$ die Programmnummer eines Registerprogramms ist} {} {}
und wenn dieses Programm $P$, angesetzt auf $0$, anhält. Wir entwickeln aus $V$ ein Programm $U$, das genau dann die Ausgabe $0$ hat, wenn
\mavergleichskette
{\vergleichskette
{n
}
{ = }{ c(P)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für ein Programm $P$ ist und wenn $P$, angesetzt auf $n$, anhält. Dies ergibt einen Widerspruch zu
Lemma 19.5.
Dazu wird $U$ folgendermaßen konstruiert: Wenn $n$ keine Programmnummer ist, so hält das Programm $U$ mit der Ausgabe $1$ an
\zusatzklammer {hier gibt es also keinen Unterschied zu $V$} {} {.}
Wenn
\mavergleichskette
{\vergleichskette
{ n
}
{ = }{ c(P)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Programmnummer ist, so wird das Programm $P'$ aufgestellt, das dem Programm $P$ die $n$-fache Inkrementierung des ersten Registers voranstellt und dessen
\zusatzklammer {in einem bedingten Sprungbefehl in einer Befehlszeile} {} {}
adressierte Befehlszeilennummern sich um $n$ erhöhen. Für die Programmnummer
\mavergleichskette
{\vergleichskette
{n'
}
{ = }{c(P')
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
wird nun mittels $V$ überprüft, welche Ausgabe $P'$, angesetzt auf $0$, besitzt. Aufgrund der Konstruktion von $P'$ besitzt $P'$ bei Eingabe $0$ die Ausgabe $0$ genau dann, wenn $P$ bei Eingabe von $n$ die Ausgabe $0$ besitzt.
\zwischenueberschrift{Aufzählbarkeit von Programmen}
Wir führen einen weiteren Berechenbarkeitsbegriff ein.
\inputdefinition
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Teilmenge der natürlichen Zahlen. Man sagt, dass diese Menge
\definitionswortpraemath {R}{ aufzählbar }{}
\zusatzklammer {oder \definitionswort {Register-aufzählbar}{}} {} {}
ist, wenn es ein Programm $P$ für eine Registermaschine gibt, die bei Eingabe von $0$ nach und nach genau die Zahlen aus $T$ ausdruckt
\zusatzklammer {dabei dürfen Zahlen aus $T$ auch mehrfach ausgedruckt werden} {} {.}
}
Zwischen Entscheidbarkeit und Aufzählbarkeit besteht der folgende Zusammenhang.
\inputfaktbeweis
{Registermaschine/Entscheidbarkeit und Aufzählbarkeit/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Teilmenge der natürlichen Zahlen.}
\faktfolgerung {Dann ist $T$ genau dann
$R$-\definitionsverweis {entscheidbar}{}{,}
wenn sowohl $T$ als auch das Komplement
\mathl{\N \setminus T}{}
$R$-\definitionsverweis {aufzählbar}{}{}
ist.}
\faktzusatz {}
\faktzusatz {}
}
{
\teilbeweis {}{}{}
{Wenn $P$ ein Programm ist, das $T$ entscheidet, so kann man einfach ein $T$ aufzählendes Programm konstruieren. Man lässt der Reihe nach jede natürliche Zahl mittels $P$ auf ihre Zugehörigkeit zu $T$ überprüfen und druckt sie aus, falls sie dazu gehört
\zusatzklammer {dazu muss man den Haltebefehl von $P$ zu einer Druckausgabe modifizieren} {} {.}
Entsprechend konstruiert man ein Aufzählungsprogramm für das Komplement.}
{}
\teilbeweis {}{}{}
{Es seien nun
\mathkor {} {T} {als auch} {\N \setminus T} {}
aufzählbar, und es seien $P$ und $Q$ Programme, die dies leisten. Dann liefert die folgende Kombination der beiden Programme ein Entscheidungsverfahren: Man schreibt die Programme $P$ und $Q$ hintereinander
\zusatzklammer {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 $n$ übereinstimmt, weiß man, ob $n$ zu $T$ gehört oder nicht. Da $n$ entweder zu $T$ oder zum Komplement gehört, muss einer dieser Fälle eintreten.}
{}
\inputfaktbeweis
{Registermaschine/Haltende Programme/Aufzählbar/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktfolgerung {Die Menge der Programmnummern von
\definitionsverweis {Registerprogrammen}{}{,}
die angesetzt auf $0$ anhalten, ist
$R$-\definitionsverweis {aufzählbar}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Die Idee für ein algorithmisches Aufzählverfahren geht so: Zu jeder natürlichen Zahl $n$ berechnet man sämtliche Programme $P$ mit
\mavergleichskette
{\vergleichskette
{c(P)
}
{ \leq }{ n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Jedes dieser Programme lässt man, angesetzt auf $0$, $n$ Schritte
\zusatzklammer {also $n$ Befehlszeilenwechsel} {} {}
lang laufen. Wenn $P$ anhält, so druckt man
\mathl{c(P)}{} aus. Wenn all diese Programme $n$ Schritte gelaufen sind, so erhöht man auf
\mathl{n+1}{.} Da ein jedes anhaltendes Programm nach einer gewissen Laufzeit $\ell$ anhält, wird es bei
\mavergleichskette
{\vergleichskette
{n
}
{ = }{ {\max { \left( c(P) , \ell \right) } }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
als anhaltendes Programm erfasst.
Daraus folgt insbesondere, dass die nicht haltenden Programme nicht aufzählbar sind.