1
$\begingroup$

I'm looking for a simple rewrite system which displays high period.

In order to do that, I've ran a brute-force search on every elementary cellular automata, for a few fixed memory lengths L. The result is that, when L=7, there are rules with the max possible period (128). Yet, for L=8, no matter which rule is used, I couldn't get a period > 180. For L=9, the maximum period of 133.

I've, then, tried a few variations of the core idea. For example, I tried using 3 symbols instead of just 2 and do a similar brute-force search, but the results are similar.

Thus, I ask: is there any similar system with a rewrite rule which displays high period?

$\endgroup$
  • $\begingroup$ Hey, could you explicitly state what is "high period" or "period"? I think it might be just about automaton falling into cycle, but it is not obvious. Also it seems that it is 1D, right? $\endgroup$ – Evil Jul 27 '16 at 18:25
  • $\begingroup$ @Evil yes, 1D, and that is what I mean with high period, I mean that it has a cycle with a high number of states - ideally, the cycle will contain all possible states. $\endgroup$ – MaiaVictor Jul 27 '16 at 19:31
  • $\begingroup$ What do you mean by "basic" automaton? I understand the problem but not constraints given. It is a bit different idea, but PRNG with small state is quite similar to what you need (but symbols count and size increases etc). $\endgroup$ – Evil Jul 27 '16 at 20:46
  • $\begingroup$ @Evil Yep but PRNGs are quite complex in comparison (think of the amount of complexity it would take to describe addition, modulus, multiplication from scratch). One of the reasons I want that is for finding a simple PRNG, and a simple counter on the λ-calculus. $\endgroup$ – MaiaVictor Jul 27 '16 at 22:49
  • 1
    $\begingroup$ I hope that LFSR as CA with "highest feasible" period would do the trick. Two simple operations (three if you count assignment). Maybe I have overused $2^L-1$ because one additional bit is used for register. $\endgroup$ – Evil Jul 28 '16 at 5:14
3
$\begingroup$

Used symbols will be $0, 1$, table $T$ with $18$ elements ($L=18$), and one element for register $B$.
Initialize table with any configuration with at least one element set to $1$.

At generation step do:
B = T[0] Xor T[7]
T[i] = T[i - 1]
T[0] = B

The array bounds act like wall, if you read from outside you get $0$. This is simple rewrite system, with minimal number of operations without any fancy operations, only rewrite by one calculate xor of two cells (hey, Rule 90 takes three), and has period $262143$ giving all $18 bit$ numbers excluding $0$.

How to get such system? This is Linear feedback shift register which fits your description of PRNG, has the highest possible period ($2^L-1$) for given number of bits (cells?) minus 1, the best one would have $2^L$.

$\endgroup$
  • $\begingroup$ Uhm that is something I never heard of which looks spot on. I'm confused by why T[0] Xor T[7] specifically. I'll read more about it, thank you! $\endgroup$ – MaiaVictor Jul 28 '16 at 10:50
  • $\begingroup$ @D.W. I have checked that this particular solution is $2^{18}-1$ (also the other properties match the description), to get arbitrary $2^L-1$ it will be needed to change the feedback polynomial. $\endgroup$ – Evil Jul 28 '16 at 10:58
  • $\begingroup$ Yes, it is primitive polynomial (sorry I had to check the name / term). $\endgroup$ – Evil Jul 28 '16 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.