Collatz at the Hilbert Hotel

From: Michael Collins (mcollins_at_arm.com)
Date: 01/05/05 

Date: Wed, 05 Jan 2005 17:34:32 +0000

First a brief story and then the maths to go with it. I'll try to keep
it as concise as possible.

1. Story
The Hilbert hotel has recently been refurbished so that each room now
has a 'Godel duplicator', a machine that can be used to duplicate
anything put into it.
Unfortunately, in order to create so many duplicators they had to
duplicate the original one.
As luck would have it was just able to fit into itself so it was copied
and eventually each room got one.
Before the system was, itself, copied it had been tested by duplicating
a person. The system tries to stop this from happening by creating
Drones that don't think, only obeying simple fixed rules. Drones are
easily destroyed using a tool called a 'bopper'.
Unfortunately there's a glitch in the system that means that at 9am
every day some of these machines will create new Drones which, by
following these rules generally clog up the hotel before finally being
rounded up by all the staff and 'bopped'.
The Manager of the hotel is distressed by this as it has been causing no
end of problems for the guests.
He has no choice but to close the hotel and call in the "Collatz
Exterminators" who specialise in drone 'bopping' and other such
problems.
Mr Ulam Collatz, the owner of the company himself comes along (in the
hail) and observes the first day's events in order to work out the rules
of Drone behaviour.
After the staff have rounded up the last straggler - there's always one
- he tells the hotel manager that he'll be quite happy to come back the
next day and get rid of them all.
The following day he arrives just before 9 and as the drones appear he
steps into the first room with a drone in, quickly bops it and is ready
to get rid of all the others.

The Rules are as follows:
The entity (Collatz or Drone) in the lowest room moves to the higher
room two along.
Every other entity duplicates itself and quickly sends the new duplicate
into the next higher room.
At this point in time the fighting breaks out, any time a Drone enters a
room that's already occupied there will be fight and one of them will
'pop' with the victor moving up a room to (possibly) fight all over
again.
Being as Collatz is a proper human (armed with a bopper no less) he's
able to win every duel.
As this is repeated over and over, Collatz always emerges the victor.

Maths:
Obviously this comes from the Collatz conjecture, the well known
iterative Diophantine equation.
The original Collatz conjecture is that any positive integer, n,
operated on iteratively eventually reaches 1.
The rules for the iteration are that of n is even n --> n/2 and that if
n is odd n -> 3n+1.
This is more usually shown as
    F(n) = 3n +1 if n=1 (mod2)
                  n/2 if n=0 (mod2)

If we look at the binary representation of n with the lowest bit on the
left and increasing powers of 2 represented to the right then n/2 is
purely shifting n left one and this will keep repeating until the lowest
bit is a 1 and therefore become 1 mod2.
As an example 12 can be represented as 0011 ( 0x2^0 + 0x2^1 + 1x2^2 +
1*2^3) = 4 + 8 and the next two iterations become 011 and then 11 in
binary, six and three respectively.
n = 3 -> n' = 10 ( n = 11 -> n' = 0101 in binary)

If, rather than n -> 3n + 1 we express the 3n+1 portion of the collatz
conjecture as n -> 3n + 2^x with 2^x being the lowest non-zero power of
two in the binary representation of n then we can do away with the n/2
section and, rather than the Colatz conjecture stating that the result
must eventually reach 1 we can instead state an equal conjecture that
iterating n->3n + 2^x eventually reaches 2^y.
 F(n) = 3n + 2^x
     n original(bin) 3n + 2^x variant
     3 11 11
   10 0101 0101
     5 101 -
   16 00001 000001
The strength in this is that we have a steadily increasing sequence that
doesn't have the n/2 section giving these additional iterations and we
have a sequence that terminates in less iterations as well.

I've not looked at whether this gives any better relationship between
the chosen starting number and the number of iterations until the result
reaches 2^y.
The chosen starting number isn't relevant, the number of digits between
the starting and ending 1 in the binary representation are relevant.
1010001100001 will behave exactly the same as
000000000000001010001100001 without having to be reduced to an odd
number first.

In effect the conjecture is getting us to multiply n by 3 and then add
an ever increasing 2^x
What is in effect happening is that the lowest bit is being multiplied
by 4 and shifting to the right by 2 in the binary representation (
multiply by 3 and then add the 2^n) and the rest of n is being
multiplied by 3
This x3 in binary represents taking the original part of n (not
including the lowest bit) and then adding itself shifted to the right by
one ( n + 2n to end up multiplying by 3).
You can only ever add zeroes to the left of the sequence as
multiplication of integers (in any number base) can never affect digits
lower than those represented in the numbers being multiplied.
All this means that no bit can ever appear in subsequent n' lower than
the lowest bit set in n. (lower than 2^(x+1) actually as the lowest bit
is multiplied by 4.)

I'm not sure how much sense the above couple of paragraphs make as I'm
more of an IT person than a mathematician but I liked working with this
and hadn't seen this being done before and besides I liked the story.

If we show subsequent iterations starting from a large number the
trailing edge always seems to be advancing faster than the leading edge.

Obviously, with the story I could have kept the original n/2 iteration
and had Collatz coming out of room 1 at the end every time but I'd been
using the maths to get rid of the modular arithmetic so didn't want to
bring it back in even though it does make the story a lot nicer.

The Drones bopping each other is binary addition leading to them to move
into the next highest room (a carry).
The duplication and sending the duplicate into the next highest room us
multiplying by three.
The entity in the lowest room moving two rooms up is the lowest bit
being multiplied by four.
The door number for each room represents the power of two in binary(if
you have a room 0 anyway).

As an addendum if the duplicators are programmed so that the creation of
the Drones is a function of the neighbouring rooms and have Drones using
similar rules about whether to remain in the room or leave (which must
be nicer than being 'bopped') then Hilbert's Hotel will instead function
as a CA and, from the CAs in Wolframm's ANKOS, the hotel can be made to
function as a Turing Machine.

We could also have the hotel not being allowed to have more than 9
entites in each room for example with 8 being requested to leave and the
remaining one moving up a room to represent base10.

This could also lead to arbitrary bases with different rooms having
different maximums based on whatever rules we choose to assign filling
electron orbitals or keep adding people to the next room until a prime
is reached and then start on the next room etc.

Any comments on this will be gratefully received.

Regards,
Mike...