Difference between revisions of "Stable reflector"
(→Prizes: added original prize information and Mike Playle's current offer) |
m (→Prizes: × using AutoWikiBrowser) |
||
| (13 intermediate revisions by 6 users not shown) | |||
| Line 1: | Line 1: | ||
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 an [[stable reflector 1|explicit example]] until [[Paul Callahan]] did so in October | {{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 an [[stable reflector 1|explicit example]] until [[Paul Callahan]] did so in October {{year|1996}}. | |||
==Types of stable reflectors== | ==Types of stable reflectors== | ||
| Line 9: | Line 10: | ||
===Repeat time=== | ===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. | 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 systems=== | ||
| Line 15: | Line 16: | ||
==History== | ==History== | ||
Before 2013, all known stable reflectors were quite slow. Callahan's original reflector has a repeat time of 4840, soon improved to 1686 and then 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 | Before 2013, all known stable reflectors were quite slow. Callahan's original reflector has a repeat time of 4840, soon improved to 1686 and then 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, on impact, directly into a Herschel, which 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 [[Silver's reflector|brought this down to 497]]. | ||
In 2009, Adam P. Goucher used a staged-recovery system to delete the beehive much quicker, lowering the repeat time to 466. In 2012 | In 2009, Adam P. Goucher used a staged-recovery system to delete the beehive much quicker, lowering the repeat time to 466.<ref name="post1307" /> In 2012 Sergei Petrov used a new conduit to reduce the repeat time further, to 444<ref>{{cite web|url=http://conwaylife.com/forums/viewtopic.php?f=2&t=279&start=525#p7102 |title=new stable glider reflector (and glider to Herschel converter) |author=[[Sergey Petrov]] (Guam) |date=September 29th, 2012 |accessdate=September 30,2014}}</ref>. When the [[Snark]] was discovered, it became possible to cut down the repeat time to 386 ticks.<ref>{{cite web|url=http://conwaylife.com/forums/viewtopic.php?f=2&t=148&start=50#p8496 |title=386-tick G-to-H |author=Martin Grant |date=July 11th, 2013 |accessdate=September 30,2014}}</ref> | ||
In April | 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 | In {{year|2009}}, [[Adam P. Goucher]] constructed a 180-degree stable glider reflector with a repeat time of only 106, known as the [[rectifier]]. | ||
In April, | 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. | ||
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 off by an [[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 | |||
}} | |||
In {{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 the repeat time of the [[syringe]]. This reflector is known as the [[Bandersnatch]]. | |||
===Prizes=== | ===Prizes=== | ||
In 2001, | 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 glider reflector that fits inside a 50×50 bounding box. | * Find a stable 90-degree glider reflector that fits inside a 50×50 bounding box. | ||
* Find a stable glider reflector that fits inside a 35×35 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: | Matthias Merzenich offered two similar $50 prizes for stable reflectors: | ||
| Line 38: | Line 49: | ||
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): | 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 | * Find a color-changing stable glider reflector that's at most 25×25, with a repeat time of 50 generations or less.<ref>{{cite web|url=http://conwaylife.com/forums/viewtopic.php?f=2&t=1082#p7843 |title=Just the place for a Snark! |author=Mike Playle |date=April 27, 2013 |accessdate=September 30, 2014}}</ref> | ||
==References== | ==References== | ||
<references /> | <references> | ||
<ref name="post1307">{{LinkForumThread | |||
|format = ref | |||
|title = Re: Herschel Tracks | |||
|p = 1307 | |||
|author = Adam P. Goucher | |||
|date = October 9, 2009 | |||
}}</ref> | |||
</references> | |||
==External links== | ==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}} | * {{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. [http://www.calcyman.co.uk/life/stable.htm] | * 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. [http:// | * A complete list of notable stable reflectors. [https://web.archive.org/web/20100522052228/http://calcyman.awardspace.co.uk:80/life/reflectors.htm] | ||
Revision as of 18:56, 22 August 2020
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.
Types of stable reflectors
There are several distinct categories of stable reflector:
- '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 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
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 'Create-then-remove' reflectors using a staged-recovery system.
History
Before 2013, all known stable reflectors were quite slow. Callahan's original reflector has a repeat time of 4840, soon improved to 1686 and then 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, on impact, directly into a Herschel, which 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.
In 2009, Adam P. Goucher used a staged-recovery system to delete the beehive much quicker, lowering the repeat time to 466.[1] In 2012 Sergei Petrov used a new conduit to reduce the repeat time further, to 444[2]. When the Snark was discovered, it became possible to cut down the repeat time to 386 ticks.[3]
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 a 180-degree stable glider reflector with a repeat time of only 106, known as the rectifier.
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 off by an eater 1 if needed.
| (click above to open LifeViewer) RLE: here Plaintext: here |
In 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 the repeat time of the syringe. This reflector is known as the Bandersnatch.
Prizes
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.[4]
References
- ↑ Adam P. Goucher (October 9, 2009). Re: Herschel Tracks (discussion thread) at the ConwayLife.com forums
- ↑ Sergey Petrov (Guam) (September 29th, 2012). "new stable glider reflector (and glider to Herschel converter)". Retrieved on September 30,2014.
- ↑ Martin Grant (July 11th, 2013). "386-tick G-to-H". Retrieved on September 30,2014.
- ↑ Mike Playle (April 27, 2013). "Just the place for a Snark!". Retrieved on September 30, 2014.
External links
- Paul Callahan (November 16, 1996). "Still-life glider reflector found". Retrieved on May 11, 2013.
- A detailed summary of stable technology, 1996-2009. [1]
- A complete list of notable stable reflectors. [2]