Demonoid

From LifeWiki
(Redirected from 10hd Demonoid)
Jump to navigation Jump to search
Demonoid
Demonoid image
Pattern type Spaceship
Number of cells 27250
Bounding box 55010 × 54964
Direction Diagonal
Period 438852
Mod Unknown
Speed 65c/438852 | 65c/438852
Heat Unknown
Discovered by Chris Cain
Dave Greene
Year of discovery 2015

Demonoid is the first type of self-constructing diagonal spaceship in the B3/S23 rule. A small "0hd Demonoid" was completed by Chris Cain in December 2015, shortly after a much larger 10hd version constructed in November[1] in collaboration with Dave Greene. The 0hd spaceship displaces itself by 65 cells diagonally every 438,852 generations. As of 2023, it is the only case where a spaceship gun pattern was completed before the actual spaceship -- the first 0hd Demonoid was fired by a gun.[2]

The name "Demonoid" is an accidental portmanteau of "diagonal" and "Geminoid" by Paul Chapman in February 2013. "0hd" and "10hd" refer to the number of half-diagonals separating the two glider lanes in the spaceships' construction arms.

The Demonoids ranked third place in the Pattern of the Year 2015 competition on the ConwayLife.com forums, behind the Simkin glider gun and the syringe.[3]

Design

Similar to the original Gemini spaceship, the Demonoid consists of two identical halves. Where the Gemini's halves are simple translations of each other, each half of the Demonoid is a glide-reflected mirror image of the other. A tape of gliders continually relays between the two halves, instructing each to construct a daughter configuration.

In the 0hd Demonoid, each half is itself made up of two identical parts. Each part consists of a syringe-based 180-degree reflector combined with an edge shooter, plus a scattering of self-destruct circuitry. A cycle is completed when one of these parts is constructed ahead of the spaceship and an identical reflector/edge shooter is destroyed at the back end as soon as its construction work is done.

Self-destruct mechanism

The self-destruct sequence is triggered by a glider that follows the construction recipe on a slightly different lane. The only output of the cleanup reaction is another trigger glider, which appears in the exact same location as the original trigger glider, relative to the end of the recipe stream.

Statistics

Demonoids are the smallest known self-constructing or self-supporting spaceships in terms of population, but the bounding box of the centipede is about half the size of the smallest Demonoid's bounding box, and the waterbear is considerably smaller in both longest diameter and bounding box.

Demonoid variants make up the nineteenth and twentieth explicitly-constructed spaceship velocities, but as with previous self-constructing spaceships they actually represent an infinite family of related velocities. If the two halves of the Demonoid are moved N cells farther away from each other, the 0hd Demonoid travels diagonally at a speed of 65c/(438852+8N).

Speed limit

Theoretically speaking, a Demonoid spaceship using the 0hd elbow-move library could be designed with any velocity slower but not equal to 17c/792 diagonally, or roughly c/47 -- much faster than the old Gemini limit of c/580[4]. A 0hd elbow can be programmed to move much faster than a Gemini elbow's speed limit of one diagonal cell per coded instruction, and signals in syringe-based Herschel circuitry can be compressed to within 90 ticks of each other. However, any speed faster than 65c/438852 would require the 0hd Demonoid's circuitry and construction recipes to be completely redesigned, with a much larger total size and population in most cases.

Single-channel Demonoids have since been created that move a block to the next construction site by creating and triggering a seed for a spaceship -- e.g., a Cordership or a 58P5H1V1 -- and then shooting it down later with a small salvo of gliders to produce a faraway target for the construction arm. Demonoids using Corderships to move a target can approach c/12 in speed, but never quite reach that limit, and 58P5H1V1-based Demonoids can be built with any rational speed below c/5. A crab-based wickstretcher seed discovered by Tanner Jacobi allows a Demonoid to reach any rational speed slower than c/4, which is the absolute speed limit for any diagonal spaceship in Life.[5] The first such "Speed Demonoid" to use the crabstretcher in this way was made on September 18, 2020 by Dave Greene and Pavel Grankovskiy.

History

The first Demonoid designs were significantly larger and more complicated than the final 10hd or 0hd models. Some early designs required all elbow operations to be made from pairs of gliders, with no singleton gliders allowed.[6]

This allowed the gliders in each pair to be coded on a single tape, one directly after the other. However, it greatly increased the amount of timing circuitry needed. It also cut the allowable signal density in half. The signal density was already low because in 2012 the repeat rate for stable Spartan circuitry was 497 ticks or more.

