Interestingly, the theory of nested recurrence relations has been correlated with “discrete chaos” by [Golomb (1991)](https://oeis.org/A005185/a005185_1.pdf) and [Tanny (1992)](https://www.sciencedirect.com/science/article/pii/0012365X92901456).


And in literature, there are very few studies that have different approaches on *chaos* in integer sequences. One curious example that has an interesting definition is by [Fraenkel (1994)](https://www.ams.org/journals/tran/1994-341-02/S0002-9947-1994-1138949-9/home.html).


**Question:** Are there other definitions of deterministic chaos for integer sequences that are generated by a recurrence relation? If the answer is *no,* why are attempts to define chaos with discrete states so scarce?


For usual discrete dynamical systems such as maps, a positive maximal [Lyapunov exponent](https://en.wikipedia.org/wiki/Lyapunov_exponent) is usually considered as a definition of deterministic chaos.



Why are attempts to define chaos with discrete states so scarce?
The biggest problem I see with discrete-state chaos is that you would want it to capture some characteristic features of normal chaos (i.e., in the sense of chaos theory), namely:


* Chaos is sensitive to initial conditions, i.e., arbitrarily small changes to the initial condition blow up.
* Chaotic dynamics are aperiodic, i.e., they do not repeat.
* Chaotic dynamics are bounded.


Mind that there is no final agreement on how to define chaos (as there is no big need for it), so the above are only what most people consider to be necessary conditions.
Anything named *chaos* that utterly fails to meet these criteria would probably raise false expectations and you are probably better off with another name for whatever interesting property you found.


In this light, I see two, not entirely unrelated problems with extending the concept of chaos to discrete states:


* Sensitivity to initial conditions requires some notion of distance that allows for infinitesimally close states (to every state, not just selected ones). Discrete states do not have this. You might cheat around this by letting finite distances grow to infinity, but then you lose boundedness.
* If a deterministic dynamics can only have a $n$ discrete states, it will inevitably be periodic. If, on the other hand, you have infinitely many, discrete states, your chaos it is not bounded.


The sequences in question kind-of alleviate this issues by introducing a state-dependent delay into the sequence:


$$ Q\_t = Q\_{t−Q\_{t-1}} + Q\_{t-Q\_{t-2}}$$


Thus, the actual state of the dynamics is not only defined by its current value of the sequence ($Q\_t$), but by its entire past, or at least a slice of it that can be arbitrarily large.
To avoid repetition, you still need unbounded states: Otherwise your state and thus your delay would be limited and you would have periodicity eventually.
However, due to the combinatorial explosion ensuing from having a arbitrarily dimensional state, you can approach infinity much more slowly.
Still, you have unbounded states and thus I would consider it problematic to denote this as *chaos.*


Finally note that every computer simulation of chaos is inevitably only a discrete approximation, as you only have finitely many floating-point numbers (or whatever number format you use).



> 
> For usual discrete dynamical systems such as maps, a positive maximal [Lyapunov exponent](https://en.wikipedia.org/wiki/Lyapunov_exponent) is usually considered as a definition of deterministic chaos.
> 
> 
> 


Note that a positive Lyapunov exponent does not suffice for chaos. It is only a necessary property.


