\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: & N7.07 (North Wing, Bush House)\\
  Slides: & KEATS (also home work is there)\\
  \end{tabular}
  \end{center}

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

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

\large\bf
Using a compiler, \\how can you mount the\\ perfect attack against a system?

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

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

{\large\bf
What is a \alert{perfect} attack?}\bigskip

\begin{enumerate}
\item you can potentially completely take over a target system
\item your attack is (nearly) undetectable
\item the victim has (almost) no chance to recover
\end{enumerate}

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

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


  \begin{center}
  \begin{tikzpicture}[scale=1]
  
  \onslide<1->{
  \node (A) at (0,0)  [draw=black, rectangle, very thick, minimum height=18mm, minimum width=17mm] {};
  \node [below right] at (A.north west) {\footnotesize\begin{tabular}{@{}l@{}}
  \only<1,2>{clean}\only<3->{\alert{hacked}}\\compiler\end{tabular}};}


  \onslide<2->{
  \node (B) at (-2,2)  [draw=black, rectangle, very thick, minimum height=10mm, minimum width=12mm] {};
  \node [below right] at (B.north west) {\footnotesize\begin{tabular}{@{}l@{}}login\\(src)\end{tabular}};
  
  \node (C) at (2,2)  [draw=black, rectangle, very thick, minimum height=10mm, minimum width=12mm] {};
  \node [below right] at (C.north west) {\footnotesize\begin{tabular}{@{}l@{}}login\\(bin)\end{tabular}};

  \draw[->, line width=2mm] (B) -- (C);
  }
  
 \onslide<3->{\node [above left=-1.5mm] at (C.south east) {\footnotesize \alert{$\blacksquare$}};}

  \end{tikzpicture}
  \end{center}

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


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

  \begin{center}
  \begin{tikzpicture}[scale=1]
  
  \onslide<1->{
  \node (A) at (0,0)  [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {};
  \node [below right] at (A.north west) {\small V0.01};
  \node [below right] (A1) at (A.south west) {\small Scala};
  \node [below right] (A1) at (A1.south west) {\small\textcolor{gray}{host language}};
  \node [above right] at (A.north west) {my compiler (src)};}

  \onslide<2->{
  \node (B) at (1.8,0)  [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {};
  \node [below right] at (B.north west) {\small V0.02};
  \node [below right] at (B.south west) {\small Scala};
  \node at (3,0) {\ldots};

  \node (C) at (5,0)  [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {};
  \node [below right] at (C.north west) {\small V1.00};
  \node [below right] at (C.south west) {\small Scala};}

  \onslide<3->{
  \node (D) at (6.8,0)  [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {};
  \node [below right] at (D.north west) {\small V1.00};

  \node (E) at (6.8,2)  [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {};
  \node [below right] at (E.north west) {\small V1.01};}
  
  \onslide<4->{
  \node (F) at (8.6,0)  [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {};
  \node [below right] at (F.north west) {\small V1.01};

  \node (G) at (8.6,2)  [draw=black, rectangle, very thick, minimum height=18mm, minimum width=14mm] {};
  \node [below right] at (G.north west) {\small V1.02};
  \node at (9.8,0) {\ldots};
  \node at (9.8,2) {\ldots};
  \node at (8,-2) {\textcolor{gray}{\begin{tabular}{@{}l@{}}no host language\\needed\end{tabular}}};
  }
  
  \end{tikzpicture}
  \end{center}

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


  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \mode<presentation>{
  \begin{frame}<1-3>
  \frametitle{\LARGE\begin{tabular}{c}Hacking Compilers 
  \end{tabular}}
  
  %Why is it so paramount to have a small trusted code base (TCB)?
  \bigskip\bigskip

  \begin{columns}
  \begin{column}{2.7cm}
  \begin{minipage}{2.5cm}%
  \begin{tabular}{c@ {}}
  \includegraphics[scale=0.2]{../pics/ken-thompson.jpg}\\[-1.8mm]
  \footnotesize Ken Thompson\\[-1.8mm]
  \footnotesize Turing Award, 1983\\
  \end{tabular}
  \end{minipage}
  \end{column}
  \begin{column}{9cm}
  \begin{tabular}{l@ {\hspace{1mm}}p{8cm}}
 
  & Ken Thompson showed how to hide a Trojan Horse in a 
  compiler \textcolor{red}{without} leaving any traces in the source code.\\[2mm]
  
  & No amount of source level verification will protect 
  you from such Thompson-hacks.\\[2mm]

  \end{tabular}
  \end{column}
  \end{columns}

  \only<2>{
  \begin{textblock}{6}(4,2)
  \begin{tikzpicture}
  \draw (0,0) node[inner sep=3mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] 
  {\normalsize
  \begin{minipage}{8cm}
  \begin{quote}
  \includegraphics[scale=0.05]{../pics/evil.png}
  \begin{enumerate}
  \item[1)] Assume you ship the compiler as binary and also with sources.
  \item[2)] Make the compiler aware when it compiles itself.
  \item[3)] Add the Trojan horse.
  \item[4)] Compile.
  \item[5)] Delete Trojan horse from the sources of the compiler.
  \item[6)] Go on holiday for the rest of your life. ;o)\\[-7mm]\mbox{}
  \end{enumerate}
  \end{quote}
  \end{minipage}};
  \end{tikzpicture}
  \end{textblock}}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Compilers \& Boeings 777}

First flight in 1994. They want to achieve triple redundancy in hardware
faults.\bigskip

They compile 1 Ada program to\medskip

\begin{itemize}
\item Intel 80486
\item Motorola 68040 (old Macintosh's)
\item AMD 29050 (RISC chips used often in laser printers)
\end{itemize}\medskip

using 3 independent compilers.\bigskip\pause

\small Airbus uses C and static analysers. Recently started using CompCert.

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

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

{\Large\bf  
How many strings are in \bl{$L(a^*)$}?}\bigskip\pause 

\normalsize
\begin{center}
\begin{tabular}{llllll}
  \bl{$[]$} &  \bl{$a$} &  \bl{$aa$} & \bl{$aaa$} & \bl{$aaaa$} & \ldots\\
  \bl{0}  &  \bl{1} &  \bl{2}  & \bl{3}   & \bl{4}  & \ldots    
\end{tabular}
\end{center}

\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: