Berechenbarkeitstheorie/Turing-Berechenbarkeit und Churchsche These

Wiki-Quelltext dieser Seite.

<language>SchemeJS</language>
==Merkwürdige aber berechenbare Funktionen==

===Collatz-Folge===

<code id="4f8a79406ab06" hidden>
(define collatz
  (lambda (n)
    (cond
      ((= n 1) '(1))
      ((even? n) (cons n (collatz (/ n 2))))
      (else
       (cons n (collatz (+ (* 3 n) 1)))))))
</code>

<run id="4f8a79406abff">(collatz 7)</run>

===Für alle Argumente undefinierte Funktion===

<code id="4f8a79406ab82" hidden>
(define nirgends_definiert
  (lambda (n)
    (nirgends_definiert n)))
</code>

<run id="4f8a79406ac79">(nirgends_definiert 12)</run>

===Totale und partielle Funktionen===

<code id="4f8aa015dc19d" hidden>
(define nicht_fuer_alle
  (lambda (n)
    (if (< n 3)
       1
       (nirgends_definiert 10))))
</code>

<run id="4f8aa015dc26f">(nicht_fuer_alle 2)</run>

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\}$.

<code id="4f8aaf2a80e56" hidden>
(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))))))
</code>

Der folgende Aufruf gibt die Indexlistenliste für $\{1,2,3\}$ der Länge $2$ zurück.
<run id="4f8aaf2a813b5">(indexlistenliste '(1 2 3) 2)</run>


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

<run id="4f8aaf2a81489">(length (indexlistenliste '(1 2 3 4) 5))</run>

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:
<code id="4f8aaf2a80f52">
(define K '(("1" . "101")("10" . "00")("011" . "11")))
</code>

<tt>gib_I</tt> ist eine Prozedur, die $K$ nimmt und $I$ zurückgibt.
<code id="4f8bb0ba87177" hidden>
(define gib_I
  (lambda (K)
    (do ([j (length K) (- j 1)]
     [res '() (cons j res)])
    ((zero? j) res))))
</code>
<run id="4f8bb0ba872ab">(gib_I K)</run>

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

<code id="4f8aaf2a8125d" hidden>
(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)))))
</code>

Mit Bezug auf obiges Beispiel liefert sowohl 
<run id="4f8aaf2a81518">(indexlistenwort '(1 3 2 3) x-komp K)</run> 
als auch
<run id="4f8aaf2a81639">(indexlistenwort '(1 3 2 3) y-komp K)</run> 
das Wort <tt>"101110011"</tt>. $(1,3,2,3)$ ist also eine Lösung dieser Probleminstanz.

Die Prozedur <tt>PCP</tt> 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.

<code id="4f8aaf2a812e0" hidden>
(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))))
</code>

Der Aufruf 
<run id="4f8aaf2a81743">(PCP K)</run> 
mit dem oben angegebenen $K$ liefert <tt>(1 3 2 3)</tt>.

Bestimmen Sie eine Lösung des PCP für folgende Instanz des Problems: $K=((0111,1),(0,001),(10,1))$.
<run id="4f8aaf2a817b3">(PCP '(("0111" . "1") ("0" . "001") ("10" . "1")))</run>
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 <tt>PCP</tt> findet eine Lösung, falls sie existiert. Anderenfalls stoppt <tt>PCP</tt>
nicht. Dies ist charakteristisch für eine semi-entscheidbare bzw. aufzählbare Sprache.