Is this c/10 spaceship known?(conwaylife.com)
conwaylife.com
Is this c/10 spaceship known?
http://www.conwaylife.com/forums/viewtopic.php?f=2&t=2057
91 comments
This writeup (found a few pages into the thread) explains things in a little bit more detail for a newcomer. https://niginsblog.wordpress.com/2016/03/07/new-spaceship-sp...
That is an awesome post and gives hints into the depth the community has gone into the conway game
This is a great post.
That's a beautifully concise numbering system for sharing being used there.
Now if only we had descriptions of chemistry that were this terse. Imagine if this kind of problem solving, collaboration, simulation, and instant verification were the norm for synthetic chem. One of the comments -- "[Let's] use gencols to rub the ship against gliders and *WSSs to see whether there is a useful collision to maybe build a puffer" -- just blew me away. If this were chemistry, that commentator would have been suggesting automatic nanomachine factory discovery.
(InChI appears to be close. But vast amounts of data are locked up in obtuse formats are either Assigned-Names-And-Numbers style formats which are useless to indexing and similarity searches, or formats that embed non-relative coordinates in 3d space, etc, in such a way that computing a deterministic ID for sharing is practically a nonstarter.)
Now if only we had descriptions of chemistry that were this terse. Imagine if this kind of problem solving, collaboration, simulation, and instant verification were the norm for synthetic chem. One of the comments -- "[Let's] use gencols to rub the ship against gliders and *WSSs to see whether there is a useful collision to maybe build a puffer" -- just blew me away. If this were chemistry, that commentator would have been suggesting automatic nanomachine factory discovery.
(InChI appears to be close. But vast amounts of data are locked up in obtuse formats are either Assigned-Names-And-Numbers style formats which are useless to indexing and similarity searches, or formats that embed non-relative coordinates in 3d space, etc, in such a way that computing a deterministic ID for sharing is practically a nonstarter.)
InChI is not designed as, nor can used for, what you propose. Last I checked, conversion from an InChI to a structure format was not a supported option, and only exists for testing purposes. Which is not to say that people don't use for that. (Also, last I checked, there are inputs which cause InChI to segfault. And there's no spec for how to interpret InChIs other than to run the reference code.)
The InChI normalization step may also change the chemistry. For example, it may put things into a preferred tautomer form or charge state. This is essential for its goal of linking disparate records, but it is not chemistry preserving, and can be worse than passing an SD file to your nanomachine factory.
It was designed as "deterministic ID for sharing", yes, but not for sharing structure information but rather information related to the structure.
The most "concise" solution is to record the positions of the nuclei and the total charge. Then any quantum mechanics program will be able to reconstruct (to the desired level of approximation) the electron density of the molecule. This is the one you reject.
For good reasons. As you say, you want a nomenclature that can help with identity and similarity, and electron density is a very slow way to do that.
But such nomenclature is driven by human concepts. Fundamentally, there are different reaction rates depending on the relative orientation of two molecules. We see this in molecular beam experiments. For example, from 1979, http://www.sciencedirect.com/science/article/pii/00092614798... "Molecular beam reaction of K atoms with sideways oriented CF3I".
InChI doesn't have a special name for "sideways oriented CF3I", even though a complete, concise system would have to be able to provide a name for it.
Instead, we've come up with concise approximations - a SMILES string, a bitstring fingerprint, etc. - which are tractable for the purposes you want, so long as we stay within relatively normal chemistry. But it's still humans who categorize things into, say, "aromatic" or "chiral", so our approximate nomenclature has to partially encode how humans think of chemistry.
The Game of Life is much simpler than the Reality of Life.
The InChI normalization step may also change the chemistry. For example, it may put things into a preferred tautomer form or charge state. This is essential for its goal of linking disparate records, but it is not chemistry preserving, and can be worse than passing an SD file to your nanomachine factory.
It was designed as "deterministic ID for sharing", yes, but not for sharing structure information but rather information related to the structure.
The most "concise" solution is to record the positions of the nuclei and the total charge. Then any quantum mechanics program will be able to reconstruct (to the desired level of approximation) the electron density of the molecule. This is the one you reject.
For good reasons. As you say, you want a nomenclature that can help with identity and similarity, and electron density is a very slow way to do that.
But such nomenclature is driven by human concepts. Fundamentally, there are different reaction rates depending on the relative orientation of two molecules. We see this in molecular beam experiments. For example, from 1979, http://www.sciencedirect.com/science/article/pii/00092614798... "Molecular beam reaction of K atoms with sideways oriented CF3I".
InChI doesn't have a special name for "sideways oriented CF3I", even though a complete, concise system would have to be able to provide a name for it.
Instead, we've come up with concise approximations - a SMILES string, a bitstring fingerprint, etc. - which are tractable for the purposes you want, so long as we stay within relatively normal chemistry. But it's still humans who categorize things into, say, "aromatic" or "chiral", so our approximate nomenclature has to partially encode how humans think of chemistry.
The Game of Life is much simpler than the Reality of Life.
All of this is true. The word "close" was chosen very, very deliberately.
Though the Game of Life is surely simpler than the Reality of Life... if one were to flat out name the core concept as "godel numbers for chemical formations", it's certainly possible, don't you think? InChI isn't it, I agree; just wanted to toss the seed of the idea out there, with an example that's a lot "closer" to the target semiotics than a bunch of unnormalized floating point coordinates drifting around in xml.
"good enough is the enemy of good" can apply in spades here, so I appreciate your thorough analysis of specific weak points in InChI.
Though the Game of Life is surely simpler than the Reality of Life... if one were to flat out name the core concept as "godel numbers for chemical formations", it's certainly possible, don't you think? InChI isn't it, I agree; just wanted to toss the seed of the idea out there, with an example that's a lot "closer" to the target semiotics than a bunch of unnormalized floating point coordinates drifting around in xml.
"good enough is the enemy of good" can apply in spades here, so I appreciate your thorough analysis of specific weak points in InChI.
InChI is not closer but actually further than SMILES or SD files for many of the use cases you wanted. It is not a supported capability to turn an InChI into a structure, which makes it hard to generate, say, a fingerprint for a Tanimoto search system. (Yes, the command-line tools and its wrappers support that, but the InChI developers do not condone its use. Even if you do so, the output may differ from your input structure in ways you disagree with.)
InChI is only closer for the classical purpose of chemical documentation - record association and text-based search. That is not a bad thing, but given the entirety of your goals, it is equally correct to use "close" for SMILES, SLN, SD, Mol2, etc.
InChI is only closer for the classical purpose of chemical documentation - record association and text-based search. That is not a bad thing, but given the entirety of your goals, it is equally correct to use "close" for SMILES, SLN, SD, Mol2, etc.
Side question: are there any open source synthetic chemistry projects that I can look at to get an idea of the techniques and problems encountered? I try to learn about a new non work related subject every few years and it piqued my interest but I haven't been able to find anything but textbooks - code is easier for me to understand.
I don't know enough about that topic to provide any sort of guidance. I don't even know who does, other than to ask on the Blue Obelisk mailing list at https://sourceforge.net/p/blueobelisk/mailman/blueobelisk-sm... .
Thanks, I've been having trouble finding a good place to start (looking) as well.
It does help that Game of Life physics is somewhat simpler than Real Life physics. Of course, Real Life physics is a little less apt to collapse into a seething mass of undifferentiated matter of you poke it in the wrong place.
This is the slowest spaceship known, right? (Which isn't a machine made out of other parts?)
This is the slowest spaceship known, right? (Which isn't a machine made out of other parts?)
> It does help that Game of Life physics is somewhat simpler than Real Life physics.
Are we sure of that yet?
> Real Life physics is a little less apt to collapse into a seething mass of undifferentiated matter of you poke it in the wrong place.
Are we sure of that yet?
Are we sure of that yet?
> Real Life physics is a little less apt to collapse into a seething mass of undifferentiated matter of you poke it in the wrong place.
Are we sure of that yet?
Yes, GoL physics is simpler than Real Life physics.
RL follows quantum mechanics. As far as we know, its state cannot be recorded perfectly.
GoL is a Turing Machine. Its state can be recorded perfectly.
RL follows relativity. There is no equivalent in GoL.
Hashlife gives a method to compute GoL boards faster than processing each cell, and gives an exact answer. There is no equivalent for RL. At best there are probabilistic predictions. (There might be a 1E-50000 chance that the Sun won't rise tomorrow because all of the atoms in the Sun fuse at the same time and it blows up.)
RL follows quantum mechanics. As far as we know, its state cannot be recorded perfectly.
GoL is a Turing Machine. Its state can be recorded perfectly.
RL follows relativity. There is no equivalent in GoL.
Hashlife gives a method to compute GoL boards faster than processing each cell, and gives an exact answer. There is no equivalent for RL. At best there are probabilistic predictions. (There might be a 1E-50000 chance that the Sun won't rise tomorrow because all of the atoms in the Sun fuse at the same time and it blows up.)
I don't think we do know that. Maybe relativity and quantum mechanics are still 10 layers of complicated structures up from a far simpler ruleset.
> RL follows relativity. There is no equivalent in GoL
Of course there is an equivalent of relativity! There's a fixed, ultimate speed-limit (i.e. c) of once-cell/time-step. It is not possible to transmit information faster than this in GoL.
Of course there is an equivalent of relativity! There's a fixed, ultimate speed-limit (i.e. c) of once-cell/time-step. It is not possible to transmit information faster than this in GoL.
You can have C without relativity. There are no relative reference frames in GoL. Reactions only work at specific absolute speeds, and most of them only work at absolute speed 0.
Relativity can exist in an absolute environment like GoL if you consider the momentum of the quantum vacuum virtual particles. Look it up :-)
Seriously guys. Downvotes for talking about digital physics? Sad me.
https://en.wikipedia.org/wiki/Superfluid_vacuum_theory#Relat...
"Relativistic quantum field theory"
https://en.wikipedia.org/wiki/Superfluid_vacuum_theory#Relat...
"Relativistic quantum field theory"
Downvotes for asking whether we're certain of some rather ignorant assumptions. -4 for me.
Um, my first comment was just referring to the fact that in an absolutely framed turing-complete environment. One can sprout a quantum vacuum full of constant noise, ie. constant producing and annihilating structures(analagous to virtual particles.)
This is already experimentally observed in our own universe. Quantum noise exists in vacuums.
If you look at C in GoL as the fastest an actual black square can propagate, then of course you'll validate your naive assumptions that our universe could never be digitally replicated by GoL. But if you take the idea of implementing a primordial sea of quantum noise, and looking at the GoL board not as physical particles directly, but as a deeper construct. Then you can actually replicate relativity.
http://arxiv.org/pdf/physics/9902034.pdf
This is already experimentally observed in our own universe. Quantum noise exists in vacuums.
If you look at C in GoL as the fastest an actual black square can propagate, then of course you'll validate your naive assumptions that our universe could never be digitally replicated by GoL. But if you take the idea of implementing a primordial sea of quantum noise, and looking at the GoL board not as physical particles directly, but as a deeper construct. Then you can actually replicate relativity.
http://arxiv.org/pdf/physics/9902034.pdf
> (There might be a 1E-50000 chance that the Sun won't rise tomorrow because all of the atoms in the Sun fuse at the same time and it blows up.)
To estimate probability of an event you must have a sample were both have occurred, to provide a probability for something like the Sun not rising tomorrow is pure non-sense.
To estimate probability of an event you must have a sample were both have occurred, to provide a probability for something like the Sun not rising tomorrow is pure non-sense.
You can easily calculate the probability of flipping heads a million times in a row, even though this also has never happened.
Because we have sampled all states of the hypothetical quarter, and are constricting many, many values concerned with flipping.
The same can't be said for the atoms in the sun.
The same can't be said for the atoms in the sun.
We have complete, verified descriptions of what the possible states look like. You can predict precisely how long it will take a cannonball to fall to the ground (at least in a vacuum), even if you've never dropped it from exactly that particular height before.
"Precise" - to within some tolerance. At some point you reach the uncertainty limits allowed by quantum mechanics.
You also have to make an arbitrary decision about when the cannonball touches the ground. How much interaction is needed between the atoms of the cannonball and ground before you say there's contact?
These issues don't exist in the GoL universe.
You also have to make an arbitrary decision about when the cannonball touches the ground. How much interaction is needed between the atoms of the cannonball and ground before you say there's contact?
These issues don't exist in the GoL universe.
We are sure that Game of Life physics is simpler than Real Life _chemistry_. There, fixed that for you.
It also helps that we GoL comes with the capacity to instantiate the universe in any configuration we wish, rather than being forced to coerce it into that state from scratch.
Not from scratch, but from inside!
Inside? Tell me what the outside is, then :)
Outside the Game of Life is easy to tell.
Outside the universe ain't. But even though, I can confidently say that we are definitely inside.
Outside the universe ain't. But even though, I can confidently say that we are definitely inside.
But does it make sense to even talk about inside and outside then when talking about the universe?
It makes about as much as uncountable infinite numbers.
I can say everything in the universe is within a countably infinite distance of me. Thus, anything an uncountable infinite distance from me is outside the universe.
Not a very tangible idea, but not useless of purpose of reasoning about the affairs of things.
Not a very tangible idea, but not useless of purpose of reasoning about the affairs of things.
It's a bit of an abuse of notation. Talking about the inside definitely makes sense. (Talking about the outside is a bit like talking about the empty set.)
Yes. Real Life physics has been proven to be either nonlocal or nondeterministic (Bell inequalities). Life physics is both local and deterministic.
"A seething mass of undifferentiated matter" describes runaway exothermic reactions fairly well.
It also helps that Games of Life can be saved and reloaded. If your lab bench explodes, too bad, start over from scratch (assuming you're uninjured).
It also helps that Games of Life can be saved and reloaded. If your lab bench explodes, too bad, start over from scratch (assuming you're uninjured).
Oh, of course, simulations without perfect replays would be an abomination! Not even worth mentioning! -- What are we, heathens who can't even manage the basics of reproducible builds?
(cough)
(cough)
Hypothesis: We don't have perfect replays because there are multiple players.
Topologically, encoding a 2D structure into a 1D line of text is dramatically simpler than encoding a 3D structure into a 1D line of text. To motivate this simply, recall that no graph whose minors include K5 or K3,3 can be drawn in the plane, whereas any graph can be drawn in 3D. It gets even simpler because all GoL graphs are confined to a grid.
tl;dr: easier problem is easier!
tl;dr: easier problem is easier!
3D software development does it with tuples all day long.
> Now if only we had descriptions of chemistry that were this terse.
Chemistry is dealing with a lot, lot more of concepts than the study of the Game of Life. Brevity only works when you have few enough information that you can map it to only concise words.
(Entropy strikes again, even if it's information entropy for a change.)
Chemistry is dealing with a lot, lot more of concepts than the study of the Game of Life. Brevity only works when you have few enough information that you can map it to only concise words.
(Entropy strikes again, even if it's information entropy for a change.)
IUPAC names are needlessly verbose and insufficiently descriptive.
if InChI doesn't do it for you, i suppose SMILES[1] isn't sufficient either? By-the-bye, you're not ever going to be able to "concisely" encode 3d (or even 2d coordinate) structures, because there isn't just one such. They're a thermally sampled average of structures.
[1] https://en.wikipedia.org/wiki/Simplified_molecular-input_lin...
[1] https://en.wikipedia.org/wiki/Simplified_molecular-input_lin...
heavenlyhash wants three things: 1) pass structure information around so it can be simulated or reproduced, 2) a deterministic ID for sharing and linking chemical information, and 3) viable methods for determining identity and similarity from the cloud of all chemical configurations.
SMILES is better at #1 than InChI, but not as good as a 3D structure representation. But the 3D structure isn't as compact, and offers few advantages for structure identity for small molecules where the 3D configuration is more easily predicted from geometry.
InChI is better for #2 than SMILES because different tools generate a different canonical structure, and because general purpose text search engines like Google don't do so well with SMILES as InChI keys.
Fingerprints, either binary or count, are more often used for the similarity aspect of #3, than n-gram solutions using the SMILES directly (like LINGO), or any method based on InChI. Also common are 3D shape and electrostatics comparison methods, with attempts to sample configuration space.
And for certain chemical structures other approximations are even more important. DNA similarity is based on very different principles than used for small molecules.
SMILES is better at #1 than InChI, but not as good as a 3D structure representation. But the 3D structure isn't as compact, and offers few advantages for structure identity for small molecules where the 3D configuration is more easily predicted from geometry.
InChI is better for #2 than SMILES because different tools generate a different canonical structure, and because general purpose text search engines like Google don't do so well with SMILES as InChI keys.
Fingerprints, either binary or count, are more often used for the similarity aspect of #3, than n-gram solutions using the SMILES directly (like LINGO), or any method based on InChI. Also common are 3D shape and electrostatics comparison methods, with attempts to sample configuration space.
And for certain chemical structures other approximations are even more important. DNA similarity is based on very different principles than used for small molecules.
In my humble experience "1)" and "2)" are sufficiently overlapping as to be indistinguishable. Whereas "3)...identity" only demands that the same system be used for both the search compound and the database ("cloud"). For that, a particular implementation of "canonical SMILES" is perfectly respectable. But it's a notably different world once one gets into "3)...similarity". With that you've opened a vast library of doctoral theses, commercial promises, and ingenuity, (and essentially my entire career). And yes, as you suggest, DNA similarity is a wholly different beast.
Taking dalke's enumeration and running with it... I'd support that "1)" and "2)" are ever so slightly different: defining a serialized form that can reheat to a consistent snapshotted simulation state is one thing; and is necessary but not quite sufficient for "2)". Defining the serialized form to be deterministic is quite an important next step, because that makes a lot of things go from `O(some)` to `O(1)`.
Very close, yes. But if we compare to, say, reproducible builds (because it's also dear to my heart), the consequences of that difference are legion. For example: the `tar` command can definitely extract you a filesystem, yes, absolutely. However: whether or not two `tar` implementations (or even the same implementation, run twice in a row) produce the same byte stream is make-or-break for whether someone else can follow your procedure and get the same result.
If the process is deterministic, the identity check is cheap: hash it. If the process requires unpacking again to do semantic checks on the contents, the amount of time is... well, if we're hand-waving on the format, essentially unbounded.
So... yeah, "canonical SMILES" is a valid answer; that "canonical" part is just really important.
Very close, yes. But if we compare to, say, reproducible builds (because it's also dear to my heart), the consequences of that difference are legion. For example: the `tar` command can definitely extract you a filesystem, yes, absolutely. However: whether or not two `tar` implementations (or even the same implementation, run twice in a row) produce the same byte stream is make-or-break for whether someone else can follow your procedure and get the same result.
If the process is deterministic, the identity check is cheap: hash it. If the process requires unpacking again to do semantic checks on the contents, the amount of time is... well, if we're hand-waving on the format, essentially unbounded.
So... yeah, "canonical SMILES" is a valid answer; that "canonical" part is just really important.
InChI Key is an example of #2 that does not imply #1.
For a variation on the theme, if we all agreed on a canonical SMILES method, then the SHA256 of that could be used as a key to connect records, without revealing what the underlying structure is.
This is done now, with InChI Key, when two companies want to compare overlap without sharing information about internal compounds. (There was a paper about this last year or so, but I can't find it.)
I also pointed out that InChI Keys are better for text-based search engines. As an extreme example, I could produce a line notation which uses only the characters "(", ")", ".", and "-". It would be fine for #1, but poor for #2 for any database search engine which expects some concept of "words" made of letters.
This is why I distinguish #1 from #2, even though they are indeed close.
For a variation on the theme, if we all agreed on a canonical SMILES method, then the SHA256 of that could be used as a key to connect records, without revealing what the underlying structure is.
This is done now, with InChI Key, when two companies want to compare overlap without sharing information about internal compounds. (There was a paper about this last year or so, but I can't find it.)
I also pointed out that InChI Keys are better for text-based search engines. As an extreme example, I could produce a line notation which uses only the characters "(", ")", ".", and "-". It would be fine for #1, but poor for #2 for any database search engine which expects some concept of "words" made of letters.
This is why I distinguish #1 from #2, even though they are indeed close.
As a structural biochemist, you may have use some of the software I've helped write or contributed to. ;)
Chemistry isn't even fully expressible using naive graph structures (atoms = vertices, bonds = edges), for example, eta-2 metal-pi bonds where the chemical bond is between an atom and another bond.
The terseness vanishes when considering the complexities of interactions and possible classifications. In fact, I'd say that the above terseness is only possible because it's about half of ALL the interesting effects possible in the game of life.
Given that what's being shared is a very small bitmap, wouldn't hex would be more concise?
Hint: Click "Show in viewer" in the first message. Zoom out a bit. Press play.
Skimming through the thread, I realized I had no idea of the type of community that exists surrounding Conway's game. I think it's awesome.
I know! There is probably some corollary to Rule 34 that states that for every obscure topic there is an internet forum of people dedicated to it.
There is, naturally, a relevant XKCD about this:
https://xkcd.com/1095/
https://xkcd.com/1095/
The Life community goes back decades!
Some members recently have put together a distributed soup search project to catalog objects that appear naturally. While the c/10 spaceship wasn't found in the search, a number of interesting things have been discovered. For more information about the catalog effort (named "catagolue" for Game of Life), the object database, and the distributed client, see http://catagolue.appspot.com/home
Some members recently have put together a distributed soup search project to catalog objects that appear naturally. While the c/10 spaceship wasn't found in the search, a number of interesting things have been discovered. For more information about the catalog effort (named "catagolue" for Game of Life), the object database, and the distributed client, see http://catagolue.appspot.com/home
I just love all the lingo in little specialized communities.
orthogonal spaceship, glider, puffer, rake, loafer.
"Trying to perfect a rake so it does not create Methuselah which eventually evolves into loaves, beehives and traffic lights isn't normal. But on Conway's Life, it is. Life. Not even once." - 'muzik
"- Use gencols to rub the ship against gliders and *WSSs to see whether there is a useful collision to maybe build a puffer." - 'HartmutHolzwart
And the excitement exhibited over this discovery. Very cool.
orthogonal spaceship, glider, puffer, rake, loafer.
"Trying to perfect a rake so it does not create Methuselah which eventually evolves into loaves, beehives and traffic lights isn't normal. But on Conway's Life, it is. Life. Not even once." - 'muzik
"- Use gencols to rub the ship against gliders and *WSSs to see whether there is a useful collision to maybe build a puffer." - 'HartmutHolzwart
And the excitement exhibited over this discovery. Very cool.
Most of the language was introduced by Conway himself, with a bit of contribution by Gardener who popularised it.
Very nice!
You might be interested in a simple proof I found of why c/2 and c/3 are speed limits for orthogonal and diagonal spaceships respectively.
Definition: In a gameplay of life, an "infinite lifeline" is a sequence of pairs (c_i,n_i) such that each c_i is alive in generation n_i and either c_(i+1)=c_i or c_(i+1) is adjacent to c_i.
Lemma ("Two Forbidden Directions"): Let x,y be any two 'forbidden' directions from among N,S,E,W,NE,NW,SE,SW. In any gameplay of life that starts finite and doesn't die out, there is an infinite lifeline that never goes in either direction x or y.
The lemma's proof uses biology. Say that (c,n) is a "father" of (c',n+1) if c' is the cell adjacent to c in direction x or y. Otherwise, (c,d) is a "mother" of (c',n+1). By the rules of the game of life it's easy to show every living (c,n+1) has at least one living father and at least one living mother. It follows (modulo some more details) that since the gameplay doesn't die out, there must be an infinite lifeline where each cell is a mother of the next, i.e., an infinite lifeline that never goes direction x or y.
Proof of c/2 orthogonal speed limit: If a spaceship went faster than c/2, say, northward, by the lemma, it would have an infinite lifeline that never goes N or NE. The only way it could ever go northward would be to go NW. Every NW step would have to be balanced out by an eastward step (of which NE is forbidden) or the spaceship would drift west. So every northward step requires a non-northward step, QED.
Proof of c/3 speed limit for diagonal: A diagonal spaceship faster than c/3, say, northeastward, would have an infinite lifeline that never goes N or NE. The only way for it to go northward would be to go NW. Each NW step would need at least two eastward steps in order for the ship to go eastward, QED.
You might be interested in a simple proof I found of why c/2 and c/3 are speed limits for orthogonal and diagonal spaceships respectively.
Definition: In a gameplay of life, an "infinite lifeline" is a sequence of pairs (c_i,n_i) such that each c_i is alive in generation n_i and either c_(i+1)=c_i or c_(i+1) is adjacent to c_i.
Lemma ("Two Forbidden Directions"): Let x,y be any two 'forbidden' directions from among N,S,E,W,NE,NW,SE,SW. In any gameplay of life that starts finite and doesn't die out, there is an infinite lifeline that never goes in either direction x or y.
The lemma's proof uses biology. Say that (c,n) is a "father" of (c',n+1) if c' is the cell adjacent to c in direction x or y. Otherwise, (c,d) is a "mother" of (c',n+1). By the rules of the game of life it's easy to show every living (c,n+1) has at least one living father and at least one living mother. It follows (modulo some more details) that since the gameplay doesn't die out, there must be an infinite lifeline where each cell is a mother of the next, i.e., an infinite lifeline that never goes direction x or y.
Proof of c/2 orthogonal speed limit: If a spaceship went faster than c/2, say, northward, by the lemma, it would have an infinite lifeline that never goes N or NE. The only way it could ever go northward would be to go NW. Every NW step would have to be balanced out by an eastward step (of which NE is forbidden) or the spaceship would drift west. So every northward step requires a non-northward step, QED.
Proof of c/3 speed limit for diagonal: A diagonal spaceship faster than c/3, say, northeastward, would have an infinite lifeline that never goes N or NE. The only way for it to go northward would be to go NW. Each NW step would need at least two eastward steps in order for the ship to go eastward, QED.
I'm no life expert, but this proof doesn't work for me. Just because there exists some configuration that doesn't generate lifelines in your chosen directions, doesn't mean that any particular configuration doesn't generate lifelines in those directions.
You're mixing up where the negation goes.
The lemma says that in any configuration which starts finite and never dies out, there DOES exist at least one lifeline which DOESN'T go in a forbidden direction. (There are almost certainly lots of other lifelines which do go in forbidden directions, that's fine.)
An example of a lifeline in a southeastward spaceship that never goes S or SE: http://www.xamuel.com/images/lifeline.gif
The proof I outlined above was published in the Elect. J. of Combinatorics (last section): http://www.combinatorics.org/ojs/index.php/eljc/article/view...
The lemma says that in any configuration which starts finite and never dies out, there DOES exist at least one lifeline which DOESN'T go in a forbidden direction. (There are almost certainly lots of other lifelines which do go in forbidden directions, that's fine.)
An example of a lifeline in a southeastward spaceship that never goes S or SE: http://www.xamuel.com/images/lifeline.gif
The proof I outlined above was published in the Elect. J. of Combinatorics (last section): http://www.combinatorics.org/ojs/index.php/eljc/article/view...
Ack, sorry. For some reason my mind wasn't wrapping around the fact that you can choose your configuration before choosing your forbidden directions.
>By the rules of the game of life it's easy to show every living (c,n+1) has at least one living father and at least one living mother.
This statement seems incorrect. It's true that every living cell has a living mother, but there's no requirement of a living father.
This statement seems incorrect. It's true that every living cell has a living mother, but there's no requirement of a living father.
When I say (c,n+1) has a "living" father what I mean is a father (b,n) such that b is alive in generation n.
Your father might have died before you were born but he didn't die before he himself was born.
I handwaved that bit anyway for expediency, if you're interested in the full details see: http://www.combinatorics.org/ojs/index.php/eljc/article/view...
Your father might have died before you were born but he didn't die before he himself was born.
I handwaved that bit anyway for expediency, if you're interested in the full details see: http://www.combinatorics.org/ojs/index.php/eljc/article/view...
Okay, I read that and now I get it. Each live cell has at least three ancestors. Two or fewer of these ancestors come from a forbidden direction, so at least one comes from an allowed direction. Among all of the ancestors from an allowed direction, arbitrarily choose one to be the “mother”. All of the other ancestors are called “fathers”. There's no requirement that a father has to come from a forbidden direction.
Ahh you're right, I messed up when I typed the proof in my comment. Your explanation of it is A++
c/3 diagonal is actually impossible as well - the limit is c/4, proved by Conway himself in Life's early years. His proof can be found here: http://www.njohnston.ca/2009/10/spaceship-speed-limits-in-li...
I'm thinking about writing a Conway's Life MMO, where you can activate "lanterns" that illuminate rectangles in the grid with Conway Life squares. These lanterns are fueled with "living" Conway Life cells, which are harvested by the player. Sound interesting?
Honestly no. Building an MMO that ran entirely on life would be amazing but probably impossible. Building something that used the trappings of life without having it mean much would just be infuriating. Unless I'm misunderstanding the proposal?
The first thing that comes to mind, is that players would build glider guns that would cause live cells to "fall into" collector cells to gather resources. So it would be a farming/RTS game, except all of the crops and weapons would be emergent from Conway's Life.
I think that's going to be unplayably difficult for anyone except serious programmers, and it will be very difficult to design life structures that have the behaviour you need to make the game fun, and even if you manage it you'll have trouble running them fast enough to perform well. I mean best of luck if you do do it, but it's going to be a real uphill struggle.
You're totally misunderstanding my proposal. (Either on purpose as a troll, or you're just having a particularly obtuse day.)
The life structures you need to start would just be glider guns. The glider guns would fire into walls of "collector cells" which are not Conway Life entities, but are implemented by the game directly.
Likewise, the character is not a Conway Life entity, but implemented directly by the game.
I think that's going to be unplayably difficult for anyone except serious programmers
What I've envisioned might well be appreciated by Life enthusiasts.
The life structures you need to start would just be glider guns. The glider guns would fire into walls of "collector cells" which are not Conway Life entities, but are implemented by the game directly.
Likewise, the character is not a Conway Life entity, but implemented directly by the game.
I think that's going to be unplayably difficult for anyone except serious programmers
What I've envisioned might well be appreciated by Life enthusiasts.
A glider gun is still incomprehensibly complex for non-programmers, I fear.
To the extent that resource collection involves stuff happening in Life you will struggle to balance it, and to the extent that it doesn't it's not really life-based at all.
To the extent that resource collection involves stuff happening in Life you will struggle to balance it, and to the extent that it doesn't it's not really life-based at all.
to the extent that it doesn't it's not really life-based at all.
Obviously, because no MMOs have contrived mechanics, ever!
Obviously, because no MMOs have contrived mechanics, ever!
MMOs need two things: mechanics that make them fun as a game, and themeing that will attract players. As far as I can see including a life aspect doesn't help with either.
I like the idea!
Maybe a turn-based roguelike where the monsters are lifeforms that follow the rules of GoL. Could either be very interesting or exceedingly boring once it settled into a self-sustaining pattern.
People have been trying to write good games based on Conway's Life for decades, but it seems as if most game mechanisms end up having too steep a learning curve -- mostly because the system is too sensitive, so one bit out of place tends to cause huge, unpredictable, uncontrollable effects.
Seems to me Life has a lot of potential as abstract art, though. I'm almost curious enough about what they're doing in Second Life these days, to sign up and go have a look:
http://www.conwaylife.com/forums/viewtopic.php?f=7&t=2068#p2...
Seems to me Life has a lot of potential as abstract art, though. I'm almost curious enough about what they're doing in Second Life these days, to sign up and go have a look:
http://www.conwaylife.com/forums/viewtopic.php?f=7&t=2068#p2...
https://niginsblog.wordpress.com/2016/03/07/new-spaceship-sp...
This link has an animation of the c/10 spaceship.
This link has an animation of the c/10 spaceship.
I'm confused about what I'm looking at... is this a pattern that emerges in conways game of life?
It is. Someone discovered that if you start with that initial pattern you get a "spaceship" that moves. I gather that it is an impressive find both because of how small it is (you'd expect someone or a computer to have already discovered it) and how slow it moves.
it's a pattern that "moves forward", i.e. recreates itself at another position.
At speed c/10, "one tenth of a cell in each iteration", or, better said: after ten iterations, the pattern has moved one cell, but is otherwise unchanged. That's why it is called a glider; it glides through the grid (a puffer stays at its location and returns to its original snape after some time, but periodically sends out gliders)
What's new here, apparently, is that this is the first glider discovered with that speed. It also is surprisingly small.
What's new here, apparently, is that this is the first glider discovered with that speed. It also is surprisingly small.
Really great explanation, thank you!
[deleted]
Is it just me or does the original frame look like Serenity (Firefly)? It's movement is backwards though.
amazing