\begin{frame}{Modified Post Correspondence Problem}
  \begin{goal}{Theorem}
    The modified PCP is undecidable.
  \end{goal}
  \pause

  \begin{proof}
    $G=(V,T,S,P)$ any unrestricted grammar. Decide $w \in L(G)$?
    \pause\medskip
    
    We define (where $F$ and $E$ are fresh):
    \begin{talign}
      w_1 =\;\;\; &\alert{F} & v_1 =\;\;\; & \alert{FS\Rightarrow} \\[-.5ex]
      w_2 =\;\;\; &\alert{{\Rightarrow}\; wE} & v_2 =\;\;\; & \alert{E} \\[-1ex]
      \raisebox{-1mm}{$\vdots$} \quad\;\;\;\; &\alert{x} & \raisebox{-1mm}{$\vdots$} \quad\;\;\;\;& \alert{y} && \alert{(x \to y \in P)} \\
      &a && a && (a\in T) \\[-.5ex]
      &A && A && (A\in V) \\[-.5ex]
      &{\Rightarrow} &&{\Rightarrow} 
    \end{talign}
    This MPCP has a solution $\iff$ $w\in L(G)$.
    \pause\medskip
    
    \emph{Contradiction:} If the MPCP was decidable, then $w \in L(G)$ was decidable for unrestricted grammars $G$!
  \end{proof}
\end{frame}