\documentclass[dvipsnames,14pt,t]{beamer}
\usepackage{beamerthemeplainculight}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{mathpartir}
\usepackage[absolute,overlay]{textpos}
\usepackage{ifthen}
\usepackage{tikz}
\usepackage{pgf}
\usepackage{calc}
\usepackage{ulem}
\usepackage{courier}
\usepackage{listings}
\renewcommand{\uline}[1]{#1}
\usetikzlibrary{arrows}
\usetikzlibrary{automata}
\usetikzlibrary{shapes}
\usetikzlibrary{shadows}
\usetikzlibrary{positioning}
\usetikzlibrary{calc}
\usetikzlibrary{plotmarks}
\usepackage{graphicx}
\usepackage{pgfplots}
\definecolor{javared}{rgb}{0.6,0,0} % for strings
\definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments
\definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords
\definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc
\lstset{language=Java,
basicstyle=\ttfamily,
keywordstyle=\color{javapurple}\bfseries,
stringstyle=\color{javagreen},
commentstyle=\color{javagreen},
morecomment=[s][\color{javadocblue}]{/**}{*/},
numbers=left,
numberstyle=\tiny\color{black},
stepnumber=1,
numbersep=10pt,
tabsize=2,
showspaces=false,
showstringspaces=false}
\lstdefinelanguage{scala}{
morekeywords={abstract,case,catch,class,def,%
do,else,extends,false,final,finally,%
for,if,implicit,import,match,mixin,%
new,null,object,override,package,%
private,protected,requires,return,sealed,%
super,this,throw,trait,true,try,%
type,val,var,while,with,yield},
otherkeywords={=>,<-,<\%,<:,>:,\#,@},
sensitive=true,
morecomment=[l]{//},
morecomment=[n]{/*}{*/},
morestring=[b]",
morestring=[b]',
morestring=[b]"""
}
\lstset{language=Scala,
basicstyle=\ttfamily,
keywordstyle=\color{javapurple}\bfseries,
stringstyle=\color{javagreen},
commentstyle=\color{javagreen},
morecomment=[s][\color{javadocblue}]{/**}{*/},
numbers=left,
numberstyle=\tiny\color{black},
stepnumber=1,
numbersep=10pt,
tabsize=2,
showspaces=false,
showstringspaces=false}
\lstdefinelanguage{while}{
morekeywords={if,then,else,while,do,true,false,write},
otherkeywords={=,!=,:=,<,>,;},
sensitive=true,
morecomment=[n]{/*}{*/},
}
\lstset{language=While,
basicstyle=\ttfamily,
keywordstyle=\color{javapurple}\bfseries,
stringstyle=\color{javagreen},
commentstyle=\color{javagreen},
morecomment=[s][\color{javadocblue}]{/**}{*/},
numbers=left,
numberstyle=\tiny\color{black},
stepnumber=1,
numbersep=10pt,
tabsize=2,
showspaces=false,
showstringspaces=false}
% beamer stuff
\renewcommand{\slidecaption}{AFL 10, King's College London, 5.~December 2012}
\newcommand{\bl}[1]{\textcolor{blue}{#1}}
\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
% The data files, written on the first run.
\begin{filecontents}{compiled.data}
%1 0.234146
%5000 0.227539
%10000 0.280748
50000 1.087897
100000 3.713165
250000 21.6624545
500000 85.872613
750000 203.6408015
1000000 345.736574
\end{filecontents}
\begin{filecontents}{interpreted.data}
%1 0.00503
200 1.005863
400 7.8296765
500 15.43106
600 27.2321885
800 65.249271
1000 135.4493445
1200 232.134097
1400 382.527227
\end{filecontents}
\begin{filecontents}{interpreted2.data}
%1 0.00503
200 1.005863
400 7.8296765
600 27.2321885
800 65.249271
1000 135.4493445
1200 232.134097
1400 382.527227
\end{filecontents}
\begin{filecontents}{compiled2.data}
200 0.222058
400 0.215204
600 0.202031
800 0.21986
1000 0.205934
1200 0.1981615
1400 0.207116
\end{filecontents}
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}<1>[t]
\frametitle{%
\begin{tabular}{@ {}c@ {}}
\\[-3mm]
\LARGE Automata and \\[-2mm]
\LARGE Formal Languages (10)\\[3mm]
\end{tabular}}
\normalsize
\begin{center}
\begin{tabular}{ll}
Email: & christian.urban at kcl.ac.uk\\
Of$\!$fice: & S1.27 (1st floor Strand Building)\\
Slides: & KEATS (also home work is there)\\
\end{tabular}
\end{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\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}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Revision: Proofs}
\begin{center}
\includegraphics[scale=0.4]{river-stones.jpg}
\end{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Subsets}
\Large
\bl{$A \subseteq B$}\bigskip\bigskip\\
\bl{$\forall e.\; e \in A \Rightarrow e \in B$}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Subsets}
\Large
\bl{$A \subseteq B$} and \bl{$B \subseteq A$}\bigskip
then \bl{$A = B$}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Injective Function}
\Large
\bl{f} is an injective function iff \bigskip
\bl{$\forall x y.\; f(x) = f(y) \Rightarrow x = y$}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\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|$}\
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\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}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{First Question}
\Large
\bl{$|\mathbb{N} - \{0\}| \;\;\;\alert{?}\;\;\; |\mathbb{N}| $}\bigskip\bigskip
\normalsize
\bl{$\geq$} or \bl{$\leq$} or \bl{$=$}
\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{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}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: