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