% !TEX program = xelatex
\documentclass[dvipsnames,14pt,t]{beamer}
\usepackage{../slides}
\usepackage{../langs}
\usepackage{../data}
\usepackage{../graphics}
\usepackage{soul}

\tikzset{onslide/.code args={<#1>#2}{%
  \only<#1>{\pgfkeysalso{#2}} % \pgfkeysalso doesn't change the path
}}

\makeatletter
\newenvironment<>{btHighlight}[1][]
{\begin{onlyenv}#2\begingroup\tikzset{bt@Highlight@par/.style={#1}}\begin{lrbox}{\@tempboxa}}
{\end{lrbox}\bt@HL@box[bt@Highlight@par]{\@tempboxa}\endgroup\end{onlyenv}}

\newcommand<>\btHL[1][]{%
  \only#2{\begin{btHighlight}[#1]\bgroup\aftergroup\bt@HL@endenv}%
}
\def\bt@HL@endenv{%
  \end{btHighlight}%   
  \egroup
}
\newcommand{\bt@HL@box}[2][]{%
  \tikz[#1]{%
    \pgfpathrectangle{\pgfpoint{1pt}{0pt}}{\pgfpoint{\wd #2}{\ht #2}}%
    \pgfusepath{use as bounding box}%
    \node[anchor=base west, fill=orange!30,outer sep=0pt,inner xsep=1pt, inner ysep=0pt, rounded corners=3pt, minimum height=\ht\strutbox+1pt,#1]{\raisebox{1pt}{\strut}\strut\usebox{#2}};
  }%
}
\makeatother


% beamer stuff
\renewcommand{\slidecaption}{CFL 10, King's College London}
\newcommand{\bl}[1]{\textcolor{blue}{#1}}       


\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{%
  \begin{tabular}{@ {}c@ {}}
  \\[-3mm]
  \LARGE Compilers and \\[-2mm] 
  \LARGE Formal Languages (10)\\[3mm] 
  \end{tabular}}

  \normalsize
  \begin{center}
  \begin{tabular}{ll}
    Email:  & christian.urban at kcl.ac.uk\\
    Office Hours: & Thursdays 12 -- 14\\
    Location: & N7.07 (North Wing, Bush House)\\
    Slides \& Progs: & KEATS (also homework is there)\\  
  \end{tabular}
  \end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
\begin{frame}[c,fragile]


\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-6mm]
def fact(n: Int) : Int = {
  if (n == 0) 1 else n * fact(n - 1) 
}


def factC(n: Int, ret: Int => Int) : Int = {
  if (n == 0) ret(1) 
  else factC(n - 1, x => ret(n * x)) 
}

fact(10)
factC(10, identity)
\end{lstlisting}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
\begin{frame}[c,fragile]


\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-6mm]
def fibC(n: Int, ret: Int => Int) : Int = {
  if (n == 0 || n == 1) ret(1) else
  fibC(n - 1,
       r1 => fibC(n - 2,
        r2 => ret(r1 + r2)))
}

fibC(10, identity)
\end{lstlisting}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]

  \Large\bf Are there more strings in \\ \hfill\bl{$L(a^*)$} or
  \bl{$L((a + b)^*)$}?

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Can you remember this HW?}

  \begin{itemize}
  \item (1) How many basic regular expressions are there to match
      the string \bl{$abcd$}? 
  \item (2) How many if they cannot include
      \bl{$\ONE$} and \bl{$\ZERO$}? 
  \item (3) How many if they are also not
      allowed to contain stars? 
  \item (4) How many if they are also
      not allowed to contain \bl{$\_ + \_$}?
   \end{itemize}  

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]

\Large\bf There are more problems, than there are
programs.\bigskip\bigskip\pause\\

There must be a problem for which there is no program.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Subsets}

\Large
If \bl{$A \subseteq B$} then \bl{$A$} has fewer or equal elements 
than \bl{$B$}\bigskip\bigskip

\Large
\bl{$A \subseteq B$} and \bl{$B \subseteq A$}\bigskip

then \bl{$A = B$}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \begin{frame}[c]
  
  \begin{center}
  \begin{tikzpicture}
  
  \draw (-4,2.5) node [scale=2.5] (X) 
    {\begin{tabular}{l}
     $\{$  
     \!\includegraphics[scale=0.02]{../pics/o1.jpg},
     \includegraphics[scale=0.02]{../pics/o2.jpg},
     \!\includegraphics[scale=0.02]{../pics/o3.jpg},
     \includegraphics[scale=0.02]{../pics/o4.jpg},
     \!\includegraphics[scale=0.027]{../pics/o5.jpg}
     $\}$
    \end{tabular}};
    
    \draw (-5.6,-2.5) node [scale=2.5] (Y) 
    {\begin{tabular}{l}
     $\{$  
     \!\includegraphics[scale=0.059]{../pics/a1.jpg},
     \includegraphics[scale=0.048]{../pics/a2.jpg},
     \includegraphics[scale=0.02]{../pics/a3.jpg}
     $\}$
    \end{tabular}};
    
     \draw (0,1.5) node (X1) {5 elements};
     \draw (0,-3.5) node (y1) {3 elements};
  \end{tikzpicture}
  \end{center}

  \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \begin{frame}[c]
  \frametitle{Newton vs Feynman}
  
  \begin{center}
  \begin{tabular}{cc}
  \includegraphics[scale=0.2]{../pics/newton.jpg} &
  \includegraphics[scale=0.2]{../pics/feynman.jpg}\\
  classical physics & quantum physics
  \end{tabular}
  \end{center}
  \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \begin{frame}[c]
  \frametitle{The Goal of the Talk}
 \large
  \begin{itemize}
  \item show you that something very unintuitive happens with very large sets	
  \bigskip\bigskip
  
  \item convince you that there are more {\bf problems} than {\bf programs}
  \end{itemize}	
  \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
%
  \begin{center}
  \begin{tikzpicture}
 
  \draw (-5,2.5) node [scale=2.3] (X) 
    {\begin{tabular}{@ {\hspace{-3mm}}l}
     \bl{$B$ $=$ $\{$  
     \!\includegraphics[scale=0.02]{../pics/o1.jpg},
     \includegraphics[scale=0.02]{../pics/o2.jpg},
     \!\includegraphics[scale=0.02]{../pics/o3.jpg},
     \includegraphics[scale=0.02]{../pics/o4.jpg},
     \!\includegraphics[scale=0.027]{../pics/o5.jpg}
     $\}$}
    \end{tabular}};
    
    \draw (-6.6,-0.5) node [scale=2.3] (Y) 
    {\begin{tabular}{@ {\hspace{-3mm}}l}
     \bl{$A$ $=$ $\{$  
     \!\includegraphics[scale=0.059]{../pics/a1.jpg},
     \includegraphics[scale=0.048]{../pics/a2.jpg},
     \includegraphics[scale=0.02]{../pics/a3.jpg}
     $\}$}
     \end{tabular}};
  
     \only<1>{\draw (-5, -3) node[scale=2] 
       {\bl{$|A|$ $=$ $5$}, \bl{$|B|$ $=$ $3$}};}
     \only<2>{
       \draw [->, line width=1mm, red] (-7.4, 0.2) -- (-6.1, 2.1);
       \draw [->, line width=1mm, red] (-5.8, 0.2) -- (-3.1, 2.1);
       \draw [->, line width=1mm, red] (-4.5, 0.2) -- (-7.6, 2.1);
       \draw (-5, -3) node[scale=2] {then \bl{$|A|$ $\le$ $|B|$}};
       }
    \only<3>{
       \draw [<-, line width=1mm, red] (-7.5, 0.2) -- (-6.1, 2.1);
       \draw [<-, line width=1mm, red] (-7.3, 0.2) -- (-3.1, 2.1);
       \draw [<-, line width=1mm, red] (-6, 0.2) -- (-7.5, 2.1);
       \draw [<-, line width=1mm, red] (-4.5, 0.2) -- (-4.5, 2.1);
       \draw [<-, line width=1mm, red] (-4.3, 0.2) -- (-1.3, 2.1);
       
       \draw (-5, -3) node[scale=1.5] {\small{}for \bl{$=$}
        has to be a {\bf one-to-one} mapping};
       }

    
  \end{tikzpicture}
  \end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Cardinality}

