Stable reflector: Difference between revisions

From LifeWiki
Jump to navigation Jump to search
Muzik (talk | contribs)
Trusted users
24,384 edits
New page: A stable reflector is any arrangement of still lifes that can absorb a glider, releasing one or more gliders and restoring itself in the process. The first reflectors were found by Pau...
 
No edit summary
 
(51 intermediate revisions by 19 users not shown)
Line 1: Line 1:
A stable reflector is any arrangement of [[still life]]s that can absorb a glider, releasing one or more gliders and restoring itself in the process. The first reflectors were found by Paul Callahan in 1996. There are several distinct categories of stable reflector:
{{Glossary}}
A '''stable reflector''' is a [[reflector]] composed entirely of [[still life]]s. That is, it is a collection of still lifes that can reflect some type of [[spaceship]] (usually a [[glider]]) without suffering permanent damage. Stable reflectors are special in that, if they satisfy certain conditions, they can be used to construct [[oscillator]]s of all sufficiently large periods. It was known for some time that stable reflectors were possible (see [[universal constructor]]), but no one was able to construct [[Stable reflector 1|an explicit example]] until [[Paul Callahan]] did so in October {{year|1996}} (see [[#History|History]]).


* 'Callahan' reflector - A reflector that temporarily creates an unwanted still-life and later destroys it.
== Types of stable reflectors ==
* 'Buckingham' reflector - A reflector that temporarily destroys a necessary still-life and later reconstructs it.
There are several distinct categories of stable reflectors:
* Direct reflector - A reflector that does not contain a Herschel track.


* 'Create-then-remove' reflector - A reflector that temporarily creates an unwanted still-life and later destroys it.
* 'Destroy-then-rebuild' reflector - A reflector that temporarily destroys a necessary still-life ([[bait]]) and later reconstructs it.
* Direct reflector - A reflector that does not contain a [[Herschel track]].


=== Repeat time ===
The '''[[repeat time]]''', also called the '''recovery time''' or '''compression''' of a stable reflector is the number of generations after the acceptance of one spaceship required for the reflector to be able to reflect the next spaceship.


== Records ==
=== Staged-recovery systems ===
[[Staged recovery]] is a construction method that attains reduced repeat time at the cost of complexity. The first such system was invented by Dave Greene, when he incorporated it into his [[highway robber]] and stable [[Heisenburp]] patterns. In 2009, Adam P. Goucher built two 'Create-then-remove' reflectors using a staged-recovery system.


Ideally, stable reflectors should be as small and fast as possible. Here are the current contenders:
== History ==
Before 2013, all known stable reflectors were quite slow. Callahan's original reflector starting with [[Herschel receiver]] has a repeat time of 4840, soon improved to 1686, 894 and then 850. In November 1996, [[Dean Hickerson]] managed to reduce the repeat time to 747 using a specialised Herschel-to-glider [[conduit]]. [[David Buckingham]] reduced it to 672 in May {{year|1997}} using a somewhat different method; he used a [[boat]] as the 'bait' catalyst, which is converted directly into a Herschel on impact, that rebuilds the initial boat. In October 1997, [[Stephen Silver]] reduced the time to 623 by a method closer to the original; instead of using a boat and [[conduit 1]] to convert the R-pentomino into a Herschel, Silver used a [[loaf]]. In November 1998, Callahan reduced this to 575 with [[Callahan G-to-H|a new initial reaction]] based on a [[beehive]], rather than a [[block]]. A small modification by Silver a few days later [[Silver's reflector|brought this down to 497]]. A brief summary of these can be found on the forums.<ref name="post72760" />


In April {{year|2001}}, [[Dave Greene]] found a 180-degree stable glider reflector with a repeat time of only 202 known as the [[boojum reflector]]. In {{year|2009}}, [[Adam P. Goucher]] constructed an improved version with a repeat time of only 106, known as the [[rectifier]].


* Smallest 90° reflector: [http://myweb.tiscali.co.uk/calcy/life/reflectors.htm#sect9]
Also in 2009, Adam P. Goucher used staged-recovery systems to delete the beehive much quicker, lowering the repeat time to [[487-tick reflector|487]] and then 466.<ref name="post1307" /><ref name="golnews200902" />  In 2012 [[Sergey Petrov]] (Guam) reduced the repeat time further, to 444<ref name="post7102" /><ref name="golnews201210" />, with a new conduit.  When the [[Snark]] was discovered, it became possible to cut down the repeat time to 386 ticks.<ref name="post8496" />
* Fastest 90° reflector: [http://myweb.tiscali.co.uk/calcy/life/reflectors.htm#sect13]
* Smallest 180° reflector: [[rectifier]]
* Fastest 90° reflector: [[rectifier]]


In April, {{year|2013}} [[Mike Playle]] found a small 90-degree reflector known as the [[Snark]].  The Snark is currently the smallest known stable reflector, with a recovery time of 43.


The third record is debatable, since the [[boojum reflector]] has a smaller bounding box across all phases; the rectifier has the smallest quiescent configuration. The terms 'active' and 'passive' bounding box should be used to avoid confusion.
{{AS OF|the end of 2017}}, the following splitter is among the smallest known 90-degree [[colour-changing]] reflectors. The top output can be blocked by [[eater 1]] if needed.


{{EmbedViewer
|pname        = smallstablesplitter
|viewerconfig = #C [[ THUMBNAIL THUMBSIZE 2 HEIGHT 400 THEME 6 GPS 60 LOOP 340 X 5 ZOOM 8 AUTOSTART ]]
|position    = center
}}


=== The $100 prize ===
On June 5, {{year|2020}}, [[Entity Valkyrie]] constructed a 0-degree stable reflector based on a reaction by [[Martin Grant]]. This "reflector" changes the color of the glider, and is the first color-changing stable reflector with repeat time lower than that of the [[syringe]]. This reflector is known as the [[Bandersnatch]].


On July 25, {{year|2022}}, [[Simon Ekström]] constructed [[Jubjub reflector|a reflector]] (shown below) that bounces a glider exactly back along its incoming path. At {{times|23|22}} or {{times|25|21}}, this is the smallest known 180-degree reflector, only five columns wider than the [[Snark]].


The first record, unbroken since 1998, fits inside a 81*64 bounding box. Dave Greene has offered two $50 prizes:
On March 9, {{year|2023}}, [[Mitchell Riley]] discovered a small elementary 0-degree colour preserving reflector with repeat time 59, that shifts the incoming glider by 8 lanes<ref name="post158774" /> (also shown below).


{|style="margin:auto;width:300px;"
|{{EmbedViewer
|pname        = simeks180degreereflector
|viewerconfig = #C [[ THUMBSIZE 2 ZOOM 10 HEIGHT 400 GPS 20 AUTOSTART T 0 PAUSE 2 T 93 PAUSE 2 LOOP 94 ]]
|position    = center
|caption      = The [[jubjub reflector]]
}}
|{{EmbedViewer
|pname        = zerodegreereflector202303
|viewerconfig = #C [[ THUMBSIZE 2 ZOOM 10 HEIGHT 400 GPS 20 AUTOSTART T 0 PAUSE 2 T 99 PAUSE 2 LOOP 100 ]]
|position    = center
|caption      = [[0-degree colour-preserving reflector (March 2023)|A 0-degree colour-preserving reflector]]<ref name="post158774" />
}}
|}


* Find a stable glider reflector that fits inside a 50*50 bounding box.
=== Prizes ===
* Find a stable glider reflector that fits inside a 35*35 bounding box.
{{Alsosee|Problem}}
In 2001, Dave Greene's discovery of the boojum reflector won two long-standing prize offers of $100 each from [[Alan Hensel]] and [[Dietrich Leithner]], for a stable reflector fitting inside a {{times|50|50}} bounding box. Greene offered two follow-up $50 prizes for stable reflectors:


* Find a stable 90-degree glider reflector that fits inside a {{times|50|50}} bounding box.
* Find a stable 90-degree glider reflector that fits inside a {{times|35|35}} bounding box.


Solving the second challenge before the first challenge has been solved would win both prizes simultaneously.
Matthias Merzenich offered two similar $50 prizes for stable reflectors:


* Find a stable glider reflector with a repeat time of 100 generations or less.
* Find a stable glider reflector with a repeat time of 61 generations or less.


== Staged-recovery systems ==
Mike Playle won all four prizes with his discovery of his small stable reflector in April, 2013.  Playle then offered a new prize of $100 USD for a similarly small and fast stable reflector that changes the glider's color (since the [[Snark]] is a color-preserving reflector):


* Find a color-changing stable glider reflector that's at most {{times|25|25}}, with a repeat time of 50 generations or less.<ref name="post7843" />


The staged-recovery system was invented by Dave Greene, when he incorporated it into his [[highway robber]] and stable [[Heisenburp]] patterns. In 2009, Adam P. Goucher built two 'Callahan' reflectors using a staged-recovery system.
== References ==
<references>
<ref name="golnews200902">{{LinkGoLNews
|filename = 2009/02/stable_reflector_with_record_r.html
|title    = Stable Reflector with Record Recovery Time
|author  = Dave Greene
|date    = February 28, 2009
}}</ref>
<ref name="golnews201210">{{LinkGoLNews
|filename = 2012/10/fastest_90degree_stable_reflec.html
|title    = Fastest 90-degree stable reflector
|author  = Adam P. Goucher
|date    = October 28, 2012
}}</ref>
<ref name="post1307">{{LinkForumThread
|format = ref
|p      = 1307
|title  = Re: Herschel Tracks
|author = Adam P. Goucher
|date  = October 9, 2009
}}</ref>
<ref name="post7102">{{LinkForumThread
|format = ref
|p      = 7102
|title  = Re: Thread For Your Accidental Discoveries
|author = Sergey Petrov
|date  = September 29, 2012
}}</ref>
<ref name="post7843">{{LinkForumThread
|format = ref
|p      = 7843
|title  = Re: Just the place for a Snark!
|author = Mike Playle
|date  = April 27, 2013
}}</ref>
<ref name="post8496">{{LinkForumThread
|format = ref
|p      = 8496
|title  = Re: Finally trying out stable Herschel tracks...
|author = Martin Grant
|date  = July 11, 2013
}}</ref>
<ref name="post72760">{{LinkForumThread
|format = ref
|p      = 72760
|title  = Re: The search for an Spartan reflector and/or g-x
|author = Dave Greene
|date  = March 8, 2019
}}</ref>
<ref name="post158774">{{LinkForumThread
|format = ref
|p      = 158774
|title  = Re: Stable signal converters
|author = Mitchell Riley
|date  = March 9, 2023
}}</ref>
</references>
 
== External links ==
* {{Cite web|url=https://groups.google.com/d/msg/comp.theory.cell-automata/sHpFoieXvk4/NQRWMvcD76oJ|title=Still-life glider reflector found|author=Paul Callahan|date=November 16, 1996|accessdate=May 11, 2013}}
* A detailed summary of stable technology, 1996-2009. [https://web.archive.org/web/20110921171148/http://www.calcyman.co.uk/life/stable.htm]
* A complete list of notable stable reflectors. [https://web.archive.org/web/20100522052228/http://calcyman.awardspace.co.uk:80/life/reflectors.htm]
* {{LinkGoLNews|2010/03/the_continuing_search_for_a_mi_1.html|title=The Continuing Search for a Microreflector|date=March 16, 2010|author=Adam P. Goucher}}

Latest revision as of 22:06, 13 September 2025

A stable reflector is a reflector composed entirely of still lifes. That is, it is a collection of still lifes that can reflect some type of spaceship (usually a glider) without suffering permanent damage. Stable reflectors are special in that, if they satisfy certain conditions, they can be used to construct oscillators of all sufficiently large periods. It was known for some time that stable reflectors were possible (see universal constructor), but no one was able to construct an explicit example until Paul Callahan did so in October 1996 (see History).

Types of stable reflectors

There are several distinct categories of stable reflectors:

  • 'Create-then-remove' reflector - A reflector that temporarily creates an unwanted still-life and later destroys it.
  • 'Destroy-then-rebuild' reflector - A reflector that temporarily destroys a necessary still-life (bait) and later reconstructs it.
  • Direct reflector - A reflector that does not contain a Herschel track.

Repeat time

The repeat time, also called the recovery time or compression of a stable reflector is the number of generations after the acceptance of one spaceship required for the reflector to be able to reflect the next spaceship.

Staged-recovery systems

Staged recovery is a construction method that attains reduced repeat time at the cost of complexity. The first such system was invented by Dave Greene, when he incorporated it into his highway robber and stable Heisenburp patterns. In 2009, Adam P. Goucher built two 'Create-then-remove' reflectors using a staged-recovery system.

History

Before 2013, all known stable reflectors were quite slow. Callahan's original reflector starting with Herschel receiver has a repeat time of 4840, soon improved to 1686, 894 and then 850. In November 1996, Dean Hickerson managed to reduce the repeat time to 747 using a specialised Herschel-to-glider conduit. David Buckingham reduced it to 672 in May 1997 using a somewhat different method; he used a boat as the 'bait' catalyst, which is converted directly into a Herschel on impact, that rebuilds the initial boat. In October 1997, Stephen Silver reduced the time to 623 by a method closer to the original; instead of using a boat and conduit 1 to convert the R-pentomino into a Herschel, Silver used a loaf. In November 1998, Callahan reduced this to 575 with a new initial reaction based on a beehive, rather than a block. A small modification by Silver a few days later brought this down to 497. A brief summary of these can be found on the forums.[1]

In April 2001, Dave Greene found a 180-degree stable glider reflector with a repeat time of only 202 known as the boojum reflector. In 2009, Adam P. Goucher constructed an improved version with a repeat time of only 106, known as the rectifier.

Also in 2009, Adam P. Goucher used staged-recovery systems to delete the beehive much quicker, lowering the repeat time to 487 and then 466.[2][3] In 2012 Sergey Petrov (Guam) reduced the repeat time further, to 444[4][5], with a new conduit. When the Snark was discovered, it became possible to cut down the repeat time to 386 ticks.[6]

In April, 2013 Mike Playle found a small 90-degree reflector known as the Snark. The Snark is currently the smallest known stable reflector, with a recovery time of 43.

As of the end of 2017, the following splitter is among the smallest known 90-degree colour-changing reflectors. The top output can be blocked by eater 1 if needed.

x = 56, y = 44, rule = B3/S23 16b2o11bo6b2o$16b2o10bobo4bo2bo$28bobo3bob3o2b2o$27b2ob2obobo6bo$31bob o3b2o3bobo$27b2obo2b4obo4b2o$27b2obobo3bo$31bobo3bo$32bobo3bo$33bo3b2o 14bo$52bobo$53bo2$24b2o$24b2o$9b2o$8bo2bo$7bob2o42b2o$7bo45b2o$6b2o$ 21b2o$21bo$22b3o$24bo5b2o$29bobo$29bo$28b2o3$36bo15b2o$35bobo14bobo$ 35bobo16bo$36bo17b2o$3o37b2o$2bo37bobo$bo40bo$42b2o5$35bobo$36b2o$36bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBNAIL THUMBSIZE 2 HEIGHT 400 THEME 6 GPS 60 LOOP 340 X 5 ZOOM 8 AUTOSTART ]]
(click above to open LifeViewer)
RLE: here Plaintext: here

On June 5, 2020, Entity Valkyrie constructed a 0-degree stable reflector based on a reaction by Martin Grant. This "reflector" changes the color of the glider, and is the first color-changing stable reflector with repeat time lower than that of the syringe. This reflector is known as the Bandersnatch.

On July 25, 2022, Simon Ekström constructed a reflector (shown below) that bounces a glider exactly back along its incoming path. At 23 × 22 or 25 × 21, this is the smallest known 180-degree reflector, only five columns wider than the Snark.

On March 9, 2023, Mitchell Riley discovered a small elementary 0-degree colour preserving reflector with repeat time 59, that shifts the incoming glider by 8 lanes[7] (also shown below).

x = 22, y = 23, rule = B3/S23 5bo$bo3b3o9b2o$2bo5bo8bo$3o4b2o5bo3b3o$14b4o3bo$19bobo$16b2ob2o$16b2o$ 19b2o$20bo$19bo$19b2o$b2o$bobo$3bo6b2o5b2o$3b3o3bo2bo4bobo$b2o3bo3bobo 6bo$o2b4o4bo7b2o$2obo10b2o$3bob2o7bo$3bobo9b3o$2b2obobo9bo$6b2o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBSIZE 2 ZOOM 10 HEIGHT 400 GPS 20 AUTOSTART T 0 PAUSE 2 T 93 PAUSE 2 LOOP 94 ]]
The jubjub reflector
(click above to open LifeViewer)
RLE: here Plaintext: here
#C https://conwaylife.com/forums/viewtopic.php?p=158774#p158774 x = 29, y = 31, rule = B3/S23 5bo13bo$6bo11bobo$4b3o11bob3o$15b2obo4bo$15bobobobobo$17bobob2o4b2o$ 16bobo8bo$17bo7bobo$2bo22b2o$bobo$o2bo$2ob2o$bo4bo$o2b4o5b2ob2o$b2o9b 2ob2o$3b2o$3bo$4bo$b3o$bo4$8b2o$8bo2bob2o$9b3obobo$13bobo2bo$11b3ob4o$ 10bo3bo$10b2o2bobo$15b2o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THUMBSIZE 2 ZOOM 10 HEIGHT 400 GPS 20 AUTOSTART T 0 PAUSE 2 T 99 PAUSE 2 LOOP 100 ]]
A 0-degree colour-preserving reflector[7]
(click above to open LifeViewer)
RLE: here Plaintext: here

Prizes

Also see: Problem

In 2001, Dave Greene's discovery of the boojum reflector won two long-standing prize offers of $100 each from Alan Hensel and Dietrich Leithner, for a stable reflector fitting inside a 50 × 50 bounding box. Greene offered two follow-up $50 prizes for stable reflectors:

  • Find a stable 90-degree glider reflector that fits inside a 50 × 50 bounding box.
  • Find a stable 90-degree glider reflector that fits inside a 35 × 35 bounding box.

Matthias Merzenich offered two similar $50 prizes for stable reflectors:

  • Find a stable glider reflector with a repeat time of 100 generations or less.
  • Find a stable glider reflector with a repeat time of 61 generations or less.

Mike Playle won all four prizes with his discovery of his small stable reflector in April, 2013. Playle then offered a new prize of $100 USD for a similarly small and fast stable reflector that changes the glider's color (since the Snark is a color-preserving reflector):

  • Find a color-changing stable glider reflector that's at most 25 × 25, with a repeat time of 50 generations or less.[8]

References

  1. ↑ Dave Greene (March 8, 2019). Re: The search for an Spartan reflector and/or g-x (discussion thread) at the ConwayLife.com forums
  2. ↑ Adam P. Goucher (October 9, 2009). Re: Herschel Tracks (discussion thread) at the ConwayLife.com forums
  3. ↑ Stable Reflector with Record Recovery Time at Game of Life News. Posted by Dave Greene on February 28, 2009.
  4. ↑ Sergey Petrov (September 29, 2012). Re: Thread For Your Accidental Discoveries (discussion thread) at the ConwayLife.com forums
  5. ↑ Fastest 90-degree stable reflector at Game of Life News. Posted by Adam P. Goucher on October 28, 2012.
  6. ↑ Martin Grant (July 11, 2013). Re: Finally trying out stable Herschel tracks... (discussion thread) at the ConwayLife.com forums
  7. ↑ 7.0 7.1 Mitchell Riley (March 9, 2023). Re: Stable signal converters (discussion thread) at the ConwayLife.com forums
  8. ↑ Mike Playle (April 27, 2013). Re: Just the place for a Snark! (discussion thread) at the ConwayLife.com forums
Retrieved from "https://conwaylife.com/w/index.php?title=Stable_reflector&oldid=164021"