ࡱ> F'| 5xJFIFHHC    $.' ",#(7),01444'9=82<.342 `G9!1AQa"#Bq2RSbr?&:5zh`JKo+YwUUʑ^Q梤\ۭ "yr'q3:Nd܇k)#o -ǖ`}y{+uTNBI")*{Շ雭cM?*6L$%…}?-\HhZbTI0F](s!Էݕ' 6|Q◦iLoYr=q遍9[*G =IDsa%pJD35+ljGMEGXBdeվR].QK2*3h$=Uc*<#\sr}4^G%U5%\{0*iUvN9NsqX63kKEM4adDL:9U^at8v#_:K99厏CGw \S"Sst;mvHgUVZ+FM[l-6QǿӶ:-ޡ-(e\Mǘlv%Z䭐4@Κ:c֖ L!K8ڞ?7zkIXc99o_Kحφfު@ǖi^ܵώd*Wc_ 13M|;g֞jagT43|NPdccE(W [l+y&FƠ)8cvMnZ=7`} N%Xnov8ի(YvG~ĀI鮺S)W#jJ֕/?OR(L}cϧܞ#z<{|][7kqHje3 ʹ l5l&J2B0yzi/T():~ 愪9T?N~NgɒstAsME (VT;O=/v2w.StL[x 3]W4WVdlHi5ۣ`Q;:N:^[zYuȟ< rI9w%j!lun*Dчf@PqtN΍: PM5Ble$WdE4m4`0_z ?{lHBx|iTЦeQ~K~.ޤDR32y3RuPLR0|~O]wgqR(QJ)6pt*;(ݱp?t]S<+&|>vn5uE8Bd.rbUnY$#'8j[h*UdO6>Ԁfh\nRvd)PWtxTҿc'9}F =U,P#'֮|9.0EK(UwÍGxKt#lx{il6$xlRqV,Ջ_&9V$8=-ʢ:YRZq%6KǞ=(H.1G3翘6~cqN8+nlgi⨼VS)җ^&"TT>@ jFZz7*@ߴUۦR*D2~SR٥38 exk٠FE=Ǿ]g\D"JFIFHHACD Systems Digital ImagingExifII*V^(ifHH02000101C    $.' ",#(7),01444'9=82<.342 `L8!1AQ"aq#B3R$2r?ɂ~ݍpiF2pv|\\˘-:3"5(2ƀ7نFhׁboi ,N_Ra$OcNNHaS*$nQn-qa $UH+J"Dt)\ Je+x̭`gl[z/EzB7#~ƽszP1*)7!4y#d1ȬXU(Y<vf_v件| kvӃTl03:N F>nIjPr큕GUm"pݘyʯ0N;h:fUͰ KY)pzQfr÷J @Ѵl|9$pY[A*ڱd`vjfy) 2eqYC~ V"?vߵ[F'3K#} (%փg"\?P6 ߆uȺ{Pld1TY {PU6&019F=9E1f>"&1zM;qojv6ZNӬ-XGdA޲ 3>>I626+`N4B[{YZ$r# n3Lv7Vl'[9rJԢ㳓#NU{=*X6 H?:P.BOI6NX{OyA 'IUBKgpin.tk;Sisr1hj,'{ ;{eT 4;~ԃ+4{I*.{ϩ; /].$`cӶ ңE†o/Rc`Rf;prO.Ϛbuj#Sn^`7sVr\^8(E=jSPrW3./bz 7\XhMƉy'x>llJ0 s63Q$ѶJ܊b wQ%y=oj ? FQ}.6dlfMSHRa /0]JvnaIC(aMSg'$NJP1?_Y(   K,Clip (MS_ClipArt_Gallery.50,Microsoft Clip Gallery8/ 00DTimes New Romanttw 0DComic Sans MSnttw 0B DSymbolans MSnttw 00DWingdings MSnttw 0E3F˸> -KZ g'g 'g  @n?" dd@  @@`` (! U  $  q,@0 13547698;:=<?>A@ CBEDFGHI KLPNNPSQTdST= WpZYX\]m_G`bdcefghijm~npo?R$'| 5x%$R$=Ǿ]g\D"M% _ж_ж     A@  A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||s " 0e@        @ABC DEEFGHIJK5%LMNOPQRSTUWYZ[ \]^_ `abN E5%  N E5%  N F   5%    !"?N@ABC DEFFGHIJK5%LMNOPQRSTUWYZ[ \]^_ `ab f3www___3f@g4idid< 0pppp@  <4BdBd@l 0tg47d7dd 0p@ pp<^ ʚ;a7ʚ;<4!d!d@l 0@<4dddd@l 0@0___PPT10 ___PPT9h/ 0L=4? %O =CsProof, Computation, Randomness, Games Kurt Gdel John von Neumann and Theoretical Computer ScienceRt(($$&$!$3@Avi Wigderson School of Mathematics Institute for Advanced StudyAA$ 4'Fundamental concepts:Proof vs. Truth Gdel s Incompleteness Theorem Computation and its limitations, Turing Efficient Computation Gdel s letter, the P vs. NP problem (artificial) Life, Intelligence Johnny s Cellular Automata Fault tolerance to errors, noise, infection. Expander graphs. Randomness Johnny tosses coins, Monte-Carlo, pseudorandom Game Strategy, Rationality, Johnny s Minimax Theorem d}Z $ . //l i,Mathematical statementsz1) For all x,y, (x+y)(x-y)=x2-y2 2) There are infinitely many primes 3) There are no x,y,z,n3, xn + yn = zn 4) Any even number is the sum of two primes Are they true? Can we prove them?B6 b HQg*ProofAxioms: self evident statements (eg 0 + 1 = 1 ) Deduction rules: simple, local (eg A, B AB ) A proof of statement T is a sequence A1, A2, & ,Ak, Ak+1& ., Ai, & , An=T, such that A1, A2, & ., Ak are axioms Each subsequent Ai is derived from two previous statements by a deduction rule. Verification is a simple mechanical procedure Truth of axioms implies truth of TFPlPRP 3  3  PP!0>/j-Truth vs. Proofl1) For all x,y, (x+y)(x-y)=x2-y2 2) There are infinitely many primes 3) There are no x,y,z,n3, xn + yn = zn 4) Even numbers are sum of two primes Are they true? Can we prove them?ZB&  b HJh+ Computation Inputs: available data (eg bits, numbers,& ) Operations: simple, local (eg x,y xy ) A computation of a function f is a sequence x1, x2, & ,xk, xk+1 & ., xi, & , xn=f(x1,& ,xk), such that x1, x2, & ,xk are inputs Each subsequent xi is computed from two previously computed values by a basic operation A finite program specifies which op to apply next 3  3  !/:k.Computation vs. ProofFathers of the  Theory of Computation : Church, Klenee, Post, Turing, Gdel& were all logicians. All introduced formal models of computation, e.g Turing machine (all turned out to be equivalent). Common feature: Simple, local steps Church-Turing thesis: These capture everything computable Can every function be computed? Turing s undecidability Theorem [1936]: Some functions are not computable! Proof: f(T) = 1 if statement T is true. f(T) = 0 if T is false. A program for f is essentially a complete proof system. Z533% (#98b0Y;Nn0Efficient ComputationNExample f(T,n)=1 if T has a proof of length n f(T,n)=0 otherwise. Algorithm for f: Try all possible sequences of length n; for each check if it proves T. Time complexity: 2n steps (terribly inefficient) Gdel s letter to von Neumann [1954]: Is there an efficient algorithm (n or n2 steps)? This is the P vs. NP question, The main problem of Computational Complexity Can creativity be efficiently automated??jZJI &    ,0fs5| Life, the Universe, and Everything Computation is everywhere&?%  Church-Turing Thesis:  Turing machine captures every realistic physical model of computation Computation: evolution of an environment via repeated application of simple, local rules (Almost) all Physics and Biology theories satisfy! Weather - Proteins in a cell - magnetization Ant hills - Fish schools - fission Brain - Populations - burning fire Epidemics - Regeneration Everything is updated in parallel!Z3-Z-Z#-Z3J 3:#p24Johnny s Cellular Automata q3 Evolution  t6Artificial Life? Intelligence?&$$> Model dynamics of biology, physics, ecology systems Emergence of Patterns, Chaos, Life, Intelligence& von Neumann s motivation: self reproduction Can a pattern  give birth to another like it (etc..)? Conway s  Game of Life : slightly different rule Can self reproduce (is it alive?) Can list prime numbers in order (intelligent?) Undecidable to tell if it stabilizes All because it is& .a universal Turing MachineZv-Z.-ZhJ.M H{:1Reliable computation from unreliable components N2$$ $ $$ v81Reliable computation from unreliable components N2$$ $ $$ |;-Best neighborhood structure: Expander graphs2.$$$ }<Johnny tosses coinsHow to analyze Neutron diffusion? Ulam, von Neumann, Metropolis& : The Monte-Carlo method The computation can use independent, unbiased coin tosses 011101001111100100001& Probabilistic Algorithms  a major field Seem incredibly powerful: Statistical Physics, Algebra, Geometry, Group Theory, Optimization& Can randomness speed up (efficient) computations? Theorem: No speed-up if  P`"NP !Z"!Ql1"b~=Johnny tosses coinsWhere do we take the random bits from? Generate deterministically Pseudo-random generators  anyone who is trying to generate random numbers by deterministic means is, of course, living in a state of sin What is randomness? Hardness vs. Randomness From nature (radioactive decay, weather, stock market fluctuation, Internet traffic) Weak random sources: biased, correlated bits Randomness extraction: make it unbiased, indep 'P" P" PV" Po" P'3r1 P3V>Johnny plays gamesvon Neumann 1928: The minimax Theorem von Neumann & Morgenstern 1944: Game Theory Make conflicts in Economics, Politics, War, and everyday life, amenable to mathematical analysis Given a conflict, is there always a rational solution? 2-person zero-sum games: YES [von Neumann 1928] n-person strategic games: YES [Nash 1950] Minimax Theorem = Duality of Linear Programming Used in Optimization, analyzing prob algorithms,& Algorithmic Game Theory:  rational Turing machinesZo7 d>'IB@  /P4  ly !#X   0` ̙33` ` ff3333f` 333MMM` f` f` 3` >?" dd@,|?" dd@   " @ ` n?" dd@   @@``PR    @ ` ` p>> jb(    6p "P  T Click to edit Master title style! !$  0\ "  RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  0( "``  X*  0\ "`   Z*  0 "`   Z*H  0޽h ? Default Design 0 zr`\ (  \ \ 0XF P   F P*   \ 0TF    F R*  d \ c $ ?  F \ 0F  @ F RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S \ 6lF `P  F P*   \ 6hF `  F R*  H \ 0޽h ? ̙3380___PPT10.`+  0 RJ0(     0hF"`p  F l  C hF@ `PP F L  C $A godel@[H  C AvonppH  0޽h ? ̙33y___PPT10Y+D='  = @B +  0 P(  r  S 0F  L   S FP <$ 0 F H  0޽h ? 3fy___PPT10Y+[W_D'  = @B D' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*0%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*0X%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*X%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* F%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*F|%(+8+0+0 +\  0 \(  x  c $9L`  L   c $:L  <$ 0 L H  0޽h ? 3f80___PPT10+[W_D'  = @B Dw' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*!%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*!E%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*En%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*n%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(+8+0+0 +y  0 `0(  x  c $HL`  L x  c $IL   L H  0޽h ? 3fy___PPT10Y+D='  = @B +_  0 - %  (  x  c $8ZL`  L x  c $D  L ^   `HiL_ж_ж ?"6@ NNN?NR  True Trivial, 0 -KZ34 g'g 'gb   ``mL_ж_ж ?"6@ NNN?NR True Euclid -300,0 -KZ3 4 g'g 'ga   `yL_ж_ж ?"6@ NNN?NR True Wiles 1995,0 -KZ3 4 g'g 'g   `4|L_ж_ж ?"6@ NNN?NR ?? Goldbach conjecture,0 -KZ34 g'g 'g  TL_ж_ж ?"6@ NNN?N ,$@ 0 &Can every true statement be proved? Is there a complete proof system? Gdel s Incompleteness Theorem [1931]: Some true statements cannot be proved!@0 -KZ2F''4 g'g 'gH  0޽h ? 3f___PPT10+hED'  = @B DQ' = @BA?%,( < +O%,( < +D' =%(Dh' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*$%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*$F%(D' =%(Dh' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*Fm%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*m%(+y  0 p0(  x  c $8L`  L x  c $L   L H  0޽h ? 3fy___PPT10Y+D='  = @B +O  0L0 \(  x  c $L`  L   c $L  <$ 0 L H  0޽h ? 3f ___PPT10+[W_D'  = @B DR' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*b%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*b%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*$%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%E%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*Em%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*m%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(+8+0+0 +7  0 \(  x  c $@L`  L   c $lL  <$ 0 L H  0޽h ? 3f ___PPT10+[W_D'  = @B DR' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*/%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*/Q%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*Q%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*2%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*2Q%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*Q~%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*~%(+8+0+0 +  0 0\(  x  c $Tp `  p    c $Tp   <$ 0 p  H  0޽h ? 3f___PPT10+[W_DN'  = @B D ' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*^%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*^%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*R%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*R%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(+8+0+0 +V  0 DDOR    `_ж_ж|?"6@`NNN?N  ?   `_ж_ж|?"6@`NNN?N  @   `_ж_ж|?"6@`NNN?N @ A   `_ж_ж|?"6@`NNN?N@`  B   `_ж_ж|?"6@`NNN?N`   C   `_ж_ж|?"6@`NNN?N   D   `_ж_ж|?"6@`NNN?NP 0Pp  E   `_ж_ж|?"6@`NNN?N0 0PP  F   `_ж_ж|?"6@`NNN?N0 PpP  G   `_ж_ж|?"6@`NNN?N0 pP  H   `_ж_ж|?"6@`NNN?NP Ppp  I   `_ж_ж|?"6@`NNN?NP pp  J   `_ж_ж|?"6@`NNN?Np 0P  K   `_ж_ж|?"6@`NNN?Np Pp  L   `_ж_ж|?"6@`NNN?Np p  M   `_ж_ж 3Ԕ?"6@`NNN?NP Ppp  N   `_ж_ж|?"6@`NNN?N0 pP ,$D 0 Q  T Up _ж_ж ?"6@ NNN?N  A collection of cells e.g. a (large) lattice A neighborhood structure e.g cells  touching you Finite state space e.g  yellow or  green Update rule e.g. Majority vote Initial configuration e.g this one 0 -KZ20-KZ20 -KZ20-KZ20 -KZ20-KZ2 0 -KZ20-KZ20 -KZ20-KZ23 >L,O 4 g'g 'gH   0޽h ? 3f___PPT10+XD' = @B Dv' = @BA?%,( < +O%,( < +D' =%(D' =%(D0' =4@BBBB%(D' =0l9 CCBB*<3<*M D' =%(D' =%(D/' =4@BB@BB%()?)?D' =.K7 BBBBB]M 3.33333E-6 1.7341E-7 L 3.33333E-6 -0.06659 *3>*B ppt_xB ppt_y=@0BBAApBBB `<*M D' =%(Dy' =%(D!' =4@BB?BB%()?)?Du' =.=7 BBBBBOM 3.33333E-6 -0.06659 L 0.05 -0.06659 *3>*B ppt_xB ppt_y=@0BBAApBB<B<*M D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*N %(D' =-o6Bdissolve*<3<*N D' =%(D' =%(D1' =4@BB BB%(D' =-o6Bdissolve*<3<*N D' =1:Bhidden*o3>+B#style.visibility<*N %(D1' =4@BB BB%(D' =-o6Bdissolve*<3<*M D' =1:Bhidden*o3>+B#style.visibility<*M %(+aq  0 +G#GRSF(  x  c $Hp   p  5F      @@ @@   `_ж_ж|?"6@`NNN?N    `_ж_ж|?"6@`NNN?N    `_ж_ж|?"6@`NNN?N     `_ж_ж|?"6@`NNN?N     `_ж_ж|?"6@`NNN?N  @     `_ж_ж|?"6@`NNN?N@ `     `_ж_ж|?"6@`NNN?N`     `_ж_ж|?"6@`NNN?N     `_ж_ж|?"6@`NNN?N p     `_ж_ж|?"6@`NNN?N p    `_ж_ж|?"6@`NNN?N p     `_ж_ж|?"6@`NNN?Np     `_ж_ж|?"6@`NNN?N p @    `_ж_ж|?"6@`NNN?N@p `    `_ж_ж|?"6@`NNN?N` p    `_ж_ж|?"6@`NNN?N p    `_ж_ж|?"6@`NNN?N P p    `_ж_ж|?"6@`NNN?N P p    `_ж_ж|?"6@`NNN?N P p    `_ж_ж|?"6@`NNN?NP p    `_ж_ж|?"6@`NNN?N P @p    `_ж_ж|?"6@`NNN?N@P ` p    `_ж_ж|?"6@`NNN?N` P p    `_ж_ж|?"6@`NNN?N P p    `_ж_ж|?"6@`NNN?N 0 P    `_ж_ж|?"6@`NNN?N 0 P    `_ж_ж|?"6@`NNN?N 0 P    `_ж_ж|?"6@`NNN?N0 P     `_ж_ж|?"6@`NNN?N 0 @P  !  `_ж_ж|?"6@`NNN?N@0 ` P  "  `_ж_ж|?"6@`NNN?N` 0 P  #  `_ж_ж|?"6@`NNN?N 0 P  $  `_ж_ж|?"6@`NNN?N  0  %  `_ж_ж|?"6@`NNN?N  0  &  `_ж_ж|?"6@`NNN?N 0  '  `_ж_ж|?"6@`NNN?N 0  (  `_ж_ж|?"6@`NNN?N @0  )  `_ж_ж|?"6@`NNN?N@` 0  *  `_ж_ж|?"6@`NNN?N`  0  +  `_ж_ж|?"6@`NNN?N  0  ,  `_ж_ж|?"6@`NNN?N   -  `_ж_ж|?"6@`NNN?N   .  `_ж_ж|?"6@`NNN?N  /  `_ж_ж|?"6@`NNN?N  0  `_ж_ж|?"6@`NNN?N @ 1  `_ж_ж|?"6@`NNN?N@`  2  `_ж_ж|?"6@`NNN?N`   3  `_ж_ж|?"6@`NNN?N   4  `_ж_ж|?"6@`NNN?N   5  `_ж_ж|?"6@`NNN?N   6  `_ж_ж|?"6@`NNN?N  7  `_ж_ж|?"6@`NNN?N  8  `_ж_ж|?"6@`NNN?N @ 9  `_ж_ж|?"6@`NNN?N@`  :  `_ж_ж|?"6@`NNN?N`   ;  `_ж_ж|?"6@`NNN?N   <  `_ж_ж|?"6@`NNN?N   =  `_ж_ж|?"6@`NNN?N   >  `_ж_ж|?"6@`NNN?N  ?  `_ж_ж|?"6@`NNN?N  @  `_ж_ж|?"6@`NNN?N @ A  `_ж_ж|?"6@`NNN?N@`  B  `_ж_ж|?"6@`NNN?N`   C  `_ж_ж|?"6@`NNN?N   D  `_ж_ж|?"6@`NNN?N   E  `_ж_ж|?"6@`NNN?N  F  `_ж_ж|?"6@`NNN?N  G  `_ж_ж|?"6@`NNN?N  H  `_ж_ж|?"6@`NNN?N   I  `_ж_ж|?"6@`NNN?N   J  `_ж_ж|?"6@`NNN?N   K  `_ж_ж|?"6@`NNN?N   L  `_ж_ж|?"6@`NNN?N  C M Tp _ж_ж ?"6@ NNN?N N Time $0 -KZ2 34 g'g 'g? N Tp _ж_ж ?"6@ NNN?NN }0$0 -KZ2 34 g'g 'gs O Tp _ж_ж ?"6@ NNN?NP,$ 0 }1$0 -KZ2 34 g'g 'gs P Tp _ж_ж ?"6@ NNN?NN,$  0 }2$0 -KZ2 34 g'g 'gs Q Tp _ж_ж ?"6@ NNN?NN,$ 0 }3$0 -KZ2 34 g'g 'g S  `Tp _ж_ж ?"6@ NNN?N$ a,$ 0 6If green was an infection, how fast does it die out?\70 -KZ33.4 g'g 'gH  0޽h ? 3f))___PPT10)+|D('  = @B D'' = @BA?%,( < +O%,( < +Dr' =%(Dz ' =%(D1' =4@BB BB%(D' =-o6Bdissolve*<3<*GD' =1:Bhidden*o3>+B#style.visibility<*G%(D1' =4@BB BB%(D' =-o6Bdissolve*<3<*ED' =1:Bhidden*o3>+B#style.visibility<*E%(D1' =4@BB BB%(D' =-o6Bdissolve*<3<*JD' =1:Bhidden*o3>+B#style.visibility<*J%(D1' =4@BB BB%(D' =-o6Bdissolve*<3<*LD' =1:Bhidden*o3>+B#style.visibility<*L%(D>' =A@BB BB0B%(D' =-o6Bdissolve*<3<*ND' =1:Bhidden*o3>+B#style.visibility<*N%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*O%(D' =-o6Bdissolve*<3<*ODr' =%(Dz ' =%(D1' =4@BB BB%(D' =-o6Bdissolve*<3<*KD' =1:Bhidden*o3>+B#style.visibility<*K%(D1' =4@BB BB%(D' =-o6Bdissolve*<3<*DD' =1:Bhidden*o3>+B#style.visibility<*D%(D1' =4@BB BB%(D' =-o6Bdissolve*<3<*FD' =1:Bhidden*o3>+B#style.visibility<*F%(D1' =4@BB BB%(D' =-o6Bdissolve*<3<*ID' =1:Bhidden*o3>+B#style.visibility<*I%(D>' =A@BB BB0B%(D' =-o6Bdissolve*<3<*OD' =1:Bhidden*o3>+B#style.visibility<*O%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*P%(D' =-o6Bdissolve*<3<*PD' =%(D' =%(D1' =4@BB BB%(D' =-o6Bdissolve*<3<*HD' =1:Bhidden*o3>+B#style.visibility<*H%(D>' =A@BB BB0B%(D' =-o6Bdissolve*<3<*PD' =1:Bhidden*o3>+B#style.visibility<*P%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*Q%(D' =-o6Bdissolve*<3<*QDA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*S%(++0+N0 ++0+O0 ++0+O0 ++0+P0 ++0+P0 ++0+Q0 ++0+S0 +7  0 @\(  x  c $Lp `  p    c $Lp ` <$ 0 p  H  0޽h ? 3f ___PPT10+[W_D'  = @B DR' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*5%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*5g%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*h%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*M%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*Mr%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*r%(+8+0+0 +  0 <4<(  <x < c $} `  }   <  `_ж_ж|?"6@`NNN?N0P <  `_ж_ж|?"6@`NNN?N%0PE_  < Tl} _ж_ж ?"6@ NNN?N 0 correct incorrect40 -KZ2 34 g'g 'g <  `l} _ж_ж ?"6@ NNN?N V  &XOn correct inputs, with small probability, say 1%, the gate gives an incorrect output vW0 -KZ0 -KZ0 -KZ< 3 4 g'g 'g 8  0  <0  h < # l6} _ж_ж|?"6@`NNN?N@ ` $8 -KZ3 4 g'g 'gh < # lA} _ж_ж|?"6@`NNN?NPp $8 -KZ3 4 g'g 'gh < # lL} _ж_ж|?"6@`NNN?N  $8 -KZ3 4 g'g 'g[2  < # l+B#style.visibility<*<%(+a  0 fR^RpPo(Q(  (x ( c $c} `  }   8 0   ( h ( # lm} _ж_ж|?"6@`NNN?N   $8 -KZ3 4 g'g 'gh ( # lv} _ж_ж|?"6@`NNN?Np0 P $8 -KZ3 4 g'g 'gh ( # l} _ж_ж|?"6@`NNN?N   $8 -KZ3 4 g'g 'g2 ( Z_ж_ж ?"6@ NNN?N @ [2  ( # l } _ж_ж |?"6@`NNN?Np @  yv 8 -KZ4 g'g 'gB  ( T_ж_жD|?"0@NNN?NP  B  ( T_ж_жD|?"0@NNN?N`   B  ( T_ж_жD|?"0@NNN?N   F 0  (  h ( # l} _ж_ж|?"6@`NNN?N   $8 -KZ3 4 g'g 'gh ( # l4} _ж_ж|?"6@`NNN?Np0 P $8 -KZ3 4 g'g 'gh ( # lܮ} _ж_ж|?"6@`NNN?N   $8 -KZ3 4 g'g 'g2 ( Z_ж_ж ?"6@ NNN?N @ [2 ( # l8} _ж_ж |?"6@`NNN?Np @  yv 8 -KZ4 g'g 'gB ( T_ж_жD|?"0@NNN?NP  B ( T_ж_жD|?"0@NNN?N`   B ( T_ж_жD|?"0@NNN?N   F 0  )(   h *( # l} _ж_ж|?"6@`NNN?N   $8 -KZ3 4 g'g 'gh +( # l`} _ж_ж|?"6@`NNN?Np0 P $8 -KZ3 4 g'g 'gh ,( # l} _ж_ж|?"6@`NNN?N   $8 -KZ3 4 g'g 'g2 -( Z_ж_ж ?"6@ NNN?N @ [2 .( # l} _ж_ж |?"6@`NNN?Np @  yv 8 -KZ4 g'g 'gB /( T_ж_жD|?"0@NNN?NP  B 0( T_ж_жD|?"0@NNN?N`   B 1( T_ж_жD|?"0@NNN?N   F 0  2( @  h 3( # l} _ж_ж|?"6@`NNN?N   $8 -KZ3 4 g'g 'gh 4( # l<} _ж_ж|?"6@`NNN?Np0 P $8 -KZ3 4 g'g 'gh 5( # l0  _ж_ж|?"6@`NNN?N   $8 -KZ3 4 g'g 'g2 6( Z_ж_ж ?"6@ NNN?N @ [2 7( # l _ж_ж |?"6@`NNN?Np @  yv 8 -KZ4 g'g 'gB 8( T_ж_жD|?"0@NNN?NP  B 9( T_ж_жD|?"0@NNN?N`   B :( T_ж_жD|?"0@NNN?N   F 0  <( `@ h =( # l  _ж_ж|?"6@`NNN?N   $8 -KZ3 4 g'g 'gh >( # l+ _ж_ж|?"6@`NNN?Np0 P $8 -KZ3 4 g'g 'gh ?( # l% _ж_ж|?"6@`NNN?N   $8 -KZ3 4 g'g 'g2 @( Z_ж_ж ?"6@ NNN?N @ [2 A( # lA _ж_ж |?"6@`NNN?Np @  yv 8 -KZ4 g'g 'gB B( T_ж_жD|?"0@NNN?NP  B C( T_ж_жD|?"0@NNN?N`   B D( T_ж_жD|?"0@NNN?N   F 0  E( ` h F( # lHM _ж_ж|?"6@`NNN?N   $8 -KZ3 4 g'g 'gh G( # lW _ж_ж|?"6@`NNN?Np0 P $8 -KZ3 4 g'g 'gh H( # lQ _ж_ж|?"6@`NNN?N   $8 -KZ3 4 g'g 'g2 I( Z_ж_ж ?"6@ NNN?N @ [2 J( # lm _ж_ж |?"6@`NNN?Np @  yv 8 -KZ4 g'g 'gB K( T_ж_жD|?"0@NNN?NP  B L( T_ж_жD|?"0@NNN?N`   B M( T_ж_жD|?"0@NNN?N   F 0  N(  h O( # lxy _ж_ж|?"6@`NNN?N   $8 -KZ3 4 g'g 'gh P( # l _ж_ж|?"6@`NNN?Np0 P $8 -KZ3 4 g'g 'gh Q( # l} _ж_ж|?"6@`NNN?N   $8 -KZ3 4 g'g 'g2 R( Z_ж_ж ?"6@ NNN?N @ [2 S( # l _ж_ж |?"6@`NNN?Np @  yv 8 -KZ4 g'g 'gB T( T_ж_жD|?"0@NNN?NP  B U( T_ж_жD|?"0@NNN?N`   B V( T_ж_жD|?"0@NNN?N   F 0  W(   h X( # l _ж_ж|?"6@`NNN?N   $8 -KZ3 4 g'g 'gh Y( # ld _ж_ж|?"6@`NNN?Np0 P $8 -KZ3 4 g'g 'gh Z( # lĺ _ж_ж|?"6@`NNN?N   $8 -KZ3 4 g'g 'g2 [( Z_ж_ж ?"6@ NNN?N @ [2 \( # l _ж_ж |?"6@`NNN?Np @  yv 8 -KZ4 g'g 'gB ]( T_ж_жD|?"0@NNN?NP  B ^( T_ж_жD|?"0@NNN?N`   B _( T_ж_жD|?"0@NNN?N   j(  `_ж_ж|?"6@`NNN?N  ,$D 0 k(  `_ж_ж|?"6@`NNN?N,$D 0 l(  `_ж_ж|?"6@`NNN?N ` ,$D 0 m(  `_ж_ж|?"6@`NNN?NP p,$D 0 n(  `_ж_ж|?"6@`NNN?N ,$D 0 o(  `d _ж_ж ?"6@ NNN?N0 ,$ 0 - Fraction of errors increases every step. - Perform error reduction (e.g. by local majorities) -This is also unreliable computation, so we d better get rid of errors faster than they arrive.<0 -KZ-3c4 g'g 'gH ( 0޽h ? 3f___PPT10+[D{'  = @B D6' = @BA?%,( < +O%,( < +D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*j(%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*k(%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*l(%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*m(%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*n(%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*o(%(+8+0+o(0 +>.  0 l@D(  @x @ c $ `0      P@  ` _ж_ж ?"6@ NNN?N`M,$@ 0 Which (sparse) graphs are best? (infection dies out fastest) Fault-tolerant, highly connected Expander graphs von Neumann: Random graphs Explicit construction: major problem in Network Theory Number Theory Selberg: l1 (/H)3/16 Deligne: Ramanujan Conjecture(q0 -KZ0 -KZ0 -KZa 4j   4 g'g 'g8 pp   k@  R@  `_ж_ж |?"6@`NNN?NP  ]@  `_ж_ж|?"6@`NNN?Npp ^@  `_ж_ж|?"6@`NNN?Nu _@  `_ж_ж|?"6@`NNN?N   a@  `_ж_ж|?"6@`NNN?N   b@  `_ж_ж|?"6@`NNN?Np c@  `_ж_ж|?"6@`NNN?Np   d@  `_ж_ж|?"6@`NNN?N p  e@  `_ж_ж|?"6@`NNN?N   8 `  l@ `` S@  `_ж_ж |?"6@`NNN?N`0  T@  `_ж_ж |?"6@`NNN?N P B U@ T_ж_жD|?"0@NNN?N B V@ T_ж_жD|?"0@NNN?NP` B W@ T_ж_жD|?"0@NNN?N0  B X@ T_ж_жD|?"0@NNN?NP0 `  [@  `_ж_ж|?"6@`NNN?N@`0 \@  `_ж_ж|?"6@`NNN?N`` `@  `_ж_ж|?"6@`NNN?Np  f@  `_ж_ж|?"6@`NNN?N0 g@  `_ж_ж|?"6@`NNN?N` h@  `_ж_ж|?"6@`NNN?N   i@  `_ж_ж|?"6@`NNN?N@p`  j@  `_ж_ж|?"6@`NNN?N`  H @ 0޽h ? 3f2*___PPT10 +D'  = @B D' = @BA?%,( < +O%,( < +D' =%(Dh' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*P@ %(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*P@ @%(D' =%(Dh' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*P@@a%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*P@aq%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*P@r%(D' =%(Dh' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*P@%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*P@%(DL' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*P@%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*P@%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*P@ %(+  0 FHt(  Hx H c $# `    FH <$  0P <$ 0   H H 0޽h ? 3f___PPT10+Ei_DN'  = @B D ' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*FH"%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*FH"C%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*FHCZ%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*FHZ%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*FH%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*FH2%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*FH2e%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*FHe%(+8+0+FH0 +   0 L^(  Lx L c $8 `    L <?  `0P   "p`PpH L 0޽h ? 3fy___PPT10Y+D='  = @B +e ! 0 p(  px p c $hF`  F  p <Q  0P<$ 0 F "p`PpH p 0޽h ? 3f ___PPT10+[W_D'  = @B DR' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p&%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p&R%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*pR%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*pD%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*pDt%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*pt%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p%(+8+0+p0 + # 0 K}(  L  C $A godelL t C $A godel8  |hT  C $A godel P  C Avon T  C $A godel (P  C Avon lT  C $A godel8P   C Avon|T   C $A godelLP   C AvonhT   C $A godelpP   C AvonT  C $A godel(P  C Avon lT  C $A godelhP  C Avon T  C $A godel  P  C Avon 0P  C Avon@T  C $A godelHP  C Avon,T  C $A godel4lP  C AvonPT  C $A godelP  C Avon0T L C $A godel P M C Avon L T N C $A godel T P O C Avon8 T P C $A godel,d P Q C AvonH T R C $A godelx P S C Avon T T C $A godel P U C Avon T V C $A godelT P W C Avon8 T X C $A godel  P Y C Avon  T Z C $A godel  P [ C Avon \ T \ C $A godel ( P ] C Avon l T ^ C $A godel< t P _ C AvonX  T ` C $A godel`  P a C Avon|  T b C $A godel  P c C Avon \ T d C $A godel P e C Avon  T f C $A godel $P g C Avon hT h C $A godel 4P i C Avon xT j C $A godelH P k C Avond T l C $A godell P m C Avon T n C $A godel $P o C Avon hT p C $A godeldP q C Avon T r C $A godel  P s C Avon ,P u C Avon<T v C $A godel DP w C Avon(T x C $A godel0hP y C AvonLT z C $A godelP { C Avon, }  `HF_ж_ж ?"6@ NNN?Nep `There is much more I haven t told you about.. B0 0 -KZ0XX4 g'g 'gH  0޽h ? 3fy___PPT10Y+D='  = @B + 0 zP(  X  C \   Fz  S XF\ @  F When short on time  efficiency shpiel Learning, knowledge, secreat, proof, random change their nature, $H  0޽h ? ̙33. 0 d\(  X  C \   \  S T \ @   Turing machine von Neumann s computer (and cellular automata) Are computers all powerful?$\LH  0޽h ? ̙3380___PPT10.!#0C\M- 0 ,](  ,X , C \    , S  \ @   _)Can we know if Goldbach is true or false?H , 0޽h ? ̙3380___PPT10.$Db< 0   T(  TX T C \    T S  \ @   For example  are two arithmetic programs identical as polynomials?H T 0޽h ? ̙3380___PPT10.$0K0/5 0 P`?(  `X ` C \    ` S H \ @   A-We need a parallel computational model - nextH ` 0޽h ? ̙3380___PPT10.$p-ܔ#: 0 `d3(  dX d C \    d S  \ @   5!Small part of a large computationH d 0޽h ? ̙3380___PPT10.$* j; 0 phz(  hX h C \    h S ܺ \ @   |hDeterministic objects in Number Theory look  random H h 0޽h ? ̙3380___PPT10.$= 0 |tl (  lX l C \   t l S $w \ @   Linear vs nonlinear generators Von Neumann s trick of unbiased coin from 2 ind biased ones> , H l 0޽h ? ̙3380___PPT10.$> 0 t(  t^ t S \     t c $Xȑ \ @   kLinear programming is a central concept of optimization Minimax is used to analyze probabilistic algorithms8-H t 0޽h ? ̙3380___PPT10.$@ 0 (  ^  S \   z  c $ϑ \ @   Linear vs nonlinear generators Von Neumann s trick of unbiased coin from 2 ind biased ones> , H  0޽h ? ̙3380___PPT10.$rxp^RЀ3ÿ lHbP  @AL G@;b bW< ]P^b (y;r>:R er0Yhb''l,$4g`,np !,Fs +vy{PHvmq#wOh+'0T `h  The Power of randomnessAvi Wigdersonuphill84Microsoft PowerPoint@ۓC @mi@ LB'GSg  )'    """)))UUUMMMBBB999|PP3f333f3333f3ffffff3f̙3ff333f333333333f33333333f33f3ff3f3f3f3333f33̙33333f333333f3333f3ffffff3f33ff3f3f3f3fff3ffffffffff3ffff̙fff3fffff3fff333f3f3ff3ff33f̙̙3̙ff̙̙̙3f̙3f333f3333f3ffffff3f̙3f3f3f333f3333f3ffffff3f̙3f3ffffffffff!___www4'A x(xKʦ """)))UUUMMMBBB999|PP3f3333f333ff3fffff3f3f̙f3333f3333333333f3333333f3f33ff3f3f3f3333f3333333f3̙33333f333ff3ffffff3f33f3ff3f3f3ffff3fffffffff3fffffff3f̙ffff3ff333f3ff33fff33f3ff̙3f3f3333f333ff3fffff̙̙3̙f̙̙̙3f̙3f3f3333f333ff3fffff3f3f̙3ffffffffff!___www\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\mmmCCCCmmmmmmmmmmmmmmmCmCmmCmmmmmmCCCmmmmmmmmmmCmmmCCCCmmmCmmmmmmmmCCmmCmmmmmCmCCmmmCmmCCCmCCCmmmmmmmmmmmmmmmmmmCCmCCCCCmmmmmmmmmmmmmmCmCmCmmmmCCCmmCmmmmmmmmmmmmCmmmmmmCCmmmmmmmmCmmmmmCmCmCmmmmCCCCCCmmmmmmmmmCmCmmmmmmCmmmmmmmmmCmCmmmmmCCCCCmmmmmCCmCCCmmmmmmmmCmmmmmCmCCmmmmmCCCmmmCmCmmmmmmmmCmCmmCmmCmCmCmCmCCCmCCCCCCmmmmmCmCmmCCmmCmmmCCmCCCCmCCCCmCmCCCCmmCCCCCCCCmCCCCmCCCCCCmmmmmCCCCCmCCCCCCmmmmCCCCCCCCCCCmmmmCCCCCmmCCCmmmmCmCCCmCCCCCCmmmCCCCCCCCCCmmmmmCCCCmCCCmmmmCCCmCCCCmCmmmCCmCCCCCCmmmCCCmCCCCCmCmmCCmmCCCCmmmmCmmCCCmmmmmmmCmmmmCCCmCCCCCmmmmmCCmmCmCmCCCmCCmmCmmCCCmmmmCCCmCCCCCCCCCmCCCCCCmmCCmmCCCmCCCmCCCCCCmCCCCCmmmCmCCCCCCmmCCCCCCCmmmmmCCCmmCCCCmmmmmmmmCCCCCmCCCCCCmCmmmmmCCCCmmmmmCCCCmCCCmmmmCCCCCCCmmmmCCCCCCCCmmCmmmmmCmmCCCCmmmmmmCCCCCmmmmmmCCmCCCCCCCCCmmmmmCCCCCCCCCCCmmmmmmmCCCCCCCCCCCCCmCCCCCCmCmCCCmCmCCCCCCCCCCCCCCCCCCCCCCCmmmmmmCmmmmmCmCmCmm՜.+,0     On-screen Show IAS-Math  Times New RomanComic Sans MSSymbol WingdingsDefault DesignMicrosoft Clip GallerytProof, Computation, Randomness, Games Kurt Gdel John von Neumann and Theoretical Computer ScienceFundamental concepts:Mathematical statementsProofTruth vs. Proof ComputationComputation vs. ProofEfficient Computation?Life, the Universe, and Everything Computation is everywhereJohnnys Cellular Automata EvolutionArtificial Life? Intelligence?2Reliable computation from unreliable components 2Reliable computation from unreliable components .Best neighborhood structure: Expander graphsJohnny tosses coinsJohnny tosses coinsJohnny plays games Slide 19  Fonts UsedDesign TemplateEmbedded OLE Servers Slide Titles_^uphilluphill  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxy{|}~Root EntrydO)PicturesCurrent UserSummaryInformation(zTPowerPoint Document( DocumentSummaryInformation8