
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<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: 
-




