Re: Collatz at the Hilbert Hotel
mensanator_at_aol.compost
Date: 01/08/05
- Next message: examachine_at_gmail.com: "Re: Is 1+1=2 analytic or synthetic?"
- Previous message: Narasimham: "Re: how long is a moment"
- In reply to: Michael Collins: "Collatz at the Hilbert Hotel"
- Next in thread: Michael Collins: "Re: Collatz at the Hilbert Hotel"
- Reply: Michael Collins: "Re: Collatz at the Hilbert Hotel"
- Messages sorted by: [ date ] [ thread ]
Date: 7 Jan 2005 18:42:10 -0800
Michael Collins wrote:
<snip>
> 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.
<snip>
>
> Any comments on this will be gratefully received.
As an addendum to my previous post where I pointed out the
equivalence of the Hilbert algorithm to the standard Collatz
algorithm, I've gone ahead and made a Cellular Automata version
of the Collatz algorithm that does indeed, operate on
neighboring cells and is completely independant of any
mathematical reference point. By contrast, the standard Collatz
algorithm always anchors the least significant 1 bit to 2**0
while the Hilbert algorithm is constantly shifting the least
significant 1 bit anchor to ever higher powers of 2.
Here's the Python program:
## Collatz Cellular Automata
##
## One dimensional CA with edge wrapping
##
#
#
#def print_ca():
# ca_out = ''
# for i in ca:
# ca_out = ca_out + i
# print ca_out
#
#
## ca is the one-dimensional array of cells.
#
#ca = []
#
## An infinite array is a bit tricky, so we'll
## make a finite array and use edge wrapping.
## Size should be chosen to be bigger than the
## bit length of the Excursion.
#
#for i in xrange(50):
# ca.append('0')
#
## Drop the life-form into the array at some
## arbitrary point. In this example, the life-form
## will be 27 (11011 in binary).
#
#ca[18] = '1'
#ca[19] = '1'
#ca[20] = '0'
#ca[21] = '1'
#ca[22] = '1'
#
## The CA rules require that we know the starting point
## of the life-form. Without a mathematical reference,
## we'll get lost otherwise when the life-form sails off
## the left end of the array and wraps around to the right end.
#
#start = 22
#
## Initialize the Full Adder lookup tables
##
## a Full Adder adds two binary operands with carry
#
#fa_sum =
{'000':'0','001':'1','010':'1','011':'0','100':'1','101':'0','110':'0','111':'1'}
#fa_car =
{'000':'0','001':'0','010':'0','011':'1','100':'0','101':'1','110':'1','111':'1'}
#
#
## A cellular automata just runs forever, so we'll kill it after a
## finite number of generations.
#
#done = 62
#
#while done>0:
# # each line of output is one generation of the automata
# print_ca()
#
# i = start
#
# # by pre-setting the Carry Bit, we don't need a seperate
# # incrementing step
# C = '1'
#
# # as we do the Full Adder arithmetic, we need to find the
# # first 1 bit that appears in the Sum. This will be where we
# # start the next generation
# next_start = -1
#
# # in each generation, we'll process every cell in the array
# field = len(ca)
#
# for j in xrange(field-1):
# # operand A is the current bit
# A = ca[i]
#
# # operand B is the bit to the left of operand A.
# # this is, of course operand A multiplied by 2.
# # added together, A and B become "3n" with the
# # pre-set Carry Bit providing the "+1"
# B = ca[i-1]
#
# # take the Carry Bit (C), operand A (A) and operand B (B)
# # and make a key for the Full Adder lookup tables
# FA = C + A + B
#
# # S is the Sum
# S = fa_sum[FA]
#
# # the carry out from the Full Adder becomes the carry-in
# # for the next bit position
# C = fa_car[FA]
#
# # if we get a '1' in the Sum and it's the first,
# # remember where it occured
# if (S=='1') and (next_start==-1):
# next_start = i
#
# # update the array
# ca[i] = S
#
# i -= 1
#
# # from the 0 index, Python can reach around the edge with
# # negative indexing, but when we actually move off the left
# # edge, wrap around to the right edge
# if i==-1:
# i = field-1
#
# # reset starting point for the next generation
# start = next_start
#
# done -= 1
Output:
00000000000000000000000000000000000000110110000000
00000000000000000000000000000000000001010010000000<--similar to a
00000000000000000000000000000000000001111100000000 spaceship or
00000000000000000000000000000000000010111100000000 puffer-train in
00000000000000000000000000000000000100011100000000 Conway's Game of
00000000000000000000000000000000000110101100000000 Life, the Collatz
00000000000000000000000000000000001010000100000000 life-form simply
00000000000000000000000000000000001111001000000000 drifts through
00000000000000000000000000000000010110110000000000 the playing field
00000000000000000000000000000000100010010000000000 without any
00000000000000000000000000000000110011100000000000 mathematical
00000000000000000000000000000001001101100000000000 reference point
00000000000000000000000000000001110100100000000000
00000000000000000000000000000010101111000000000000
00000000000000000000000000000100000111000000000000
00000000000000000000000000000110001011000000000000
00000000000000000000000000001001010001000000000000
00000000000000000000000000001101111010000000000000
00000000000000000000000000010100111000000000000000
00000000000000000000000000011111011000000000000000
00000000000000000000000000101111001000000000000000
00000000000000000000000001000110110000000000000000
00000000000000000000000001101010010000000000000000
00000000000000000000000010011111100000000000000000
00000000000000000000000011101111100000000000000000
00000000000000000000000101100111100000000000000000
00000000000000000000001000011011100000000000000000
00000000000000000000001100101001100000000000000000
00000000000000000000010010111110100000000000000000
00000000000000000000011100011110000000000000000000
00000000000000000000101010101110000000000000000000
00000000000000000001000000000110000000000000000000
00000000000000000001100000001010000000000000000000
00000000000000000010010000010000000000000000000000
00000000000000000011011000100000000000000000000000
00000000000000000101000101000000000000000000000000
00000000000000000111101000000000000000000000000000
00000000000000001011100000000000000000000000000000
00000000000000010001100000000000000000000000000000
00000000000000011010100000000000000000000000000000
00000000000000101000000000000000000000000000000000
00000000000001000000000000000000000000000000000000<--but, as we know,
00000000000010000000000000000000000000000000000000 all Collatz
00000000000100000000000000000000000000000000000000 life-forms evolve
00000000001000000000000000000000000000000000000000 into a glider
00000000010000000000000000000000000000000000000000
00000000100000000000000000000000000000000000000000
00000001000000000000000000000000000000000000000000
00000010000000000000000000000000000000000000000000
00000100000000000000000000000000000000000000000000
00001000000000000000000000000000000000000000000000
00010000000000000000000000000000000000000000000000
00100000000000000000000000000000000000000000000000
01000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000001<--note the edge
00000000000000000000000000000000000000000000000010 wrapping
00000000000000000000000000000000000000000000000100
00000000000000000000000000000000000000000000001000
00000000000000000000000000000000000000000000010000
00000000000000000000000000000000000000000000100000
00000000000000000000000000000000000000000001000000
I could have dropped the "27" life-form anywhere in the playing field:
00000000000000000011011000000000000000000000000000
00000000000000000101001000000000000000000000000000
00000000000000000111110000000000000000000000000000
00000000000000001011110000000000000000000000000000
00000000000000010001110000000000000000000000000000
00000000000000011010110000000000000000000000000000
00000000000000101000010000000000000000000000000000
00000000000000111100100000000000000000000000000000
00000000000001011011000000000000000000000000000000
00000000000010001001000000000000000000000000000000
00000000000011001110000000000000000000000000000000
00000000000100110110000000000000000000000000000000
00000000000111010010000000000000000000000000000000
00000000001010111100000000000000000000000000000000
00000000010000011100000000000000000000000000000000
00000000011000101100000000000000000000000000000000
00000000100101000100000000000000000000000000000000
00000000110111101000000000000000000000000000000000
00000001010011100000000000000000000000000000000000
00000001111101100000000000000000000000000000000000
00000010111100100000000000000000000000000000000000
00000100011011000000000000000000000000000000000000
00000110101001000000000000000000000000000000000000
00001001111110000000000000000000000000000000000000
00001110111110000000000000000000000000000000000000
00010110011110000000000000000000000000000000000000
00100001101110000000000000000000000000000000000000
00110010100110000000000000000000000000000000000000
01001011111010000000000000000000000000000000000000
01110001111000000000000000000000000000000000000000
10101010111000000000000000000000000000000000000000
00000000011000000000000000000000000000000000000001<--edge wrapping
10000000101000000000000000000000000000000000000001 shows how the
01000001000000000000000000000000000000000000000010 pattern is
01100010000000000000000000000000000000000000000011 independent of
00010100000000000000000000000000000000000000000101 any mathematical
10100000000000000000000000000000000000000000000111 anchor. this is
10000000000000000000000000000000000000000000001011 simply a circular
10000000000000000000000000000000000000000000010001 array. as long as
10000000000000000000000000000000000000000000011010 the array is
00000000000000000000000000000000000000000000101000 larger than the
00000000000000000000000000000000000000000001000000 Excursion, the CA
00000000000000000000000000000000000000000010000000 will generate the
00000000000000000000000000000000000000000100000000 same bit patterns
00000000000000000000000000000000000000001000000000 as the standard
00000000000000000000000000000000000000010000000000 Collatz algorithm
00000000000000000000000000000000000000100000000000
00000000000000000000000000000000000001000000000000
00000000000000000000000000000000000010000000000000
00000000000000000000000000000000000100000000000000
00000000000000000000000000000000001000000000000000
00000000000000000000000000000000010000000000000000
00000000000000000000000000000000100000000000000000
00000000000000000000000000000001000000000000000000
00000000000000000000000000000010000000000000000000
00000000000000000000000000000100000000000000000000
00000000000000000000000000001000000000000000000000
00000000000000000000000000010000000000000000000000
00000000000000000000000000100000000000000000000000
00000000000000000000000001000000000000000000000000
00000000000000000000000010000000000000000000000000
00000000000000000000000100000000000000000000000000
>
> Regards,
> Mike...
- Next message: examachine_at_gmail.com: "Re: Is 1+1=2 analytic or synthetic?"
- Previous message: Narasimham: "Re: how long is a moment"
- In reply to: Michael Collins: "Collatz at the Hilbert Hotel"
- Next in thread: Michael Collins: "Re: Collatz at the Hilbert Hotel"
- Reply: Michael Collins: "Re: Collatz at the Hilbert Hotel"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
