Once a year or so I find myself on those forums and I'm always astounded how many people there are that dedicate massive amounts of time and brain power to this.
There's something exceedingly interesting about how you can model complexity with something extremely simple. Brainfuck is fun because it forces you to think extremely low level, because ultimately it is basically just a raw implementation of a Turing machine. I wouldn't want to write a big program in it, but it is fun to think about how you might express a complicated algorithm with it.
Similarly with CGOL, it is really interesting to see how far you can stretch really simple rules into something really complex.
I've written CGOL dozens of times, it's a common project that I do to "break in" a language I've learned, since it's not completely trivial but it's simple enough to not be frustrating, and I completely understand why math/computability-theory folks find it something to dedicate brain power to.
I would probably need to find a similar language with a different name though.
You don’t really get any of that with brainfuck. You have a theoretical tape and counters and that’s basically it.
"What if we had the lambda calculus without the lambda forms?" asked no one.
Primarily because of the note on the "calculating pi" example program:
> Richard Mitton supplies this amazing program which calculates an approximation of pi... literally by dividing a circular area by the radius twice.
> Naturally, a more accurate value can be obtained by using a bigger program.
This was recreated from memory. I think it is close but I may have a bounding bug.
import random
def pi(count):
inside = 0
for i in range(count):
test_x = random.random()
test_y = random.random()
if test_x ** 2 + test_y ** 2 < 1:
inside += 1
return inside / count * 4 #above is a quarter circle
print(pi(2 ** 30) )```
$ cat << EOF > pi.py
state = [0, 0, 2*8, 2*12]; _ = [print(f'\rRun {state.__setitem__(0, state[0] + 1) or state[0]}/{state[3]} | Last \u03c0: {current_pi:.6f} | *Average \u03c0: {(state.__setitem__(1, state[1] + current_pi) or state[1]) / state[0]:.6f}*', end='', flush=True) for current_pi in [(4 * sum([1 for _ in range(state[2]) if __import__("random").random()*2 + __import__("random").random()*2 < 1]) / state[2]) for _ in range(state[3])]]; print()
EOF
$ time python3 pi.py
Run 4096/4096 | Last π: 3.140625 | *Average π: 3.143051*
python3 pi.py 0.41s user 0.01s system 99% cpu 0.429 total
```
Play around with the `2*8` and `2*10` values in the state, they control the amount of rounds and the range in which the random values get generated respectively.
Honestly, as an educational tool, the only thing wrong with it is the name!
Writing a naive CGOL is fun and quick. But writing a _fast_ one can get arbitrarily complicated.
https://en.wikipedia.org/wiki/Hashlife is one particular example of where you can go for a faster-than-naive CGOL.
Or even just lots and lots of variation and some process selecting which one we focus our attention one. Compare the anthropic principle.
In our current algorithmic-obsessed era, this is reminiscent of procedural generation (but down/up the scale of complexity, not "one man's sky" style of PG).
However, we also have a long track record of seeing the world as nails for our latest hammer. The idea of an algorithm, or even computation in general, could be in reality conceptually closer to "pointy stone tool" than "ultimate substrate".
That's a tempting thing to say, but quantum mechanics suggests that we don't have infinite layers at the bottom. Most thermodynamic arguments combined with quantum mechanics. See eg also https://en.wikipedia.org/wiki/Bekenstein_bound about the amount of information that can even in theory be contained in a specific volume of space time.
> the maximum amount of information that is required to perfectly describe a given physical system _down to the quantum level_
(emphasis added by me)
It looks like it makes predictions for the quantum layer and above.
--
Historically, we humans have a long proven track record of missing layers at the bottom that were unknown but now are known.
You could do it on an analog computer but then you'd be into the noise very quickly.
In theory you can, but in practice this is super hard to do.
Btw, quantum mechanics is both linear and stable--and even deterministic. Admittedly it's a bit of a mystery how the observed chaotic nature of eg Newtonian billard balls emerges from quantum mechanics.
'Stable' in this case means that small perturbations in the input only lead to small perturbations in the output. You can insert your favourite epsilon-delta formalisation of that concept, if you wish.
To get back to the meat of your comment:
You can simulate such a stable system 'lazily'. Ie you simulate it with any given fixed precision at first, and (only) when someone zooms in to have a closer look at a specific part, you increase the precision of the numbers in your simulation. (Thanks to the finite speed of light, you might even get away with only re-simulating that part of your system with higher fidelity. But I'm not quite sure.)
Remember those fractal explorers like Fractint that used to be all the rage: they were digital at heart---obviously---but you could zoom in arbitrarily as if they had infinite continuous precision.
Sure, but that 'If' isn't true for all but the simplest analog systems. Non-linearities are present in the most unexpected places and just about every system can be made to oscillate.
That's the whole reason digital won out: not because we can't make analog computers but because it is impossible to make analog computers beyond a certain level of complexity if you want deterministic behavior. Of course with LLMs we're throwing all of that gain overboard again but the basic premise still holds: if you don't quantize you drown in an accumulation of noise.
Quantum mechanics is linear and stable. Quantum mechanics is behind all systems (analog or otherwise), unless they become big enough that gravity becomes important.
> That's the whole reason digital won out: not because we can't make analog computers but because it is impossible to make analog computers beyond a certain level of complexity if you want deterministic behavior.
It's more to do with precision: analog computers have tolerances. It's easier and cheaper to get to high precision with digital computers. Digital computers are also much easier to make programmable. And in the case of analog vs digital electronic computers: digital uses less energy than analog.
It goes much beyond just cellular automata, the thousand pages or so all seem to drive down the same few points:
- "I, Stephen Wolfram, am an unprecedented genius" (not my favorite part of the book) - Simple rules lead to complexity when iterated upon - The invention of field of computation is as big and important of an invention as the field of mathematics
The last one is less explicit, but it's what I took away from it. Computation is of course part of mathematics, but it is a kind of "live" mathematics. Executable mathematics.
Super cool book and absolutely worth reading if you're into this kind of thing.
I say something-like-Turing completeness, because it requires a very specially prepared tape to work that makes it a bit borderline. (But please look it up properly, this is all from memory.)
Having said all that, the result is a nice optimisation / upper bound on how little you need in terms of CA to get Turing completeness, but I agree that philosophically nothing much changes compared to having to use a slightly more complicated CA to get to Turing completeness.