3 ms·

Seeing this wonderful simulation makes me wonder if a physics simulation using cellular automata could benefit from a HashLife-esque algo to speed up calculatio

Seeing this wonderful simulation makes me wonder if a physics simulation using cellular automata could benefit from a HashLife-esque algo to speed up calculations. For GoL, the speedups are just insane. The linked wiki shows a simulation: The 6,366,548,773,467,669,985,195,496,000 (6 octillionth) generation of a Turing machine in Life computed in less than 30 seconds on an Intel Core Duo 2GHz CPU using Hashlife But then of course, Game of Life has loads of 'boring' repeating stuff and is much more discrete compared to physical fluid dynamics simulation. https://en.m.wikipedia.org/wiki/Hashlife https://en.m.wikipedia.org/wiki/Hashlife

renox 4y ago
I'm not an expert on this topic but: GoL cells have only a very limited number of states whereas realistic simulations have a big numbers of possible states for each cells so I doubt it's possible.
taneq 4y ago
Calling it a specific insanely high generation when it’s a repeating cycle just rubs me up the wrong way. Very cool algorithm though!
- addaon 4y ago
  It's a turing machine -- it potentially never halts / repeats. Hashlife isn't just about exponential time-stepping, though that's a major part of it -- it's also about isolating periodic portions of the grid for memoization and speed-up, without requiring that the entire grid be periodic. All said, it really is a specific insanely high generation here.
  - taneq 4y ago
    It's deterministic, though, so once it detects a repeated global state it will cycle endlessly so you're not calculating generation N, you're calculating generation firstOccurrence+N*cycleLength for all N. At least, this line from the wiki reads to me like this is what's happening: > Computed by detecting a repeating cycle in the pattern, and skipping ahead to any requested generation.
    - addaon 4y ago
      Yes. But if the automaton being modeled implements a non-terminating turing machine, there is never a repeated global state.

renox 4y ago

I'm not an expert on this topic but: GoL cells have only a very limited number of states whereas realistic simulations have a big numbers of possible states for each cells so I doubt it's possible.

taneq 4y ago

Calling it a specific insanely high generation when it’s a repeating cycle just rubs me up the wrong way. Very cool algorithm though!

addaon 4y ago
It's a turing machine -- it potentially never halts / repeats. Hashlife isn't just about exponential time-stepping, though that's a major part of it -- it's also about isolating periodic portions of the grid for memoization and speed-up, without requiring that the entire grid be periodic. All said, it really is a specific insanely high generation here.
- taneq 4y ago
  It's deterministic, though, so once it detects a repeated global state it will cycle endlessly so you're not calculating generation N, you're calculating generation firstOccurrence+N*cycleLength for all N. At least, this line from the wiki reads to me like this is what's happening: > Computed by detecting a repeating cycle in the pattern, and skipping ahead to any requested generation.
  - addaon 4y ago
    Yes. But if the automaton being modeled implements a non-terminating turing machine, there is never a repeated global state.