\Large
\bl{$|A|$} $\dn$ ``how many elements''\bigskip\\

\bl{$A \subseteq B  \Rightarrow |A| \leq |B|$}\bigskip\\\pause

if there is an injective function \bl{$f: A \rightarrow B$} then \bl{$|A| \leq |B|$}\

\begin{center}
\bl{\large$\forall x y.\; f(x) = f(y) \Rightarrow x = y$}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]

  \begin{center}
  \begin{tikzpicture}
  
  \draw (-6.6,2.5) node [scale=2.3] (X) 
    {\begin{tabular}{@ {\hspace{-3mm}}l}
     $A$ $=$ $\{$  
     \!\includegraphics[scale=0.02]{../pics/o1.jpg},
     \includegraphics[scale=0.02]{../pics/o2.jpg},
     \!\includegraphics[scale=0.02]{../pics/o3.jpg}
     $\}$
    \end{tabular}};
    
    \draw (-6.6,-0.5) node [scale=2.3] (Y) 
    {\begin{tabular}{@ {\hspace{-3mm}}l}
     $B$ $=$ $\{$  
     \!\includegraphics[scale=0.059]{../pics/a1.jpg},
     \includegraphics[scale=0.048]{../pics/a2.jpg},
     \includegraphics[scale=0.02]{../pics/a3.jpg}
     $\}$
     \end{tabular}};
   \onslide<3->{\draw (-7, -3) node[scale=1.5] 
      {then \bl{$|A|$ \alert{$=$} $|B|$}};}
     \only<1>{
       \draw [->, line width=1mm, red] (-7.4, 0.2) -- (-6.1, 2.1);
       \draw [->, line width=1mm, red] (-5.8, 0.2) -- (-4.3, 2.1);
       \draw [->, line width=1mm, red] (-4.5, 0.2) -- (-7.6, 2.1);
     }
    \only<2->{
       \draw [<-, line width=1mm, blue] (-7.5, 0.2) -- (-7.5, 2.1);
       \draw [<-, line width=1mm, blue] (-5.8, 0.2) -- (-4.3, 2.1);
       \draw [<-, line width=1mm, blue] (-4.5, 0.2) -- (-6.1, 2.1);
       }
   
    
  \end{tikzpicture}
  \end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Natural Numbers}

