2293: RIP John Conway

Explain xkcd: It's 'cause you're dumb.
Revision as of 09:46, 14 April 2020 by Kynde (talk | contribs) (Explanation)
Jump to: navigation, search
RIP John Conway
1937-2020
Title text: 1937-2020

Explanation

Ambox notice.png This explanation may be incomplete or incorrect: Created by a GLIDER. Needs more in-depth explanation of how the Game Evolves. Include remaining stills from the GIF in the table below. Should also expand more on why Conway is a person of note. Do NOT delete this tag too soon.
If you can address this issue, please edit the page! Thanks.
John Conway, an English mathematician, passed away of COVID-19. Two days later, Randall created this memorial comic. One of Conway's most famous creations was Conway's Game of Life, which consists of a grid of square cells with rules for how they change over time.

In a given generation, each cell can either be alive or dead (empty). To compute the grid for the next generation, each cell is affected only by the eight cells adjacent to it, both orthogonal and diagonal to it. Those are its neighbors. The rules are:

  • A live cell with no live neighbors, or only one neighbor, will die of isolation.
  • A live cell with four or more live neighbors will die of overcrowding.
  • Therefore, the only cells that survive have exactly two or three live neighbors.
  • In addition, a new cell is "born" in each empty cell with exactly three live neighbors.

Although the rules are simple, enormously complex patterns can develop from them, such as "still lifes" (which do not change over generations), "oscillators" (which cycle repeatedly through a set of patterns over a specific period), and "spaceships" (which reproduce their own pattern at an offset from the original).

This comic begins with the shape of a stick figure as the starting configuration, which then evolves according to the rules of the Game of Life. The pattern breaks into three parts, two of which stay at the same level as the original figure's feet before rapidly melting away, and a third (called a "glider") that ascends up and to the right. Randall may be suggesting a soul breaking away from the rapidly disintegrating corporeal remains here.

The initial state of the game presented in the comic *does*, in fact, evolve as depicted, according to the rules above.

Table of generations

Generation Notes
Generation 0.jpg
Starting state (or "zeroth generation").
Generation 1.jpg
First generation. Note that this image is not aligned with the previous one: the position of all cells has shifted downward by one cell. All further generations are aligned the same as this one.
Generation 2.jpg
Second generation.
Generation 3.jpg
Third generation.
Generation 4.jpg
Fourth generation.
Generation 5.jpg
Fifth generation.
Generation 6.jpg
Sixth generation. The first appearance of the glider, a well-known formation in Conway's Game of Life.
Generation 7.jpg
Seventh generation. The glider takes on its other shape.
Generation 8.jpg
Eighth generation. The glider returns to its first shape, pointing right instead of up.
Generation 9.jpg
Ninth generation. The glider's second shape again, pointing right instead of up.
Generation 10.jpg
Tenth generation. The glider is now in its original form, but one cell higher and one cell to the right. It will continue to progress, cycling through these four states every four generations. The remains of the chaos down below will take two more generations to disappear completely.

Transcript

