
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<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}
+
+\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<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 1$} 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{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: 
+




