Site Info

Authors
  • H.Koenig
  • Adam Goucher
  • Dave Greene

Contribute

Powered by
Movable Type 3.2

2014-May-23

Glider Constructions
Constructions Known for All Still Lifes up to 17 Bits

17-bit still life index pattern
Index pattern showing the 298 remaining 17-bit
still lifes that were not trivially synthesizable
as of January 2014.
A project to find glider syntheses for all stable objects up to 16 bits was completed at the beginning of 2014. Since then, an impressive five-month collaborative effort mostly between Martin Grant, Mark Niemiec, and Matthias Merzenich has produced new syntheses for about three hundred "non-trivial" 17-bit still lifes. There has been more progress in solving glider-synthesis problems in the last year than in the entire preceding decade, according to Mark's description of the recent surge of activity. The image at right links to a conwaylife.com forum posting with the original index pattern.

Continue reading "Constructions Known for All Still Lifes up to 17 Bits" More

2013-May-29

Discovery
Recent Discoveries, part II

This is intended to be a follow-up to my earlier post on cp4space (mentioning Mike Playle's new reflector). The content of this post is slightly too niche for cp4space, so I've included it here instead.

Mike Playle's new reflector has prompted a new surge in activity, with several derivative patterns being constructed. Firstly, Dave Greene has utilised the 'Snark' to reduce the area of the period-59 gun (Goucher and Summers) by two orders of magnitude.

image
Dave Greene's period-59 gun.

Secondly, a contributor on Nathaniel Johnston's forum has found a way to synthesise the reflector using 50 gliders. There has been much interest about the constructibility and destructibility of reflectors, with Paul Chapman writing a program entitled Seeds of Destruction to search for efficient self-destruction circuits. This is part of an ongoing project by Chapman and Greene to produce a smaller replicator than Andrew Wade's Gemini. A preliminary edition of Seeds of Destruction can be downloaded from here.

image
Screenshot of the Seeds of Destruction puzzle game.

Another recent discovery is a true period-20 glider gun, making it the most rapid glider gun known. This was discovered after a large period-40 gun was built by Adam P. Goucher and optimised by Matthias Merzenich, and (since 40 is a multiple of 20) can be trivially modified to yield a more compact p40 gun.

image
Matthias' period-20 glider gun.

Mike Playle has used his search program (Bellman) to find further discoveries, including a completion of the elusive period-94 AK47 glider gun and an elegant stabilisation of a known period-33 oscillator. There has been speculation about whether the latter could be coaxed into releasing gliders.

image
Mike Playle's period-94 gun and a new period-33 oscillator stabilisation.

2013-March-10

Spaceships
c/7 orthogonal spaceship

Josh Ball has discovered a microscopic orthogonal spaceship with a new velocity, namely c/7. It is the slowest orthogonal spaceship, which (together with its loaf-pushing behaviour) led to it being named 'the loafer'. Adam P. Goucher discovered how to synthesise it with 18 gliders; this was further reduced to 8 by Matthias Merzenich. Shortly afterwards, a gun was engineered to repeatedly emit the spaceship.

A summary of the known orthogonal spaceship speeds is given in the following diagram, using Ford circles to represent rational numbers:

orthogonal-velocities.png

2013-January-19

New HighLife velocities

HighLife differs quantatively from Conway's Game of Life due to an additional birth condition: if a dead cell is surrounded by six live neighbours, it becomes alive. Qualitatively, the main difference between Life and HighLife is that the replicators in Life are imagined to be very large (no explicit examples have been discovered, although the technology behind Gemini could be adapted to yield one), whereas there is a nice small example in HighLife.

The HighLife replicator after thirty-six generations

Soon after the discovery of the replicator, it was realised that it could be tamed into a c/6 spaceship by pulling a blinker behind it. In 1999, Dean Hickerson proposed the existence of spaceships with much slower velocities, obtained by pushing junk at one end of a replicator track and pulling it at the other end. No explicit examples of spaceships were discovered this way, although Dean found a workable push reaction. This was mentioned on David Eppstein's website and in a chapter he wrote for Game of Life Cellular Automata.

It was pretty much forgotten for 14 years, until Adam P. Goucher wrote a search program to attempt to construct replicator tracks capable of forming spaceships. Initially, he found a c/69 spaceship with over 84 billion replicator units; his results and method of searching are summarised on Complex Projective 4-Space. Due to its immense size, slow movement and general appearance, it was named the Basilisk. Karel Suhajda commented on the post, suggesting trying different speeds. Tweaking the search parameters resulted in a c/63 spaceship with about 2 billion units; however, this was still prohibitively large for Golly.

Matthias Merzenich's (6,6) push reaction

Matthias Merzenich found a vastly more efficient push reaction, which moves a constellation by (6, 6) as opposed to Dean's (8,8) push. Adam P. Goucher did further alterations to incorporate this into the search program, which gave a c/24 Basilisk of just over 15000 replicator units. This is comfortably within the limitations of Golly, and there is an explicit RLE file of it. Using this technology, he proceeded to build c/24 glider rakes and even a gun to periodically emit c/24 Basilisks! A more comprehensive description and links to pattern files were posted on a later cp4space article.

A gun and a series of c/24 Basilisks emerging from it

Helmut Postl subsequently discovered a c/32 Basilisk, which is slightly smaller than its c/24 counterpart. Together with Matthias' c/5 diagonal spaceship from a couple of years ago, there are now twelve known spaceship velocities in HighLife: c/2, c/3, c/4, c/5 and 2c/5 orthogonal; c/4, c/5, c/6, c/24, c/32, c/63, c/69 diagonal. Additionally, Dean found a c/22 quadruple blinker-puffer by composing his (6,6) push with a (6,6) beacon pull, but it is unlikely that it can be exploited to yield further technology.

This all stems from the existence of the replicator in HighLife. If a similar construct were created in ordinary Life (proved to be possible), then similar XOR-extendable spaceships and so forth could be built. Dave Greene has been researching the possibilities in this direction.

2012-October-28

Records
Fastest 90-degree stable reflector

A wealth of new generalised Herschel conduits have been discovered recently, even since the latest update on LifeNews. A member of the ConwayLife.com forums with the alias 'Guam' has successfully built a stable 90-degree reflector with a repeat time of 444 generations, marginally faster than its 466-tick predecessor.

2012-10-28-444-tick-reflector.png

The core of the reflector is a staged-recovery mechanism found in an earlier 487-tick reflector. The speed-up is therefore achieved by surrounding the core with a more efficient Herschel track (exploiting the new conduits), enabling the gliders to be delivered to the active site faster than before.

In other news, there is now a continuous version of the Game of Life exhibiting rich behaviour. It cannot be simulated in Golly due to its incompatibility with HashLife, although I believe the next release of Ready will incorporate it.

2012-September-11

The Mandelbrot set in HighLife

As detailed over on Complex Projective 4-Space, I computed some large images of the Mandelbrot set. For example, here is part of a screenshot of Golly, looking at the Seahorse Valley in the Mandelbrot set:

2012-09-11-seahorse.PNG

With Golly, we can run the Mandelbrot set in a cellular automaton. The results are fairly uninteresting with B3/S23, so I simulated the boundary (obtained from the original image by one generation of B3/S23) in HighLife (B36/S23) instead. As with all sufficiently large chaotic HighLife universes, profusions of replicators emerge:

2012-09-11-mset-b36s23.PNG

You can download the files from Complex Projective 4-Space yourself if you're interested in running a simulation. For these purposes, you'll want the 262144 by 262144 monochromatic image (25 MB download as .mc.gz), rather than the scaled-down colourful version.

In both HighLife and ordinary Life, we obtain four waves of gliders, a handful of orthogonal spaceships and a few diamonds on the real axis. These diamonds are caused by long unbroken lines expanding. In Life, we get two back-to-back Sierpinski triangles, compared with a uniform pattern of blinkers in HighLife. Further, these blinkers are very vulnerable to chaos, resulting in the destruction apparent in the green-bordered inset image.

2012-August-25

Life Variants
Penrose tilings and Ready

My apologies for the lack of recent postings. There are rumours that the LifeNews server may be turning off in the immediate future, so I was tentative about uploading something new. Nevertheless, Andrew Trevorrow convinced me that this deserves to be published on ConwayLife.com, and I understand this to currently be the most direct way of doing so.

The developers of Golly have recently turned their attentions to creating a new piece of software capable of supporting reaction-diffusion systems and cellular automata on arbitrary meshes. This has been discussed on Complex Projective 4-Space and The Aperiodical, amongst other places.

There has also been some work on cellular automata on Penrose tilings. Nick Owens and Susan Stepney investigated B3/S23 a while ago, writing a chapter about the topic in Adamatzky's Game of Life Cellular Automata. This summer, a couple of related, independent and almost simultaneous discoveries were made. One of these was a weakly universal cellular automaton on a Penrose tiling; the other was a glider.

The glider attracted a lot more attention, not least because a $100 prize was offered for its discovery. Again, this was mentioned on Complex Projective 4-Space, New Scientist and The Aperiodical. Even more recently, it was investigated on the kite-and-dart Penrose tiling, where it follows fractal paths and symmetrical loops. An image is displayed below:

The lengths of loops (half the period of the resulting oscillators, since the glider is c/2) are tabulated in the sequence A215878 of the Online Encyclopedia of Integer Sequences.

2012-January-14

Discovery
Gardens of Eden

orphan.png
Smallest GoE.

Marijn Heule, Christiaan Hartman, Kees Kwekkeboom and Alain Noels systematically searched the entire space of 10-by-10 patterns with fourfold rotational symmetry, finding a Garden of Eden with 92 specified cells (56 live, 36 dead). Moreover, they proved the non-existence of Gardens of Eden within a 6-by-6 box.

2011-October-25

Discovery
Beyond Herschels

If you asked a fellow Life enthusiast for the most important GoL discoveries in the 1990s, the Herschel track must surely feature. With a few elementary conduits, it is possible to design tracks capable of moving a signal to anywhere in spacetime (as long as there is enough 'manouevring room' and sufficient time), and placing it in any orientation. Herschel tracks underpin all but two of the known stable reflectors, and support the construction of glider guns for every period greater than or equal to 62.

2011-10-27-flowmatrix.PNG
Flow matrix for five common transient objects.

Firstly, what is so special about the Herschel? Is it really so much more useful than any other transient objects? It appears that the answer is both yes and no: other objects can be used, but they must eventually decay into Herschels. This is illustrated rather eloquently by a simple matrix. The row represents the input; the column represents the output. A red blob indicates if a primary (one-stage) conduit exists to transform the input into the output. Clicking on the matrix will enable you to download a complete collection of primary conduits. (A collection of all conduits, primary and composite, is provided later in this article.)

2011-10-27-L309.PNG
Guam's 309-generation left-turn conduit.

Some of these conduits are new discoveries. The Pi-to-R converter was discovered by Guam on the conwaylife.com forums, published in the form of a quaternary Herschel conduit: H-Pi-R-B-H. The completed conduit takes 309 generations to turn a Herschel anticlockwise, so is designated L309. In terms of the number of intermediary objects, L309 is the most complex Herschel conduit to date. Indeed, its 309-tick delay is rather rapid for a quaternary conduit.

2011-10-27-isomers.PNG
Isomers of Guam's 266-tick Herschel conduit.

Not content with a single new conduit, Guam proceeded to discover a pi-to-Herschel converter capable of attaching to a handful of 'pre-Herschel' conduits. Moreover, the symmetry of the pi heptomino means that Guam discovered not only one conduit, but two 'isomers'! The conduits are designated F266 and Fx266 for the translation and glide-reflection variants, respectively. However, the restrictions upon which conduits may follow F*266 severely limit its use in practical Herschel circuitry.

2011-10-27-Lx496.PNG
Matthias' tertiary Herschel conduit, the Lx496.

From an earlier posting of mine, you may remember the contributions of a certain 'MikeP', again from the conwaylife.com forums. Matthias Merzenich has utilised a particular catalyst of his in a few conduits, including the periodic R135 conduit and a stable Pi-to-century converter. To process the resulting century, Matthias proceeded to find two unique century-to-Herschel converters, one of which is sufficiently compatible to yield a new tertiary Herschel conduit, the Lx496.

Matthias even found a use for this new inundation of Herschel conduits; he has incorporated them into glider guns with smaller dimensions than the current record-holders. Specifically, they are a p421 gun derived from the L309 and p685 gun based on the Lx496.

2011-10-27-receiver.PNG
Guam's 4hd Herschel receiver.

In addition to his spectacular Herschel conduits, Guam also found two reactions in which gliders collide with constellations of still lifes to form extra junk. We already have a glider-to-beehive and glider-to-block converter, virtue of Paul Callahan, but we can now add loaves and bi-blocks to the collection. The latter is especially interesting, as a glider in the same direction as the original can liberate the bi-block in the form of a Herschel. The gliders are separated by 4 half-diagonals, unlike in previous receivers, where the separation must be 2, 5 or 6; hence, this new receiver could function where others fail. Also, it transpires that the bi-block functions as a LWSS eater, which can be toggled by incoming gliders.

Finally, he noted that two gliders separated by 4 or 5 half-diagonals can be reflected into a single glider. Here it is demonstrated as part of a stable reflector and related pulse divider. Alas, this reflector does not break any records, unlike the next subject of discussion -- the rectifier. This fast reflector, subject of a previous article on LifeNews, can be used in various conduits for transforming Herschels into gliders, by either modifying the output or assisting in the cleanup of surplus blocks.

To summarise this article, here is a collection of the 30 distinct Herschel conduits (including four adjustable ones), and a comprehensive collection of every (sufficiently simple) conduit, transceiver and converter known, as of the time of writing.

Continue reading "Beyond Herschels" More

2011-August-26

New spaceship velocity

Matthias Merzenich has discovered a c/7 diagonal spaceship -- the first of its speed. This raises the total to thirteen reasonably-low-period spaceship velocities, specifically eight orthogonal (c/2, c/3, c/4, c/5, 2c/5, c/6, 2c/7, 17c/45) and five diagonal (c/4, c/5, c/6, c/7, c/12). Of course, an infinite number of spaceship velocities are known, as the Gemini can be adapted accordingly.

image
Matthias' extensible c/7 diagonal spaceship.

Moreover, Matthias has actually discovered an infinite family of such spaceships, as one of the frontal components can support itself to yield an extensible spaceship.

2011-August-08

Engineered Objects
Painting with pulsars

As we've been busy recently, there have been no LifeNews postings for the last couple of months. Nevertheless, there have still been miraculous discoveries in Life that need reporting; this is one such example.

image
Pulsar-based display device

'Triller' from Nathaniel's forum has engineered an impressive construction: a fully functional display using pulsars to represent individual pixels. The display is continually refreshed at regular intervals, updating it with the data contained within several memory loops.

As he/she has included a comprehensive description of the mechanism, it would violate Occam's razor for me to describe it in great detail. However, there are some interesting features worth mentioning:

  • Triller has opted for period-30 technology, as opposed to the more modern option of Herschel tracks. This makes the device significantly more compact than its stable counterparts.
  • The image data is contained in data loops, similar to the Golly-ticker in Golly's pattern collection.
  • The sample image is the set of hexadecimal symbols, displayed in alternately ascending and descending order.

2011-May-24

Websites
The Return of ConwayLife.com

Nathaniel Johnston's website, conwaylife.com, is now back online, so the forums are accessible once again. Moreover, the homepage is updated with relevant blog entries from his blog, b3s23life, and even LifeNews itself!

image
Scaled-down screenshot of Nathaniel's refurbished website