Glider (Conway's Game of Life)

{{short description|Moving pattern in Conway's Game of Life}} {{Use mdy dates|date=July 2017}} right|frame|The mutation and movement of a "glider" thumb|200px|right|A three-dimensional view of a glider, with previous generations visible going down the z-axis. The c/4 period is clearly visible as "stacks" of cells that remain alive for successive generations.

The '''glider''' is a pattern that travels across the board in Conway's Game of Life.<ref>{{Cite magazine |date=1975-09-01 |title=Life line |magazine=Byte |last=Helmers |first=Carl |url=https://archive.org/details/1982-10-byte-magazine-october-1-byte-magazine-21533/1975%2009%20BYTE%2000-01%20The%20Worlds%20-%20Byte%20Magazine_21693/page/74/mode/2up |pages=72–80 |issue=1}}</ref> It was first discovered by Richard K. Guy in 1969, while John Conway's group was attempting to track the evolution of the R-pentomino. Gliders are the smallest spaceships, and they travel diagonally at a speed of one cell every four generations, or <math>c/4</math>.{{efn|Sometimes referred to as c/4d, whereas c/4o is used for orthogonal movement.}} The glider is often produced from randomly generated starting configurations.<ref>{{Cite web|url=http://wwwhomes.uni-bielefeld.de/achim/moving.html|title=Spontaneous appeared Spaceships out of Random Dust|last=Flammenkamp|first=Achim|publisher=Bielefeld University|date=December 9, 1995|access-date=February 27, 2009|archive-date=April 13, 2009|archive-url=https://web.archive.org/web/20090413192821/http://wwwhomes.uni-bielefeld.de/achim/moving.html|url-status=live}}</ref>

The name comes from the fact that, after two steps, the glider pattern repeats its configuration with a glide reflection symmetry. After four steps and two glide reflections, it returns to its original orientation.<ref>{{cite conference | last = Wainwright | first = Robert T. | contribution = Life is universal! | doi = 10.1145/800290.811303 | publisher = ACM Press | title = Proceedings of the 7th conference on Winter simulation - WSC '74 | year = 1974| volume = 2 | pages = 449–459 | doi-access = free }}</ref> John Conway remarked that he wished he hadn't called it the glider. The game was developed before the widespread use of interactive computers, and after seeing it animated, he feels the glider looks more like an ant walking across the plane.<ref>{{Cite AV media|url=https://www.youtube.com/watch?v=E8kUJL04ELA&t=3m55s |archive-url=https://ghostarchive.org/varchive/youtube/20211222/E8kUJL04ELA |archive-date=2021-12-22 |url-status=live|title=Does John Conway hate his Game of Life?|last=Haran|first=Brady|author-link=Brady Haran|date=March 3, 2014|publisher=YouTube|access-date=May 9, 2014}}{{cbignore}}</ref>

== Importance == Gliders are important to the Game of Life because they are easily produced, can be collided with each other to form more complicated objects, and can be used to transmit information over long distances. Instances of this second advantage are called '''glider syntheses'''. For instance, eight gliders can be positioned so that they collide to form a Gosper glider gun.<ref>{{Cite book|first=Mark D.|last=Niemiec|contribution=Object synthesis in Conway's Game of Life and other cellular automata|editor-first=Andrew|editor-last=Adamatzky|title=Game of Life Cellular Automata|pages=115–134|doi=10.1007/978-1-84996-217-9_8|year=2010|publisher=Springer-Verlag|isbn=978-1-84996-216-2 }} Fig. 8.12 on [https://books.google.com/books?id=5iz6C0zzWKcC&pg=PA129 p. 129] depicts a closely related synthesis with seven gliders and a block. The 8-glider synthesis combines two of the four-glider units described in this figure.</ref> Glider collisions designed to result in certain patterns are also called glider syntheses. Patterns such as blocks, beehives, blinkers, traffic lights, even the uncommon Eater, can be synthesized with just two gliders. It takes three gliders to build the three other basic spaceships, and even the pentadecathlon oscillator.

Some patterns require a very large number (sometimes hundreds) of glider collisions; some oscillators, exotic spaceships, puffer trains, guns, etc. Whether the construction of an exotic pattern from gliders can possibly mean it can occur naturally is still a conjecture.

Gliders can also be collided with other patterns with interesting results. For example, if two gliders are shot at a block in just the right way, the block moves closer to the source of the gliders. If three gliders are shot in just the right way, the block moves farther away. This "sliding block memory" can be used to simulate a counter, which would be modified by firing gliders at it. It is possible to construct logic gates such as ''AND'', ''OR'' and ''NOT'' using gliders. One may also build a pattern that acts like a finite-state machine connected to two counters. This has the same computational power as a universal Turing machine, so, using the glider, the Game of Life is theoretically as powerful as any computer with unlimited memory and no time constraints: it is Turing complete.<ref name="chapman">{{Cite web|url=http://www.igblan.free-online.co.uk/igblan/ca/|title=Life Universal Computer|date=November 11, 2002|last=Chapman|first=Paul|website=Igblan|access-date=July 12, 2009|archive-date=September 6, 2009|archive-url=https://web.archive.org/web/20090906014935/http://www.igblan.free-online.co.uk/igblan/ca/|url-status=dead}}</ref><ref name="bcg">{{Cite book|title=Winning ways for your mathematical plays|title-link=Winning ways for your mathematical plays|last1=Berlekamp|first1=E. R.|author1-link=Elwyn Berlekamp|last2=Conway|first2=John Horton|author2-link=John Horton Conway|last3=Guy|first3=Richard K.|author3-link=Richard K. Guy|date=2004|publisher=A K Peters|isbn=156881142X|edition=2nd|location=Natick, Mass|oclc=560267317}}</ref>

It was conjectured that any still life could be synthesized by gliders, with the details of the structure encoded by the positions and phases of the gliders. This has been disproven by a still life with 306 cells, constructed by Ilkka Törmä and Ville Salo in 2022, which can only be descended from itself without change.<ref>{{Cite web |last=apgoucher |date=2022-01-14 |title=29-year-old Conway conjecture settled |url=https://cp4space.hatsya.com/2022/01/14/conway-conjecture-settled/ |access-date=2025-03-24 |website=Complex Projective 4-Space |language=en-US}}</ref><ref>{{cite arXiv |eprint=2202.07346 |last1=Salo |first1=Ville |last2=Törmä |first2=Ilkka |title=What can oracles teach us about the ultimate fate of life? |date=2022 |class=math.DS }}</ref> Also, anything that ''can'' be synthesized with gliders, can be synthesized with certain constructions called "universal constructors". There is a universal constructor that starts with only 15 gliders, with a construction algorithm published in 2022.<ref>{{Cite web |last=biggiemac42 |date=2022-11-16 |title=Building arbitrary Life patterns in 15 gliders |url=https://biggieblog.com/building-arbitrary-life-patterns-in-15-gliders/ |access-date=2025-03-24 |website=a blog by biggiemac42 |language=en-US}}</ref>

== Hacker emblem == thumb|upright|The Glider in its usage as the hackers' emblem.<ref>{{cite web | url=http://www.catb.org/hacker-emblem/faqs.html | title=Glider Emblem FAQ | date=22 May 2014 | access-date=20 September 2016 | archive-date=12 September 2016 | archive-url=https://web.archive.org/web/20160912030747/http://www.catb.org/hacker-emblem/faqs.html | url-status=live }}</ref> Eric S. Raymond has proposed the glider as an emblem to represent the hacker subculture, as the Game of Life appeals to hackers, and the concept of the glider was "born at almost the same time as the Internet and Unix".<ref>{{Cite web|url=http://www.catb.org/hacker-emblem/faqs.html|title=Frequently Asked Questions about the Glider Emblem|last=Raymond|first=Eric S.|author-link=Eric S. Raymond|website=catb.org|access-date=November 5, 2012|archive-date=September 12, 2016|archive-url=https://web.archive.org/web/20160912030747/http://www.catb.org/hacker-emblem/faqs.html|url-status=live}}</ref> The emblem is in use in various places within the subculture.<ref>{{Cite web|url=http://bluehackers.org/logos|title=BlueHackers Logo|work=BlueHackers|access-date=July 17, 2017|archive-date=June 18, 2017|archive-url=https://web.archive.org/web/20170618063510/http://bluehackers.org/logos|url-status=live}}</ref><ref>{{Cite web|url=http://www.inkblurt.com/2007/05/16/the-glider-as-hacker-emblem/|title=The Glider as Hacker Emblem|last=Hinton|first=Andrew|date=May 16, 2007|website=inkblurt|access-date=July 17, 2017|archive-date=July 8, 2017|archive-url=https://web.archive.org/web/20170708154155/http://www.inkblurt.com/2007/05/16/the-glider-as-hacker-emblem|url-status=dead}}</ref>

== Notes == {{Notelist}}

== References == {{Reflist}}

== External links == *[http://www.conwaylife.com/wiki/Glider Glider] {{Webarchive|url=https://web.archive.org/web/20170702025334/http://www.conwaylife.com/wiki/Glider |date=July 2, 2017 }} at the LifeWiki *[http://www.catb.org/hacker-emblem/ The Glider: Proposal for a Hacker Emblem] {{Webarchive|url=https://web.archive.org/web/20230702064327/http://www.catb.org/hacker-emblem/ |date=July 2, 2023 }}

{{Conway's Game of Life}}

Category:Cellular automaton patterns