Turing-Berechenbarkeit und Churchsche These

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Merkwürdige aber berechenbare Funktionen 1.1 Collatz-Folge 1.2 Für alle Argumente undefinierte Funktion 1.3 Totale und partielle Funktionen 2 Das Postsche Korrespondenzproblem (PCP)

Merkwürdige aber berechenbare Funktionen

Collatz-Folge

(define collatz (lambda (n) (cond ((= n 1) '(1)) ((even? n) (cons n (collatz (/ n 2)))) (else (cons n (collatz (+ (* 3 n) 1)))))))

(collatz 7)

ausführen

Für alle Argumente undefinierte Funktion

(define nirgends_definiert (lambda (n) (nirgends_definiert n)))

(nirgends_definiert 12)

ausführen

Totale und partielle Funktionen

(define nicht_fuer_alle (lambda (n) (if (< n 3) 1 (nirgends_definiert 10))))

(nicht_fuer_alle 2)

ausführen

Verändern Sie das Argument in diesem Aufruf zu 2 und bewerten Sie das Resultat.

Das Postsche Korrespondenzproblem (PCP)

Wir definieren eine Liste von Indexlisten, kurz: Indexlistenliste, der Länge $r$ rekursiv wie folgt. Dabei ist $I$ die Indexmenge.

• Die Indexlistenliste für $I$ der Länge $0$ ist $(())$.
• Die Indexlistenliste für $I$ der Länge $r$ ergibt sich aus der

Indexlistenliste für $I$ der Länge $r-1$, indem jedes Element aus $I$ in jede Indexliste hinein gesteckt wird.

So entsteht beispielsweise aus $((1)(2)(3))$ die Indexlistenliste $((1\ 1)(1\ 2)(1\ 3)\; (2\ 1)(2\ 2)(2\ 3)\; (3\ 1)(3\ 2)(3\ 3))$, wobei $I=\{1,2,3\}$.

(define indexlistenliste (lambda (I r) (if (= r 0) '(()) (let ((ill (indexlistenliste I (- r 1)))) (do ([im I (cdr im)] [res '() (append res (map (lambda (il) (cons (car im) il)) ill))]) ((null? im) res))))))

Der folgende Aufruf gibt die Indexlistenliste für $\{1,2,3\}$ der Länge $2$ zurück.

(indexlistenliste '(1 2 3) 2)

ausführen

Offenbar besteht die Indexlistenliste aus $n^r$ Elementen, wenn $|I|=n$.

(length (indexlistenliste '(1 2 3 4) 5))

ausführen

Um auf das $i$-te Paar der Vorgabeliste direkt zugreifen zu können, ist es zweckmäßig, mit einem Vektor anstelle einer Liste für $K$ zu arbeiten:

(define K '(("1" . "101")("10" . "00")("011" . "11")))

gib_I ist eine Prozedur, die $K$ nimmt und $I$ zurückgibt.

(define gib_I (lambda (K) (do ([j (length K) (- j 1)] [res '() (cons j res)]) ((zero? j) res))))

(gib_I K)

ausführen

Wir schreiben eine Prozedur indexlistenwort, die eine Indexliste, eine Prozedur und die Vorgabeliste für $K$ erwartet. Die übergebene Prozedur ist entweder x-komp, nämlich dann, wenn das Wort $x_{i_1}\circ x_{i_2}\circ\ldots\circ x_{i_n}$, oder y-komp, wenn $y_{i_1}\circ y_{i_2}\circ\ldots\circ y_{i_n}$ bestimmt wird.

(define x-komp car) (define y-komp cdr) (define indexlistenwort (lambda (indexliste op K) (if (null? indexliste) "" (string-append (op (list-ref K (- (car indexliste) 1))) (indexlistenwort (cdr indexliste) op K)))))

Mit Bezug auf obiges Beispiel liefert sowohl

(indexlistenwort '(1 3 2 3) x-komp K)

ausführen

als auch

(indexlistenwort '(1 3 2 3) y-komp K)

ausführen

das Wort "101110011". $(1,3,2,3)$ ist also eine Lösung dieser Probleminstanz.

Die Prozedur PCP ist nun hinreichend vorbereitet. Sie nimmt die vorgegebene Paarliste und eine natürliche Zahl für die Länge der Indexlisten als Eingaben. Falls es für die jeweils aktuelle Länge eine Lösung gibt, wird sie ausgegeben und die Prozedur stoppt, wenn nicht, hält sie nicht an.

(define PCP (lambda (K) (letrec ((helfer (lambda (r) (let ((resultat (test (indexlistenliste (gib_I K) r)))) (if (null? resultat) (helfer (+ r 1)) resultat)))) (test (lambda (ill) (cond ((null? ill) '()) ((string=? (indexlistenwort (car ill) car K) ; wort-x (indexlistenwort (car ill) cdr K)) ; wort-y (car ill)) (else (test (cdr ill))))))) (helfer 1))))

Der Aufruf

(PCP K)

ausführen

mit dem oben angegebenen $K$ liefert (1 3 2 3).

Bestimmen Sie eine Lösung des PCP für folgende Instanz des Problems: $K=((0111,1),(0,001),(10,1))$.

(PCP '(("0111" . "1") ("0" . "001") ("10" . "1")))

ausführen

Erwartetes Ergebnis: (2 2 3 1)

Für $K=((001,0)(01,011),(01,101),(10,001))$ gibt es ebenfalls eine Lösung. Die gesuchte Indexfolge heißt (2 4 3 4 4 2 1 2 4 3 4 3 4 4 3 4 4 2 1 4 4 2 1 3 4 1 1 3 4 4 4 2 1 2 1 1 1 3 4 3 4 1 2 1 4 4 2 1 4 1 1 3 4 1 1 3 1 1 3 1 2 1 4 1 1 3). Überprüfen Sie die angegebene Lösung.

Wir fassen zusammen: Die Prozedur PCP findet eine Lösung, falls sie existiert. Anderenfalls stoppt PCP nicht. Dies ist charakteristisch für eine semi-entscheidbare bzw. aufzählbare Sprache.