Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: Lists
Posted:
Jan 24, 2013 1:40 PM


Don Deluise wrote: > > This list enumerates all 2 bit binary sequences: > > 00 > 01 > 10 > 11 > > This one enumerates all 3 bit binary sequences: > > 000 > 001 > 010 > 011 > 100 > 101 > 110 > 111 > > Using diagonalization on the first to produce a sequence that is not in the > list fails. It produces '10' which *is* in the list. > > Using diagonalization on the second list also fails. It produces '111' > which *is* in the list. > > Clearly, increasing the length of the sequences does not produce lists in > which diagonalization will achieve its purpose, i.e. to produce binary > sequences of a given length which are not already in the list. > > So if we were to compile an enumeration of infinite length binary > sequences, how do we know that diagonalization produces a sequence not > already in the list?
Infinite things don't behave the same as finite ones.
 When a true genius appears in the world, you may know him by this sign, that the dunces are all in confederacy against him. Jonathan Swift: Thoughts on Various Subjects, Moral and Diverting



