# HG changeset patch # User Christian Urban # Date 1354680792 0 # Node ID 6a7fe83820c8ee975408a3444d27a76c4ec2e79a # Parent 1a4065f965fb2d6747274e6350777a16f316760e added diff -r 1a4065f965fb -r 6a7fe83820c8 slides10.pdf Binary file slides10.pdf has changed diff -r 1a4065f965fb -r 6a7fe83820c8 slides10.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/slides10.tex Wed Dec 05 04:13:12 2012 +0000 @@ -0,0 +1,400 @@ +\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} + +\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 1$} 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 1$} 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{def H}{\Rightarrow}$ \bl{$C(C)\downarrow$} $\stackrel{def C}{\Rightarrow}$ \bl{$H(C, C)=0$} +\item \bl{$H(C, C) = 0$} $\stackrel{def H}{\Rightarrow}$ \bl{$C(C)$} loops $\stackrel{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: +