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.

<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
== 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 id="4dbefb567e4ea">
(define create-string
  (lambda (l il f)
    (cond
      ((null? 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 id="4dbefb567e555">
(create-string '(("001" . "0") ("01" . "011") ("01" . "101") ("10" . "001")) '(2 3 1 0 3 1) car)
</run>
Desweiteren benötigen wir eine Funktion, die uns die nächste Indexliste, zu einer gegebenen Indexliste gibt. Dazu muss der Funktion natürlich noch der maximale Index übergeben werden.
Diese Funktion benötigt zudem noch 2 weitere Hilfsfunktionen. Zum Einen eine Funktion, die überprüft ob eine gegebene Indexliste 'voll' ist, das heißt, ob alle Elemente, den höchstmöglichen Wert haben. Zum Anderen eine Funktion die eine neue Liste mit der vorgegebenen Anzahl an Elementen erzeugt. In unserem Fall sollen diese mit 0 vorbelegt werden.

<code id="4dbf0084c23fc">
(define list-full?
  (lambda (il n index)
    (if (null? il)
      #t
      (if (= 0 index)
        (and (= (car il) n) (list-full? (cdr il) n index))
        (list-full? (cdr il) n (- index 1))))))

(define new-list
  (lambda (length elem)
    (cond
      ((= 0 length) '())
      (else (append (list elem) (new-list (- length 1) elem))))))

(define next-index-list
  (lambda (il n)
    (cond
      ((list-full? il n 0) (new-list (+ (length il) 1) 0))
      ((list-full? (cdr il) n 0) (append (list (+ (car il) 1)) (new-list (- (length il) 1) 0)))
      (else (append (list (car il)) (next-index-list (cdr il) n))))))
</code>

<code id="4dbf0084c2471" hidden>
(define head car)

(define (tail stream) (force (cdr stream)))

(define-syntax cons-stream
  (syntax-rules ()
    ((cons-stream x y)
     (cons x (delay y)))))

(define (indexlisten-starting-from l)
 (cons-stream l 
  (indexlisten-starting-from (next-index-list l 2))))

(define indexlisten
  (indexlisten-starting-from '(0)))

(define (stream-elems s n)
  (cond
    ((= n 0) (list (head s)))
    (else
     (append (list (head s)) (stream-elems (tail s) (- n 1))))))
</code>

Zum anzeigen der ersten Indexlisten (hier für Listen mit einem maximalen Index von 2) verwenden wir Streams:
<run id="4dbf0084c2561">
(stream-elems indexlisten 15)
</run>
Nun ist es kein Problem mehr, eine Funktion anzugeben, die, in diesem Fall sogar eine der kürzesten Indexlisten, ab einer bestimmten 'Start-Indexliste' zurückgibt.
<code id="4dbf0084c24d9">
(define post-problem-list
  (lambda (l il)
    (if (string=? (create-string l il car) (create-string l il cdr))
      il
      (post-problem-list l (next-index-list il (- (length l) 1))))))
</code>
Als Beispiel sei hier ein Aufruf mit einer weniger komplexen Lösung genannt:
<run id="4dbf0084c25cf">
(post-problem-list '(("1" . "101") ("010" . "0")) '(0))
</run>
Zum Beweis der Lösung, kann man sich auch nochmal die Ausgabe von create-string ansehen. (Probieren Sie den Aufruf auch mit cdr)
<run id="4dbf0084c2630">
(create-string '(("1" . "101") ("010" . "0")) '(0 1) car)
</run>
Da die Lösung für die oben genannte Paarliste, mit einer 66-Elemente großen Indexliste sehr komplex ist und somit die Berechnung enorm viel Zeit in Anspruch nehmen würde. Haben wir uns dazu entschieden, eine Indexliste vorzugeben, die nicht weit von der eigentlichen Lösung entfernt ist (tatsächlich muss nur ein Index geändert werden).
Die Ausführungsdauer des folgenden Aufrufs, wird somit auf ein annehmbares Maß reduziert.
<run id="4dbf0372d3fcb">
(post-problem-list '(("001" . "0") ("01" . "011") ("01" . "101") ("10" . "001"))
'(1 3 2 3 3 1 0 1 3 2 3 2 3 3 2 3 3 1 0 3 3 1 0 2 3 0 0 2 3 3 3 1 0 1 0 0 0 2 3 2 3 0 1 0 3 3 1 0 3 0 0 2 3 0 0 2 0 0 1 0 1 0 3 0 0 2))
</run>
Zum Vergleich können nun noch die beiden Wörter manuell verglichen werden, indem man den folgenden Aufruf wieder zunächst mit car und daraufhin mit cdr ausführt.
<run id="4dbf0372d409a">
(create-string '(("001" . "0") ("01" . "011") ("01" . "101") ("10" . "001"))
'(1 3 2 3 3 1 0 1 3 2 3 2 3 3 2 3 3 1 0 3 3 1 0 2 3 0 0 2 3 3 3 1 0 1 0 0 0 2 3 2 3 0 1 0 3 3 1 0 3 0 0 2 3 0 0 2 0 0 2 0 1 0 3 0 0 2) car)
</run>