Deep Question #2 Mysteries of Infinity Countability Two sets of numbers(or other objects) are said to have the them. this means each element in the first set Are there well-defined things that to exactly one element in the second set, cannot be compute Any set of same cardinality as the integers is called integers)same size as (even integers): n> 2n (integers)same size as(squares): n>n2 integers) same size as (rational numbers) Countable- rational numbers Uncountable- real numbers As many integers as rational numbers(no more, no less). The eal numbers between o and 1 is uncountable f: Represent a real number by its decimal expansion 111y1如15/16/17/1 ly require an infinite number of digits), e.g. 0.49373 Assume there are a countable number of such numbers Then can arbitrarily number them, as in this table: 51/52/53/54/55/56/57/5 #20.33333333 ng between the set of rationals and set of integers as move alon countability is false, re more reals than integers There are more functions than programs halts? There are a countable number of procedures: e.g. can write Even simple procedures can cause deep difficulties every program in a binary(integer)form, 100110100110 to check procedures before running Assume there are a countable number of predicate them to catch accidental infinite loops nctions, i.e. mappings from an integer arg to the value 0 or 1. Then we can arbitrarily number these functions Assume a procedure halts? exists halts? p) →舞ff 010 halts? is well specified-has a clear value for its inputs function by complementing the diagonals. By construction (halts? return-seven) #t this predicate cannot be in the list(of all integers, of all halts? loop-forever) #f programs). Thus there are more predicate functions than there are procedures erin, Kaiser, and Kngh, Concede Abstradiors, p. 114, P 19992 7 Deep Question #2 Are there well-defined things that cannot be computed? 8 Mysteries of Infinity: Countability • Two sets of numbers (or other objects) are said to have the same cardinality (or size) if there is a one-to-one mapping between them. This means each element in the first set matches to exactly one element in the second set, and vice versa. • Any set of same cardinality as the integers is called countable. • {integers} same size as {even integers}: n
2n • {integers} same size as {squares}: n
n2 • {integers} same size as {rational numbers} 9 Countable – rational numbers • As many integers as rational numbers (no more, no less). Proof: 1 2 3 4 5 6 7… 1 1/1 2/1 3/1 4/1 5/1 6/1 7/1 … 2 1/2 2/2 3/2 4/2 5/2 6/2 7/2 … 3 1/3 2/3 3/3 4/3 5/3 6/3 7/3 … 4 1/4 2/4 3/4 4/4 5/4 6/4 7/4 … 5 1/5 2/5 3/5 4/5 5/5 6/5 7/5 … • Mapping between the set of rationals and set of integers – match integers to rationals starting from 1 as move along line 10 Uncountable – real numbers • The set of real numbers between 0 and 1 is uncountable, i.e. there are more of them than there are integers: • Proof: Represent a real number by its decimal expansion (may require an infinite number of digits), e.g. 0.49373 • Assume there are a countable number of such numbers. Then can arbitrarily number them, as in this table: #1 0. 4 9 3 7 3 0 0 0 ... #2 0. 3 3 3 3 3 3 3 3 ... #3 0. 5 8 7 5 3 2 1 4 ... • Pick a new number by adding 1 (modulo 10) to every element on the diagonal, e.g. 0.437... becomes 0.548… This number cannot be in the list! The assumption of countability is false, and there are more reals than integers 11 There are more functions than programs • There are a countable number of procedures: e.g. can write every program in a binary (integer) form, 100110100110 • Assume there are a countable number of predicate functions, i.e. mappings from an integer arg to the value 0 or 1. Then we can arbitrarily number these functions: #1 0 1 0 1 1 0 … #2 1 1 0 1 0 1 … #3 0 0 1 0 1 0 … • Use Cantor Diagonalization again! Define a new predicate function by complementing the diagonals. By construction this predicate cannot be in the list (of all integers, of all programs). Thus there are more predicate functions than there are procedures. 12 halts? • Even simple procedures can cause deep difficulties. Suppose we wanted to check procedures before running them to catch accidental infinite loops. • Assume a procedure halts? exists: (halts? p)
#t if (p) terminates
#f if (p) does not terminate • halts? is well specified – has a clear value for its inputs (halts? return-seven)
#t (halts? loop-forever)
#f Halperin, Kaiser, and Knight, "Concrete Abstractions," p. 114, ITP 1999