\Large
\bl{$\mathbb{N}$} \bl{$\dn$} \bl{$\{0, 1, 2, 3, .......\}$}\bigskip\pause 

\bl{$A$} is \alert{countable} iff \bl{$|A| \leq |\mathbb{N}|$}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{First Question}

\Large
\bl{$|\mathbb{N} - \{0\}|   \;\;\;\alert{?}\;\;\;  |\mathbb{N}| $}\bigskip\bigskip 

\large
\bl{$\geq$} or \bl{$\leq$} or \bl{$=$} ?
\bigskip\bigskip\bigskip\pause

\bl{$x$ $\mapsto$ $x + 1$},\\  \bl{$|\mathbb{N} - \{0\}|$ $=$  
$|\mathbb{N}|$}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]

\Large
\bl{$|\mathbb{N} - \{0, 1\}|   \;\;\;\alert{?}\;\;\;  |\mathbb{N}| $}\bigskip\pause 

\bl{$|\mathbb{N} - \mathbb{O}|   \;\;\;\alert{?}\;\;\;  |\mathbb{N}| $}\bigskip\bigskip

\normalsize
\bl{$\mathbb{O}$} $\dn$ odd numbers\quad   \bl{$\{1,3,5......\}$}\\ \pause
\bl{$\mathbb{E}$} $\dn$ even numbers\quad   \bl{$\{0,2,4......\}$}\\
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]

\Large
\bl{$|\mathbb{N} \cup \mathbb{-N}|   \;\;\;\alert{?}\;\;\;  |\mathbb{N}| $}\bigskip\bigskip


\normalsize
\bl{$\mathbb{\phantom{-}N}$} $\dn$ positive numbers\quad   \bl{$\{0,1,2,3,......\}$}\\
\bl{$\mathbb{-N}$} $\dn$ negative numbers\quad   \bl{$\{0,-1,-2,-3,......\}$}\\
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]

\Large
\bl{$A$} is \alert{countable} if there exists an injective \bl{$f : A \rightarrow \mathbb{N}$}\bigskip

