\section{Das Postsche Korrespondenzproblem}
\inhalta{5-11}

\begin{frame}

\only<article>{
 Das folgende von Post formulierte Problem ($PCP$ = 
Post's Correspondence Problem)
 formuliert die folgende algorithmische Aufgabenstellung:} 
\only<presentation>{
 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<article>{
 Dass das $PCP$
 ein hohes Ma"s an Komplexität besitzt, zeigt das folgende harmlos 
 aussehende Beispiel aus dem Buch von Schöning: 
}
\only<presentation>{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<article>{ Dieses Problem besitzt eine Lösung, aber die kürzeste 
Lösung besteht aus 66 Indizes: } 
\only<presentation>{\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<article>{
 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<presentation>{
 $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<article>{
 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<presentation>{\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<article>{ 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<presentation>{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<article>{ Wir führen zunächst einige Notationen ein: Seien $\$$ und $\#$ neue Symbole, die im Alphabet $E$
 des $MPCP$s nicht vorkommen. }
\only<presentation>{
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<presentation>{
\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<article>{\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<presentation>{\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<n$: \pause  $i_1$, $i_2$,...,$i_m$ ist ebenfalls Lösung...\pause 
\item Daher o.B.d.A.: $i_m\neq k{+2}$ für $m<n$, \pause\\ dann auch $i_m\neq 1$ für $m<n$\pause 
\item Dann ist $(1, i_2 {-} 1,..., i_{n-1} {-}1)$ eine Lösung für $P$ \pause (d.h. bei $MPCP$)
\end{itemize}
\end{frame}}


\begin{frame}
\begin{lemma}\pause
$K$ ist reduzierbar auf $MPCP$.\label{MPCP}
\end{lemma}
\only<article>{
 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<presentation>{
\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<article>{\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<presentation>{\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<presentation>{
'$\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<article>{
 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}
