This preview shows page 1-2-3-4-5-6-7-50-51-52-53-54-55-56-100-101-102-103-104-105-106 out of 106 pages.
Slide Number 1Slide Number 2Slide Number 3Ideas from the courseThe Ideal Computer: no bound on amount of memory no bound on amount of timeInfinite RAM ModelHere’s a programHere’s a programHere’s a programHere’s a programSlide Number 11An Ideal ComputerPrinting Out An Infinite Sequence..Computable Real NumbersDescribable NumbersSlide Number 16Computable describableComputable describableSlide Number 19Slide Number 20Little SusieLittle JohnnyLittle Susie and Little JohnnySusie’s mistakeSusie’s mistakeCorrespondence PrincipleCorrespondence DefinitionGeorg Cantor (1845-1918)Cantor’s Definition (1874)Cantor’s Definition (1874)Do N and E have the same cardinality?Slide Number 32Slide Number 33Slide Number 34Cantor’s Definition (1874)Slide Number 36Do N and Z have the same cardinality?Slide Number 38Slide Number 39Transitivity LemmaTransitivity LemmaDo N and Q have the same cardinality?Slide Number 43Slide Number 44Slide Number 45Theorem: N and NxN have the same cardinalityTheorem: N and NxN have the same cardinalityTheorem: N and NxN have the same cardinalityDefining 1-1 onto f: N -> NxNSlide Number 50Slide Number 51Slide Number 52Hold it!Hold it!Hold it!Hold it!Hold it!Hold it!Cantor-Bernstein-SchroederCantor-Bernstein-SchroederSlide Number 61Injection from Q to NInjection from Q to NCantor-Bernstein-SchroederCountable SetsDo N and R have the same cardinality?Slide Number 67Slide Number 68Slide Number 69Theorem: The set of reals between 0 and 1 is not countable.Theorem: The set of reals between 0 and 1 is not countable.Slide Number 72Slide Number 73Slide Number 74Slide Number 75Slide Number 76Slide Number 77Slide Number 78Slide Number 79Diagonalized!Slide Number 81Slide Number 82Slide Number 83Back to the questions we were asking earlierSlide Number 85Standard NotationTheorem: Every infinite subset S of S* is countableStringing Symbols TogetherSlide Number 89Slide Number 90Slide Number 91Slide Number 92Slide Number 93Slide Number 94Definition: Power SetSlide Number 96Slide Number 97Slide Number 98Slide Number 99Slide Number 100Slide Number 101Slide Number 102Slide Number 103Slide Number 104Little Susie and Little JohnnySlide Number 10615-251Great Theoretical Ideas in Computer ScienceaboutAWESOMESomeGeneratingFunctionsProbability15-251Great Theoretical Ideas in Computer ScienceaboutAWESOMESomeGeneratingFunctionsProbabilityInfinity15-251What Little Susie Should’ve Said to Little JohnnyIdeas from the courseInductionNumbersFinite Counting and ProbabilityA hint of the infiniteInfinite row of dominoesInfinite sums (Generating functions!!)Infinite choice trees, and infinite probability Infinite tapesThe Ideal Computer:no bound on amount of memoryno bound on amount of timeIdeal Computer is defined as a computer with infinite RAM. You can run a Java program and never have any overflow, or out of memory errors.Infinite RAM ModelPlatonic Version:One memory location for each natural number 0, 1, 2, …Aristotelian Version:Whenever you run out of memory, the computer contacts the factory. A maintenance person is flown by helicopter and attaches 1000 Gig of RAM and all programs resume their computations, as if they had never been interrupted.Here’s a programSystem.out.print(“0.”);for(int i=0;true;i++){ System.out.print( getDigit(i) );}Here’s a programint getDigit(int i){return 3;}Here’s a programint getDigit(int i){return i%10;}Here’s a programCan we do:Pi?e?Any real?Chudnovsky brothersÅAn Ideal ComputerIt can be programmed to print out:2: 2.0000000000000000000000…1/3: 0.3333333333333333333333…φ: 1.6180339887498948482045…e: 2.7182818284590452353602…π: 3.14159265358979323846264…Printing Out An Infinite Sequence..A program P prints out the infinite sequence s0, s1, s2, …, sk, …if when P is executed on an ideal computer, it outputs a sequence of symbols such that-The kthsymbol that it outputs is sk-For every k, P eventually outputs the kthsymbol. I.e., the delay between symbol k and symbol k+1 is not infinite.Computable Real NumbersA real number R is computable if there is a program that prints out the decimal representation of R from left to right. Thus, each digit of R will eventually be output.Are all real numbers computable?Describable NumbersA real number R is describable if it can be denoted unambiguously by a finite piece of English text.2: “Two.”π: “The area of a circle of radius one.”Are all real numbers describable?Is every computable real number, also a describable real number?And what about the other way?Computable R: some program outputs RDescribable R: some sentence denotes RComputable ⇒ describableTheorem:Every computable real is also describableComputable ⇒ describableTheorem:Every computable real is also describableProof: Let R be a computable real that is output by a program P. The following is an unambiguousdescription of R:“The real number output by the following program:” PMORAL: A computer program can be viewed as a description of its output.Syntax: The text of the programSemantics: The real number output by PAre all reals describable?Are all reals computable?We saw thatcomputable ⇒describable, but do we also havedescribable ⇒computable?Questions we will answer in this (and next) lecture…Little SusieLittle JohnnyLittle Susie and Little JohnnyLittle Susie: I hate youLittle Johnny: I hate you moreLittle Susie: I hate you times a zillionLittle Johnny: I hate you times infinityPlus one!Little Susie: I hate you times infinitySusie’s mistakeInfinity: N.Infinity plus one : N U {cupcake} Can we establish a bijection between N and N U {cupcake}?Susie’s mistakeSure!f : N -> N U {cupcake}f(x) = cupcake if x=0f(x) = x-1 if x>00 1 021324354……Correspondence PrincipleIf two finite sets can be placed into 1-1 onto correspondence, then they have the same size.That is, if there exists a bijectionbetween them.Correspondence DefinitionIn fact, we can use the correspondence as the definition: Two finite sets are defined to have the same sizeif and only if they can be placed into 1-1 onto correspondence.Georg Cantor (1845-1918)Cantor’s Definition (1874)Two sets are defined to have the same sizeif and only if they can be placed into 1-1 onto correspondence.Cantor’s Definition (1874)Two sets are defined to have the same cardinalityif and only if they can be placed into 1-1 onto correspondence.Therefore, N and N U {cupcake} have the same cardinality.Do N and E have the same cardinality?N = { 0, 1,
View Full Document