\bl{$A$} is \alert{uncountable} if there does not exist an injective \bl{$f : A \rightarrow \mathbb{N}$}\bigskip\bigskip 


countable:  \bl{$|A| \leq |\mathbb{N}|$}\\
uncountable:  \bl{$|A| > |\mathbb{N}|$}\pause\bigskip


Does there exist such an \bl{$A$} ?

\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \mode<presentation>{
  \begin{frame}[c]
  \frametitle{Hilbert's Hotel}

  \begin{center}
 \includegraphics[scale=0.8]{../pics/hilberts_hotel.jpg}
  \end{center}

  \begin{itemize}
  \item \ldots has as many rooms as there are natural numbers
  \end{itemize}

  \end{frame}}
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
  
  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
 \frametitle{\begin{tabular}{c}Real Numbers between\\[-2mm] 0 and 1\end{tabular}}

  \begin{center}
  \begin{tikzpicture}
  \draw [fill, color=black!50] (1,4) rectangle (2, 3);
  \draw [fill, color=black!50] (2,3) rectangle (3, 2);
  \draw [fill, color=black!50] (3,2) rectangle (4, 1);
  \draw [fill, color=black!50] (4,1) rectangle (5, 0);
  \draw (0, 0) grid (8, 5);
  \draw [line width = 1.mm] (1,0) -- (1, 5);    
  \draw [line width = 1.mm] (0, 4) -- (8, 4);    
  \draw (0.5,3.5) node {$1$};
  \draw (0.5,2.5) node {$2$};
  \draw (0.5,1.5) node {$3$};
  \draw (0.5,0.5) node {$4$};
  
  \draw (1.5,3.5) node {\only<1>{$3$}\only<2->{$4$}};
  \draw (2.5,3.5) node {$3$};
  \draw (3.5,3.5) node {$3$};
  \draw (4.5,3.5) node {$3$};
  \draw (5.5,3.5) node {$3$};
  \draw (6.5,3.5) node {$3$};
  \draw (7.5,3.5) node {$\ldots$};
  
  \draw (1.5,2.5) node {$1$};
  \draw (2.5,2.5) node {\only<1-2>{$2$}\only<3->{$3$}};
  \draw (3.5,2.5) node {$3$};
  \draw (4.5,2.5) node {$4$};
  \draw (5.5,2.5) node {$5$};
  \draw (6.5,2.5) node {$6$};
  \draw (7.5,2.5) node {$7$};

  \draw (1.5,1.5) node {$0$};
  \draw (2.5,1.5) node {$1$};
  \draw (3.5,1.5) node {\only<1-3>{$0$}\only<4->{$1$}};
  \draw (4.5,1.5) node {$1$};
  \draw (5.5,1.5) node {$0$};
  \draw (6.5,1.5) node {$\ldots$};
  
   \draw (1.5,0.5) node {$7$};
  \draw (2.5,0.5) node {$8$};
  \draw (3.5,0.5) node {$5$};
  \draw (4.5,0.5) node {\only<1-4>{$3$}\only<5->{$4$}};
  \draw (5.5,0.5) node {$9$};
  \draw (6.5,0.5) node {$\ldots$};
  
   \draw (1.5,-0.5) node {$\ldots$};
   \draw (8.5,3.5) node {$\ldots$};
  \end{tikzpicture}
  \end{center}
  \mbox{}\\[-20mm]\mbox{}
  
  \onslide<6->{
  \begin{center}
  \Large\bl{$|\mathbb{N}| < |R|$}
  \end{center}
  }

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
 \frametitle{The Set of Problems}

  $\aleph_0$

  \begin{center}
  \begin{tikzpicture}
  \draw [fill, color=black!50] (1,4) rectangle (2, 3);
  \draw [fill, color=black!50] (2,3) rectangle (3, 2);
  \draw [fill, color=black!50] (3,2) rectangle (4, 1);
  \draw [fill, color=black!50] (4,1) rectangle (5, 0);
  \draw (0, 0) grid (8, 5);
  \draw [line width = 1.mm] (1,0) -- (1, 5);    
  \draw [line width = 1.mm] (0, 4) -- (8, 4);    
  \draw (0.5,3.5) node {$1$};
  \draw (0.5,2.5) node {$2$};
  \draw (0.5,1.5) node {$3$};
  \draw (0.5,0.5) node {$4$};
  
  \draw (1.5,4.5) node {$0$};
  \draw (2.5,4.5) node {$1$};
  \draw (3.5,4.5) node {$2$};
  \draw (4.5,4.5) node {$3$};
  \draw (5.5,4.5) node {$4$};
  \draw (6.5,4.5) node {$5$};
  \draw (7.5,4.5) node {$\ldots$}; 
  
  \draw (1.5,3.5) node {$0$};
  \draw (2.5,3.5) node {$1$};
  \draw (3.5,3.5) node {$0$};
  \draw (4.5,3.5) node {$1$};
  \draw (5.5,3.5) node {$0$};
  \draw (6.5,3.5) node {$1$};
  \draw (7.5,3.5) node {$\ldots$};
  
  \draw (1.5,2.5) node {$0$};
  \draw (2.5,2.5) node {$0$};
  \draw (3.5,2.5) node {$0$};
  \draw (4.5,2.5) node {$1$};
  \draw (5.5,2.5) node {$1$};
  \draw (6.5,2.5) node {$0$};
  \draw (7.5,2.5) node {$0$};

  \draw (1.5,1.5) node {$0$};
  \draw (2.5,1.5) node {$0$};
  \draw (3.5,1.5) node {$0$};
  \draw (4.5,1.5) node {$0$};
  \draw (5.5,1.5) node {$0$};
  \draw (6.5,1.5) node {$\ldots$};
  
   \draw (1.5,0.5) node {$1$};
  \draw (2.5,0.5) node {$1$};
  \draw (3.5,0.5) node {$0$};
  \draw (4.5,0.5) node {$1$};
  \draw (5.5,0.5) node {$1$};
  \draw (6.5,0.5) node {$\ldots$};
  
  \draw (1.5,-0.5) node {$\ldots$};
   \draw (8.5,3.5) node {$\ldots$};

  \end{tikzpicture}
  \end{center}
  
  
  \onslide<2>{
  \begin{center}
  \large \bl{|Progs| $=$ $|\mathbb{N}|$ $<$ |Probs|}
 \end{center}
  }


\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Halting Problem}

