Vorlesungsprotokoll zur Vorlesung

"Grundlagen der theoretischen Informatik" vom 6.6.2001

Nils Barnickel

Dozent: Prof. Dr. Günter Rote

Themen der Vorlesung:

· Universelle Turingmaschinen, die universelle Sprache

· Unentscheidbarkeit des Halteproblems

· Turingmaschinen mit mehreren Bändern

· Turingmaschinen, die eine Sprache aufzählen

Universelle Turingmaschinen, die universelle Sprache

In der vorigen Vorlesungen wurde gezeigt wie sich Turingmaschinen geeignet codieren lassen. Sei <M> ein solcher Code und w eine Eingabe für diese Turingmaschine, dann ist die universelle Sprache wie folgt definiert:

U = {<M> w | M akzeptiert w}

Satz:

Es gibt eine Turingmaschine Mu mit L(Mu) = U.

Diese Turingmaschine heiszlig;t universelle Turingmaschine.

Beweis:

Mu liest <M> (das "Programm") und w (die "Eingabe" für M) und simuliert anschlieszlig;end die Maschine M Schritt für Schritt.

Satz:

U ist rekursiv aufzählbar aber nicht entscheidbar.

Beweis:

1) rekursiv aufzählbar, da L(Mu) = U existiert.

2) Wenn U entscheidbar wäre, dann würde der folgende Algorithmus die

Diagonalsprache D entscheiden.

Eingabe wi

Berechne Mi

Ist < Mi> wi in U?

Wenn "ja" würde die Ausgabe von Md "nein" sein.

Wenn "nein" würde die Ausgabe von Md "ja" sein.

Somit wäre D entscheidbar.

(D ist aber nicht entscheidbar =>Widerspruch, also U nicht entscheidbar)

Unentscheidbarkeit des Halteproblems

Hält eine Turingmaschine M bei Eingabe w ?

H = {<M> w | M hält bei Eingabe von w}

Satz:

H ist unentscheidbar.

Beweis:

Idee: Mit Hilfe von H wäre jede rekursiv aufzählbare Sprache entscheidbar. Insbesondere wäre U entscheidbar, mit folgendem Algorithmus.

Eingabe: <M> w

Hält M auf Eingabe w?

Wenn "nein", Ausgabe "nein".

Wenn "ja", simuliere M bis sie hält. Wenn sie in einem akzeptierenden Zustand hält, Ausgabe "ja", sonst "nein".

Frage: Kommt jeder endliche Ziffernblock aus {0,1,2,...,9} in der

Dezimaldarstellung von P vor?

Diese Frage ist entscheidbar. Denn einer der folgenden Algorithmen gibt die richtige Antwort.

ALG1: Ausgabe "ja"

ALG2: Ausgabe "nein"

Das Post'sche Korrespondenzproblem(PKP)

Eingabe (x1,y1),(x2,y2),...,(xk,yk) mit xi,yi in Sigma^*

Frage: Gibt es eine Folge i1,i2,...,in , n>=1 mit xi1,xi2,...,xin = yi1,yi2,...,yin?

Bsp.1) (10,1),(001,0),(111,000)

x1x2 = 10001

y1y2 = 10

Es gibt keine Lösung.(x ist immer länger/gleich y)

Bsp.2) (10,1),(001,0),(1,010011)

x1x2x2x3 = 10.001.001.1

y1y2y2y3 = 1.0.0.010011

Es gibt eine Lösung.

Satz: Das PKP ist unentscheidbar.

(ohne Beweis(Das Halteproblem kann auf das PKP zurückgeführt werden.))

Turingmaschinen mit mehreren Bändern

Turingmaschinen mit mehren Bändern bringen einen Geschwindigkeitsvorteil.

Es kann dann ein Eingabeband geben, das nur zum Lesen ist, oder ein Ausgabeband, das nur zum Schreiben ist.

Z.B. kann man eine TM mit Ausgabeband als Erzeugungsmechanismus verwenden.

Auf dem Ausgabeband darf man nur schreiben und nach rechts gehen.

Turingmaschinen, die eine Sprache aufzählen

Satz:

Eine Sprache L = {x1,x2,...} ist genau dann rekursiv aufzählbar, wenn die Wörter von L (in beliebiger Reihenfolge, durch "*"-Zeichen getrennt) von einer erzeugenden Turingmaschine G auf das Ausgabeband geschrieben werden. ("aufgezählt") G hält genau dann, wenn L endlich ist.

Beweis:

"<=": Eingabe w

Simuliere G und warte, bis das Wort w ausgeben wird.

Dann akzeptiere.

"=>": Sigma^* = {w1,w2,...}

L(M) = L

k Schritte

k	0	1	2	3	4	...
w1	a	b	d	g	k
w2	c	e	X	...
w3	f	i
w4	X
...

(Es wird in alphabetischer Reihenfolge gezählt.)

for n:= 1 to unendlich

for k:= 0 to n-1 do

Überprüfe, ob M das Wort w(n-k) nach genau k Schritten akzeptiert.

Wenn ja, dann schreibe w(n-k) auf das Ausgabeband.

Es werden genau die Wörter von L(M) ausgeben.