4 ms·
The basic idea is to use the distance of the gliders to encode information, so when they hit each other allows for an embedding of a Turing machine. I'm no exp
by abetusk 4y ago
The basic idea is to use the distance of the gliders to encode information, so when they hit each other allows for an embedding of a Turing machine.
I'm no expert here but some basic ideas are that some small number of gliders (two?) can hit each other and produce a "glider gun", allowing for just a few gliders to "upgrade" to producing a steady stream of gliders. There's a "Reverse Caber Tosser" (RCT) structure which has a stationary element that "tosses" a glider back and forth with a structure moving away (or towards?) it, emitting another glider in another direction after each toss, allowing for logarithmic glider/population growth. Another key idea looks to be the "glider producing switch engine" (GPSE) which incorporates the ideas of the RCT with a delay and some other logic?
The distances involved are astronomical because they're encoding everything in the distance but they still manage to make it Turing machine equivalent with only 15 gliders.
Anyway, I'm floored at the ingenuity of the GoL community. It's as close to programming with butterflies as I've ever seen [0].
[0] https://xkcd.com/378/ https://xkcd.com/378/
- hinkley 4y agoI might have my books mixed up but I believe this idea was a subplot in one of David Brin's early books, The Practice Effect. First Edition: 1984.
- biggiemac42 4y agoTo clean up the mistakes in your summary: 4 gliders hit each other to make a stream of gliders. This isn't a gun, because a gun costs more. instead it's a GPSE, which looks like a gun from the barrel end, but has a limit. As it approaches that limit, the RCT mechanism lets another three GPSEs generate an arbitrary list of bits, controlled by the precise location of the first (as a binary number). The final count 15 comes from the naive 4×4 minus one from being able to piggyback one of the constructions off a neighbor to save a single glider. From bits to an embedded turing machine is gol magic that the blog post treats better than my comment could.
- robertsdionne 4y agoIt's like how a Turing machine tape can be represented by two natural numbers (or even a single natural number via interleaving).
- dvgrn 4y agoThe reference that comes to mind for me is something out of one of Martin Gardner's _Aha! Insight_ books from decades ago -- the idea of encoding something like the Encyclopedia Britannica into one big long bitstring, then converting it into a fraction... and putting one single very careful mark on a stick to represent that fraction. The difference is that where the real world doesn't allow for storing anywhere near that level of precision in a mark on a stick, the Conway's Life universe is considered to be unbounded, so there's as much room as we need to implement this RCT trick.