A sizable improvement involved moving to a design with the two halves of the recipe encoded in series instead of interleaved. This allowed for better signal density, and also any combination of singleton gliders and glider pairs.[7]

These early designs were all 9hd -- the two construction lanes were separated by 9 half diagonals, and a block centered between the lanes served as the elbow. This allowed all elbow operations to be used either directly or in mirror-image, which meant that gliders could be fired either left or right from the elbow, and elbow moves could be mirrored if there was limited space available and the move recipe had a larger spark on one side than on the other.

After the 9hd linear propagator was completed, it became clear that 10hd was significantly more efficient, in part because it allowed for two block elbows in slightly different positions between the construction lanes.

The 10hd and 0hd Demonoid both use a much larger number of elbow locations. A library of thousands of elbow operations allows easy switching between different elbow types, and gliders can be output on any nearby lane by stringing recipes together.

The 10hd Demonoid was the first complete self-constructing diagonal spaceship.[8] Its construction recipe encoded two complete 180-degree reflector/edge shooter components, which were mostly identical to each other but had significant differences near the construction lanes. It included complex machinery that blocked the construction lanes during the half of the Demonoid's cycle when the recipe gliders intended for one circuit were passing through the other circuit's reflector.

The 0hd Demonoid improved on the 10hd model by removing the blocking mechanisms and the resulting long pause in construction. Instead, the two reflector/edge shooter components were designed to be completely identical. Each newly constructed component would first produce the trailing halves of the glider pairs in the next construction recipe. Then the same edge shooter would fire the leading halves of the glider pairs for the following construction.

In June 2017 Dave Greene completed a much simpler single-channel Demonoid using a temporary lossless elbow, which displaces itself 79 cells diagonally every 1,183,842 ticks.[9] This was an improvement in terms of design complexity, but not in terms of speed, population, or bounding box. However, all of these could be further optimized. "Scorbie's Demonoid", a single-channel Demonoid design with much more compact stable circuitry suggested by Dongook Lee, was completed in October 2018.[10] A week later this was followed by a larger but more Hashlife-friendly version traveling 32 times faster, using somewhat different construction methods.[11]

On September 18, 2020, Pavel Grankovskiy constructed the Speed Demonoid. It goes at 3492022/17833792=1746011/8916896 ≈ 0.1958c, very close to c/5, making it the fastest Demonoid. It uses double crabstretchers to accelerate a self-constructing spaceship to the aforementioned speed. It can be changed to any rational speed below 2c/9. Eight days later, Speed Demonoid version 2 was completed, removing the 2c/9 barrier and enabling the creation of any Demonoid with a speed of less than c/4.

Pattern files

See also

References

  1. Chris Cain (December 6, 2015). "Re: Demonoid (diagonal Geminoid) completed!". ConwayLife.com forums. Retrieved on December 7, 2015.
  2. Chris Cain (December 7, 2015). "Re: Demonoid (diagonal Geminoid) completed!". ConwayLife.com forums. Retrieved on January 4, 2016.
  3. Alexey Nigin (February 11, 2016). Re: Pattern of the Year 2015 (Votes) (discussion thread) at the ConwayLife.com forums
  4. Adam P. Goucher (May 21, 2010). "Re: Universal Constructor Based Spaceship". ConwayLife.com forums. Retrieved on December 9, 2015.
  5. Tanner Jacobi (August 2, 2020). "One Glider Seeds". ConwayLife.com forums. Retrieved on August 12, 2020.
  6. Dave Greene (December 22, 2012). "Re: Geminoid Challenge". ConwayLife.com forums. Retrieved on December 8, 2015.
  7. Dave Greene (February 15, 2013). "Re: Geminoid Challenge". ConwayLife.com forums. Retrieved on December 8, 2015.
  8. Dave Greene (November 25, 2015). "Re: Demonoid (diagonal Geminoid) completed!". ConwayLife.com forums. Retrieved on December 8, 2015.
  9. Dave Greene (June 26, 2017). "Re: Demonoid (diagonal Geminoid) completed!". ConwayLife.com forums. Retrieved on June 3, 2018.
  10. Dave Greene (October 3, 2018). "Re: Demonoid (diagonal Geminoid) completed!". ConwayLife.com forums. Retrieved on October 3, 2018.
  11. Dave Greene (October 10, 2018). "Re: Demonoid (diagonal Geminoid) completed!". ConwayLife.com forums. Retrieved on October 10, 2018.

External links