4 ms·

I find Game of Life utterly fascinating. Every time I read about it, I find myself wanting to understand more of the memephere surrounding it. One question th

by jMyles 9y ago

I find Game of Life utterly fascinating. Every time I read about it, I find myself wanting to understand more of the memephere surrounding it. One question that arises in me here: > What makes this an elementary knightship is that it isn't built out of smaller discrete components How is that determined? In other words, can't you take small components, smash them together to get a bigger thing, and then pass it off as elementary? Don't we need to "reverse the hash function" to determine if it's possible to make Sir Robin (that's what thing thing is going to be called) out of smaller things? Or is it possible to prove for a given larger object that it can't possibly be the result of smaller things combining?

dazmax 9y ago
It's not about combining, it's about being designed as a construction based on other known patterns. See http://conwaylife.com/wiki/Gemini http://conwaylife.com/wiki/Gemini for an example of a non-elementary ship.
deleted 9y ago
[deleted]
Someone 9y ago
”Or is it possible to prove for a given larger object that it can't possibly be the result of smaller things combining?” For some, that is possible. Trivial examples are objects of zero, one, or two pixels; less trivial are gardens of Eden (http://conwaylife.com/w/index.php?title=Garden_of_eden http://conwaylife.com/w/index.php?title=Garden_of_eden) However, I don’t think “elementary” is synonymous with “can’t possibly be the result of smaller things combining”. http://conwaylife.com/wiki/Elementary http://conwaylife.com/wiki/Elementary defines it as ”A pattern is said to be elementary if it is not reducible to a combination of smaller parts.” If one takes two gardens of eden and place them far enough apart, the result is a new garden of Eden that ”can’t possibly be the result of smaller things combining” (even stronger: it can’t possibly be the result of anything), but it is reducible to smaller parts. I don’t think there is a formal definition of ‘elementary’ that everybody can agree on. In the limit, only patterns of a single cell are elementary.
- dvgrn 9y ago
  The "elementary" vs. "engineered" distinction might be clearer with an example of an engineered spaceship, like one of the Corderships: http://conwaylife.com/wiki/13-engine_Cordership http://conwaylife.com/wiki/13-engine_Cordership . Inside the 13-engine Cordership are thirteen switch engines, each of which moves at a twelfth of the speed of light, but leaves junk behind. The thirteen pieces basically collaborate on cleaning up each other's junk to make a clean spaceship. It's very difficult to prove that a large elementary spaceship can't possibly be created by crashing gliders together (for example). Several elementary spaceships do in fact have known glider constructions, but that doesn't stop them from being elementary -- you can't pick those spaceships back apart into their constitutent gliders once they're constructed, and often they're traveling a totally different speed and direction than a glider anyway.
  - Someone 9y ago
    I understand that, but those are the easy ones, and I think they are the exception, when looking at all possible spaceships, rather than the spaceships we know of. A definition for ‘elementary’ that I think is closest to intuition is that ‘elements’ are connected (for some definition of connected) subsets of a pattern do not touch other parts of the pattern and that would survive individually in isolation. Problems with that definition are that, after cutting of the obvious elements, you may be left with stuff. Using the term ‘elementary’ implies that that stuff either must be elementary, or be built of other elements. The former is the easiest way out, but (as an extreme example) the resulting element might be a garden of Eden with a billion cells that, in isolation, would die out. Would you really want to call such a monster an element? Also, if a pattern of <50 cells can be constructed from a few dozen carefully placed small ‘obvious elementary’ parts, less than 100 or so time units in the past, I think many would agree the pattern’s elements are those parts. Problem 1: AFAIK, it is an open problem to decide whether such a set of items exists for a given pattern. Problem 2: that set may not be unique, and there may not even be a unique smallest (for whatever definition chosen) one in the set of solutions. Problem 3: if the smallest such set is way, way larger than the pattern it constructs, and must be constructed way, way in the past, do you still consider the pattern to be constructed from those many, many elementary parts?
fossuser 9y ago
I haven't read it yet, but you'd probably find Stephen Wolfram's "A New Kind of Science" pretty interesting. From the talks I've seen a lot of it seems to stem from the idea of simple rules allowing a lot of complexity. He talks about other cellular automata other than Conway's Game of Life, but the ideas are similar. http://blog.stephenwolfram.com/2017/06/oh-my-gosh-its-covered-in-rule-30s/ http://blog.stephenwolfram.com/2017/06/oh-my-gosh-its-covere... This idea comes up a little bit differently in Max Tegmark's book "Our Mathematical Universe" which I liked too.
westoncb 9y ago
If you want to experiment some more, I made this little webgl app [0] that makes it easy to mess with Conway's GoL while it's executing (you hold shift, which pauses the simulation, and click on cells to toggle them on or off). It's easy to 'paint' some basic gliders (e.g. http://images.slideplayer.com/25/8056158/slides/slide_3.jpg http://images.slideplayer.com/25/8056158/slides/slide_3.jpg), then un-pause and watch them go off for instance. Or just try drawing a vertical or horizontal line of three cells (you get a simple oscillator), then try adding or removing things to it. There's also a dropdown full of interesting patterns you can load up (with descriptions from mathematicians). [0] http://symbolflux.com/conwayz/ http://symbolflux.com/conwayz/
invisibowl 9y ago
It's actually easily provable, and simply by observation, because "smaller things combining" has a much simpler definition than what you're assuming! What it actually refers to is how some spaceships, such as the Waterbear -- https://www.youtube.com/watch?v=on3ZLLKQp-4 https://www.youtube.com/watch?v=on3ZLLKQp-4 -- are constructed explicitly as a circuit of building blocks (as you can see in the video), whereas elementary spaceships like this knightship consist of "space dust" that isn't separable into independently-functioning components.
Parcissons 9y ago
Also remember Conways compression- any series of bytes, could be interpreted as the endresult of several conway games, layed over one another with relational operations. So it compresses titanic data down to some Booleans and chess expressions. Size: 4096 x 4096 Offset: (0,0) Def: GameA Opening Lib:C3 Turns: 2567 [&] Size: 512x 512 Offset: (12,0) Def: GameB Opening Lib:G42 Turns: 12 [!] Size: 4096 x 4096 Offset: (0,0) Def: GameD Opening Lib: FULL_HOUSE Turns: 0 Its a pretty nifty way to compress files beyond the point of no return, knowing that the deterministic knowledge of the game- allows for a full recreation of any file, given enough processing power and time. There are of course some attempts to optimize the whole process- having often used game snapshots to fast-forward from and re-wind back too.

by jMyles 9y ago

dazmax 9y ago

It's not about combining, it's about being designed as a construction based on other known patterns. See http://conwaylife.com/wiki/Gemini http://conwaylife.com/wiki/Gemini for an example of a non-elementary ship.

deleted 9y ago

[deleted]

Someone 9y ago

”Or is it possible to prove for a given larger object that it can't possibly be the result of smaller things combining?” For some, that is possible. Trivial examples are objects of zero, one, or two pixels; less trivial are gardens of Eden (http://conwaylife.com/w/index.php?title=Garden_of_eden http://conwaylife.com/w/index.php?title=Garden_of_eden) However, I don’t think “elementary” is synonymous with “can’t possibly be the result of smaller things combining”. http://conwaylife.com/wiki/Elementary http://conwaylife.com/wiki/Elementary defines it as ”A pattern is said to be elementary if it is not reducible to a combination of smaller parts.” If one takes two gardens of eden and place them far enough apart, the result is a new garden of Eden that ”can’t possibly be the result of smaller things combining” (even stronger: it can’t possibly be the result of anything), but it is reducible to smaller parts. I don’t think there is a formal definition of ‘elementary’ that everybody can agree on. In the limit, only patterns of a single cell are elementary.

dvgrn 9y ago
The "elementary" vs. "engineered" distinction might be clearer with an example of an engineered spaceship, like one of the Corderships: http://conwaylife.com/wiki/13-engine_Cordership http://conwaylife.com/wiki/13-engine_Cordership . Inside the 13-engine Cordership are thirteen switch engines, each of which moves at a twelfth of the speed of light, but leaves junk behind. The thirteen pieces basically collaborate on cleaning up each other's junk to make a clean spaceship. It's very difficult to prove that a large elementary spaceship can't possibly be created by crashing gliders together (for example). Several elementary spaceships do in fact have known glider constructions, but that doesn't stop them from being elementary -- you can't pick those spaceships back apart into their constitutent gliders once they're constructed, and often they're traveling a totally different speed and direction than a glider anyway.
- Someone 9y ago
  I understand that, but those are the easy ones, and I think they are the exception, when looking at all possible spaceships, rather than the spaceships we know of. A definition for ‘elementary’ that I think is closest to intuition is that ‘elements’ are connected (for some definition of connected) subsets of a pattern do not touch other parts of the pattern and that would survive individually in isolation. Problems with that definition are that, after cutting of the obvious elements, you may be left with stuff. Using the term ‘elementary’ implies that that stuff either must be elementary, or be built of other elements. The former is the easiest way out, but (as an extreme example) the resulting element might be a garden of Eden with a billion cells that, in isolation, would die out. Would you really want to call such a monster an element? Also, if a pattern of <50 cells can be constructed from a few dozen carefully placed small ‘obvious elementary’ parts, less than 100 or so time units in the past, I think many would agree the pattern’s elements are those parts. Problem 1: AFAIK, it is an open problem to decide whether such a set of items exists for a given pattern. Problem 2: that set may not be unique, and there may not even be a unique smallest (for whatever definition chosen) one in the set of solutions. Problem 3: if the smallest such set is way, way larger than the pattern it constructs, and must be constructed way, way in the past, do you still consider the pattern to be constructed from those many, many elementary parts?

fossuser 9y ago

I haven't read it yet, but you'd probably find Stephen Wolfram's "A New Kind of Science" pretty interesting. From the talks I've seen a lot of it seems to stem from the idea of simple rules allowing a lot of complexity. He talks about other cellular automata other than Conway's Game of Life, but the ideas are similar. http://blog.stephenwolfram.com/2017/06/oh-my-gosh-its-covered-in-rule-30s/ http://blog.stephenwolfram.com/2017/06/oh-my-gosh-its-covere... This idea comes up a little bit differently in Max Tegmark's book "Our Mathematical Universe" which I liked too.

westoncb 9y ago

If you want to experiment some more, I made this little webgl app [0] that makes it easy to mess with Conway's GoL while it's executing (you hold shift, which pauses the simulation, and click on cells to toggle them on or off). It's easy to 'paint' some basic gliders (e.g. http://images.slideplayer.com/25/8056158/slides/slide_3.jpg http://images.slideplayer.com/25/8056158/slides/slide_3.jpg), then un-pause and watch them go off for instance. Or just try drawing a vertical or horizontal line of three cells (you get a simple oscillator), then try adding or removing things to it. There's also a dropdown full of interesting patterns you can load up (with descriptions from mathematicians). [0] http://symbolflux.com/conwayz/ http://symbolflux.com/conwayz/

invisibowl 9y ago

It's actually easily provable, and simply by observation, because "smaller things combining" has a much simpler definition than what you're assuming! What it actually refers to is how some spaceships, such as the Waterbear -- https://www.youtube.com/watch?v=on3ZLLKQp-4 https://www.youtube.com/watch?v=on3ZLLKQp-4 -- are constructed explicitly as a circuit of building blocks (as you can see in the video), whereas elementary spaceships like this knightship consist of "space dust" that isn't separable into independently-functioning components.

Parcissons 9y ago

Also remember Conways compression- any series of bytes, could be interpreted as the endresult of several conway games, layed over one another with relational operations. So it compresses titanic data down to some Booleans and chess expressions. Size: 4096 x 4096 Offset: (0,0) Def: GameA Opening Lib:C3 Turns: 2567 [&] Size: 512x 512 Offset: (12,0) Def: GameB Opening Lib:G42 Turns: 12 [!] Size: 4096 x 4096 Offset: (0,0) Def: GameD Opening Lib: FULL_HOUSE Turns: 0 Its a pretty nifty way to compress files beyond the point of no return, knowing that the deterministic knowledge of the game- allows for a full recreation of any file, given enough processing power and time. There are of course some attempts to optimize the whole process- having often used game snapshots to fast-forward from and re-wind back too.