\begin{frame}{Post Correspondence Problem}
  \begin{goal}{Theorem}
    The PCP is undecidable.
  \end{goal}
  \pause\medskip
  
  \begin{proof}
    Given an MPCP $X$: \alert{$(w_1,v_1),\ldots,(w_n,v_n)$} where
    \begin{salign}
      w_i = a_{i1}\cdots a_{im_i} &&\text{and}&& v_i=b_{i1}\cdots b_{ir_i} && (\text{with } m_i+r_i>0)
    \end{salign}
    \pause
    We define PCP $X'$ \alert{$(y_0,z_0),\ldots,(y_{n+1},z_{n+1})$} by:
    \begin{salign}
      \alert{y_0} &= @ \$y_1 &
      \alert{y_i} &= a_{i1}\$a_{i2}\$\cdots a_{im_i}\$ &
      \alert{y_{n+1}} &= \# \\
      \alert{z_0} &= @ z_1 &
      \alert{z_i} &= \$b_{i1}\$b_{i2}\cdots \$b_{ir_i} &
      \alert{z_{n+1}} &= \$\#
    \end{salign}
    for $1 \leq i \leq n$.
    The letters $@$, $\$$ and $\#$ are fresh.
    \pause\medskip
    
    Every PCP $X'$ solution must start with $(y_0,z_0)$:
    \begin{salign}
      \alert{y_0} y_j \cdots y_k \alert{y_{n+1}} = \alert{z_0} z_j \cdots z_k \alert{z_{n+1}} 
    \end{salign}
    \pause
    Solution exists $\iff$ $\alert{w_1} w_j \cdots w_k = \alert{v_1} v_j \cdots v_k$ is a solution of $X$.
    \pause\medskip
    
    As the MPCP is undecidable, so must be the PCP.
  \end{proof}
\end{frame}