\section{Das Postsche Korrespondenzproblem} \inhalta{5-11} \begin{frame} \only
{ Das folgende von Post formulierte Problem ($PCP$ = Post's Correspondence Problem) formuliert die folgende algorithmische Aufgabenstellung:} \only{ Betrachte $PCP$ = \Fb{Post's Correspondence Problem}:\pause} \begin{itemize} \item Eingabe: eine endliche Folge von Wortpaaren \[(x_1, y_1), ~~(x_2, y_2),...,~~(x_k,y_k)\] \pause wobei $k \geq 1$ und $x_i, y_i\in E^+$ seien, (also $x_i,y_i\neq \varepsilon$).\pause \item Frage: gibt es eine Folge $\cal I$ von Indizes $i_1$,..., $i_n$ aus $\{1, 2,..., k\}$ mit $n\geq 1$ \pause und mit $$x_{i_1}...x_{i_n}= y_{i_1}...y_{i_n}$$ \end{itemize} \pause Eine derartige Folge $\cal I$ nennt man \\ \emph{Lösung} des Korrespondenzproblems $(x_1, y_1)$, $(x_2, y_2)$,..., $(x_k,y_k)$.\pause \begin{example} \[\begin{array}{|c|c|c|} \hline i & x_i & y_i \\ \hline 1 & bab & a \\ \hline 2 & ab & abb \\ \hline 3 & a & ba \\ \hline \end{array}\] \pause Bei der Indexfolge ${\cal I}=(2, 1, 3)$ ergibt sich \pause $ab~bab~a \pause= abb\pause~a\pause~ba$. \end{example} \end{frame} \begin{frame} \begin{cont}{} \only
{ Dass das $PCP$ ein hohes Ma"s an Komplexität besitzt, zeigt das folgende harmlos aussehende Beispiel aus dem Buch von Schöning: } \only{Weiteres Beispiel, Schöning \cite{Sch01}:} \[\begin{array}{|c|c|c|} \hline i & x_i & y_i \\ \hline 1 & 001 & 0 \\ \hline 2 & 01 & 011 \\ \hline 3 & 01 & 101 \\ \hline 4 & 10 & 001 \\ \hline \end{array}\] \only
{ Dieses Problem besitzt eine Lösung, aber die kürzeste Lösung besteht aus 66 Indizes: } \only{\pause Kürzeste Lösung: \[\begin{array}{l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l@{}l} 0&1|&1&0|&0&1|&1&0|&1&0|&0&1|&0&0&1|&0&1|&1&0|&0&1|&1&0|&&&&&&&&...&001|001|01 \\ 0&1&1|&0&0&1|&1&0&1|&0&0&1|&0&0&1|&0&1&1|&0|&0&1&1|&0&0&1|&1&0&1| 0&0&1|&...&0|0|101\end{array}\] \pause mit 66 Indizes:} \[\begin{tabular}{l} $ 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$. \end{tabular}\] \end{cont} \end{frame}\begin{frame} \begin{remark} \only
{ Die naive Vorgehensweise, die bei gegebener Eingabe $(x_1, y_1)$, $(x_2, y_2)$,..., $(x_k,y_k)$ systematisch durch Probieren immer längere Indexfolgen $i_1,i_2,...$ daraufhin untersucht, ob sie eine Lösung darstellen und im positiven Fall stoppt, zeigt, dass das $PCP$ semi-entscheidbar (oder rekursiv aufzählbar) ist: Es gibt ein Verfahren, das bei Eingaben, die eine Lösung besitzen, diese nach endlich vielen Schritten findet und stoppt. Bei Eingaben, die keine Lösung besitzen, stoppt das Verfahren jedoch nicht. } \only{ $PCP$ ist semi-entscheidbar \pause (durch einfache Suche nach einer Lösung):\pause \begin{itemize} \item Eingabe sei $(x_1, y_1)$, $(x_2, y_2)$,..., $(x_k,y_k)$\pause \item Für alle Längen $n=1,2,3,...$ \pause\\ und alle Indexfolgen $i_1,i_2,...,i_n$ der Länge $n$:\pause \\ ~~~~teste, ob $x_{i_1}...x_{i_n}\stackrel{?}{=} y_{i_1}...y_{i_n}$ \\ \pause ~~~~Wenn ja, akzeptiere die Eingabe! \end{itemize} } \end{remark} \only
{ Wir zeigen im Folgenden, dass das $PCP$ unentscheidbar ist, d.h. dass es keinen Algorithmus gibt, der bei Eingabe einer nichtleeren Folge von Paaren nichtleerer Wörter nach endlich vielen Rechenschritten entscheidet, ob das durch die Folge gegebene Korrespondenzproblem eine Lösung hat oder nicht. Wir werden also zeigen, dass die Menge } \only{\pause Jetzt: $PCP$ ist unentscheidbar, \pause genauer: Die Menge} \GLA PCP &=& \{((x_1, y_1), (x_2, y_2),..., (x_k,y_k)) \mid \\&&~~~~~~~~~ k \in \nz, x_i,y_i\in E^+ \textrm{ für }i= 1,\ldots, k,\textrm{ und }\\ &&~~~~~~~\left((x_1, y_1), (x_2, y_2),..., (x_k,y_k)\right)\textrm{ hat eine Lösung}\}\GLE \only
{ eine unentscheidbare Menge ist. Wir machen dazu Gebrauch von der Idee der Reduktion und unserem Wissen, dass das Selbstanwendbarkeitsproblem $K$ unentscheidbar ist. Wir reduzieren zunächst $K$ auf ein anderes Problem, genannt $MPCP$ (`modifiziertes $PCP$'), und dann $MPCP$ auf $PCP$. } \only{ist nicht entscheidbar, \pause mit Beweisweg: \pause (1) Selbstanwendbarkeitsproblem $K$ ist reduzierbar auf \pause $MPCP$ \pause(`modifiziertes $PCP$') \pause (2) $MPCP$ ist reduzierbar auf $PCP$ } \end{frame} \begin{frame} Das Problem $MPCP$ ist definiert wie folgt:\pause \begin{itemize} \item Eingabe: \pause wie beim Problem $PCP$. \pause \item Frage: gibt es eine Lösung $i_1$, $i_2$,...,$i_n$ des $PCP$ \pause \Fb{mit $i_1 = 1$}? \end{itemize} \pause \begin{lemma} Das Problem $MPCP$ ist auf $PCP$ reduzierbar.\label{PCP} \end{lemma} \pause Beweis: \pause \only
{ Wir führen zunächst einige Notationen ein: Seien $\$$ und $\#$ neue Symbole, die im Alphabet $E$ des $MPCP$s nicht vorkommen. } \only{ Verwende neue Symbole $\$$ und $\#$, die im Alphabet $E$ des $MPCP$s nicht vorkommen. \pause } Für ein Wort $w= a_1a_2...a_m$ aus $E^+$ sei\pause \GLA w^a &:=& \#a_l\#a_2\#...\#a_m\#\\ \pause w^b&\pause :=& \pause ~~~a_1\#a_2\#...\#a_m\# \\ \pause w^c&\pause :=&\pause \#a_1\#a_2\#...\#a_m \GLE \only{ \pause Definiere Reduktion $f$ von $MPCP$ auf $PCP$ wie folgt:\pause \[\begin{array}{@{}lrlr@{}l@{}l@{}l@{}l@{}}\textrm{ zu } &P &=& (&(x_1, y_1),& (x_2, y_2),&...,& (x_k,y_k))\\ \pause\textrm{ setze }&\pause f(P) &\pause := &\pause((x_1^a, y_1^c),&\pause(x_1^b, y_1^c), &\pause(x_2^b, y_2^c),&\pause...,& \pause(x_k^b, y_k^c),\pause (\$,\#\$)) \end{array}\] } \end{frame} \only
{\begin{frame} Jeder Eingabe von $k$ Paaren $P = ((x_1, y_1)$, $(x_2, y_2)$,..., $(x_k,y_k))$ für das $MPCP$ wird nun die folgende Eingabe von $k{+}2$ Paaren zugeordnet: \[f(P) = ((x_1^a, y_1^c), (x_1^b, y_1^c), (x_2^b, y_2^c),..., (x_k^b, y_k^c), (\$,\#\$))\] Diese Abbildung $f $ ist offensichtlich berechenbar, da sie im Prinzip nur die Eingabe leicht abändert. Wir zeigen nun, dass diese Funktion $f$ eine Reduktion von $MPCP$ nach $PCP$ ist. Dazu müssen wir zeigen: \GLA &&P\textrm{ besitzt eine Lösung mit }i_1 = 1\\ &\Longleftrightarrow& f(P)\textrm{ besitzt (irgend)eine Lösung}\GLE Beweis von '$\Longrightarrow$': \pause\\ $P$ besitze eine Lösung $i_1$, $i_2$,...,$i_n$ \pause mit $i_1 = 1$ ($MPCP$!). \pause Dann ist $(1, i_2 {+} 1,..., i_n {+} 1, k {+} 2)$ eine Lösung für $f(P)$. \pause Beweis von '$\Longleftarrow$': \pause\\ $f(P)$ besitze eine Lösung $i_1$, $i_2$,...,$i_n$ \pause aus $\{1,..., k{+} 2\}$. Dann kann wegen der Bauart der Wortpaare nur $i_1 = 1$ und $i_n = k{+} 2$ sein. Wenn keine echte Anfangsteilfolge der Lösung ebenfalls Lösung ist (in dem Fall betrachten wir die kürzeste Anfangsteilfolge, die Lösung ist), muss au"serdem $i_j$ aus $\{2,...,k{+} l\}$ für $2\leq j\leq n- 1$ sein. In diesem Fall ist $(1, i_2 {-} 1,..., i_{n-1} {-}1)$ eine Lösung für $P$. \end{frame}} \only{\begin{frame} \begin{itemize} \item \pause $f$ ist offensichtlich berechenbar \pause \item Zeige: \GLA &&P\textrm{ besitzt eine Lösung mit }i_1 = 1 \pause\textrm{, d.h. }P\in MPCP\\ & \pause\Longleftrightarrow& \pause f(P)\textrm{ besitzt (irgend)eine Lösung}\pause\textrm{, d.h. }f(P)\in PCP \GLE \end{itemize} \pause Beweis von '$\Longrightarrow$': \pause\\ $P$ besitze eine Lösung $i_1$, $i_2$,...,$i_n$ \pause mit $i_1 = 1$ ($MPCP$!). \pause Dann ist $(1, i_2 {+} 1,..., i_n {+} 1, k {+} 2)$ eine Lösung für $f(P)$. \pause Beweis von '$\Longleftarrow$': \pause\\ $f(P)$ besitze eine Lösung $i_1$, $i_2$,...,$i_n$ \pause aus $\{1,..., k{+} 2\}$. \pause \begin{itemize} \item Aufbau der Wortpaare in $f(P)$: \pause nur $i_1 = 1$ und $i_n = k{+} 2$ möglich\pause \item Falls $i_m=k{+2}$ für ein $m{ Beweis: Wir müssen eine totale berechenbare Funktion angeben, die jedes Wort $w$ (für die Codierung einer Turingmaschine $M_w$ und gleichzeitig als Eingabewort $w\in E^*$ für $M_w$) überführt in eine Folge $(x_1, y_1)$, $(x_2, y_2)$,..., $(x_k,y_k)$ von Wortpaaren (die die Voraussetzungen des $PCP $ erfüllt), so dass gilt: (*) $M_w$ angesetzt auf $w $ hält genau dann nach endlich vielen Schritten an, wenn $(x_1, y_1), (x_2, y_2),..., (x_k,y_k)$ eine Lösung mit $i_1 = 1$ besitzt. Sei $w$ gegeben und $M_w= (S, E, A, \delta, s_0,\Box, F)$. Das Alphabet für das zu konstruierende $MPCP$ wird $A\cup S \cup \{\#\}$ sein; das erste Wortpaar soll $(\#, \#\Box s_0w\Box \#)$ sein. Die uns interessierenden Lösungswörter müssen also mit diesem Paar beginnen. } \only{ \pause Gesucht also: totale berechenbare Funktion $f$ mit $f(w)=P$, \pause wobei \begin{itemize} \item $w$ eine Turingmaschine $M_w$ \pause und ein Eingabewort $w$ für $M_w$ darstellt, \pause und \item $P=((x_1, y_1),(x_2, y_2),...,(x_k,y_k))$ eine Probleminstanz passend zum $MPCP$ ist, \end{itemize} \pause so dass gilt: \pause \begin{itemize} \item[$(*)$] $M_w$ angesetzt auf $w $ \pause hält nach endlich vielen Schritten an, \pause\\$\Longleftrightarrow$ \\ $P=((x_1, y_1), (x_2, y_2),..., (x_k,y_k))$ besitzt Lösung (mit $i_1 = 1$). \end{itemize} \pause Sei $w$ gegeben \pause und $M_w= (S, E, A, \delta, s_0,\Box, F)$.\pause \begin{itemize} \item Nutze $A\cup S \cup \{\#\}$ als Alphabet für das $MPCP$\pause \item Erstes Wortpaar sei $(\#, \#\Box s_0w\Box\#)$ \end{itemize} \pause$\Rightarrow$ jede Lösung muss mit diesem Paar beginnen! } \end{frame} \begin{frame} Die weiteren Paare werden wie folgt konstruiert: \pause 1. \emph{Kopierregeln}: \pause $(a, a)$ für alle $a\in A\cup \{\#\}$ \pause 2. \emph{\"Uberführungsregeln}: \pause Für alle \"Ubergänge der Turingmaschine $M_w$:\pause \begin{tabular}{ll} $(sa, s'c)$ &falls $\delta(s, a) = (s', c, N)$\\ \pause $(sa, cs')$ &\pause falls $\delta(s, a) = (s', c, R)$\\ \pause $(bsa, s'bc)$ &\pause falls $\delta (s, a) = (s', c, L)$, für alle $b$ aus $A$ \\[1ex] \pause$(\#sa,\#s'\Box c)$ &\pause falls $\delta(s, a) = (s', c, L)$\\ \pause $(s\#, s'c\#)$ &\pause falls $\delta(s,\Box) = (s', c, N)$\\ \pause $(s\#, cs'\#)$ &\pause falls $\delta(s,\Box) = (s', c, R)$\\ \pause $(bs\#, s'bc\#)$ &\pause falls $\delta(s,\Box)= (s', c, L)$, für alle $b$ aus $A$ \end{tabular} \pause 3. \emph{Löschregeln}: \pause $(as_f, s_f)$ und $(s_f a, s_f)$ für alle $a\in A$ und $s_f\in F$.\pause 4. \emph{Abschlussregeln}: \pause $(s_f\#\#, \#)$ für alle $s_f\in F$. \end{frame} \only
{\begin{frame} Wir halten zuerst fest, dass die Funktion, die jedem $w$ wie oben angegeben, eine derartige Folge von Wortpaaren zuordnet, sicher berechenbar ist. Jetzt müssen wir noch zeigen, dass sie auch die Bedingung (*) erfüllt. Falls die Turingmaschine $M_w$ bei Eingabe $w$ stoppt, so gibt es eine Folge von Konfigurationen $(k_0, k_1,...,k_t)$, so dass gilt: $k_0 = \Box s_0w\Box$, $k_t$ ist eine Endkonfiguration (also $k_t = us_fv$ mit $u,v\in A^*$ und $s_f\in F$), und $k_i\vdash k_{i+1} $ für $i= 0,..., t{-}1$. Die oben angegebene Eingabe für das $MPCP$ besitzt dann eine Lösung mit einem Lösungswort der Form \[\# k_0 \# k_1 \# ... \# k_t\# k_t'\# k_t'' \# ... \# s_f\#\#\] Hierbei entstehen $k_t', k''_t,... $ aus $k_t = us_f v$ durch Löschen von Nachbarsymbolen von $s_f$. Der erste Teil der Lösung baut sich so auf, dass die Folge der $x_{ij}$ eine Konfiguration hinter der Folge der $y_{ij}$ `hinterherhinkt'. Der `\"Uberhang' hat also immer die Länge einer Konfiguration, skizzierbar wie folgt: \[\begin{array}{cl@{~}c@{~}c@{~}cc@{~}c@{~}c@{~}cc@{~}r} x:&\# &k_0 \# &k_1\# &k_2\# &...&k_t\#&k'_t\#&k''_t\#&...&s_f\#\#\\ y:&\#k_0 \# &k_1 \# &k_2\# &...&k_t\#&k'_t\#&k''_t\#&...& s_f\#&\# \end{array}\] Falls umgekehrt die obige Eingabe für das $MPCP$ eine Lösung (mit $i_1=1$) besitzt, so lässt sich aus dieser Lösung in ähnlicher Weise eine stoppende Rechnung der Turingmaschine $M_w$ bei Eingabe $w$ ablesen. Damit ist gezeigt, da"s die Abbildung, die $w$, wie oben angegeben, eine Eingabe für das $MPCP$ zuordnet, eine Reduktion von $K $ nach $MPCP$ vermittelt. Unter Ausnützen der Tatsache, dass $K $ unentscheidbar ist (Satz \ref{Halteproblem}) und wegen Satz \ref{Reduktion} über die Reduktion erhält man wegen Lemma \ref{MPCP}, dass $MPCP $ unentscheidbar ist, und dann wegen Lemma \ref{PCP}, dass auch $PCP $ unentscheidbar ist. \end{frame}} \only{\begin{frame} \begin{itemize} \item $f: w\mapsto P$ mit o.a. Paaren $P$ ist berechenbar\pause \item Zeige noch: Bedingung $(*)$ ist erfüllt. \end{itemize} \pause '$\Longrightarrow$', $M_w$ stoppt bei Eingabe $w$:\pause\\ Dann gibt es eine Folge von Konfigurationen $(k_0, k_1,...,k_t)$ mit \pause \begin{itemize} \item$k_0 = \Box s_0w\Box$ \pause (Zusätzliche $\Box$ stören nicht...)\pause \item $k_t$ ist Endkonfiguration \pause (also $k_t = us_fv$ \pause mit $u,v\in A^*, s_f\in F$)\pause \item $k_i\vdash k_{i+1} $ für $i= 0,..., t{-}1$. \end{itemize} \pause $P$ besitzt dann eine Lösung für das $MPCP$ der Form: \pause \[\begin{array}{cl@{~}c@{~}c@{~}cc@{~}c@{~}c@{~}cc@{~}r} x:&\# &k_0 \# &k_1\# &k_2\# &...&k_t\#&k'_t\#&k''_t\#&...&s_f\#\#\\ y:&\#k_0 \# &k_1 \# &k_2\# &...&k_t\#&k'_t\#&k''_t\#&...& s_f\#&\# \end{array}\] \begin{itemize} \item \pause Folge $x_{{i_1}}...x_{{i_j}}$ liegt eine Konfiguration hinter den $y_{{i_1}}...y_{{i_j}}$ zurück.\pause \item $k_t', k''_t,... $ entstehen aus $k_t = us_f v$ durch Löschen um $s_f$ herum \end{itemize} \end{frame}} \begin{frame} \only{ '$\Longleftarrow$', $P$ hat eine Lösung (mit $i_1=1$):\pause\\ \begin{itemize} \item Lösungswort ist durch $\#$ in Konfigurationen $k_0,k_1,...k_t$ unterteilt\pause \item Wegen Start mit $i_1=1$: \pause $k_0= \Box s_0w\Box$\pause \item Nach Konstruktion: $k_i\vdash k_{i+1}$ \pause oder $k_i$ ist Endkonfiguration \end{itemize} \pause Also hält $M_w$ auf Eingabe $w$.\pause Insgesamt: \pause\begin{itemize} \item $K$ ist auf $MPCP$ reduzierbar\pause \item $K$ ist nicht entscheidbar, \pause also auch $MPCP$ nicht entscheidbar\pause \item $MPCP$ ist auf $PCP$ reduzierbar, \pause also auch $PCP$ nicht entscheidbar \end{itemize} } \pause \begin{theorem}\pause Das Postsche Korrespondenzproblem $PCP$ ist unentscheidbar. \end{theorem} \end{frame} \begin{frame} \only
{ Sogar der folgende spezielle Fall ist unentscheidbar: } \begin{theorem}\pause Das $PCP$ ist bereits dann nicht entscheidbar, \pause wenn man sich auf das Alphabet $\{0, 1\}$ beschränkt. \pause Diese Problemvariante heißt $01{-}PCP$. \end{theorem} \pause Zum Beweis zeige, dass $PCP$ auf $01{-}PCP$ reduzierbar ist:\pause Sei $E=\{a_1,...,a_m\}$ das Alphabet des gegebenen $PCP$s.\pause \\ Jedem Symbol $a_j\in E$ ordne das Wort $a_j' = 01^j\in\{0, 1\}^*$ zu; \pause\\ verallgemeinere dies auf beliebige Wörter \pause $$ w = a_1...a_n\in E^+~~~\mapsto~~~ w' = a_1'...a_n'\in\{0, 1\}^*$$ \pause Dann gilt offensichtlich: \GLA &&(x_1, y_1),..., (x_k, y_k)\textrm{ hat eine Lösung } \\&\pause\Longleftrightarrow& \pause (x_1', y_1'),..., (x_k', y_k')\textrm{ hat eine Lösung } \GLE \end{frame}