2293: RIP John Conway

Explain xkcd: It's 'cause you're dumb.
Jump to: navigation, search
RIP John Conway
1937-2020
Title text: 1937-2020

Explanation[edit]

John Conway, an English mathematician, passed away of COVID-19 on April 11, 2020. Two days later, Randall created this memorial comic. It is the 6th memorial comic, but it is the first released in almost 5 years, since 1560: Bubblegum.

One of Conway's most famous creations was the cellular automaton known as Conway's Game of Life. A cellular automaton is a machine composed of cells, each of which can be in a different state. Every generation, each cell in the automaton may transition to a new state depending on a set of rules. (Conway's work in mathematics was vast and various, but he is perhaps best known in the field for discovering the surreal numbers, which inspired Donald Knuth to write a novel which may have been referenced back in 505: A Bunch of Rocks.)

Conway's Game of Life was first popularized to the general public in the form of a game, Life Genesis, bundled into some distributions of Windows 3.1, an operating system from the early-90s that Randall most likely used in his preteen years.

Conway's Game of Life is a 2-state automaton (i.e., every cell can be "alive" or "dead") that is implemented on a two-dimensional grid of cells using the Moore neighborhood - this means that each cell can only be influenced by the eight cells directly surrounding it, both orthogonally and diagonally. The transition rules that Conway used are as follows:

  • If an "alive" cell has no live neighbors, or only one live neighbor, it becomes "dead". (This simulates death by isolation).
  • If an "alive" cell has four or more live neighbors, it becomes "dead". (This simulates death by overcrowding).
  • If a "dead" cell has exactly three live neighbors, it becomes "alive". (This simulates birth).

Despite the simplicity of these three rules, Conway showed that patterns of amazing complexity can nonetheless develop out of simple cell arrangements. Some patterns do not evolve at all ("still lifes"), some enter a cyclic, repeating state ("oscillators"), and some reproduce their own pattern displaced by an offset, resulting in patterns that can move across the grid under their own power ("gliders" and "spaceships"). This last category is of particular interest, as it allows the Game of Life to transmit information from one location to another, allowing for rich, dynamic behavior and even for the creation of computational machines within the automaton itself.

This comic begins with the shape of a stick figure as the starting cell configuration of the Game of Life. The black cells are "alive" and the white cells are "dead". This configuration then evolves via Conway's rules, disintegrating into nothingness except for a five-cell pattern known as a "glider", which ascends up and to the right. This visually suggests a "soul" breaking away as the corporeal body disintegrates. The glider is perhaps the most iconic pattern of the Game of Life, and is often used symbolically to represent the phenomenon of emergence.

Here the topology of the grid on which the cells evolve is not known, the cellular automaton can be run on many topologies, for example you can choose to make cells reappear from the opposite side once they reach an edge (similarly to the behaviour of the well known Pacman). Here once the glider reaches the top right, we know for sure that the actual grid is bigger (since the glider leaves the frame while continuing its pattern), and we are only seeing part of the full grid.

The initial state presented in the comic does actually evolve in that manner, as can be verified by entering the pattern into a cellular automaton simulator such as Golly or web services such as this one. It seems that no one else have created this pattern before. At least, despite discussion in the comments, no one has found anything to show that this is not Randall's own discovery of this pattern.

The title text simply states Conway's birth and death year: 1937-2020.

Conway's Game of Life was previously mentioned in 696: Strip Games. Cellular automata was also referenced in 505: A Bunch of Rocks.

This comic is the 18th comic in a row (not counting the April Fools' comic) in a series of comics related to the 2020 pandemic of the coronavirus SARS-CoV-2, which causes COVID-19. Although this comic is, of course, mainly a tribute to John Conway, the fact that he died of COVID-19 in the middle of this long series of coronavirus-related comics by Randall is relevant.

Table of generations[edit]

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[edit]

[A pixelated image of a stick figure using 21 pixels, could be a pixel Cueball, which waves with one hand up while holding the other hand down. The head consist of 7 pixels, the top row of three having two pixels beneath the two outer pixels, thus having two empty pixels beneath the central pixel. The neck and torso is a typical cross made from six pixels. The two legs are two pixels each shifted left and right of the cross. The arm to the left that waves is two pixels one down and the next back up to the level of the cross central beam. The arm to the right has the first pixel similarly but the second pixel continues one further step down. After less than one second it turns out that the image is animated, with the pixels changing according to the rules of Conway's Game of Life. The figure splits into three groups, two of which dissipates in a similar way at the bottom of the panel. The other becomes a 'glider' and moves off to the top-right corner of the image and out of the 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?[edit]

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?[edit]

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[edit]

"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[edit]

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[edit]

" 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[edit]

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[edit]

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)