28/116
\begin{frame}{The Halting Problem is Undecidable (Proof 2)}\onslide<11>{}
\vspace{-.5ex}
\begin{goal}{}\vspace{-.5ex}
Assume there would be a program $T$ with the behaviour:
\begin{itemize}\setlength{\itemsep}{0pt}
\item input: a program $M$
\item output: \textit{yes} if $M$ terminates on input $M$, \textit{no} otherwise
\end{itemize}
\end{goal}
\pause

\begin{center}\vspace{-.25ex}
\begin{tikzpicture}[p/.style={rectangle,minimum width=37mm,fill=yellow!50!orange!20,draw=black,dashed,rounded corners=2mm,inner sep=2mm,align=left},scale=.95,nodes={scale=.95}]
\node (p) [p] {p = read input;\\[-.5ex]\hspace{1.1cm}\vdots\\[-.5ex]print result;};
\draw [decorate,decoration={brace,amplitude=10pt},xshift=-4pt,yshift=0pt]
($(p.south west) + (-2mm,0)$) to node [left,xshift=-3mm] {program $T$} ($(p.north west) + (-2mm,0)$);

\mpause[1]{
\node (p')  at (p.south) [p,anchor=north] {\dm{if} result = yes\\\dm{then}\;\, loop forever\\\dm{else}\;\; terminate};

\draw [decorate,decoration={brace,amplitude=10pt},xshift=-4pt,yshift=0pt]
($(p.north east) + (2mm,0)$) to node [right,xshift=3mm] {program $T'$} ($(p'.south east) + (2mm,0)$);
}
\end{tikzpicture}
\end{center}\vspace{-1.2ex}
\pause\pause

\begin{goal}{}\vspace{-.5ex}
What happens if we run $T'$ with input $T'$?
\begin{itemize}\setlength{\itemsep}{0pt}
\pause
\item initial part $T$ decides whether $T'$ terminates on input $T'$
\pause
\item if the result is \alert{yes}, then $T'$ runs forever\pause{} $\,$ \alert{Contradiction}
\pause
\item if the result is \alert{no}, then $T'$ terminates\pause{} $\,$ \alert{Contradiction}
\end{itemize}
\end{goal}
\pause
\vspace{-.5ex}
Thus $T$ cannot exist!\pause{} The halting problem is undecidable!