BuK/IIm10/BuK-Kreativaufgabe05 G1

Wiki-Quelltext dieser Seite.

= 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 <math>((x_1,y_1),(x_2,y_2),\ldots,(x_m,y_m))</math> von nicht-leeren Wörtern <math>x_1, x_2, \ldots, x_m, y_1, y_2, \ldots, y_m</math> über einem endlichen Alphabet. Man nennt P auch einen Problemfall oder eine Instanz.

Eine nicht-leere Folge <math>I = i_1, i_2, \ldots, i_n</math> von Indices aus <math>\{1, 2, \ldots, m\}</math> heißt eine Lösung zum Problemfall P, falls die Konkatenation (Verkettung) der Wörte <math>{x_{i_1},x_{i_2},\ldots,x_{i_n}}</math> gleich der Konkatenation der Wörter <math>{y_{i_1},y_{i_2},\ldots,y_{i_n}}</math> 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: [http://de.wikipedia.org/wiki/Postsches_Korrespondenzproblem 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: <math>K = ((001, 0), (01, 011), (01, 101), (10, 001))</math>.
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 <math>x_{i}</math> bzw. aller <math>y_{i}</math> zurückgibt.
Diese Funktion nimmt dafür zusätzlich noch einen Parameter entgegen. Erwartet wird dabei entweder car, um auf <math>x_{i}</math> zuzugreifen oder cdr, um auf <math>y_{i}</math> zuzugreifen.

<code>
(define create-string
  (lambda (l il f)
    (cond
      ((empty? il) "")
      (else
       (string-append (f (list-ref l (car il))) (create-string l (cdr il) f))))))
</code>

Ein Beispielaufruf sieht hierbei wie folgt aus:

<run>
(create-string '(("001" . "0") ("01" . "011") ("01" . "101") ("10" . "001")) '(2 3 1 0 3 1) car)
</run>