 | On 14 Dec 2001 23:19:01 -0500,
Dave Seaman @seaman.cc.purdue.edu> wrote:
I am starting to confuse myself now :-)
If a machine has N bits it can have 2**N states.
In C, a left shift of x (written <multplying by 2^x. e.g. y< In C, the largest possible number can be written as ~0U (barring
confusions of sizeof(long)>sizeof(int) )
therefore,
for all N>0, 1<<~0U will have more than N bits and hence will overflow.
Now, I understand that this is true, even in the limit where N -> infinity.
(I am happy to this point but now I start getting confused).
A machine with a maximum (unsigned) int of ~0U has log(~0U + 1) bits. (logs
to base 2)
But this hypothetical machine can handle all countable numbers and so has
log(aleph-null) bits.
But it appears to me that log(aleph-null) must be smaller than aleph-null
but must also be infinite and so there is an infinite number smaller than
aleph-null.
Is this possible?
Have I (re)discovered aleph-minus-n ?
And how many bits does the hypothetical machine have?
Tim.
--
God said, "div D = rho, div B = 0, curl E = - @B/@t, curl H = J + @D/@t,"
and there was light.
http://locofungus.2y.net/ http://www.locofungus.btinternet.co.uk/
|
| In article @pauli.locofungus.org>,
Tim Woodall @locofungus.org> wrote:
>If a machine has N bits it can have 2**N states.
>In C, a left shift of x (written <>multplying by 2^x. e.g. y<>In C, the largest possible number can be written as ~0U (barring
>confusions of sizeof(long)>sizeof(int) )
>therefore,
>for all N>0, 1<<~0U will have more than N bits and hence will overflow.
>Now, I understand that this is true, even in the limit where N -> infinity.
>(I am happy to this point but now I start getting confused).
>A machine with a maximum (unsigned) int of ~0U has log(~0U + 1) bits. (logs
>to base 2)
If ~0U is to have meaning as a cardinal number, I suppose you could
interpret it as the supremum of the set {1, 2, 4, 8, 16, ...}, which is
aleph_0.
But then your log(~0U+1) notation makes no sense. If ~0U = aleph_0, then
also ~0U+1 = aleph_0, and log_2 (aleph_0) would have to be a cardinal
number x such that 2^x = aleph_0.
There is no such number. It can't be finite, because 2^x is finite for
each finite x. It can't be infinite, because aleph_0 is the smallest
infinity (assuming the axiom of choice), and 2^aleph_0 is already greater
than aleph_0. There is no set whose power set is countably infinite.
>But this hypothetical machine can handle all countable numbers and so has
>log(aleph-null) bits.
Not every property of finite numbers can be extended to infinity.
>But it appears to me that log(aleph-null) must be smaller than aleph-null
>but must also be infinite and so there is an infinite number smaller than
>aleph-null.
>Is this possible?
No, if by "infinite number" you mean "the cardinality of some infinite
set." The closest I can think of is that, in the absence of the axiom of
choice, there may be sets that are infinite but do not contain any
countably infinite subset. The cardinality of such a set (called a
Dedekind set) is neither larger nor smaller than aleph_0.
>Have I (re)discovered aleph-minus-n ?
>And how many bits does the hypothetical machine have?
The machine has aleph_0 bits, but it cannot express numbers larger than
aleph_0. Any bit pattern in which there are infinitely many 1's turns
out to be equivalent to aleph_0, which obeys such arithmetical laws as:
aleph_0 + 1 = aleph_0,
aleph_0 + aleph_0 = aleph_0,
aleph_0 * aleph_0 = aleph_0.
--
Dave Seaman dsea...@purdue.edu
Amnesty International calls for new trial for Mumia Abu-Jamal
<http://www.amnestyusa.org/abolish/reports/mumia/>
|
| In article <3C1B9427.7751E...@eton.powernet.co.uk>,
Richard Heathfield @eton.powernet.co.uk> wrote:
>Dave Seaman wrote:
>> >> The shift can be done any finite number of times, but not infinitely
>> >> often.
>> >This is a contradiction. If there's an upper limit on the number of
>> >times that you can do the shift, then "any finite number" doesn't work.
>> >And if there's no upper limit, then you have an infinite number.
>> Where did I say anything about an upper limit?
>Read what I said again. Either there's an upper limit or there isn't. In
>either case, I can't square your statement with reality.
I said that each shift operation is finite. I most certainly did *not*
say that there is an upper limit to the bit positions. When I asked you
where I said anything about upper limits, it was intended to be a polite
way of pointing out that I had not mentioned upper limits at all. That
was entirely your invention.
By the way, aleph_0 is certainly an upper limit for the magnitude of the
bit shifts, but somehow I suspect this is not what you meant. There is
no *finite* upper limit.
>> The operation 1 << n makes
>> sense for any finite value of n, and there are infinitely many such
>> values.
>The original operation (~0 << n) also makes sense where there are an
>infinite number of bits. Let n = 1. Let ~0 have infinitely many bits. We
>can accommodate another bit by left shifting one place and setting the
>low bit.
Yes, but I don't see what this has to do with whether shifts make sense
for infinite values of n. They don't.
>> >> That's why, when infinitely many new guests arrive, the guests
>> >> have to do something other than a simple shift in order to make room.
>> >> For example, the guest in room n can move to room 2*n for each n, leaving
>> >> all the odd-numbered rooms available for newcomers.
>> >No, you simply accommodate each new guest as and when he arrives. You
>> >can do this infinitely often. If you have an infinite number of guests,
>> >you simply register them one at a time. Easy.
>> If you do this infinitely often, then in what room does the first guest
>> wind up after you are done?
>It doesn't matter. The point is that he is safely ensconced in a room,
>hopefully with an en suite shower (since he's been doing a lot of
>exercise recently).
But what number is on the door? When he called for clean towels, what
room number did he ask for them to be delivered to?
>> The correct statement is that you can do the
>> shift any finite number of times, and there are infinitely many finite
>> numbers, but you cannot shift infinitely often, because the result is
>> undefined.
>If you can shift any finite number of times, then there is no upper
>limit to the number of times you can shift. Therefore, you can shift an
>infinite number of times.
You were doing fine up until that last statement, but your conclusion
does not follow from what you stated previously. A set that is not
bounded above does not need to contain any infinite members.
>> >> If you disagree, then tell me the final bit position for that 1 after it
>> >> has shifted infinitely many times.
>> >Well, I don't know it, but it's countable. Initialise a counter to zero,
>> >and shift your value right in a loop, incrementing the counter as you
>> >go. When the value hits zero, read the counter. (In other words, make
>> >the guests leave, one at a time, and count how many go out of the door.)
>> Your question presumes that "the value" makes sense in the first place.
>> It doesn't. Start by telling me the value of the bit in position n for
>> each finite value of n, and then we have a value we can talk about.
>I have a better idea. You tell me the maximum number of guests that can
>be accommodated in Hilbert's Hotel. THEN we'll have a value we can talk
>about.
Aleph_0.
Your turn.
>> >> It can't be any finite-numbered bit
>> >> position, but the finite-numbered ones are the only ones we have.
>> >No, that's not true. We have an infinite number of bits, according to
>> >the original spec.
>> Yes, that is correct. There are an infinite number of bits. What do you
>> conclude from that? Are you claiming that this somehow proves that some
>> of them must be in infinite-numbered bit positions?
>Not at all.
>> How did you draw
>> that conclusion?
>I didn't.
Then you agree with me that it is possible for the bit shifts not to be
bounded above (by any finite value), and yet for each one of them to be
finite?
Then you agree with me that if I say infinite bit shifts do not make
sense, it doesn't mean I am claiming there is an upper bound?
By the way, if we had a larger hotel, we could have larger shifts. In a
hotel with aleph_1 rooms, we can shift guests by any countable number of
rooms, and there are uncountably many different shifts that can be
carried out, each one of them countable. There is no countable upper
limit. The only reason we can't do this in the Hilbert Hotel is that
there are no rooms with infinite numbers on them.
>> Question: how many finite-numbered bit positions are there?
>Lots.
>> a) There are infinitely many finite bit positions.
>> b) There are only finitely many finite bit positions.
>> Think carefully.
>> Did you choose (b)?
>No. I chose a). There is no upper limit, so there are infinitely many.
>Each is finite. Pick an integer. Any integer. Is it finite? Of course!
>But there are still infinitely many of them.
Then I rest my case.
>> That is the only answer that is consistent with your
>> argument above,
>Then you misunderstood my argument, or (to be fair to you) perhaps I
>didn't explain myself terribly well.
>> but it leads to an obvious contradiction. If there are
>> only finitely many finite bit positions, then there must be a
>> largest-numbered one, say position n. Then what do you get if you shift
>> one position to the left? What kind of number is n+1? Is it finite, or
>> infinite?
>Yes. :-) Of course, I didn't claim there were only finitely many finite
>bit positions, so it's a moot point.
Did you, or did you not, claim that if a set contains only finite values,
then the set is bounded above? Looking at your statements that are
quoted at the start of this article (such as the "read what I said again"
statement), I cannot find any other way to interpret what you said.
>> Since answer (b) leads to a contradiction, it follows that the correct
>> answer is (a). But this negates your entire argument.
>No, it doesn't.
Ok, then it only negates the part of your argument where you claimed that
if I don't accept infinite bit shifts, then I must be placing a (finite)
upper bound on the size of the bit shifts. You did mean a finite upper
bound, didn't you? Because otherwise I can't see what all the fuss was
about.
>> There are
>> infinitely many bit positions, as you said, but it is still true that
>> each one of them is in a finite position.
>I agree entirely. But somehow, I suspect we still disagree. :-)
I suspect that depends on which one of you I am having the discussion
with. I have been completely consistent in everything I have said.
--
Dave Seaman dsea...@purdue.edu
Amnesty International calls for new trial for Mumia Abu-Jamal
<http://www.amnestyusa.org/abolish/reports/mumia/>
|
|
