Search NKS | Online
11 - 20 of 41 for BitOr
![](/common/images/search/spacer.gif)
Implementing boundary conditions [in cellular automata]
In the bitwise representation discussed on page 865 , 0's outside of a width n can be implemented by applying BitAnd[a, 2 n -1] at each step.
Note that the original rule with k colors and r neighbors involves Log[2, k k 2 r + 1 ] bits of information; the two-color rule that emulates it involves Log[2, 2 2 2 s + 1 ] bits.
The first n elements can be found efficiently using
Module[{a = 1}, Table[First[IntegerDigits[ a, a = BitXor[a, BitOr[2a, 4a]]; 2, i]], {i, n}]]
The sequence does not repeat in at least its first million steps, and I would amazed if it ever repeats, but as of now I know of no rigorous proof of this. ( Erica Jen showed in 1986 that no pair of columns can ever repeat, and the arguments on page 1087 suggest that neither can the center column together with occasional neighboring cells.)
Particularly dramatic are the concatenation systems discussed on page 913 , as well as successive rows in nested patterns such as Flatten[IntegerDigits[NestList[BitXor[#, 2 #] &, 1, 500], 2]] and sequences based on numbers such as Flatten[Table[If[GCD[i, j] 0, 1, 0], {i, 1000}, {j, i}]] (see page 613 ).
My 1973 computer experiments
I used a British Elliott 903 computer with 8 kilowords of 18-bit ferrite core memory.
Acceptable randomness has however been obtained at rates of tens of bits per second.
The fact that there are a million nerve fibers going from the eye to the brain, but only about 30,000 going from the ear to the brain means that while it takes several million bits per second to transmit video of acceptable quality, a few tens of thousands of bits are adequate for audio (NTSC television is 5 MHz; audio CDs 22 kHz; telephone 8 kHz).
Games between programs
One can set up a game between two programs generating single bits of output by for example taking the input at each step to be the concatenation of the historical sequences of outputs from the two programs.
And if one always does computations using systems that have only nearest-neighbor rules then just combining 2t + 1 bits of information can take up to t steps—even if the bits are combined in a way that is not computationally irreducible.
A total of 40 disks were started with positions and velocities determined by a middle-square random number generator (see page 975 ), and their motion was followed for about 10 collision times—after which roundoff errors in the 64-bit numbers used had grown too big.
![](/common/images/search/spacer.gif)