\large
Assume a program \bl{$H$} that decides for all programs \bl{$A$} and all 
input data \bl{$D$} whether\bigskip

\begin{itemize}
\item \bl{$H(A, D) \dn 1$} iff \bl{$A(D)$} terminates
\item \bl{$H(A, D) \dn 0$} otherwise
\end{itemize}

\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Halting Problem (2)}

\large
Given such a program \bl{$H$} define the following program \bl{$C$}:
for all programs \bl{$A$}\bigskip

\begin{itemize}
\item \bl{$C(A) \dn 0$} iff \bl{$H(A, A) = 0$} 
\item \bl{$C(A) \dn$ loops} otherwise
\end{itemize}

\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Contradiction}


\bl{$H(C, C)$} is either \bl{$0$} or \bl{$1$}.

\begin{itemize}
\item \bl{$H(C, C) = 1$} $\stackrel{\text{def}\,H}{\Rightarrow}$ \bl{$C(C)\downarrow$} $\stackrel{\text{def}\,C}{\Rightarrow}$ \bl{$H(C, C)=0$} 
\item \bl{$H(C, C) = 0$} $\stackrel{\text{def}\,H}{\Rightarrow}$ \bl{$C(C)$} loops $\stackrel{\text{def}\,C}{\Rightarrow}$\\ 
\hspace{7cm}\bl{$H(C, C)=1$} 
\end{itemize}

Contradiction in both cases. So \bl{$H$} cannot exist.

\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \mode<presentation>{
  \begin{frame}[c]
  \frametitle{Take Home Points}
 \large
 
  \begin{itemize}
  \item there are sets that are more infinite than others\bigskip
  \item even  with the most powerful computer we can imagine, there 
  are problems that cannot be solved by any program\bigskip\bigskip
  
  \item in CS we actually hit quite often such problems (halting problem)
  \end{itemize}

  \end{frame}}
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
  
\end{document}

%%% Local Variables:  
%%% mode: latex
%%% TeX-master: t
%%% End: