% !TEX program = xelatex
\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
\usepackage{../slides}
\usepackage{../langs}
\usepackage{../data}
\usepackage{../graphicss}
\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\\[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}
\begin{center}
\begin{tikzpicture}
\node[drop shadow,fill=white,inner sep=0pt]
{\footnotesize\rowcolors{1}{capri!10}{white}
\begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline
1 Introduction, Languages & 6 While-Language \\
2 Regular Expressions, Derivatives & 7 Compilation, JVM \\
3 Automata, Regular Languages & 8 Compiling Functional Languages \\
4 Lexing, Tokenising & 9 Optimisations \\
5 Grammars, Parsing & \cellcolor{blue!50}10 LLVM \\ \hline
\end{tabular}%
};
\end{tikzpicture}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\tikzstyle{sensor}=[draw, fill=blue!20, text width=3.8em, line width=1mm,
text centered, minimum height=2em,drop shadow]
\tikzstyle{ann} = [above, text width=4em, text centered]
\tikzstyle{sc} = [sensor, text width=7em, fill=red!20,
minimum height=6em, rounded corners, drop shadow,line width=1mm]
\begin{frame}[fragile,c]
\frametitle{LLVM: Overview}
\begin{tikzpicture}
% Validation Layer is the same except that there are a set of nodes and links which are added
\path (0,0) node (IR) [sc] {\textbf{LLVM-IR}\\ Optimisations};
\path (IR.west)+(-2.2,1.7) node (sou1) [sensor] {C++};
\path (IR.west)+(-2.2,0.5) node (sou2)[sensor] {C};
\path (IR.west)+(-2.2,-1.0) node (dots)[ann] {$\vdots$};
\path (IR.west)+(-2.2,-1.8) node (sou3)[sensor] {Haskell};
\path [draw,->,line width=1mm] (sou1.east) -- node [above] {} (IR.160);
\path [draw,->,line width=1mm] (sou2.east) -- node [above] {} (IR.180);
\path [draw,->,line width=1mm] (sou3.east) -- node [above] {} (IR.200);
\path (IR.east)+(2.2,2.0) node (tar1)[sensor] {x86};
\path (IR.east)+(2.2,0.8) node (tar2)[sensor] {ARM};
\path (IR.east)+(2.2,-0.4) node (tar3)[sensor] {MIPS};
\path (IR.east)+(2.2,-1.6) node (tar4)[sensor] {RISC};
\path (IR.east)+(2.2,-2.8) node (tar5)[sensor] {Power PC};
\path (IR.east)+(2.2,-4.2) node (dots2)[ann] {$\vdots$};
\path [draw,<-,line width=1mm] (tar1.west) -- node [above] {} (IR.10);
\path [draw,<-,line width=1mm] (tar2.west) -- node [above] {} (IR.5);
\path [draw,<-,line width=1mm] (tar3.west) -- node [above] {} (IR.0);
\path [draw,<-,line width=1mm] (tar4.west) -- node [above] {} (IR.-5);
\path [draw,<-,line width=1mm] (tar5.west) -- node [above] {} (IR.-10);
\end{tikzpicture}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\frametitle{Static Single-Assignment}
\bl{$(1 + a) + (3 + (b * 5))$}\bigskip\bigskip
\begin{lstlisting}[language=LLVMIR,numbers=left]
let tmp0 = add 1 a in
let tmp1 = mul b 5 in
let tmp2 = add 3 tmp1 in
let tmp3 = add tmp0 tmp2
in tmp3
\end{lstlisting}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\small
\mbox{}\bigskip\bigskip\bigskip
\begin{lstlisting}[language=llvm,numbers=left]
define i32 @fact (i32 %n) {
%tmp_20 = icmp eq i32 %n, 0
br i1 %tmp_20, label %if_branch_24, label %else_branch_25
if_branch_24:
ret i32 1
else_branch_25:
%tmp_22 = sub i32 %n, 1
%tmp_23 = call i32 @fact (i32 %tmp_22)
%tmp_21 = mul i32 %n, %tmp_23
ret i32 %tmp_21
}
\end{lstlisting}
\begin{lstlisting}[language={},numbers=none]
def fact(n) = if n == 0 then 1 else n * fact(n - 1)
\end{lstlisting}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile,c]
\frametitle{LLVM Types}
\tt
\begin{center}
\begin{tabular}{ll}
boolean & i1 \\
byte & i8 \\
short & i16\\
char & i16\\
integer & i32\\
long & i64\\
float & float\\
double & double\\
*\_ & pointer to \\
**\_ & pointer to a pointer to\\
\mbox{}[\_] & arrays of\\
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\begin{lstlisting}[language=LLVM,numbers=none]
br i1 %var, label %if_br, label %else_br
icmp eq i32 %x, %y ; for equal
icmp sle i32 %x, %y ; signed less or equal
icmp slt i32 %x, %y ; signed less than
icmp ult i32 %x, %y ; unsigned less than
%var = call i32 @foo(...args...)
\end{lstlisting}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile,c]
\frametitle{Abstract Syntax Trees}
\footnotesize
\begin{lstlisting}[language=Scala,numbers=none,xleftmargin=-3mm]
// Fun language (expressions)
abstract class Exp
abstract class BExp
case class Call(name: String, args: List[Exp]) extends Exp
case class If(a: BExp, e1: Exp, e2: Exp) extends Exp
case class Write(e: Exp) extends Exp
case class Var(s: String) extends Exp
case class Num(i: Int) extends Exp
case class Aop(o: String, a1: Exp, a2: Exp) extends Exp
case class Sequence(e1: Exp, e2: Exp) extends Exp
case class Bop(o: String, a1: Exp, a2: Exp) extends BExp
\end{lstlisting}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile,c]
\frametitle{K-(Intermediate)Language}
\footnotesize
\begin{lstlisting}[language=Scala,numbers=none,xleftmargin=-3mm]
abstract class KExp
abstract class KVal
// K-Values
case class KVar(s: String) extends KVal
case class KNum(i: Int) extends KVal
case class Kop(o: String, v1: KVal, v2: KVal) extends KVal
case class KCall(o: String, vrs: List[KVal]) extends KVal
case class KWrite(v: KVal) extends KVal
// K-Expressions
case class KIf(x1: String, e1: KExp, e2: KExp) extends KExp
case class KLet(x: String, v: KVal, e: KExp) extends KExp
case class KReturn(v: KVal) extends KExp
\end{lstlisting}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile,c]
\frametitle{KLet}
\begin{lstlisting}[language=LLVM]
tmp0 = add 1 a
tmp1 = mul b 5
tmp2 = add 3 tmp1
tmp3 = add tmp0 tmp2
\end{lstlisting}
\begin{lstlisting}[language=LLVMIR]
KLet tmp0 , add 1 a in
KLet tmp1 , mul b 5 in
KLet tmp2 , add 3 tmp1 in
KLet tmp3 , add tmp0 tmp2 in
...
\end{lstlisting}
\begin{lstlisting}[language=Scala,numbers=none]
case class KLet(x: String, e1: KVal, e2: KExp)
\end{lstlisting}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile,c]
\frametitle{KLet}
\begin{lstlisting}[language=LLVM]
tmp0 = add 1 a
tmp1 = mul b 5
tmp2 = add 3 tmp1
tmp3 = add tmp0 tmp2
\end{lstlisting}
\begin{lstlisting}[language=LLVMIR]
let tmp0 = add 1 a in
let tmp1 = mul b 5 in
let tmp2 = add 3 tmp1 in
let tmp3 = add tmp0 tmp2 in
...
\end{lstlisting}
\begin{lstlisting}[language=Scala,numbers=none]
case class KLet(x: String, e1: KVal, e2: KExp)
\end{lstlisting}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile,c]
\frametitle{CPS-Translation}
\small
\begin{lstlisting}[language=Scala,numbers=none]
def CPS(e: Exp)(k: KVal => KExp) : KExp =
e match { ... }
\end{lstlisting}
\bigskip\bigskip
the continuation \texttt{k} can be thought of:\medskip
\small
\begin{lstlisting}[language=LLVMIR,numbers=none,xleftmargin=30mm,escapeinside={(*@}{@*)}]
let tmp0 = add 1 a in
let tmp1 = mul (*@$\Box$@*) 5 in
let tmp2 = add 3 tmp1 in
let tmp3 = add tmp0 tmp2 in
KReturn tmp3
\end{lstlisting}
\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}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}<1-20>[c]
\end{frame}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: