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?
PRNG
s 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$