Turing-Berechenbarkeit und Churchsche These

Merkwürdige aber berechenbare Funktionen

Collatz-Folge

Für alle Argumente undefinierte Funktion

Totale und partielle Funktionen

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

Das {\sc Post}sche Korrespondenzproblem (PCP)

Wir definieren eine Liste von Indexlisten, kurz: Indexlistenliste, der Länge r rekursiv wie folgt. Dabei ist I die Indexmenge. \begin{itemize} \item Die Indexlistenliste für I der Länge 0 ist \verb|(())|. \item Die Indexlistenliste für I der Länge r ergibt sich aus der Indexlistenliste für I der Länge r-1, indem {\em jedes} Element aus I in {\em jede} Indexliste hinein gesteckt wird. \end{itemize}

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

\begin{verbatim} (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))))))

\end{verbatim}

\verb|(indexlistenliste '(1 2 3) 2)| gibt die Indexlistenliste für \{1,2,3\} der Länge 2 zurück, nämlich \verb|((1 1) (1 2) (1 3) (2 1) (2 2) (2 3) (3 1) (3 2) (3 3))|.

Offenbar besteht die Indexlistenliste aus n^r Elementen, wenn \left| I\right|=n.

\Uea{Testen Sie \texttt{(length (indexlistenliste '(1 2 3 4) r))} für verschiedene r.}

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: \begin{verbatim} (define K (list->vector '(("1" . "101")("10" . "00")("011" . "11")))) \end{verbatim}

\verb|gib_I| ist eine Prozedur, die K -- als Vektor -- nimmt und I -- als Liste -- zurückgibt. \begin{verbatim} (define gib_I

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

\end{verbatim}

\Uea{Schreiben Sie eine Prozedur \texttt{indexlistenwort}, die eine Indexliste, eine Prozedur und die Vorgabeliste für K erwartet. Die Prozedur ist entweder \texttt{car}, nämlich dann, wenn das Wort $x_{i_1}\circ x_{i_2}\circ\ldots\circ x_{i_n}, oder \texttt{cdr}, wenn y_{i_1}\circ y_{i_2}\circ\ldots\circ y_{i_n}$ bestimmt wird.}

\begin{comment} (define indexlistenwort

 (lambda (indexliste op K)
   (if (null? indexliste)
     ""
     (string-append
       (op (vector-ref K (- (car indexliste) 1)))
      (indexlistenwort (cdr indexliste) op K)))))

\end{comment}

Mit Bezug auf obiges Beispiel liefert sowohl \verb|(indexlistenwort '(1 3 2 3) car K))| als auch \verb|(indexlistenwort '(1 3 2 3) cdr K))| das Wort \verb|"101110011"|. (1,3,2,3) ist also eine Lösung dieser Probleminstanz.

Die Prozedur \verb|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.

\begin{verbatim} (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))))

\end{verbatim}

Der Aufruf \verb|(PCP K)| mit dem oben angegebenen K liefert \verb|(1 3 2 3)|.

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

\begin{comment} > (PCP (list->vector '(("0111" . "1") ("0" . "001") ("10" . "1")))) (2 2 3 1) \end{comment}

\Uea{Für K=((001,0)(01,011),(01,101),(10,001)) gibt es 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. Hätten Sie dieses Ergebnis auch mit \texttt{PCP} finden können?}

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

Es muss allerdings noch gezeigt werden, dass die Menge der Indexlisten, die die PCP-Bedingung erfüllen, nicht entscheidbar ist. Die Angabe des obigen Algorithmus reicht dafür {\em nicht} aus!

Der Beweis wird geführt, indem man das Halteproblem auf das PCP reduziert. Die Technik der \emph{Problemreduktion} wird in Abschn.~\ref{sec:reduzierbarkeit} behandelt. Die Unentscheidbarkeit des PCP wird ihrerseits benutzt, um zu zeigen, dass auch andere Sprachen oder Probleme nicht entscheidbar sind. Beispielsweise kann man auf diese Art beweisen, dass man für beliebige kfG nicht allgemein entscheiden kann, ob sie mehrdeutig sind.