223 \end{textblock}} |
221 \end{textblock}} |
224 |
222 |
225 \end{frame}} |
223 \end{frame}} |
226 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
224 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
227 |
225 |
228 |
226 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
229 |
227 \begin{frame}[c] |
|
228 \frametitle{Compilers \& Boeings 777} |
|
229 |
|
230 First flight in 1994. They want to achieve triple redundancy in hardware |
|
231 faults.\bigskip |
|
232 |
|
233 They compile 1 Ada program to\medskip |
|
234 |
|
235 \begin{itemize} |
|
236 \item Intel 80486 |
|
237 \item Motorola 68040 (old Macintosh's) |
|
238 \item AMD 29050 (RISC chips used often in laser printers) |
|
239 \end{itemize}\medskip |
|
240 |
|
241 using 3 independent compilers.\bigskip\pause |
|
242 |
|
243 \small Airbus uses C and static analysers. Recently started using CompCert. |
|
244 |
|
245 \end{frame} |
|
246 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
247 |
|
248 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
249 \begin{frame}[c] |
|
250 |
|
251 {\Large\bf |
|
252 How many strings are in \bl{$L(a^*)$}?}\bigskip\pause |
|
253 |
|
254 \normalsize |
|
255 \begin{center} |
|
256 \begin{tabular}{llllll} |
|
257 \bl{$[]$} & \bl{$a$} & \bl{$aa$} & \bl{$aaa$} & \bl{$aaaa$} & \ldots\\ |
|
258 \bl{0} & \bl{1} & \bl{2} & \bl{3} & \bl{4} & \ldots |
|
259 \end{tabular} |
|
260 \end{center} |
|
261 |
|
262 \end{frame} |
|
263 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
264 |
|
265 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
266 \begin{frame}[c] |
|
267 |
|
268 \Large\bf There are more problems, than there are |
|
269 programs.\bigskip\bigskip\pause\\ |
|
270 |
|
271 There must be a problem for which there is no program. |
|
272 \end{frame} |
|
273 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
274 |
|
275 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
276 \begin{frame}[c] |
|
277 \frametitle{Subsets} |
|
278 |
|
279 \Large |
|
280 If \bl{$A \subseteq B$} then \bl{$A$} has fewer or equal elements |
|
281 than \bl{$B$}\bigskip\bigskip |
|
282 |
|
283 \Large |
|
284 \bl{$A \subseteq B$} and \bl{$B \subseteq A$}\bigskip |
|
285 |
|
286 then \bl{$A = B$} |
|
287 \end{frame} |
|
288 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
289 |
|
290 |
|
291 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
292 \begin{frame}[c] |
|
293 |
|
294 \begin{center} |
|
295 \begin{tikzpicture} |
|
296 |
|
297 \draw (-4,2.5) node [scale=2.5] (X) |
|
298 {\begin{tabular}{l} |
|
299 $\{$ |
|
300 \!\includegraphics[scale=0.02]{../pics/o1.jpg}, |
|
301 \includegraphics[scale=0.02]{../pics/o2.jpg}, |
|
302 \!\includegraphics[scale=0.02]{../pics/o3.jpg}, |
|
303 \includegraphics[scale=0.02]{../pics/o4.jpg}, |
|
304 \!\includegraphics[scale=0.027]{../pics/o5.jpg} |
|
305 $\}$ |
|
306 \end{tabular}}; |
|
307 |
|
308 \draw (-5.6,-2.5) node [scale=2.5] (Y) |
|
309 {\begin{tabular}{l} |
|
310 $\{$ |
|
311 \!\includegraphics[scale=0.059]{../pics/a1.jpg}, |
|
312 \includegraphics[scale=0.048]{../pics/a2.jpg}, |
|
313 \includegraphics[scale=0.02]{../pics/a3.jpg} |
|
314 $\}$ |
|
315 \end{tabular}}; |
|
316 |
|
317 \draw (0,1.5) node (X1) {5 elements}; |
|
318 \draw (0,-3.5) node (y1) {3 elements}; |
|
319 \end{tikzpicture} |
|
320 \end{center} |
|
321 |
|
322 \end{frame} |
|
323 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
324 |
|
325 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
326 \begin{frame}[c] |
|
327 \frametitle{Newton vs Feynman} |
|
328 |
|
329 \begin{center} |
|
330 \begin{tabular}{cc} |
|
331 \includegraphics[scale=0.2]{../pics/newton.jpg} & |
|
332 \includegraphics[scale=0.2]{../pics/feynman.jpg}\\ |
|
333 classical physics & quantum physics |
|
334 \end{tabular} |
|
335 \end{center} |
|
336 \end{frame} |
|
337 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
338 |
|
339 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
340 \begin{frame}[c] |
|
341 \frametitle{The Goal of the Talk} |
|
342 \large |
|
343 \begin{itemize} |
|
344 \item show you that something very unintuitive happens with very large sets |
|
345 \bigskip\bigskip |
|
346 |
|
347 \item convince you that there are more {\bf problems} than {\bf programs} |
|
348 \end{itemize} |
|
349 \end{frame} |
|
350 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
351 |
|
352 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
353 \begin{frame}[t] |
|
354 % |
|
355 \begin{center} |
|
356 \begin{tikzpicture} |
|
357 |
|
358 \draw (-5,2.5) node [scale=2.3] (X) |
|
359 {\begin{tabular}{@ {\hspace{-3mm}}l} |
|
360 \bl{$B$ $=$ $\{$ |
|
361 \!\includegraphics[scale=0.02]{../pics/o1.jpg}, |
|
362 \includegraphics[scale=0.02]{../pics/o2.jpg}, |
|
363 \!\includegraphics[scale=0.02]{../pics/o3.jpg}, |
|
364 \includegraphics[scale=0.02]{../pics/o4.jpg}, |
|
365 \!\includegraphics[scale=0.027]{../pics/o5.jpg} |
|
366 $\}$} |
|
367 \end{tabular}}; |
|
368 |
|
369 \draw (-6.6,-0.5) node [scale=2.3] (Y) |
|
370 {\begin{tabular}{@ {\hspace{-3mm}}l} |
|
371 \bl{$A$ $=$ $\{$ |
|
372 \!\includegraphics[scale=0.059]{../pics/a1.jpg}, |
|
373 \includegraphics[scale=0.048]{../pics/a2.jpg}, |
|
374 \includegraphics[scale=0.02]{../pics/a3.jpg} |
|
375 $\}$} |
|
376 \end{tabular}}; |
|
377 |
|
378 \only<1>{\draw (-5, -3) node[scale=2] |
|
379 {\bl{$|A|$ $=$ $5$}, \bl{$|B|$ $=$ $3$}};} |
|
380 \only<2>{ |
|
381 \draw [->, line width=1mm, red] (-7.4, 0.2) -- (-6.1, 2.1); |
|
382 \draw [->, line width=1mm, red] (-5.8, 0.2) -- (-3.1, 2.1); |
|
383 \draw [->, line width=1mm, red] (-4.5, 0.2) -- (-7.6, 2.1); |
|
384 \draw (-5, -3) node[scale=2] {then \bl{$|A|$ $\le$ $|B|$}}; |
|
385 } |
|
386 \only<3>{ |
|
387 \draw [<-, line width=1mm, red] (-7.5, 0.2) -- (-6.1, 2.1); |
|
388 \draw [<-, line width=1mm, red] (-7.3, 0.2) -- (-3.1, 2.1); |
|
389 \draw [<-, line width=1mm, red] (-6, 0.2) -- (-7.5, 2.1); |
|
390 \draw [<-, line width=1mm, red] (-4.5, 0.2) -- (-4.5, 2.1); |
|
391 \draw [<-, line width=1mm, red] (-4.3, 0.2) -- (-1.3, 2.1); |
|
392 |
|
393 \draw (-5, -3) node[scale=1.5] {\small{}for \bl{$=$} |
|
394 has to be a {\bf one-to-one} mapping}; |
|
395 } |
|
396 |
|
397 |
|
398 \end{tikzpicture} |
|
399 \end{center} |
|
400 |
|
401 \end{frame} |
|
402 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
403 |
|
404 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
405 \begin{frame}[c] |
|
406 \frametitle{Cardinality} |
|
407 |
|
408 \Large |
|
409 \bl{$|A|$} $\dn$ ``how many elements''\bigskip\\ |
|
410 |
|
411 \bl{$A \subseteq B \Rightarrow |A| \leq |B|$}\bigskip\\\pause |
|
412 |
|
413 if there is an injective function \bl{$f: A \rightarrow B$} then \bl{$|A| \leq |B|$}\ |
|
414 |
|
415 \begin{center} |
|
416 \bl{\large$\forall x y.\; f(x) = f(y) \Rightarrow x = y$} |
|
417 \end{center} |
|
418 \end{frame} |
|
419 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
420 |
|
421 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
422 \begin{frame}[t] |
|
423 |
|
424 \begin{center} |
|
425 \begin{tikzpicture} |
|
426 |
|
427 \draw (-6.6,2.5) node [scale=2.3] (X) |
|
428 {\begin{tabular}{@ {\hspace{-3mm}}l} |
|
429 $A$ $=$ $\{$ |
|
430 \!\includegraphics[scale=0.02]{../pics/o1.jpg}, |
|
431 \includegraphics[scale=0.02]{../pics/o2.jpg}, |
|
432 \!\includegraphics[scale=0.02]{../pics/o3.jpg} |
|
433 $\}$ |
|
434 \end{tabular}}; |
|
435 |
|
436 \draw (-6.6,-0.5) node [scale=2.3] (Y) |
|
437 {\begin{tabular}{@ {\hspace{-3mm}}l} |
|
438 $B$ $=$ $\{$ |
|
439 \!\includegraphics[scale=0.059]{../pics/a1.jpg}, |
|
440 \includegraphics[scale=0.048]{../pics/a2.jpg}, |
|
441 \includegraphics[scale=0.02]{../pics/a3.jpg} |
|
442 $\}$ |
|
443 \end{tabular}}; |
|
444 \onslide<3->{\draw (-7, -3) node[scale=1.5] |
|
445 {then \bl{$|A|$ \alert{$=$} $|B|$}};} |
|
446 \only<1>{ |
|
447 \draw [->, line width=1mm, red] (-7.4, 0.2) -- (-6.1, 2.1); |
|
448 \draw [->, line width=1mm, red] (-5.8, 0.2) -- (-4.3, 2.1); |
|
449 \draw [->, line width=1mm, red] (-4.5, 0.2) -- (-7.6, 2.1); |
|
450 } |
|
451 \only<2->{ |
|
452 \draw [<-, line width=1mm, blue] (-7.5, 0.2) -- (-7.5, 2.1); |
|
453 \draw [<-, line width=1mm, blue] (-5.8, 0.2) -- (-4.3, 2.1); |
|
454 \draw [<-, line width=1mm, blue] (-4.5, 0.2) -- (-6.1, 2.1); |
|
455 } |
|
456 |
|
457 |
|
458 \end{tikzpicture} |
|
459 \end{center} |
|
460 |
|
461 \end{frame} |
|
462 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
463 |
|
464 |
|
465 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
466 \begin{frame}[c] |
|
467 \frametitle{Natural Numbers} |
|
468 |
|
469 \Large |
|
470 \bl{$\mathbb{N}$} \bl{$\dn$} \bl{$\{0, 1, 2, 3, .......\}$}\bigskip\pause |
|
471 |
|
472 \bl{$A$} is \alert{countable} iff \bl{$|A| \leq |\mathbb{N}|$} |
|
473 |
|
474 \end{frame} |
|
475 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
476 |
|
477 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
478 \begin{frame}[c] |
|
479 \frametitle{First Question} |
|
480 |
|
481 \Large |
|
482 \bl{$|\mathbb{N} - \{0\}| \;\;\;\alert{?}\;\;\; |\mathbb{N}| $}\bigskip\bigskip |
|
483 |
|
484 \large |
|
485 \bl{$\geq$} or \bl{$\leq$} or \bl{$=$} ? |
|
486 \bigskip\bigskip\bigskip\pause |
|
487 |
|
488 \bl{$x$ $\mapsto$ $x + 1$},\\ \bl{$|\mathbb{N} - \{0\}|$ $=$ |
|
489 $|\mathbb{N}|$} |
|
490 \end{frame} |
|
491 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
492 |
|
493 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
494 \mode<presentation>{ |
|
495 \begin{frame}[c] |
|
496 |
|
497 \Large |
|
498 \bl{$|\mathbb{N} - \{0, 1\}| \;\;\;\alert{?}\;\;\; |\mathbb{N}| $}\bigskip\pause |
|
499 |
|
500 \bl{$|\mathbb{N} - \mathbb{O}| \;\;\;\alert{?}\;\;\; |\mathbb{N}| $}\bigskip\bigskip |
|
501 |
|
502 \normalsize |
|
503 \bl{$\mathbb{O}$} $\dn$ odd numbers\quad \bl{$\{1,3,5......\}$}\\ \pause |
|
504 \bl{$\mathbb{E}$} $\dn$ even numbers\quad \bl{$\{0,2,4......\}$}\\ |
|
505 \end{frame}} |
|
506 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
507 |
|
508 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
509 \mode<presentation>{ |
|
510 \begin{frame}[c] |
|
511 |
|
512 \Large |
|
513 \bl{$|\mathbb{N} \cup \mathbb{-N}| \;\;\;\alert{?}\;\;\; |\mathbb{N}| $}\bigskip\bigskip |
|
514 |
|
515 |
|
516 \normalsize |
|
517 \bl{$\mathbb{\phantom{-}N}$} $\dn$ positive numbers\quad \bl{$\{0,1,2,3,......\}$}\\ |
|
518 \bl{$\mathbb{-N}$} $\dn$ negative numbers\quad \bl{$\{0,-1,-2,-3,......\}$}\\ |
|
519 \end{frame}} |
|
520 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
521 |
|
522 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
523 \mode<presentation>{ |
|
524 \begin{frame}[c] |
|
525 |
|
526 \Large |
|
527 \bl{$A$} is \alert{countable} if there exists an injective \bl{$f : A \rightarrow \mathbb{N}$}\bigskip |
|
528 |
|
529 \bl{$A$} is \alert{uncountable} if there does not exist an injective \bl{$f : A \rightarrow \mathbb{N}$}\bigskip\bigskip |
|
530 |
|
531 |
|
532 countable: \bl{$|A| \leq |\mathbb{N}|$}\\ |
|
533 uncountable: \bl{$|A| > |\mathbb{N}|$}\pause\bigskip |
|
534 |
|
535 |
|
536 Does there exist such an \bl{$A$} ? |
|
537 |
|
538 \end{frame}} |
|
539 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
540 |
|
541 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
542 \mode<presentation>{ |
|
543 \begin{frame}[c] |
|
544 \frametitle{Hilbert's Hotel} |
|
545 |
|
546 \begin{center} |
|
547 \includegraphics[scale=0.8]{../pics/hilberts_hotel.jpg} |
|
548 \end{center} |
|
549 |
|
550 \begin{itemize} |
|
551 \item \ldots has as many rooms as there are natural numbers |
|
552 \end{itemize} |
|
553 |
|
554 \end{frame}} |
|
555 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
556 |
|
557 |
|
558 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
559 \begin{frame}[t] |
|
560 \frametitle{\begin{tabular}{c}Real Numbers between\\[-2mm] 0 and 1\end{tabular}} |
|
561 |
|
562 \begin{center} |
|
563 \begin{tikzpicture} |
|
564 \draw [fill, color=black!50] (1,4) rectangle (2, 3); |
|
565 \draw [fill, color=black!50] (2,3) rectangle (3, 2); |
|
566 \draw [fill, color=black!50] (3,2) rectangle (4, 1); |
|
567 \draw [fill, color=black!50] (4,1) rectangle (5, 0); |
|
568 \draw (0, 0) grid (8, 5); |
|
569 \draw [line width = 1.mm] (1,0) -- (1, 5); |
|
570 \draw [line width = 1.mm] (0, 4) -- (8, 4); |
|
571 \draw (0.5,3.5) node {$1$}; |
|
572 \draw (0.5,2.5) node {$2$}; |
|
573 \draw (0.5,1.5) node {$3$}; |
|
574 \draw (0.5,0.5) node {$4$}; |
|
575 |
|
576 \draw (1.5,3.5) node {\only<1>{$3$}\only<2->{$4$}}; |
|
577 \draw (2.5,3.5) node {$3$}; |
|
578 \draw (3.5,3.5) node {$3$}; |
|
579 \draw (4.5,3.5) node {$3$}; |
|
580 \draw (5.5,3.5) node {$3$}; |
|
581 \draw (6.5,3.5) node {$3$}; |
|
582 \draw (7.5,3.5) node {$\ldots$}; |
|
583 |
|
584 \draw (1.5,2.5) node {$1$}; |
|
585 \draw (2.5,2.5) node {\only<1-2>{$2$}\only<3->{$3$}}; |
|
586 \draw (3.5,2.5) node {$3$}; |
|
587 \draw (4.5,2.5) node {$4$}; |
|
588 \draw (5.5,2.5) node {$5$}; |
|
589 \draw (6.5,2.5) node {$6$}; |
|
590 \draw (7.5,2.5) node {$7$}; |
|
591 |
|
592 \draw (1.5,1.5) node {$0$}; |
|
593 \draw (2.5,1.5) node {$1$}; |
|
594 \draw (3.5,1.5) node {\only<1-3>{$0$}\only<4->{$1$}}; |
|
595 \draw (4.5,1.5) node {$1$}; |
|
596 \draw (5.5,1.5) node {$0$}; |
|
597 \draw (6.5,1.5) node {$\ldots$}; |
|
598 |
|
599 \draw (1.5,0.5) node {$7$}; |
|
600 \draw (2.5,0.5) node {$8$}; |
|
601 \draw (3.5,0.5) node {$5$}; |
|
602 \draw (4.5,0.5) node {\only<1-4>{$3$}\only<5->{$4$}}; |
|
603 \draw (5.5,0.5) node {$9$}; |
|
604 \draw (6.5,0.5) node {$\ldots$}; |
|
605 |
|
606 \draw (1.5,-0.5) node {$\ldots$}; |
|
607 \draw (8.5,3.5) node {$\ldots$}; |
|
608 \end{tikzpicture} |
|
609 \end{center} |
|
610 \mbox{}\\[-20mm]\mbox{} |
|
611 |
|
612 \onslide<6->{ |
|
613 \begin{center} |
|
614 \Large\bl{$|\mathbb{N}| < |R|$} |
|
615 \end{center} |
|
616 } |
|
617 |
|
618 \end{frame} |
|
619 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
620 |
|
621 |
|
622 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
623 \mode<presentation>{ |
|
624 \begin{frame}[t] |
|
625 \frametitle{The Set of Problems} |
|
626 |
|
627 $\aleph_0$ |
|
628 |
|
629 \begin{center} |
|
630 \begin{tikzpicture} |
|
631 \draw [fill, color=black!50] (1,4) rectangle (2, 3); |
|
632 \draw [fill, color=black!50] (2,3) rectangle (3, 2); |
|
633 \draw [fill, color=black!50] (3,2) rectangle (4, 1); |
|
634 \draw [fill, color=black!50] (4,1) rectangle (5, 0); |
|
635 \draw (0, 0) grid (8, 5); |
|
636 \draw [line width = 1.mm] (1,0) -- (1, 5); |
|
637 \draw [line width = 1.mm] (0, 4) -- (8, 4); |
|
638 \draw (0.5,3.5) node {$1$}; |
|
639 \draw (0.5,2.5) node {$2$}; |
|
640 \draw (0.5,1.5) node {$3$}; |
|
641 \draw (0.5,0.5) node {$4$}; |
|
642 |
|
643 \draw (1.5,4.5) node {$0$}; |
|
644 \draw (2.5,4.5) node {$1$}; |
|
645 \draw (3.5,4.5) node {$2$}; |
|
646 \draw (4.5,4.5) node {$3$}; |
|
647 \draw (5.5,4.5) node {$4$}; |
|
648 \draw (6.5,4.5) node {$5$}; |
|
649 \draw (7.5,4.5) node {$\ldots$}; |
|
650 |
|
651 \draw (1.5,3.5) node {$0$}; |
|
652 \draw (2.5,3.5) node {$1$}; |
|
653 \draw (3.5,3.5) node {$0$}; |
|
654 \draw (4.5,3.5) node {$1$}; |
|
655 \draw (5.5,3.5) node {$0$}; |
|
656 \draw (6.5,3.5) node {$1$}; |
|
657 \draw (7.5,3.5) node {$\ldots$}; |
|
658 |
|
659 \draw (1.5,2.5) node {$0$}; |
|
660 \draw (2.5,2.5) node {$0$}; |
|
661 \draw (3.5,2.5) node {$0$}; |
|
662 \draw (4.5,2.5) node {$1$}; |
|
663 \draw (5.5,2.5) node {$1$}; |
|
664 \draw (6.5,2.5) node {$0$}; |
|
665 \draw (7.5,2.5) node {$0$}; |
|
666 |
|
667 \draw (1.5,1.5) node {$0$}; |
|
668 \draw (2.5,1.5) node {$0$}; |
|
669 \draw (3.5,1.5) node {$0$}; |
|
670 \draw (4.5,1.5) node {$0$}; |
|
671 \draw (5.5,1.5) node {$0$}; |
|
672 \draw (6.5,1.5) node {$\ldots$}; |
|
673 |
|
674 \draw (1.5,0.5) node {$1$}; |
|
675 \draw (2.5,0.5) node {$1$}; |
|
676 \draw (3.5,0.5) node {$0$}; |
|
677 \draw (4.5,0.5) node {$1$}; |
|
678 \draw (5.5,0.5) node {$1$}; |
|
679 \draw (6.5,0.5) node {$\ldots$}; |
|
680 |
|
681 \draw (1.5,-0.5) node {$\ldots$}; |
|
682 \draw (8.5,3.5) node {$\ldots$}; |
|
683 |
|
684 \end{tikzpicture} |
|
685 \end{center} |
|
686 |
|
687 |
|
688 \onslide<2>{ |
|
689 \begin{center} |
|
690 \large \bl{|Progs| $=$ $|\mathbb{N}|$ $<$ |Probs|} |
|
691 \end{center} |
|
692 } |
|
693 |
|
694 |
|
695 \end{frame}} |
|
696 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
697 |
|
698 |
|
699 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
700 \mode<presentation>{ |
|
701 \begin{frame}[c] |
|
702 \frametitle{Halting Problem} |
|
703 |
|
704 \large |
|
705 Assume a program \bl{$H$} that decides for all programs \bl{$A$} and all |
|
706 input data \bl{$D$} whether\bigskip |
|
707 |
|
708 \begin{itemize} |
|
709 \item \bl{$H(A, D) \dn 1$} iff \bl{$A(D)$} terminates |
|
710 \item \bl{$H(A, D) \dn 0$} otherwise |
|
711 \end{itemize} |
|
712 |
|
713 \end{frame}} |
|
714 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
715 |
|
716 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
717 \mode<presentation>{ |
|
718 \begin{frame}[c] |
|
719 \frametitle{Halting Problem (2)} |
|
720 |
|
721 \large |
|
722 Given such a program \bl{$H$} define the following program \bl{$C$}: |
|
723 for all programs \bl{$A$}\bigskip |
|
724 |
|
725 \begin{itemize} |
|
726 \item \bl{$C(A) \dn 0$} iff \bl{$H(A, A) = 0$} |
|
727 \item \bl{$C(A) \dn$ loops} otherwise |
|
728 \end{itemize} |
|
729 |
|
730 \end{frame}} |
|
731 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
732 |
|
733 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
734 \mode<presentation>{ |
|
735 \begin{frame}[c] |
|
736 \frametitle{Contradiction} |
|
737 |
|
738 |
|
739 \bl{$H(C, C)$} is either \bl{$0$} or \bl{$1$}. |
|
740 |
|
741 \begin{itemize} |
|
742 \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$} |
|
743 \item \bl{$H(C, C) = 0$} $\stackrel{\text{def}\,H}{\Rightarrow}$ \bl{$C(C)$} loops $\stackrel{\text{def}\,C}{\Rightarrow}$\\ |
|
744 \hspace{7cm}\bl{$H(C, C)=1$} |
|
745 \end{itemize} |
|
746 |
|
747 Contradiction in both cases. So \bl{$H$} cannot exist. |
|
748 |
|
749 \end{frame}} |
|
750 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
751 |
|
752 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
753 \mode<presentation>{ |
|
754 \begin{frame}[c] |
|
755 \frametitle{Take Home Points} |
|
756 \large |
|
757 |
|
758 \begin{itemize} |
|
759 \item there are sets that are more infinite than others\bigskip |
|
760 \item even with the most powerful computer we can imagine, there |
|
761 are problems that cannot be solved by any program\bigskip\bigskip |
|
762 |
|
763 \item in CS we actually hit quite often such problems (halting problem) |
|
764 \end{itemize} |
|
765 |
|
766 \end{frame}} |
|
767 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
768 |
230 \end{document} |
769 \end{document} |
231 |
770 |
232 %%% Local Variables: |
771 %%% Local Variables: |
233 %%% mode: latex |
772 %%% mode: latex |
234 %%% TeX-master: t |
773 %%% TeX-master: t |