4 ms·

I thought that cellular referred to each point (cell) having its own neighborhood and reacting individually. IIRC, cellular automata have been generalized (mad

I thought that cellular referred to each point (cell) having its own neighborhood and reacting individually. IIRC, cellular automata have been generalized (made continuous) in both space and time by various researchers, making them (as you point out) less "cellular". As for how they are different from general dynamical systems, the GDSs I've seen have a small set of differential equations that describe the whole system; a cellular automaton has the same rule for each cell but the system comprises a large number of cells. In other words, locality and massive parallelism. But this isn't my field so correct me if I'm wrong...

jessriedel 7y ago
That definition of cellular automata would still include all local dynamical systems in physics, e.g., the wave equation, the heat equation, etc.
- posterboy 7y ago
  except those aren't automata in the chomsky hierarchy
  - jessriedel 7y ago
    But no continuous systems are in the Chomsky hierarchy, right? Isn't that just support for my suggestion that cellular automata are by definition discrete?
    - posterboy 7y ago
      The simulation is still using floating point. The fundamental Floating point arithmetic is regular in principle. It's the rules and algorithms that can potentially achieve higher order. And even classical game of live is turing complete. They built a TM inside GoL! But it can be modeled by a finite state automaton (if the grid is finite), I suppose, so the rules are just a regular grammar. A regular machine can output the grammar of a context sensitive language, but not accept the corresponding programms. In the same sense, the turing machine in GoL is ... you know what, I have no idea.
      - posterboy 7y ago
        PS: I'm not sure how Lenia is implemented. If the model is that the points move, you can nevertheless think of each point as a cell on a regular grid, that holds a n-ary variable, that encodes the color (or hight or what) and the position in a x*y=n-1 dimensional coordinate sytem, with one dimension per cell. In other words, each cell would encode its distance to all other cells. Which seems a bit redundant.

jessriedel 7y ago

That definition of cellular automata would still include all local dynamical systems in physics, e.g., the wave equation, the heat equation, etc.

posterboy 7y ago
except those aren't automata in the chomsky hierarchy
- jessriedel 7y ago
  But no continuous systems are in the Chomsky hierarchy, right? Isn't that just support for my suggestion that cellular automata are by definition discrete?
  - posterboy 7y ago
    The simulation is still using floating point. The fundamental Floating point arithmetic is regular in principle. It's the rules and algorithms that can potentially achieve higher order. And even classical game of live is turing complete. They built a TM inside GoL! But it can be modeled by a finite state automaton (if the grid is finite), I suppose, so the rules are just a regular grammar. A regular machine can output the grammar of a context sensitive language, but not accept the corresponding programms. In the same sense, the turing machine in GoL is ... you know what, I have no idea.
    - posterboy 7y ago
      PS: I'm not sure how Lenia is implemented. If the model is that the points move, you can nevertheless think of each point as a cell on a regular grid, that holds a n-ary variable, that encodes the color (or hight or what) and the position in a x*y=n-1 dimensional coordinate sytem, with one dimension per cell. In other words, each cell would encode its distance to all other cells. Which seems a bit redundant.