Slide 1Ideas from the courseInfinite RAM ModelThe Ideal Computer: no bound on amount of memory no bound on amount of timeAn Ideal ComputerSlide 6Printing Out An Infinite Sequence..Computable Real NumbersDescribable NumbersSlide 10Computable describableSlide 12Slide 13Slide 14Correspondence PrincipleCorrespondence DefinitionGeorg Cantor (1845-1918)Cantor’s Definition (1874)Slide 19Do N and E have the same cardinality?Slide 21Slide 22Slide 23Slide 24Slide 25Do N and Z have the same cardinality?Slide 27Slide 28Transitivity LemmaSlide 30Do N and Q have the same cardinality?Slide 32Slide 33Slide 34Theorem: N and N×N have the same cardinalitySlide 36Slide 37Defining 1-1 onto f: N -> N×NSlide 39Slide 40Slide 41Cantor’s 1877 letter to Dedekind: “I see it, but I don't believe it! ”Countable SetsDo N and R have the same cardinality?Slide 45Slide 46Slide 47Theorem: The set R[0,1] of reals between 0 and 1 is not countable.Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Diagonalized!Slide 59Slide 60Slide 61Another diagonalization proofSlide 63Slide 64Back to the questions we were asking earlierSlide 66Standard NotationTheorem: Every infinite subset S of S* is countableStringing Symbols TogetherSlide 70Slide 71Slide 72Slide 73Slide 74Slide 75Definition: Power SetSlide 77Slide 78Slide 79Slide 80Slide 81Slide 82Slide 83Slide 84Slide 85Slide 86Slide 8715-251Great Theoretical Ideas in Computer ScienceIdeas from the courseInductionNumbersRepresentationFinite Counting and ProbabilityA hint of the infinite Infinite row of dominoes Infinite sums (formal power series) Infinite choice trees, and infinite probabilityInfinite 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.The 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.An Ideal ComputerIt can be programmed to print out:2: 2.0000000000000000000000…1/3: 0.33333333333333333333…: 1.6180339887498948482045…e: 2.7182818284559045235336…: 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 kth symbol that it outputs is sk-For every k2, P eventually outputs the kth symbol. 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 unambiguous description 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…Correspondence PrincipleIf two finite sets can be placed into 1-1 onto correspondence, then they have the same size.Correspondence DefinitionIn fact, we can use the correspondence as the definition: Two finite sets are defined to have the same size if 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 size if and only if they can be placed into 1-1 onto correspondence.Cantor’s Definition (1874)Two sets are defined to have the same cardinality if and only if they can be placed into 1-1 onto correspondence.Do and have the same cardinality?= { 0, 1, 2, 3, 4, 5, 6, 7, … } = { 0, 2, 4, 6, 8, 10, 12, … }The even, natural numbers. and do not have the same cardinality! is a proper subset of with plenty left over. The attempted correspondence f(x)=x does not take onto . and do have the same cardinality! = 0, 1, 2, 3, 4, 5, … = 0, 2, 4, 6, 8,10, …f(x) = 2x is 1-1 onto.Lesson: Cantor’s definition only requires that some 1-1 correspondence between the two sets is onto, not that all 1-1 correspondences are onto. This distinction never arises when the sets are finite.Cantor’s Definition (1874)Two sets are defined to have the same size if and only if they can be placed into 1-1 onto correspondence.You just have to get used to this slight subtlety in order to argue about infinite sets!Do and have the same cardinality? = { 0, 1, 2, 3, 4, 5, 6, 7, … } = { …, -2, -1, 0, 1, 2, 3, … }No way! is infinite in two ways: from 0 to positive infinity and from 0 to negative infinity. Therefore, there are far more integers than naturals.Actually, no! and do have the samecardinality! = 0, 1, 2, 3, 4, 5, 6 … = 0, 1, -1, 2, -2, 3, -3, ….f(x) = x/2 if x is odd -x/2 if x is evenTransitivity LemmaTransitivity LemmaLemma: If f: AB is 1-1 onto, and g: BC is 1-1 onto.Then h(x) = g(f(x)) defines a functionh: AC that is 1-1 ontoHence, , , and all have the same cardinality.Do and have the same cardinality?= { 0, 1, 2, 3, 4, 5, 6, 7, …. }= The Rational NumbersNo way!The rationals are dense: between any two there is a third. You can’t list them one by one without leaving out an infinite number of them.Don’t jump to conclusions!There is a clever way to list the rationals, one at a time, without
View Full Document
Unlocking...