Das POSTsche Korrespondenzproblem

Problembeschreibung

Das Postsche Korrespondenzproblem (nach Emil Leon Post, abgekürzt auch PKP oder englisch PCP) ist ein Beispiel für ein unentscheidbares Problem in der Theoretischen Informatik. Es wird häufig verwendet, um mittels Reduktion die Unentscheidbarkeit anderer Probleme zu zeigen.

Gegeben ist eine endliche Folge P von Paaren ((x_1,y_1),(x_2,y_2),\ldots,(x_m,y_m)) von nicht-leeren Wörtern x_1, x_2, \ldots, x_m, y_1, y_2, \ldots, y_m über einem endlichen Alphabet. Man nennt P auch einen Problemfall oder eine Instanz.

Eine nicht-leere Folge I = i_1, i_2, \ldots, i_n von Indices aus \{1, 2, \ldots, m\} heißt eine Lösung zum Problemfall P, falls die Konkatenation (Verkettung) der Wörte {x_{i_1},x_{i_2},\ldots,x_{i_n}} gleich der Konkatenation der Wörter {y_{i_1},y_{i_2},\ldots,y_{i_n}} ist.

Das Korrespondenzproblem ist dann die Aufgabe, zu einem beliebigen Problemfall anzugeben, ob er eine Lösung besitzt oder nicht. Das Korrespondenzproblem ist unentscheidbar, das heißt, es gibt keinen Algorithmus, der zu einem beliebigen Problemfall die richtige Antwort gibt.

(Quelle: Wikipedia)

Aufgabenstellung

Entwickeln Sie ein Scheme-Programm, das eine zugehörige Indexfolge mit den im Problem gegebenen Eigenschaften findet, falls eine solche Indexfolge existiert.

Testen Sie die unter anderem mit: K = ((001, 0), (01, 011), (01, 101), (10, 001)). Lösung: Die gesuchte Indexliste enthält 66 Elemente.

Lösung

Zur Vereinfachung der Lösung, ist es zunächst sinnvoll, einige Hilfsprozeduren zu implementieren. Zunächst benötigen wir eine Prozedur, die die Paarliste sowie die Indexliste entgegennimmt und die Verkettung aller x_{i} bzw. aller y_{i} zurückgibt. Diese Funktion nimmt dafür zusätzlich noch einen Parameter entgegen. Erwartet wird dabei entweder car, um auf x_{i} zuzugreifen oder cdr, um auf y_{i} zuzugreifen.

Ein Beispielaufruf sieht hierbei wie folgt aus: