Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: Lists
Replies: 7   Last Post: Jan 24, 2013 5:06 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Michael Stemper

Posts: 671
Registered: 6/26/08
Re: Lists
Posted: Jan 24, 2013 12:39 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

In article <1xh71bla4hvjd$.wf5fd9paee0w$.dlg@40tude.net>, Don Deluise <thedon@tomato.red> writes:

>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?


If you look at what you've done, it only includes changing the first
two or three items in the list. Since there are either four or eight
items, it's not surprising that you haven't created an item not on
the list.

If you examine the case where you change bit/digit n of item n for
all items on the list, then you'll see that your resultant has to
differ from all of them.

--
Michael F. Stemper
#include <Standard_Disclaimer>
2 + 2 = 5, for sufficiently large values of 2



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.