3. Das Postsche Korrespondenzproblem (PCP)
Emil Leon Post, polnisch-amerikanischer Mathematiker und Logiker, gest. 1954
gegeben: endliche Folge von Wortpaaren (x1, y1), ... ,(xk, yk)
alle Wörter aus + für ein Alphabet .
gefragt: gibt es Folge von Indizes i1, i2, ..., in, so dass
xi1...xin = yi1...yin
Beispiel: K = ((10,1), (110, 0110), (01, 001))
x1 y1 x2 y2 x3 y3
Lösung: (1,2,1,3): 10 110 10 01
1 0110 1 001
Nicht immer so einfach:
Beispiel: K = ((001,0), (01,011), (01,101), (10,001))
Kürzeste Lösung Folge von 66 Indizes!
PCP semi-entscheidbar: man kann alle möglichen Indexfolgen der Reihe nach erzeugen und testen (alle Indexfolgen der Länge1, 2, 3 usw.)
Aber es gilt der folgende Satz:
Satz: Das Postsche Korrespondenzproblem (PCP) ist unentscheidbar.
Beweis: siehe etwa Schöning
Es ist sogar unentscheidbar, wenn man sich auf {0,1} beschränkt.
Beweis durch Reduktion des Halteproblems auf das PCP.
Anmerkungen:
Da H PCP und PCP semi-entscheidbar, muss auch H semi-entscheidbar sein. Das heißt, es gibt eine Turingmaschine, die bei Eingabe von w#x hält genau dann wenn Mw bei Eingabe x hält.
|
