Rule 90 and left-to-right reversal
Nikita Ayzikovsky
property of the Rule 90 automaton. On states of certain finite lengths
(powers of two, it appears), surrounded at the sides by zeroes (which
themselves don't undergo change), the whole state is reversed
left-to-right after a number of steps equal to the length of the
state.
Example, for a 16-cell state:
|## ##### # # |
|## # ## # #|
|## # ##### # # |
|#### # # #|
|# ### # # # # |
| ### # ## #|
|## # # ### |
|## ## # ## ## |
|###### #### ###|
|# #### # # #|
| # ## ### |
|# ####### ## |
| # # ### |
| # # # # ## |
|# # # ## ### |
| # # ##### ##|
The first state (random):
|## ##### # # |
The final state:
| # # ##### ##|
I couldn't find anything regarding this property on the 'net, or in
Wolfram's NKS. Is this a known property?
Nikita Ayzikovsky.
Rich Holmes
> When playing with 1D cellular automata, I have found the following
> property of the Rule 90 automaton. On states of certain finite lengths
> (powers of two, it appears), surrounded at the sides by zeroes (which
> themselves don't undergo change), the whole state is reversed
> left-to-right after a number of steps equal to the length of the
> state.
[...]
> I couldn't find anything regarding this property on the 'net, or in
> Wolfram's NKS. Is this a known property?
I don't know, but probably not unrelated to some of the stuff I looked
into and wrote up at
<http://www.richholmes.net/games/cellaut/r90.html>.
Frank Buss
I don't know, but I've checked it for other lengths and it looks like it
is possible for other even lengths, too:
length, steps needed for reverse:
2,2
4,4
6,8
8,8
10,32
12,64
14,16
16,16
18,512
20,64
22,2048
24,1024
26,512
28,16384
30,32
32,32
34,4096
36,87382
38,4096
40,1024
42,128
44,4096
46 looks like it has many steps or it is not possible, because my Haskell
program (see at the end of this posting), with which I've tested it, is
still calculating. For the other lengths I'm not sure, because I've
tested it with one pattern, only.
Perhaps someone in sci.math can find a formula for the number of steps or
can prove, that for length 2^n the number of steps is n, which should be
easy.
Rule 90 description: A one dimension cellular automaton. The next state
of a cell is 1, if the left or the right neighbour is 1. If both
neighbours are 1 or both neighbours are 0, the next state is 0.
The Haskell test program:
charToBool x = map (=='#') x
boolToChar xs = [if x then '#' else ' ' | x<-xs]
rule90 True _ False = True
rule90 False _ True = True
rule90 _ _ _ = False
applyRuleBool _ _ [] _ = []
applyRuleBool f left (x:[]) right = [f left x right]
applyRuleBool f left (x1:xs'@(x2:xs)) right =
f left x1 x2 : applyRuleBool f x1 xs' right
applyRule f xs = boolToChar $ applyRuleBool f False (charToBool xs) False
iterateRule90 x = iterate (applyRule rule90) x
checkRule90 x = length (takeWhile (/=(reverse x)) (iterateRule90 x)) + 1
test = [(length x, checkRule90 x)|x<-(iterate (++ " ") " #")]
--
Frank Buß, f...@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Rich Holmes
The above numbers are the generation number at which the reversal
appears, counting from generation 1, so are one greater than the
actual reversal period.
Definitely related to what's on
<http://www.richholmes.net/games/cellaut/r90.html>, then. I tabulate
the replication (not reversal) period for a pattern consisting of a
single live cell at the end of the line, and (except for length 2) I
get twice the above numbers minus two (i.e. twice the actual reversal
period). In which case the number you should find for 46 would be
8388608. I didn't come up with a formula but I did find an easier way
to calculate a recurrence length which is either the period or a
multiple of the period; for all lengths up to 254 the calculated
recurrence length *is* the period -- *except* for 36, where I
calculate 524286 while the period is 174762, a factor of 3 smaller.
I didn't generalize this to arbitrary patterns, but evidently it works
out the same.
James Dolan
frank buss <f...@frank-buss.de> wrote:
i took the first 11 period lengths you listed:
2,4,8,8,32,64,16,16,512,64,2048
and then took their logs base 2:
1,2,3,3,5,6,4,4,9,6,11
and then fed them into sloane's on-line encycploedia of integer
sequences:
<http://www.research.att.com/~njas/sequences/index.html>.
this yielded:
ID Number: A003558
URL: http://www.research.att.com/projects/OEIS?Anum=A003558
Sequence: 1,2,3,3,5,6,4,4,9,6,11,10,9,14,5,5,12,18,12,10,7,12,23,21,8,
26,20,9,29,30,6,6,33,22,35,9,20,30,39,27,41,8,28,11,12,10,
36,24,15,50,51,12,53,18,36,14,44,12,24,55
Name: Least number m such that 2^m = +- 1 mod 2n + 1.
See also: Sequence in context: A023160 A085312 A046530 this_sequence A072451
A023156 A051599
Adjacent sequences: A003555 A003556 A003557 this_sequence A003559
A003560 A003561
Keywords: nonn
Offset: 0
Author(s): njas
so evidently something's going on here. you sure about that 87382,
though? the encyclopedia predicts 2^18.
--
[e-mail address jdo...@math.ucr.edu]
Frank Buss
> The above numbers are the generation number at which the reversal
> appears, counting from generation 1, so are one greater than the
> actual reversal period.
>
> Definitely related to what's on
> <http://www.richholmes.net/games/cellaut/r90.html>, then.
Your site has moved: http://web.syr.edu/~rsholmes/games/cellaut/r90.html
> I didn't generalize this to arbitrary patterns, but evidently it works
> out the same.
I've enhanced the Haskell program and verified it for all patterns for
the first 8 lengths (2, 4, 6, 8, ... 16):
numberOfSteps = [(length x, checkRule90 x)|x<-(iterate (++ " ") " #")]
intToPattern 0 = []
intToPattern i =
(if i `mod` 2 == 1 then '#' else ' ') : (intToPattern (i `div` 2))
createPattern i len = pattern ++ replicate (len - (length pattern)) ' '
where pattern = intToPattern i
createPatterns bits = [createPattern x bits | x<-[0..2^bits-1]]
checkAllPatterns len steps =
foldl1 (&&) (map (\x->iterateRule90 x !! (steps-1) == reverse x)
(createPatterns len))
checkAll =
[(len, steps, checkAllPatterns len steps) |
(len, steps) <- numberOfSteps]
Frank Buss
> so evidently something's going on here. you sure about that 87382,
> though? the encyclopedia predicts 2^18.
Yes. Testing it for all values would take some 200 years, if I could test
1 million steps per second, but I've verified it for 100000 random values
with this Java program:
import java.util.*;
public class Test {
public static void main(String args[]) {
Random r = new Random();
int len = 36;
long count = 1;
for (int i = 0; i < len; i++)
count *= 2;
int max = 0;
long checks = 0;
while (true) {
// generate random test value
long value = Math.abs(r.nextLong()) % count;
// reverse value
long reverse = 0;
for (long b1 = 1, b2 = count / 2; b2 > 0; b1 *= 2, b2 /= 2) {
if ((value & b1) != 0)
reverse |= b2;
}
// count number of steps for reversing
int steps = 0;
long current = value;
while (current != reverse) {
steps++;
current = (current >> 1) ^ (current << 1) & (count - 1);
}
// check, if more than the current maximum
if (steps > max)
max = steps;
// print every 1000 steps
if ((checks++ % 1000) == 0)
System.out.println(
"length: "
+ len
+ ", steps: "
+ max
+ ", checks: "
+ checks);
Rich Holmes
> Rich Holmes<rsholme...@mailbox.syr.edu> wrote:
>
> > The above numbers are the generation number at which the reversal
> > appears, counting from generation 1, so are one greater than the
> > actual reversal period.
> >
> > Definitely related to what's on
> > <http://www.richholmes.net/games/cellaut/r90.html>, then.
>
> Your site has moved: http:...
It's a redirect. The first URL should always work; the second might
not.
Rich Holmes
> ID Number: A003558
> URL: http://www.research.att.com/projects/OEIS?Anum=A003558
> Sequence: 1,2,3,3,5,6,4,4,9,6,11,10,9,14,5,5,12,18,12,10,7,12,23,21,8,
> 26,20,9,29,30,6,6,33,22,35,9,20,30,39,27,41,8,28,11,12,10,
> 36,24,15,50,51,12,53,18,36,14,44,12,24,55
> Name: Least number m such that 2^m = +- 1 mod 2n + 1.
> See also: Sequence in context: A023160 A085312 A046530 this_sequence A072451
> A023156 A051599
> Adjacent sequences: A003555 A003556 A003557 this_sequence A003559
> A003560 A003561
> Keywords: nonn
> Offset: 0
> Author(s): njas
Thanks for this -- I'm not sure what I looked for, if anything, in the
EIS, but evidently not this.
> so evidently something's going on here. you sure about that 87382,
> though? the encyclopedia predicts 2^18.
That's the length = 36 anomaly I mentioned in another post. The
procedure I came up with proves the pattern recurs in 524286 (2^19-2)
steps, and in fact it does, but for the third time -- the recurrence
period is 174762 ((2^19-2)/3).
Frank Buss
> It's a redirect. The first URL should always work; the second might
> not.
Did you tried it? The redirect doesn't work for me. I've tested it with
Internet Explorer and Mozilla.
David Eppstein
Rich Holmes<rsholme...@mailbox.syr.edu> wrote:
> > > Definitely related to what's on
> > > <http://www.richholmes.net/games/cellaut/r90.html>, then.
> >
> > Your site has moved: http:...
>
> It's a redirect. The first URL should always work; the second might
> not.
I get a 404 from the URL above.
--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science
Paul Chapman
<snip>
> I didn't come up with a formula but I did find an easier way
> to calculate a recurrence length which is either the period or a
> multiple of the period; for all lengths up to 254 the calculated
> recurrence length *is* the period -- *except* for 36, where I
> calculate 524286 while the period is 174762, a factor of 3 smaller.
524286 = 2*(2^18-1), while 18 = 36/2.
Just skimmed this thread - not doing research on this.
HTH.
Cheers, Paul
Rich Holmes
> In article <u4adak5...@mep1.phy.syr.edu>,
> Rich Holmes<rsholme...@mailbox.syr.edu> wrote:
>
> > > > Definitely related to what's on
> > > > <http://www.richholmes.net/games/cellaut/r90.html>, then.
> > >
> > > Your site has moved: http:...
> >
> > It's a redirect. The first URL should always work; the second might
> > not.
>
> I get a 404 from the URL above.
Works on my system. But I've changed domain name registrars and DNS;
maybe that's taking a while to propagate.
Rich Holmes
So indeed, use <http://web.syr.edu/~rsholmes/games/cellaut/r90.html>.
Plamen Petrov
Nikita:
check out my paper "Non-Replicative Fredkin's Rules in Homogeneous
Cellular Spaces" from PhysComp96:
http://www.digitalphysics.org/Publications/Petrov/Non-Rep/nr-ps.zip
It's all about rule 90 (called also "Fredkin's rule", or "XOR rule").
---
Plamen Petrov
http://digitalphysics.org
Mcintosh Harold V.
news:10e04221.03080...@posting.google.com
[...]
>
> I couldn't find anything regarding this property on the 'net, or in
> Wolfram's NKS. Is this a known property?
>
ANKOS may not be the best Wolfram reference on this. You might do
better by looking at his old World Scientific or more recent Addison
Wesley books. Essentially, Rule 90 is an Additive Finite Field rule
so you can practically calculate evolutions explicitly. To do lots
of generations, use eigenvalues and eigenvectors. I'm not sure if
the (his) paper which he has reprinted there would apply directly
to your situation or not.
- hvm
--
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
Frank Buss
> so evidently something's going on here. you sure about that 87382,
> though? the encyclopedia predicts 2^18.
Now I've implemented a symbolic Xor (see below) and the sequence is
proved until length 62:
1, 3, 7, 7, 31, 63, 15, 15, 511, 63, 2047, 1023, 511, 16383, 31, 31,
4095, 87381, 4095, 1023, 127, 4095, 8388607, 2097151, 255, 67108863,
1048575, 511, 536870911, 1073741823, 63
You can find it at OEIS:
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A086839
(I've send a comment to add the new elements).
The program with symbolic Xor calculating:
public class Rule90 {
public static void main(String args[]) {
long mul2[] = new long[64];
long start = 1;
for (int i = 0; i < 64; i++, start *= 2)
mul2[i] = start;
long pattern[] = new long[64];
long next[] = new long[64];
long reverse[] = new long[64];
for (int len = 2; len < 64; len += 2) {
/* init pattern and reverse check */
for (int i = 0; i < len; i++) {
pattern[i] = mul2[i];
reverse[i] = mul2[len - i - 1];
}
/* calculate steps needed for reversing */
long steps = 0;
while (true) {
/* calculate next step */
next[0] = pattern[1];
for (int i = 1; i < len - 1; i++) {
next[i] = pattern[i - 1] ^ pattern[i + 1];
}
next[len - 1] = pattern[len - 2];
/* check for reverse */
boolean found = true;
for (int i = 0; i < len; i++) {
if (pattern[i] != reverse[i]) {
found = false;
break;
}
}
if (found)
break;
/* swap "pattern" and "next" */
long tmp[] = next;
next = pattern;
pattern = tmp;
/* increment step count */
steps++;
}
/* print number of steps */
System.out.println(steps + ", ");
Ilmari Karonen
>When playing with 1D cellular automata, I have found the following
>property of the Rule 90 automaton. On states of certain finite lengths
>(powers of two, it appears), surrounded at the sides by zeroes (which
>themselves don't undergo change), the whole state is reversed
>left-to-right after a number of steps equal to the length of the
>state.
>
>Example, for a 16-cell state:
>
>|## ##### # # |
>
>The final state:
>| # # ##### ##|
For patterns whose length is a power of two, this property is pretty
easy to prove. In fact, it follows readily from the first two sections
of Rich Holmes's page mentioned elsewhere in this thread.
The key insight is to note that on an infinite line (following Rich's
convention of numbering generations from zero) the state of a cell at
generation 2^n-1 is given by
s(x, 2^n-1) = XOR s(x+d, 0)
where d takes all odd integer values between -2^n+1 and 2^n-1 inclusive.
Now consider the infinite analog of a 2^n cells wide pattern. We'll
number the cells of the pattern from 1 to 2^n, and extend the pattern
infinitely to so that cell 0 is off, and cells -x and x+2*(2^n+1) always
have the same state as cell x. (This is the same construction as given
by Rich Holmes, except that I've introduced explicit cell numbers.)
For any given cell x0 (0 < x0 <= 2^n) we can rewrite the equation for
its state at generation 2^n-1 in the form
s(x0, 2^n-1) = XOR s(-2^n+1+x0 ... 2^n-1-x0, 0),
s(2^n+1-x0, 0),
s(2^n+3-x0 ... 2^n-1+x0, 0)
where the ellipses are taken to mean every second cell position in the
range, i.e. only odd cells if the endpoints are odd, and only even cells
if the endpoints are even. (It should be noted that either of the
ranges may be empty.)
Since cells x and -x always have the same state, it's easy to see that
the first range above must XOR to state off, since the cells in it (with
the possible exception of cell 0, which is always off anyway) come in
mirror image pairs.
Since cells x and 2*(2^n+1)-x also have the same state, it follows that
the second range of cells in the above formula also has the same
symmetry, and therefore also XORs to state off. This leaves simply
s(x0, 2^n-1) = s(2^n+1-x0, 0)
which means that the pattern at generation 2^n-1 will be a mirror image
of the starting pattern, QED.
--
Ilmari Karonen
Mcintosh Harold V.
news:504b803cea6ec66a60a...@mygate.mailgate.org
> [...] Essentially, Rule 90 is an Additive Finite Field rule
> so you can practically calculate evolutions explicitly. To do lots
> of generations, use eigenvalues and eigenvectors. I'm not sure if
> the (his) paper which he has reprinted there would apply directly
> to your situation or not.
It seems the reference I had in mind was
Olivier Martin, Andrew M. Odlyzko and Stephen Wolfram
Algebraic Properties of Cellular Automata,
Communications in Mathematical Physics 93 219-258 (1984)
which was reprinted in the World Scientific reprint collection,
pages 51-90, but not in the Addison-Wesley collection.
Besides eigenvalues and eigenvectors, there is a Green's function,
which soulld be even more helpful.
David C
> When playing with 1D cellular automata, I have found the following property of the Rule 90 automaton. On states of certain finite lengths (powers of two, it appears), surrounded at the sides by zeroes (which themselves don't undergo change), the whole state is reversed left-to-right after a number of steps equal to the length of thestate. Example, for a 16-cell state:|## ##### # # ||## # ## # #| |## # ##### # # ||#### # # #||# ### # # # # || ### # ## #| |## # # ### ||## ## # ## ## ||###### #### ###||# #### # # #| | # ## ### ||# ####### ## || # # ### || # # # # ## | |# # # ## ### || # # ##### ##|The first state (random): |## ##### # # |The final state:| # # ##### ##|I couldn't find anything regarding this property on the 'net, or in Wolfram's NKS. Is this a known property?Nikita Ayzikovsky.
I am investigating a cellular automata that can compute each entry in Sequence A086839 separately. It is very likely that it is an implementation of rule 90. http://logicruleca.webs.com/bsg_list.html The listing in OEIS stops at 31. Here is a listing of additional entries. The entries with a '?' denotes an entry that takes a very long time to compute. I am attempting to re-write the algorithm in 8086 assembly that should allow a few more entries to be computed.
I am curious if this cellular automata is actually compting A086839 or if the predicitions would break down after a while.
OEIS Sequence A086839 continuing:
1 - 31 as listed in A086389
32 63
33 ?
34 4194303
35 ?
36 511
37 1048575
38 ?
39 ?
40 ?
41 ?
42 255
43 ?
44 2047
45 4095
46 1023
47 ?
48 ?
49 32767
50 ?
51 ?
52 4095
53 ?
54 262143
55 ?
56 16383
57 ?
58 4095
59 ?
60 ?
61 1048575
62 ?
63 127
64 127
65 ?
66 262143
67 ?
68 ?
69 ?
70 ?
71 ?
72 16383
73 ?
74 ?
75 32767
76 ?
77 1048575
78 ?
79 ?
80 ?
81 ?
82 1048575
83 ?
84 ?
85 511
86 ?
87 ?
88 ?
89 ?
90 ?
91 ?
92 262143
93 ?
94 262143
95 ?
96 ?
97 4095
98 ?
99 ?
100 ?
101 ?
102 1023
103 ?
104 ?
105 ?
106 ?
107 ?
108 32767
109 262143
110 ?
111 ?
112 ?
113 ?
114 ?
115 ?
116 ?
117 ?
118 ?
119 ?
120 4095
121 ?
122 ?
123 ?
124 ?
125 ?
126 ?
127 255
128 255
129 ?
130 ?
131 ?
132 ?
133 4194303
134 ?
135 ?
136 4095
137 1048575