Ambox notice.png This transcript is incomplete. Please help editing it! Thanks.
[A pixelated image of a stick figure. The image is animated, with the pixels changing according to the rules of Conway's Game of Life. The figure splits into two groups, one of which dissipates. The other becomes a 'glider' and moves off to the top-right corner of the image and out of frame. The animation then repeats.]


comment.png add a comment! ⋅ comment.png add a topic (use sparingly)! ⋅ Icons-mini-action refresh blue.gif refresh comments!

Discussion

This is really very impressive. The design of the stick figure to allow it to release a glider that ascends upwards (the "soul" rising to "heaven" or whatever) with the body decaying - that's a hard thing to get right using just the Game of Life rules. 172.69.68.175 17:49, 13 April 2020 (UTC)

Although Randall is clever, the Game of Life has been studied for so long that I'm sure this is a well-known animation. Barmar (talk) 18:29, 13 April 2020 (UTC)
I played with the game a bunch in the past, but I've only done a bit of research after this appeared. I don't immediately find any previous report of this starting arrangement
This is unlikely, as the Game of Life has an uncountable number of patterns of this size, some of which are still being discovered. The pattern above is 7 cells wide by 9 cells tall - the number of distinct patterns that can be drawn in that box nears 2 --> 60 --> 1 (2^60). It's most likely that patterns such as this one are commonplace, and Randall just fiddled around until he reached one that he desired. The pattern itself, however, has likely never been discovered before. (As a fun postscript, a notable 8-cell wide, 9-cell tall pattern oscillating at period 16, just slightly larger than the one above, was discovered in February 2020.)Hdjensofjfnen (talk) 21:31, 13 April 2020 (UTC)
I suspect it's probably more likely that he worked it out backwards, rather than "just fiddled with it." 108.162.216.244 04:24, 14 April 2020 (UTC)
AFAIK, many CAs such as Life have the property of being irreversible, which is the entire point for various pattern search efforts.162.158.92.54 07:13, 14 April 2020 (UTC)
He probably started with the floater, and adjusted the rest so it wouldn't interfere. Most figures decay in the game of life (I learned when playing with it, decades ago) --162.158.111.79 10:45, 14 April 2020 (UTC)
The Game of Life has been researched a lot. One sub-problem is finding an arrangement of cells that cannot be produced by a prior arrangement of cells. They are called Garden of Eden patterns, and the known ones are not small. Glider generators are rather common, so it is most likely that the initial pattern was created by working backward from an existing glider generator.173.245.54.125 17:33, 14 April 2020 (UTC)
I like the comment above by Hdjensofjfnen, where 2^60 is written using Conway’s chained arrow notation. That’s a slick way to honor Conway. Anyway, when the number of possible candidates is around 2^64 or less, you can find a desired solution by brute-force search if you have to, provided that the problem is relatively simple and well-defined (i.e. if you can write an efficient program). In this case, the number of the candidates of the initial state is very small, if it should be a tiny, pixel image of a stick figure. So, intuitively, an exhaustive search should be easy—at least it should be doable. (PS: I mean, the idea of this comic is cool and awesome; it’s not trivial at all for you to come up with this. But if you do come up with this problem, then the solution may not be so difficult.) Yosei (talk) 17:35, 20 April 2020 (UTC)

was there a placeholder comic posted before the gif went live?

I am certain there was one with "uh oh one of the lights went out" "that's not supposed to happen" and a picture of a pattern that I did not recognise, which I found to be quite sad. 162.158.92.54 10:35, 14 April 2020 (UTC)
This was SMBC, and the pattern is a glider generator. 188.114.111.211 12:30, 14 April 2020 (UTC)

Looks like this is second animated comic in xkcd, besides 1116(though 1190 could be possibly counted together) 172.69.190.16 19:34, 13 April 2020 (UTC)

Uh, 1331: Frequency and 1264: Slideshow immediately come to mind, and then I remember about 961: Eternal Flame. There's a lot more than two. Volleo6144 (talk) 19:43, 13 April 2020 (UTC)
Category:Comics with animation; just added it. Yngvadottir (talk) 20:19, 13 April 2020 (UTC)

The explanation says that the simulation is run on an infinite grid, but even when the grid is calculated out beyond the border of the viewable area, bounding errors & boundary formations can occur. I've never seen any implementation that actually produces an infinite, nor even practically infinite grid. (In fact, wasn't there a Minecraft mod that runs until it lags out the engine?) Can anybody point me to a truly infinite grid implementation? Conway's definitely was not infinite, he even commented at length about the boundary formations that show up at the grid edges (which are among the most subjectively beautiful, incidentally). I think the explanation needs correction? ProphetZarquon (talk) 21:59, 13 April 2020 (UTC)

The explanation is describing Conway's game of life, not any particular implementation IMHO. No change needed IMHOA. Also, the previous post was not signed properly. 162.158.107.167 21:47, 13 April 2020 (UTC)
Except many of Conway's observations about the "game" & even his initial description of it explicitly state & indeed hinge upon the fact that it's not (& thus far cannot be) implemented as an "infinite" grid. Part of the whole point of his experiment with it & the various demonstrations is to illustrate edge effects resulting from a finite range of calculations. It's extremely relevant that it's not infinite. It's actually kinda the whole point of his creating it, much the same way people working with fractals likewise tend to become very interested in bounding errors. The boundaries are where the interesting work is done. Apparently someone agreed with me at least in part, because they edited the wording. Thanks... Brian? I think we should actually add to the description of the "game" info highlighting the edge effects, because that's the primary focus of the project & its outgrowths in the first place. (We can't adequately simulate infinity & that's a big part of the interest in it.) Also, I frequently have to submit & then refresh & sign afterward because of the device I'm on. In this case I'm glad I did, because I saw your reply & the other new stuff!
ProphetZarquon (talk) 22:17, 13 April 2020 (UTC)
Golly uses a grid of arbitrary size by default. It can very easily be verified to at least ±210000. (Note that it also includes finite rectangular and toroidal grids.) LegionMammal978 (talk) 01:39, 14 April 2020 (UTC)
Winning Ways, p. 817 (3rd printing): 'Life is a "game" played on an infinite squared board.'--172.68.54.208 13:45, 17 April 2020 (UTC)

