Interestingly, the theory of nested recurrence relations has been correlated with “discrete chaos” by Golomb (1991) and Tanny (1992).

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).

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 is usually considered as a definition of deterministic chaos.

  • 2
    $\begingroup$ Interestingly, all of this seems to hinge on a preprint that was apparently never published. $\endgroup$ – Wrzlprmft Aug 3 at 12:51
  • 1
    $\begingroup$ Isn't all this addressed by symbolic dynamics ? en.wikipedia.org/wiki/Symbolic_dynamics $\endgroup$ – Piyush Grover Aug 4 at 18:38
  • 1
    $\begingroup$ @PiyushGrover: Unless there is some facet of it that I don’t know about, symbolic dynamics discretises states of a continious-state dynamics for analysis. $\endgroup$ – Wrzlprmft Aug 4 at 18:41
  • 1
    $\begingroup$ It appears that the never published preprint is available at oeis.org/A005185/a005185_1.pdf $\endgroup$ – Gerry Myerson Aug 5 at 0:14
  • 1
    $\begingroup$ Has anyone made a serious attempt to do this using finite state automata? I'm thinking of some of the chaotic (as they seem to me) configurations that arise in Conway's Game of Life. $\endgroup$ – Mark Wildon Aug 5 at 17:41

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 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.

| cite | improve this answer | |
  • $\begingroup$ "Chaotic dynamics are unbounded." Did you mean bounded? $\endgroup$ – Gerry Myerson Aug 5 at 0:16
  • $\begingroup$ @GerryMyerson: Indeed, fixed. $\endgroup$ – Wrzlprmft Aug 5 at 6:12
  • $\begingroup$ @Wrzlprmft, many thanks for your answer that explain the key points of my question deeply. I agree with your remarks in terms of scope of my question. Best regards. $\endgroup$ – Alkan Aug 5 at 8:14

As Piyush Grover mentioned, symbolic dynamics provides a solid foundation for studying the dynamics with a discrete phase space. Usually one considers just a finite alphabet of symbols, however one may also consider all of $\mathbb{Z}$ as the alphabet. If one computes the topological entropy of the dynamical system to be positive, it may be considered to be chaotic.

A likely obstacle though in the definition of topological entropy is that it assumes that the phase space (or at the least the chaotic attractor) is compact. While there is no “one true” definition of chaos, a system where everything runs off to infinity would not be considered to be chaotic – even if everything runs off to infinity in a slightly different way.

To get around that, perhaps you could take your integer sequences modulo $p$ and show they have positive topological entropy for some and/or all $p \geq 2$.

| cite | improve this answer | |
  • 1
    $\begingroup$ To get around that, perhaps you could take your integer sequences modulo $p$ – If you do that, what you are assessing with your symbolic apparatus is not the full state of the dynamical system anymore. The compactness aspect of chaos relates to the actual state of the system, not a projection of it. You cannot run the system completely in modulo $p$. $\endgroup$ – Wrzlprmft Aug 5 at 6:29

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.