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