No computer [Citation Needed] can run an actual infinite grid, but with some intelligent bounding you can mitigate early signs of problems by maintaining "bubbles" of cells with offsets. You get into problems once you start machine-gunning out gliders (offsets will eventually overflow or awkwardly lose precision, depending on the var-types used; and maintaining a longer and longer bubble, or more and more bubbles just above glider-sized, is probably your other challenge) but it's probably good enough for most purposes. If you somehow have finite patterns that move out in huge (wasteless) cycles from the 'origin' and hold that path until enacting hugely-delayed doglegs (mathematically, it must be a point no further away than can be reasonably enumerated by the bits of information contained within each formation, and significantly less as it'd be a far less efficient count-down cycler than any folded LFSR, but it's imaginable) to meet again at some arbitrary (though deterministic and replicable) distance out in the far far reaches of your abstracted bubble-land then it's possible you could pretend you have infinite space. 162.158.91.101 22:26, 13 April 2020 (UTC) ProphetZarquon, do you have a source for your claim that the main point of Conway's creation of Life was to study the edge effects? The page for Life on its own wiki describes the Life grid as "infinite" and only mentions edge effects as inaccuracies to be avoided, and this Conway interview about Life's creation doesn't mention edges at all. 108.162.241.24 23:34, 13 April 2020‎ (UTC)

First of all, as a tip, reply directly to the comment when you want to talk with someone. Secondly, yeah, I'm pretty sure that person's just blasting ass ham. 172.69.69.28 02:49, 14 April 2020 (UTC)

Possibly worth noting is the bit of artistry in the rendering. Munroe alters the step period of the iterations so that the deconstruction of the humanoid shape happens more quickly, with the stepping of the glider translating away occurring more slowly. Fixer (talk) 21:52, 13 April 2020 (UTC)

I like the comic very much, and I'm afraid to say I hadn't heard of his death in amongst... well, everything else. RIP. While I'm here, though, I'm a bit concerned about the current cell generation cycle explanation, as it feels awkward. Currently it is (paraphrased) "live cells survive if just enough neighbours / dead cells come to life with exactly enough neighbours / any other dies or stays dead". I'd prefer something that more delineates it as birth (dead to live, by propogation from the right number of live neighbours), death (live to dead due to either isolation or overcrowding) and continuation of state in all other cases. Can't work out a good phrasing yet, but may try it out later. 162.158.91.101 22:26, 13 April 2020 (UTC)

Agreed 100%. I believe the problem lies in the confusion between "cell as in biology" versus "cell as in jail". It would be better to avoid the word "cell" and describe a grid with squares that are either inhabited or empty; inhabitants with two or three neighbours survive to the next generation, otherwise they die (square becomes empty the next generation); exactly three neighbours to an empty square will give birth (become inhabited) in the next generation; and any other empty square stays empty.

Given the cause of death, should this comic be listed among the Covid-19 series? Momerath (talk) 05:02, 14 April 2020 (UTC)

Yes.--Kynde (talk) 10:51, 14 April 2020 (UTC)
No. This is about John Conway. It would have presumably run regardless of the cause of death.

Interesting to see if the next comic is also a Covid-19 comic, because then it will be the 19th covid-19 comic... --Kynde (talk) 10:53, 14 April 2020 (UTC)

I really think this should not be regarded as a Covid-19 comic, since it's a memorial one and the cause of death is not important for this comic. 162.158.93.105 14:18, 14 April 2020 (UTC)

Agree with the others, this is a memorial comic, NOT a COVID-19 comic. I feel like too many comics are being forced into the COVID-19 theme, when they have little to no relation. 172.69.22.62 16:12, 14 April 2020 (UTC)
Covid-19 is obviously not directly the topic of the comic, but it is related quite close. So I vote to re-add it to the category, but to put the mention of the connection with the other comics not into the explanation, or on its bottom. If this is acceptable, 961: Eternal Flame should also be included to Category:Cancer. --Lupo (talk) 10:43, 15 April 2020 (UTC)
Of course this is one in the Covid series. Randall very rarely makes tributes and it has been 5 year since the last. Conway is not very famous, and had he died a year ago, chances are Randall would not have made this comic. But because he died of Covid while all Randall's comics is about Covid he makes a tribute now. For the same reason I do not think that Eternal flame has anything with the cancer category. Because this was a tribute Randall made without any connection to a series of cancer comics. --Kynde (talk) 11:25, 15 April 2020 (UTC)
Thanks for correcting my spelling errors :D all of that is speculation. How do you know, that Randall is not a huge Conway fan? seems to play exactly into his geekynes. --Lupo (talk) 12:47, 15 April 2020 (UTC)
I also disagree that Randall is not a huge Conway fan. I believe he would be familiar and interested in the Game of Life automata, as a nerd/geek. It was previously mentioned over 10 years ago in 696: Strip Games. I agree with Lupo's suggestions for this comic. 172.69.34.44 17:01, 15 April 2020 (UTC)

