diff -r e85600529ca5 -r 4794759139ea slides10.tex --- a/slides10.tex Sat Jun 15 09:11:11 2013 -0400 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,383 +0,0 @@ -\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{ -\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{ -\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{ -\begin{frame}[c] -\frametitle{Revision: Proofs} - -\begin{center} -\includegraphics[scale=0.4]{river-stones.jpg} -\end{center} - -\end{frame}} - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\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{ -\begin{frame}[c] -\frametitle{Subsets} - -\Large -\bl{$A \subseteq B$} and \bl{$B \subseteq A$}\bigskip - -then \bl{$A = B$} -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\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{ -\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{ -\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{ -\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{ -\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{ -\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{ -\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{ -\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{ -\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{ -\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: -