4 ms·

Is there any hardware designed to just run cellular automata? I wonder if it could actually be a very efficient form of calculation, because cells are almost b

Is there any hardware designed to just run cellular automata? I wonder if it could actually be a very efficient form of calculation, because cells are almost bits, but seem to possess more power than bits. For instance this Lisp in GoL. Could it run faster than lisps on "bit processors" if it ran on special purpose hardware? So instead of 64-bit processors we might have "64-cell processors" ?

nynx 5y ago
You could totally design a chip that runs some cellular automata or another, but there's not much point aside from it being cool.
m12k 5y ago
Do modern graphics cards have optimizations for applying a kernel to a texture? If so, that should work well with cellular automata too
eesmith 5y ago
GoL implementations for big systems don't evaluate the cellular automata step-by-step. They implement HashLife - https://en.wikipedia.org/wiki/Hashlife https://en.wikipedia.org/wiki/Hashlife . The first example on that page shows position 6.3+ octillion for a Turing machine, computed in under 30 seconds. If the special purpose hardware ran at 1 THz, it would take about 4 quadrillion seconds to get to the same point, which is a bit over 200 million years.
- galaxyLogic 5y ago
  Special-purpose hardware for cellular automata would not evaluate it "step-by-step" either, but in parallel. Every cell could evaluate its next state independently of others. We could think of some kind of version of RAM where each 'cell' would implement this behavior. Perhaps similar optimizations like HashLife could be developed for such special purpose hardware as well.
  - rezmason 5y ago
    I implemented Hashlife for a different CA rule set earlier this year. Hashlife's data structure is a quad tree embedded in a hash table. Most Hashlife instances only spend a few short moments simulating cellular automata at the "ground level"— the real work involves combining the future of the children of a quad tree node into the future of the node. That might be optimizable, but it feels extremely application-specific. Edit: shameless, shameless plug: https://rezmason.github.io/wireworld-player/?engine=macrocell https://rezmason.github.io/wireworld-player/?engine=macrocel...
  - eesmith 5y ago
    "evaluate its next state" is what I meant by "step-by-step". There could certainly be a dedicated hardware implementation of HashLife. It would not be based on the idea "cells are almost bits", nor would it be faster than a direct CPU implementation of Lisp.
    - galaxyLogic 5y ago
      But isn't the idea of Game of Life to evaluate all its states, all the steps, step by step? Or is HashLife doing something like "Calculating state N + 100 without having to calculate all states in between?
      - woodrush 5y ago
        Hi, I'm the author of this project. HashLife actually does just that, by memoizing and reusing past occurrences and outcomes of the same pattern. Since one cell can only interact with its 8 neighbors in one timestep, there is a limit to the distance that a fixed-size pattern can interfere with in a fixed amount of time, analogous to the speed of light in physics. (It is in fact called the speed of light for cellular automatons as well, as described in https://en.wikipedia.org/wiki/Speed_of_light_(cellular_automaton) https://en.wikipedia.org/wiki/Speed_of_light_(cellular_autom... .) Therefore, by remembering the outcomes of a certain pattern in a certain timeframe, you can jump to that amount of time in one step by using the memoized pattern. More details are explained in this article: https://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478 https://www.drdobbs.com/jvm/an-algorithm-for-compressing-spa... By the way, with all the passion for Lisp, simple but Turing-complete systems, and programming that I put into this project, I'm very happy that other people have enjoyed it too. Thanks to everyone for checking it out!
abecedarius 5y ago
Cellular Automata Machines by Toffoli and Margolus. Somewhere over 30 years ago now.

nynx 5y ago

You could totally design a chip that runs some cellular automata or another, but there's not much point aside from it being cool.

m12k 5y ago

Do modern graphics cards have optimizations for applying a kernel to a texture? If so, that should work well with cellular automata too

eesmith 5y ago

GoL implementations for big systems don't evaluate the cellular automata step-by-step. They implement HashLife - https://en.wikipedia.org/wiki/Hashlife https://en.wikipedia.org/wiki/Hashlife . The first example on that page shows position 6.3+ octillion for a Turing machine, computed in under 30 seconds. If the special purpose hardware ran at 1 THz, it would take about 4 quadrillion seconds to get to the same point, which is a bit over 200 million years.

galaxyLogic 5y ago
Special-purpose hardware for cellular automata would not evaluate it "step-by-step" either, but in parallel. Every cell could evaluate its next state independently of others. We could think of some kind of version of RAM where each 'cell' would implement this behavior. Perhaps similar optimizations like HashLife could be developed for such special purpose hardware as well.
- rezmason 5y ago
  I implemented Hashlife for a different CA rule set earlier this year. Hashlife's data structure is a quad tree embedded in a hash table. Most Hashlife instances only spend a few short moments simulating cellular automata at the "ground level"— the real work involves combining the future of the children of a quad tree node into the future of the node. That might be optimizable, but it feels extremely application-specific. Edit: shameless, shameless plug: https://rezmason.github.io/wireworld-player/?engine=macrocell https://rezmason.github.io/wireworld-player/?engine=macrocel...
- eesmith 5y ago
  "evaluate its next state" is what I meant by "step-by-step". There could certainly be a dedicated hardware implementation of HashLife. It would not be based on the idea "cells are almost bits", nor would it be faster than a direct CPU implementation of Lisp.
  - galaxyLogic 5y ago
    But isn't the idea of Game of Life to evaluate all its states, all the steps, step by step? Or is HashLife doing something like "Calculating state N + 100 without having to calculate all states in between?
    - woodrush 5y ago
      Hi, I'm the author of this project. HashLife actually does just that, by memoizing and reusing past occurrences and outcomes of the same pattern. Since one cell can only interact with its 8 neighbors in one timestep, there is a limit to the distance that a fixed-size pattern can interfere with in a fixed amount of time, analogous to the speed of light in physics. (It is in fact called the speed of light for cellular automatons as well, as described in https://en.wikipedia.org/wiki/Speed_of_light_(cellular_automaton) https://en.wikipedia.org/wiki/Speed_of_light_(cellular_autom... .) Therefore, by remembering the outcomes of a certain pattern in a certain timeframe, you can jump to that amount of time in one step by using the memoized pattern. More details are explained in this article: https://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478 https://www.drdobbs.com/jvm/an-algorithm-for-compressing-spa... By the way, with all the passion for Lisp, simple but Turing-complete systems, and programming that I put into this project, I'm very happy that other people have enjoyed it too. Thanks to everyone for checking it out!

abecedarius 5y ago

Cellular Automata Machines by Toffoli and Margolus. Somewhere over 30 years ago now.