Is this original?

It would seem remarkable if Randall was able to create this starting pattern at such short notice. If it's copied from somewhere, we should provide that detail. Stevage (talk) 03:54, 15 April 2020 (UTC)

I do not know if it is taken from another place or a common/known pattern (the comments above seem to suggest otherwise), but it is not uncommon to have an obituary / memorial in stock for elderly persons of relevance. So it might be possible, that e.g. Randall played around with putting stick figures into a simulation, and accidently found this, deciding to keep it somewehere in his archive for this occasion. The seperation of the decaying body and the everlasting part going upward is actually obvious enough to connect with the idea to use it for this occasion. --Lupo (talk) 10:36, 15 April 2020 (UTC)

First popularized?

The game's popularization "to the general public" in Windows 3.1 really depends on your definition of popular - how many members of the general public had PCs then? I mention this to point out that it was really Martin Gardner's article in SciAm in October 1970 that showed the game to a pretty wide public, although admittedly few people were in a position to program it at the time. As I maintained the University of Cambridge's version on the PDP-7 (then their only computer with a graphics display) in 1971-72 I'm still astonished at how early this publication was. Gardner then did the same for the Mandelbrot Set (which originated in the Other Cambridge...) 162.158.78.74 04:23, 16 April 2020 (UTC)

Leaving the grid

"However, any given Game of Life is on a finite grid, so once the glider leaves the grid, it has ceased to exist."

Maybe a philosophical nitpick, but I'd like to dispute this. I submit that it is not possible for anything to "leave the grid". A glider can certainly hit the boundary of a bounded grid, but at that point boundary conditions disrupt the pattern and it ceases to be a glider; thus, gliders cannot leave the grid.

Additionally, the grid can be finite and yet still have no boundary; it is quite common for Life grids to wrap one side of the screen to the other. On such a grid, the glider would in fact persist indefinitely. Hawthorn (talk) 09:18, 16 April 2020 (UTC)

Also we don't know if the grid maybe is larger than the screen shown in the comic. --Lupo (talk) 11:36, 16 April 2020 (UTC)

Triple whammy

FYI: Richard Guy, who found the glider first, and is coauthor of Winning Ways with Conway, already died this March. In the biblical age of 103, so possibly nobody even bothered to check for the cause. (The third author, Elwyn Berlekamp, died a year ago.) 141.101.77.32 18:02, 16 April 2020 (UTC)

Conway was not a fan of his fame for Life

" He’d like to remembered for any of his accomplishments except the Game of Life. He once said he checked the index of every book and if it listed the Game of Life he would refuse to read it." -- https://twitter.com/standupmaths/status/1249105201992171522 172.69.22.146 00:04, 17 April 2020 (UTC)

Conway died on a Doomsday

The thing I remember Conway for (in addition to Game of Life) is discovering the Doomsday rule/algorithm for determining days of the week (see https://en.wikipedia.org/wiki/Doomsday_rule). Of course, I'm nowhere near anywhere as fast as he is (I'm happy if I can do it without making a mistake in 10 seconds, more if I'm calculating under the influence). I find it fitting that Conway died on a Doomsday (Saturday for 2020).Tovodeverett (talk) 05:41, 17 April 2020 (UTC)

Trivia: I was introduced to Conway's Game of Life through the book "The Magic of Lewis Carroll", by John Fischer (1973). One of the Life patterns was the "Cheshire Cat", which was a cat-like face that became a smile, then a paw-print (2x2 stable block). Conway developed the Doomsday algorithm from Lewis Carroll's initial formula, primarily by noting the even month pattern (4/4, 6/6, 8/8, 10/10, 12/12) and the 9 to 5 at 7-11 mnemonic.172.69.63.191 13:17, 17 April 2020 (UTC)
Trivia: More trivia - April 11, 2020 was 42 days after Feb 29, 2020.Tovodeverett (talk) 04:39, 18 April 2020 (UTC)

Symbolism of the evolving configuration

Should we perhaps add an explanation as to what the evolving configuration symbolizes, for the sake of readers with different cultural backgrounds? E.g., that it evokes the religious imagery related to Ecclesiastes 12:7 (KJV: "Then shall the dust return to the earth as it was: and the spirit shall return unto God who gave it."), that the glider can be viewed as representing the soul departing to heaven, etc. -- 172.68.215.224 20:19, 29 September 2020 (UTC)