I find it astonishing that new discoveries for life are still found. It is such a simple set of rules, that you’d think it would be fully understood, and fully research complete by now.
Conway’s Game of Life is Turing-complete. I wonder if that makes it literally impossible to find an exact upper bound for the fastest possible spaceship?
Not inherently. If you just want an upper bound rather than one you know is achievable, nothing can move faster than one cell per tick. :)
A little more formally: You can still prove things about the system and its rules, in general. You could even prove that particular start states halt or don’t. What you can’t do is decide the halting problem for the general case of all start states.
nothing can move faster than one cell per tick
Of course. I said exact upper bound because I was wondering if perhaps there doesn’t exist a unique fastest spaceship? ♥
Edit: oh so apparently there does exist a unique fastest spaceship, moving at c/2. Darn.
The fastest possible spaceship moves at exactly c/2 and there are many known spaceships with that speed. There is a known algorithm for constructing arbitrarily slow spaceships. What makes this one interesting is that it’s a small, primitive-ish construct that moves more slowly than any that was previously known.
A while ago we came up with a pretty good axiomatic basis for math, ZFC is such a simple set of rules, you would think math would be fully understood by now.
Go is such a simple board game, there are barely any rules at all! You would think we would have solved it by now.
Lisp is such a simple language, the first definition of it fit on a single half-page! You would think we would know everything about macros by now.
Please don’t assume my comments were meant to put down the people doing important work on Life, cellular automaton generally, or the people dedicating every waking moment to understand Go, or ZFC, or what have you. They weren’t.
It’s just fascinating to me that something that can be implemented in a couple of lines of code, by a first year programming student, still has the ability (with each new discovery) to completely alter our perspective across so many different scientific disciplines.
Sorry, that comment came off a little harsher than I had intended.
I meant to point out that while our intuition is that simple rules lead to simple systems there are quite a few counter-examples which show that intuition wrong. Turing machines and lambda calculus are notable examples, using nothing but function application you can compute anything. Considering Life was explicitly engineered to have simple rules create complex behavior, is it really that surprising that it does?
If I can be a pedant for just a little longer. This discovery is certainly cool and it’s fun to hear about the kinds of research still happening in Life, but I doubt it has altered our perspective in any discipline, including Life. The article even mentions the most notable thing about this discovery is that it was low-hanging fruit, nobody has even bothered to look for it before.
but I doubt it has altered our perspective in any discipline, including Life. The article even mentions the most notable thing about this discovery is that it was low-hanging fruit, nobody has even bothered to look for it before
Sure. But, I think you’re again missing my point. Cellular automatons are studied in a number of different disciplines. While this particular discovery is “meh,” tomorrow’s discovery might lead to the next unbreakable crypto, or understanding of sea creature $X, which leads to prevention of $Y’s extinction. Maybe that’s all far fetched, but…
Simple rules can give rise to complex behaviour. Chemistry is “solved” in as much as the basic rules are known, but important discoveries are made every day. A group is the most basic and banal construct, but the classification of groups was only recently finished and there’s still fascinating research to be done.
the story aspect of this is pretty fascinating too - someone came out of nowhere with a search technique that found this in 19 seconds (while the standard gfind program took an hour to reproduce the discovery), delivered the result, and from the looks of it has vanished again, or has at the least not made another post (other than one comment in the thread) in the 4-5 days since.
I could easily imagine them being overwhelmed by the response and trying to process the feelings before saying anything else!
I think (especially given the tone of their one reply) it’s more likely they don’t care anything like as much as the rest of these people about their discovery, and if anything may be slightly freaked out by the reactions of these obsessives. The whole thread made me think of http://www.newyorker.com/magazine/2012/12/24/utopian-for-beginners
He just came back and shared his source.