Berechenbarkeitstheorie/Turing-Berechenbarkeit und Churchsche These

Wiki-Quelltext dieser Seite.

<language>Scheme</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 {\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.