Home     
    
    Bücher   Links   Impressum

next up previous contents
Nächste Seite: Halteproblem Aufwärts: Entscheidbarkeit Vorherige Seite: Zusammenhang zwischen Entscheidbarkeit und   Inhalt

Unterabschnitte

Rekursive Aufzählbarkeit

Rekursiv aufzählbar $\rightarrow$ Semientscheidbar

Rekursiv aufzählbar heißt, daß entweder die Sprache leer ist, oder daß es ein Verfahren gibt, welches die Sprache komplett aufzählt. Dabei können einzelne Elemente mehrfach aufgezählt werden.

Das Semientscheidungsverfahren kann man folgendermaßen auf die rekursive Aufzählbarkeit zurückführen: Wenn man fragt, ob ein Wort $w$ in der Sprache enthalten ist, so kann man das Aufzählungsverfahren durchlaufen lassen. Wenn das Wort enthalten ist, so berechnet das Aufzählungsverfahren irgendwann das Wort. Dann können wir ,,JA'' zurückgeben. Andernfalls läuft das Aufzählungsverfahren endlos und es wird eben halt nicht abgebrochen.

Semientscheidbar $\rightarrow$ Rekursiv aufzählbar

Die Sprache wird mit Hilfe des Semientscheidungsverfahrens rekursiv aufgezählt. Wir laufen allerdings in das Problem, daß, wenn für ein Wort $w$, daß nicht in der Sprache enthalten ist, das Semientscheidungsverfahren nicht terminiert, die Sprache nicht weiter aufzählt wird und der Algorithmus dann an dieser Stelle ,,hängt''.
Wir bedienen uns hierfür eines kleinen Tricks:
Wir stellen an das Semientscheidungsverfahren die Frage, ob nach $k$ Schritten, die DTM, die semientscheidet, akzeptiert. Wenn nach $k$ Schritten nicht akzeptiert wird, brechen wir einfach ab. Wir benutzen eine Funktion $\mathbb{N}\rightarrow\mathbb{N}\times\mathbb{N}$, die alle Tupel $(n,k)$ aufzählt und zwar so, daß $n$ und $k$ gleichmäßig erhöht werden. Beispielsweise folgendermaßen12:

\begin{picture}(100,100)(0,0) \put(0,0){\vector(1,0){100}} \put(0,0){\vector(0,1... ...let_{7}\,$} \put(6,-10){$1\,\,\,\,\,\, 2\,\,\,\,\,\, 3\,\,\,\, 4$} \end{picture}
Die Zahlen an den Punkten geben hierbei die Reihenfolge an, mit der die Punkte ,,besucht'' werden. Die x-Achse kann beispielsweise $n$ sein, die y-Achse $k$. Wir erhalten bei diesem Verfahren beispielweise die Paare

\begin{displaymath}(1,1),(2,1),(1,2),(1,3),(2,2),(3,1),(4,1),(3,2),(2,3),(1,4)\ldots\end{displaymath}

Nun bekommen wir für jedes Wort, welches in der Sprache enthalten ist, irgendwann ein ,,JA'', da die DTM ja nach endlich vielen Schritten ($k$) akzeptieren muß. Wir bekommen dann danach mehrmals für dieses Wort ein ,,JA'' und können es in die Sprache einreihen. Dies ist aber egal, da die Worte ja auch mehrmals auftreten dürfen.

Fußnoten

... folgendermaßen12
Dieses Verfahren ist das Verfahren zum Beweis, daß die rationalen Zahlen abzählbar sind.
next up previous contents
Nächste Seite: Halteproblem Aufwärts: Entscheidbarkeit Vorherige Seite: Zusammenhang zwischen Entscheidbarkeit und   Inhalt