\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.28074850000 1.087897100000 3.713165250000 21.6624545500000 85.872613750000 203.64080151000000 345.736574\end{filecontents}\begin{filecontents}{interpreted.data}%1 0.00503200 1.005863400 7.8296765500 15.43106600 27.2321885800 65.2492711000 135.44934451200 232.1340971400 382.527227\end{filecontents}\begin{filecontents}{interpreted2.data}%1 0.00503200 1.005863400 7.8296765600 27.2321885800 65.2492711000 135.44934451200 232.1340971400 382.527227\end{filecontents}\begin{filecontents}{compiled2.data}200 0.222058400 0.215204600 0.202031800 0.219861000 0.2059341200 0.19816151400 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\bfThere 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$}\bigskipthen \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\\\pauseif 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\bigskipDoes there exist such an \bl{$A$} ?\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\frametitle{Halting Problem}\largeAssume 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)}\largeGiven 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: