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?

Improve this question
$\endgroup$
7
  • $\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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 5:14

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
3
  • $\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, 2016 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, 2016 at 10:58
  • $\begingroup$ Yes, it is primitive polynomial (sorry I had to check the name / term). $\endgroup$
    – Evil
    Jul 28, 2016 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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