|
1 \documentclass[dvipsnames,14pt,t]{beamer} |
|
2 \usepackage{../slides} |
|
3 \usepackage{../graphics} |
|
4 \usepackage{../langs} |
|
5 \usepackage{../data} |
|
6 \usepackage{../grammar} |
|
7 |
|
8 % beamer stuff |
|
9 \renewcommand{\slidecaption}{AFL, King's College London} |
|
10 \newcommand{\bl}[1]{\textcolor{blue}{#1}} |
|
11 |
|
12 |
|
13 \begin{document} |
|
14 |
|
15 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
16 \begin{frame}[t] |
|
17 \frametitle{% |
|
18 \begin{tabular}{@ {}c@ {}} |
|
19 \\[-3mm] |
|
20 \LARGE Automata and \\[-2mm] |
|
21 \LARGE Formal Languages\\[3mm] |
|
22 \end{tabular}} |
|
23 |
|
24 \normalsize |
|
25 \begin{center} |
|
26 \begin{tabular}{ll} |
|
27 Email: & christian.urban at kcl.ac.uk\\ |
|
28 Office: & S1.27 (1st floor Strand Building)\\ |
|
29 Slides: & KEATS (also home work is there)\\ |
|
30 \end{tabular} |
|
31 \end{center} |
|
32 |
|
33 \end{frame} |
|
34 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
35 |
|
36 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
37 \begin{frame}[c] |
|
38 |
|
39 \Large\bf There are more problems, than there are |
|
40 programs.\bigskip\bigskip\pause\\ |
|
41 |
|
42 There must be a problem for which there is no program. |
|
43 \end{frame} |
|
44 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
45 |
|
46 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
47 \begin{frame}[c] |
|
48 \frametitle{Subsets} |
|
49 |
|
50 \Large |
|
51 If \bl{$A \subseteq B$} then \bl{$A$} has fewer elements |
|
52 than \bl{$B$}\bigskip\bigskip |
|
53 |
|
54 \Large |
|
55 \bl{$A \subseteq B$} and \bl{$B \subseteq A$}\bigskip |
|
56 |
|
57 then \bl{$A = B$} |
|
58 \end{frame} |
|
59 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
60 |
|
61 |
|
62 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
63 \begin{frame}[c] |
|
64 |
|
65 \begin{center} |
|
66 \begin{tikzpicture} |
|
67 |
|
68 \draw (-4,2.5) node [scale=2.5] (X) |
|
69 {\begin{tabular}{l} |
|
70 $\{$ |
|
71 \!\includegraphics[scale=0.02]{../pics/o1.jpg}, |
|
72 \includegraphics[scale=0.02]{../pics/o2.jpg}, |
|
73 \!\includegraphics[scale=0.02]{../pics/o3.jpg}, |
|
74 \includegraphics[scale=0.02]{../pics/o4.jpg}, |
|
75 \!\includegraphics[scale=0.027]{../pics/o5.jpg} |
|
76 $\}$ |
|
77 \end{tabular}}; |
|
78 |
|
79 \draw (-5.6,-2.5) node [scale=2.5] (Y) |
|
80 {\begin{tabular}{l} |
|
81 $\{$ |
|
82 \!\includegraphics[scale=0.059]{../pics/a1.jpg}, |
|
83 \includegraphics[scale=0.048]{../pics/a2.jpg}, |
|
84 \includegraphics[scale=0.02]{../pics/a3.jpg} |
|
85 $\}$ |
|
86 \end{tabular}}; |
|
87 |
|
88 \draw (0,1.5) node (X1) {5 elements}; |
|
89 \draw (0,-3.5) node (y1) {3 elements}; |
|
90 \end{tikzpicture} |
|
91 \end{center} |
|
92 |
|
93 \end{frame} |
|
94 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
95 |
|
96 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
97 \begin{frame}[c] |
|
98 \frametitle{Newton vs Feynman} |
|
99 |
|
100 \begin{center} |
|
101 \begin{tabular}{cc} |
|
102 \includegraphics[scale=0.2]{../pics/newton.jpg} & |
|
103 \includegraphics[scale=0.2]{../pics/feynman.jpg}\\ |
|
104 classical physics & quantum physics |
|
105 \end{tabular} |
|
106 \end{center} |
|
107 \end{frame} |
|
108 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
109 |
|
110 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
111 \begin{frame}[c] |
|
112 \frametitle{The Goal of the Talk} |
|
113 \large |
|
114 \begin{itemize} |
|
115 \item show you that something very unintuitive happens with very large sets |
|
116 \bigskip\bigskip |
|
117 |
|
118 \item convince you that there are more {\bf problems} than {\bf programs} |
|
119 \end{itemize} |
|
120 \end{frame} |
|
121 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
122 |
|
123 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
124 \begin{frame}[t] |
|
125 % |
|
126 \begin{center} |
|
127 \begin{tikzpicture} |
|
128 |
|
129 \draw (-5,2.5) node [scale=2.3] (X) |
|
130 {\begin{tabular}{@ {\hspace{-3mm}}l} |
|
131 \bl{$B$ $=$ $\{$ |
|
132 \!\includegraphics[scale=0.02]{../pics/o1.jpg}, |
|
133 \includegraphics[scale=0.02]{../pics/o2.jpg}, |
|
134 \!\includegraphics[scale=0.02]{../pics/o3.jpg}, |
|
135 \includegraphics[scale=0.02]{../pics/o4.jpg}, |
|
136 \!\includegraphics[scale=0.027]{../pics/o5.jpg} |
|
137 $\}$} |
|
138 \end{tabular}}; |
|
139 |
|
140 \draw (-6.6,-0.5) node [scale=2.3] (Y) |
|
141 {\begin{tabular}{@ {\hspace{-3mm}}l} |
|
142 \bl{$A$ $=$ $\{$ |
|
143 \!\includegraphics[scale=0.059]{../pics/a1.jpg}, |
|
144 \includegraphics[scale=0.048]{../pics/a2.jpg}, |
|
145 \includegraphics[scale=0.02]{../pics/a3.jpg} |
|
146 $\}$} |
|
147 \end{tabular}}; |
|
148 |
|
149 \only<1>{\draw (-5, -3) node[scale=2] |
|
150 {\bl{$|A|$ $=$ $5$}, \bl{$|B|$ $=$ $3$}};} |
|
151 \only<2>{ |
|
152 \draw [->, line width=1mm, red] (-7.4, 0.2) -- (-6.1, 2.1); |
|
153 \draw [->, line width=1mm, red] (-5.8, 0.2) -- (-3.1, 2.1); |
|
154 \draw [->, line width=1mm, red] (-4.5, 0.2) -- (-7.6, 2.1); |
|
155 \draw (-5, -3) node[scale=2] {then \bl{$|A|$ $\le$ $|B|$}}; |
|
156 } |
|
157 \only<3>{ |
|
158 \draw [<-, line width=1mm, red] (-7.5, 0.2) -- (-6.1, 2.1); |
|
159 \draw [<-, line width=1mm, red] (-7.3, 0.2) -- (-3.1, 2.1); |
|
160 \draw [<-, line width=1mm, red] (-6, 0.2) -- (-7.5, 2.1); |
|
161 \draw [<-, line width=1mm, red] (-4.5, 0.2) -- (-4.5, 2.1); |
|
162 \draw [<-, line width=1mm, red] (-4.3, 0.2) -- (-1.3, 2.1); |
|
163 |
|
164 \draw (-5, -3) node[scale=1.5] {\small{}for \bl{$=$} |
|
165 has to be a {\bf one-to-one} mapping}; |
|
166 } |
|
167 |
|
168 |
|
169 \end{tikzpicture} |
|
170 \end{center} |
|
171 |
|
172 \end{frame} |
|
173 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
174 |
|
175 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
176 \begin{frame}[c] |
|
177 \frametitle{Cardinality} |
|
178 |
|
179 \Large |
|
180 \bl{$|A|$} $\dn$ ``how many elements''\bigskip\\ |
|
181 |
|
182 \bl{$A \subseteq B \Rightarrow |A| \leq |B|$}\bigskip\\\pause |
|
183 |
|
184 if there is an injective function \bl{$f: A \rightarrow B$} then \bl{$|A| \leq |B|$}\ |
|
185 |
|
186 \begin{center} |
|
187 \bl{\large$\forall x y.\; f(x) = f(y) \Rightarrow x = y$} |
|
188 \end{center} |
|
189 \end{frame} |
|
190 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
191 |
|
192 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
193 \begin{frame}[t] |
|
194 |
|
195 \begin{center} |
|
196 \begin{tikzpicture} |
|
197 |
|
198 \draw (-6.6,2.5) node [scale=2.3] (X) |
|
199 {\begin{tabular}{@ {\hspace{-3mm}}l} |
|
200 $A$ $=$ $\{$ |
|
201 \!\includegraphics[scale=0.02]{../pics/o1.jpg}, |
|
202 \includegraphics[scale=0.02]{../pics/o2.jpg}, |
|
203 \!\includegraphics[scale=0.02]{../pics/o3.jpg} |
|
204 $\}$ |
|
205 \end{tabular}}; |
|
206 |
|
207 \draw (-6.6,-0.5) node [scale=2.3] (Y) |
|
208 {\begin{tabular}{@ {\hspace{-3mm}}l} |
|
209 $B$ $=$ $\{$ |
|
210 \!\includegraphics[scale=0.059]{../pics/a1.jpg}, |
|
211 \includegraphics[scale=0.048]{../pics/a2.jpg}, |
|
212 \includegraphics[scale=0.02]{../pics/a3.jpg} |
|
213 $\}$ |
|
214 \end{tabular}}; |
|
215 \onslide<3->{\draw (-7, -3) node[scale=1.5] |
|
216 {then \bl{$|A|$ \alert{$=$} $|B|$}};} |
|
217 \only<1>{ |
|
218 \draw [->, line width=1mm, red] (-7.4, 0.2) -- (-6.1, 2.1); |
|
219 \draw [->, line width=1mm, red] (-5.8, 0.2) -- (-4.3, 2.1); |
|
220 \draw [->, line width=1mm, red] (-4.5, 0.2) -- (-7.6, 2.1); |
|
221 } |
|
222 \only<2->{ |
|
223 \draw [<-, line width=1mm, blue] (-7.5, 0.2) -- (-7.5, 2.1); |
|
224 \draw [<-, line width=1mm, blue] (-5.8, 0.2) -- (-4.3, 2.1); |
|
225 \draw [<-, line width=1mm, blue] (-4.5, 0.2) -- (-6.1, 2.1); |
|
226 } |
|
227 |
|
228 |
|
229 \end{tikzpicture} |
|
230 \end{center} |
|
231 |
|
232 \end{frame} |
|
233 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
234 |
|
235 |
|
236 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
237 \begin{frame}[c] |
|
238 \frametitle{Natural Numbers} |
|
239 |
|
240 \Large |
|
241 \bl{$\mathbb{N}$} \bl{$\dn$} \bl{$\{0, 1, 2, 3, .......\}$}\bigskip\pause |
|
242 |
|
243 \bl{$A$} is \alert{countable} iff \bl{$|A| \leq |\mathbb{N}|$} |
|
244 |
|
245 \end{frame} |
|
246 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
247 |
|
248 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
249 \begin{frame}[c] |
|
250 \frametitle{First Question} |
|
251 |
|
252 \Large |
|
253 \bl{$|\mathbb{N} - \{0\}| \;\;\;\alert{?}\;\;\; |\mathbb{N}| $}\bigskip\bigskip |
|
254 |
|
255 \large |
|
256 \bl{$\geq$} or \bl{$\leq$} or \bl{$=$} ? |
|
257 \bigskip\bigskip\bigskip\pause |
|
258 |
|
259 \bl{$x$ $\mapsto$ $x + 1$},\\ \bl{$|\mathbb{N} - \{0\}|$ $=$ |
|
260 $|\mathbb{N}|$} |
|
261 \end{frame} |
|
262 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
263 |
|
264 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
265 \mode<presentation>{ |
|
266 \begin{frame}[c] |
|
267 |
|
268 \Large |
|
269 \bl{$|\mathbb{N} - \{0, 1\}| \;\;\;\alert{?}\;\;\; |\mathbb{N}| $}\bigskip\pause |
|
270 |
|
271 \bl{$|\mathbb{N} - \mathbb{O}| \;\;\;\alert{?}\;\;\; |\mathbb{N}| $}\bigskip\bigskip |
|
272 |
|
273 \normalsize |
|
274 \bl{$\mathbb{O}$} $\dn$ odd numbers\quad \bl{$\{1,3,5......\}$}\\ \pause |
|
275 \bl{$\mathbb{E}$} $\dn$ even numbers\quad \bl{$\{0,2,4......\}$}\\ |
|
276 \end{frame}} |
|
277 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
278 |
|
279 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
280 \mode<presentation>{ |
|
281 \begin{frame}[c] |
|
282 |
|
283 \Large |
|
284 \bl{$|\mathbb{N} \cup \mathbb{-N}| \;\;\;\alert{?}\;\;\; |\mathbb{N}| $}\bigskip\bigskip |
|
285 |
|
286 |
|
287 \normalsize |
|
288 \bl{$\mathbb{\phantom{-}N}$} $\dn$ positive numbers\quad \bl{$\{0,1,2,3,......\}$}\\ |
|
289 \bl{$\mathbb{-N}$} $\dn$ negative numbers\quad \bl{$\{0,-1,-2,-3,......\}$}\\ |
|
290 \end{frame}} |
|
291 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
292 |
|
293 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
294 \mode<presentation>{ |
|
295 \begin{frame}[c] |
|
296 |
|
297 \Large |
|
298 \bl{$A$} is \alert{countable} if there exists an injective \bl{$f : A \rightarrow \mathbb{N}$}\bigskip |
|
299 |
|
300 \bl{$A$} is \alert{uncountable} if there does not exist an injective \bl{$f : A \rightarrow \mathbb{N}$}\bigskip\bigskip |
|
301 |
|
302 |
|
303 countable: \bl{$|A| \leq |\mathbb{N}|$}\\ |
|
304 uncountable: \bl{$|A| > |\mathbb{N}|$}\pause\bigskip |
|
305 |
|
306 |
|
307 Does there exist such an \bl{$A$} ? |
|
308 |
|
309 \end{frame}} |
|
310 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
311 |
|
312 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
313 \mode<presentation>{ |
|
314 \begin{frame}[c] |
|
315 \frametitle{Hilbert's Hotel} |
|
316 |
|
317 \begin{center} |
|
318 \includegraphics[scale=0.8]{../pics/hilberts_hotel.jpg} |
|
319 \end{center} |
|
320 |
|
321 \begin{itemize} |
|
322 \item \ldots has as many rooms as there are natural numbers |
|
323 \end{itemize} |
|
324 |
|
325 \end{frame}} |
|
326 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
327 |
|
328 |
|
329 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
330 \begin{frame}[t] |
|
331 \frametitle{\begin{tabular}{c}Real Numbers between\\[-2mm] 0 and 1\end{tabular}} |
|
332 |
|
333 \begin{center} |
|
334 \begin{tikzpicture} |
|
335 \draw [fill, color=black!50] (1,4) rectangle (2, 3); |
|
336 \draw [fill, color=black!50] (2,3) rectangle (3, 2); |
|
337 \draw [fill, color=black!50] (3,2) rectangle (4, 1); |
|
338 \draw [fill, color=black!50] (4,1) rectangle (5, 0); |
|
339 \draw (0, 0) grid (8, 5); |
|
340 \draw [line width = 1.mm] (1,0) -- (1, 5); |
|
341 \draw [line width = 1.mm] (0, 4) -- (8, 4); |
|
342 \draw (0.5,3.5) node {$1$}; |
|
343 \draw (0.5,2.5) node {$2$}; |
|
344 \draw (0.5,1.5) node {$3$}; |
|
345 \draw (0.5,0.5) node {$4$}; |
|
346 |
|
347 \draw (1.5,3.5) node {\only<1>{$3$}\only<2->{$4$}}; |
|
348 \draw (2.5,3.5) node {$3$}; |
|
349 \draw (3.5,3.5) node {$3$}; |
|
350 \draw (4.5,3.5) node {$3$}; |
|
351 \draw (5.5,3.5) node {$3$}; |
|
352 \draw (6.5,3.5) node {$3$}; |
|
353 \draw (7.5,3.5) node {$\ldots$}; |
|
354 |
|
355 \draw (1.5,2.5) node {$1$}; |
|
356 \draw (2.5,2.5) node {\only<1-2>{$2$}\only<3->{$3$}}; |
|
357 \draw (3.5,2.5) node {$3$}; |
|
358 \draw (4.5,2.5) node {$4$}; |
|
359 \draw (5.5,2.5) node {$5$}; |
|
360 \draw (6.5,2.5) node {$6$}; |
|
361 \draw (7.5,2.5) node {$7$}; |
|
362 |
|
363 \draw (1.5,1.5) node {$0$}; |
|
364 \draw (2.5,1.5) node {$1$}; |
|
365 \draw (3.5,1.5) node {\only<1-3>{$0$}\only<4->{$1$}}; |
|
366 \draw (4.5,1.5) node {$1$}; |
|
367 \draw (5.5,1.5) node {$0$}; |
|
368 \draw (6.5,1.5) node {$\ldots$}; |
|
369 |
|
370 \draw (1.5,0.5) node {$7$}; |
|
371 \draw (2.5,0.5) node {$8$}; |
|
372 \draw (3.5,0.5) node {$5$}; |
|
373 \draw (4.5,0.5) node {\only<1-4>{$3$}\only<5->{$4$}}; |
|
374 \draw (5.5,0.5) node {$9$}; |
|
375 \draw (6.5,0.5) node {$\ldots$}; |
|
376 |
|
377 \draw (1.5,-0.5) node {$\ldots$}; |
|
378 \draw (8.5,3.5) node {$\ldots$}; |
|
379 \end{tikzpicture} |
|
380 \end{center} |
|
381 \mbox{}\\[-20mm]\mbox{} |
|
382 |
|
383 \onslide<6->{ |
|
384 \begin{center} |
|
385 \Large\bl{$|\mathbb{N}| < |R|$} |
|
386 \end{center} |
|
387 } |
|
388 |
|
389 \end{frame} |
|
390 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
391 |
|
392 |
|
393 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
394 \mode<presentation>{ |
|
395 \begin{frame}[t] |
|
396 \frametitle{The Set of Problems} |
|
397 |
|
398 $\aleph_0$ |
|
399 |
|
400 \begin{center} |
|
401 \begin{tikzpicture} |
|
402 \draw [fill, color=black!50] (1,4) rectangle (2, 3); |
|
403 \draw [fill, color=black!50] (2,3) rectangle (3, 2); |
|
404 \draw [fill, color=black!50] (3,2) rectangle (4, 1); |
|
405 \draw [fill, color=black!50] (4,1) rectangle (5, 0); |
|
406 \draw (0, 0) grid (8, 5); |
|
407 \draw [line width = 1.mm] (1,0) -- (1, 5); |
|
408 \draw [line width = 1.mm] (0, 4) -- (8, 4); |
|
409 \draw (0.5,3.5) node {$1$}; |
|
410 \draw (0.5,2.5) node {$2$}; |
|
411 \draw (0.5,1.5) node {$3$}; |
|
412 \draw (0.5,0.5) node {$4$}; |
|
413 |
|
414 \draw (1.5,4.5) node {$0$}; |
|
415 \draw (2.5,4.5) node {$1$}; |
|
416 \draw (3.5,4.5) node {$2$}; |
|
417 \draw (4.5,4.5) node {$3$}; |
|
418 \draw (5.5,4.5) node {$4$}; |
|
419 \draw (6.5,4.5) node {$5$}; |
|
420 \draw (7.5,4.5) node {$\ldots$}; |
|
421 |
|
422 \draw (1.5,3.5) node {$0$}; |
|
423 \draw (2.5,3.5) node {$1$}; |
|
424 \draw (3.5,3.5) node {$0$}; |
|
425 \draw (4.5,3.5) node {$1$}; |
|
426 \draw (5.5,3.5) node {$0$}; |
|
427 \draw (6.5,3.5) node {$1$}; |
|
428 \draw (7.5,3.5) node {$\ldots$}; |
|
429 |
|
430 \draw (1.5,2.5) node {$0$}; |
|
431 \draw (2.5,2.5) node {$0$}; |
|
432 \draw (3.5,2.5) node {$0$}; |
|
433 \draw (4.5,2.5) node {$1$}; |
|
434 \draw (5.5,2.5) node {$1$}; |
|
435 \draw (6.5,2.5) node {$0$}; |
|
436 \draw (7.5,2.5) node {$0$}; |
|
437 |
|
438 \draw (1.5,1.5) node {$0$}; |
|
439 \draw (2.5,1.5) node {$0$}; |
|
440 \draw (3.5,1.5) node {$0$}; |
|
441 \draw (4.5,1.5) node {$0$}; |
|
442 \draw (5.5,1.5) node {$0$}; |
|
443 \draw (6.5,1.5) node {$\ldots$}; |
|
444 |
|
445 \draw (1.5,0.5) node {$1$}; |
|
446 \draw (2.5,0.5) node {$1$}; |
|
447 \draw (3.5,0.5) node {$0$}; |
|
448 \draw (4.5,0.5) node {$1$}; |
|
449 \draw (5.5,0.5) node {$1$}; |
|
450 \draw (6.5,0.5) node {$\ldots$}; |
|
451 |
|
452 \draw (1.5,-0.5) node {$\ldots$}; |
|
453 \draw (8.5,3.5) node {$\ldots$}; |
|
454 |
|
455 \end{tikzpicture} |
|
456 \end{center} |
|
457 |
|
458 |
|
459 \onslide<2>{ |
|
460 \begin{center} |
|
461 \large \bl{|Progs| $=$ $|\mathbb{N}|$ $<$ |Probs|} |
|
462 \end{center} |
|
463 } |
|
464 |
|
465 |
|
466 \end{frame}} |
|
467 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
468 |
|
469 |
|
470 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
471 \mode<presentation>{ |
|
472 \begin{frame}[c] |
|
473 \frametitle{Halting Problem} |
|
474 |
|
475 \large |
|
476 Assume a program \bl{$H$} that decides for all programs \bl{$A$} and all |
|
477 input data \bl{$D$} whether\bigskip |
|
478 |
|
479 \begin{itemize} |
|
480 \item \bl{$H(A, D) \dn 1$} iff \bl{$A(D)$} terminates |
|
481 \item \bl{$H(A, D) \dn 0$} otherwise |
|
482 \end{itemize} |
|
483 |
|
484 \end{frame}} |
|
485 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
486 |
|
487 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
488 \mode<presentation>{ |
|
489 \begin{frame}[c] |
|
490 \frametitle{Halting Problem (2)} |
|
491 |
|
492 \large |
|
493 Given such a program \bl{$H$} define the following program \bl{$C$}: |
|
494 for all programs \bl{$A$}\bigskip |
|
495 |
|
496 \begin{itemize} |
|
497 \item \bl{$C(A) \dn 0$} iff \bl{$H(A, A) = 0$} |
|
498 \item \bl{$C(A) \dn$ loops} otherwise |
|
499 \end{itemize} |
|
500 |
|
501 \end{frame}} |
|
502 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
503 |
|
504 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
505 \mode<presentation>{ |
|
506 \begin{frame}[c] |
|
507 \frametitle{Contradiction} |
|
508 |
|
509 |
|
510 \bl{$H(C, C)$} is either \bl{$0$} or \bl{$1$}. |
|
511 |
|
512 \begin{itemize} |
|
513 \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$} |
|
514 \item \bl{$H(C, C) = 0$} $\stackrel{\text{def}\,H}{\Rightarrow}$ \bl{$C(C)$} loops $\stackrel{\text{def}\,C}{\Rightarrow}$\\ |
|
515 \hspace{7cm}\bl{$H(C, C)=1$} |
|
516 \end{itemize} |
|
517 |
|
518 Contradiction in both cases. So \bl{$H$} cannot exist. |
|
519 |
|
520 \end{frame}} |
|
521 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
522 |
|
523 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
524 \mode<presentation>{ |
|
525 \begin{frame}[c] |
|
526 \frametitle{Take Home Points} |
|
527 \large |
|
528 |
|
529 \begin{itemize} |
|
530 \item there are sets that are more infinite than others\bigskip |
|
531 \item even with the most powerful computer we can imagine, there |
|
532 are problems that cannot be solved by any program\bigskip\bigskip |
|
533 |
|
534 \item in CS we actually hit quite often such problems (halting problem) |
|
535 \end{itemize} |
|
536 |
|
537 \end{frame}} |
|
538 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
539 |
|
540 |
|
541 \end{document} |
|
542 |
|
543 %%% Local Variables: |
|
544 %%% mode: latex |
|
545 %%% TeX-master: t |
|
546 %%% End: |
|
547 |