Difference between revisions of "Catagolue"

From LifeWiki
Jump to: navigation, search
m
(Added Just Friends and Snowflakes to rules list)
Line 339: Line 339:
 
* B3678/S34678 ([[Day & Night]])
 
* B3678/S34678 ([[Day & Night]])
 
* B368/S245 ([[Move]], aka [[Morley]])
 
* B368/S245 ([[Move]], aka [[Morley]])
 +
* B2-a/S12 ([[Just Friends]])
 +
* B2ci3ai4c8/S02ae3eijkq4iz5ar6i7e ([[Snowflakes]])
  
 
==Catagolue as a generic pattern inventory==
 
==Catagolue as a generic pattern inventory==

Revision as of 23:52, 19 January 2019

Catagolue
Catagolue B3S23 C1 20160724.png
Conducted by Adam P. Goucher
Type Distributed
Contributors >100[note 1]
Year(s) 2015 – 2018
Status Ongoing
Parameters
Universe Infinite plane
Soup size 16×16
Initial soup density 0.5[note 2]
Soups searched ≥15,138,228,209,232
Results
Total objects ≥330,680,301,229,741
Distinct objects ≥144,781

Catagolue[note 3] is an ongoing distributed census of naturally occurring ash objects conducted by Adam P. Goucher, started in late February 2015. The census is primarily focused on asymmetric soups in Conway's Life, but supports arbitrary outer-totalistic and non-totalistic rules and a variety of symmetries.[endpoint 1] Over 100 users have contributed to the census.

The results are obtained by evolving random soups of size 16×16 with density 0.5 in an infinite planar universe; as of February 9, 2019, at least 15,138,228,209,232 soups have been investigated by the census's participants, yielding a total of at least 330,680,301,229,741 objects of 144,781 distinct types. Submissions of new results (called "hauls") are subjected to both statistical tests and peer-review by other participants before being committed to the census.

Catagolue is primarily fed by apgsearch 4.x (apgluxe). Each resulting object is identified by apgsearch by its unique apgcode; the Catagolue website gives overviews over the various classes of objects found, and provides further information as well as sample soups for each object.[endpoint 2] A simple text-based interface for querying sample soups, including their owners, also exists.[endpoint 3]

History

Main article: History of Catagolue

Catagolue became operative on February 20, 2015.[1] The B3/S23/C1 census reached a total of one trillion objects on April 24, 2015[2], ten trillion objects on September 2, 2015[3], 100 trillion objects on June 20, 2016[4], and 200 trillion objects on May 16, 2017.

Results

Also see: Most common objects on Catagolue

As of February 9, 2019, at least 15,138,228,209,232 soups have been investigated by the census's participants, yielding a total of at least 330,680,301,229,741 objects. 144,781 distinct objects were identified, including:[5]

Plots

Scatter plot of total still life counts vs. populations in B3/S23/C1 as of July 15, 2017.
Scatter plot of distinct still life counts vs. populations in B3/S23/C1 as of July 15, 2017; the blue line indicates the total number of distinct still lifes per population (OEISicon light 11px.pngA019473).

Notable patterns

x = 13, y = 10, rule = B3/S23 4bo3bo$2b2obobob2o$bo3bobo3bo$o3b2ob2o3bo$obo7bobo$bo9bo2$4b2ob2o$3bob obobo$4bo3bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THEME 6 GRID GRIDMAJOR 0 THUMBLAUNCH AUTOSTART GPS 4 THUMBSIZE 2 ]]
Rich's p16 (click above to open LifeViewer)

A variety of notable natural and semi-natural patterns have been submitted to Catagolue:

  • The first known natural occurrence of a nonstandard spaceship was found during alpha testing of apgsearch. The soup, which produced an LWSS on HWSS 1, was submitted to the conwaylife.com forums on August 26, 2014 by Adam P. Goucher.[6] Many other nontrivial spaceship flotillae have since been found.
  • The pufferfish was discovered in the ash of a symmetric soup in November 2014.[7]
  • The first known natural occurrence of a puffer other than the block-laying or glider-producing switch engine, a p1152 made from two switch engines dubbed the pony express, was found in September 2015.[8]
  • A copperhead emerged from a D2_+2 soup in April 2016 soon after its initial discovery by zdr, followed by a second one in June 2016 and a third in August 2016; two more copperheads were found in D4_+4 and D8_4 soups in November 2016.[9]
  • 112P15 was first discovered in the ash of a symmetric soup in April 2016.[10]
  • Rich's p16 was first discovered in the ash of a symmetric soup in July 2016.[11]
  • thunk's discovery of a period 28 pre-pulsar-shuttle variant in November 2016 enabled the construction of smaller (in terms of minimum population) period 26 and period 28 pre-pulsar-shuttles.[12]
  • 34P14.1 was first discovered in the ash of a symmetric soup in September 2018, but was not noticed on Catagolue until October.[13]
  • 68P9 was first discovered in the ash of a symmetric soup in October 2018.[14]
  • 42100M was first discovered in October 2018, a few days after Catagolue began collecting data on methuselahs.[15]
  • Dueling banjos was first discovered in the ash of a symmetric soup in January 2019, in a tetramer form.[16]

Other objects found by apgsearch in asymmetric soups are smiley, Achim's p8, Elkies' p5, heart, Silver's p5, phoenix 1, and seven occurrences of the Coe ship. Sample soups submitted to Catagolue have also led to cheaper glider syntheses for many patterns, including tumbler, eater 2, and smiley.

Higher symmetries

6bo11bo$7b2o7b2o$3bobob2o7b2obobo$2bobo15bobo$3bo17bo$2bo19bo$o9b2ob2o 9bo$b2o8bobo8b2o$b2o6bobobobo6b2o$8bobo3bobo$6bo2bo5bo2bo$6b3o7b3o2$6b 3o7b3o$6bo2bo5bo2bo$8bobo3bobo$b2o6bobobobo6b2o$b2o8bobo8b2o$o9b2ob2o 9bo$2bo19bo$3bo17bo$2bobo15bobo$3bobob2o7b2obobo$7b2o7b2o$6bo11bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THEME 6 GRID GRIDMAJOR 0 THUMBLAUNCH AUTOSTART GPS 4 THUMBSIZE 2 WIDTH 480 HEIGHT 480 ]]
112P15 (click above to open LifeViewer)

In addition to asymmetric (C1) soups, Catagolue also collects census data for symmetric soups of the following types:

  • C2_1, C2_2, C2_4: 180° (two-fold) rotational symmetry
  • C4_1, C4_4: 90° (four-fold) rotational symmetry
  • D2_+1, D2_+2: reflectional symmetry along an orthogonal line
  • D2_x: reflectional symmetry along a diagonal line
  • D4_+1, D4_+2, D4_+4: reflectional symmetry along two perpendicular orthogonal lines
  • D4_x1, D4_x4: reflectional symmetry along two perpendicular diagonal lines
  • D8_1, D8_4: reflectional symmetry along four orthogonal/diagonal through a common center

Furthermore, the following pseudo-symmetries are used for asymmetric soups of different sizes:

  • 8x32, 4x64, 2x128, 1x256: for 256-cell soups of size 8×32, 4×64, 2×128 and 1×256

8x32 was one of the initial (pseudo-)symmetries the site handled; support for 4x64, 2x128 and 1x256 was added in August 2017.[17]

Inflation of a toy 4×4 soup.

All symmetries can be "inflated" using the "i" prefix, replacing each cell in the sample soup with a 2×2 alignment of cells in the same state and resulting in soups of size e.g. 32×32 for iC1 instead of 16×16 for C1. Multiple "i" prefixes can be stacked to "inflate" cells to 4×4, 8×8, etc.[18]

The 25pct and 75pct pseudo-symmetries were used in the past to investigate soups with initial densities of 0.25 and 0.75 respectively, but they fell into disuse and are not supported by v3.x and above.[note 6] Other pseudo-symmetries such as 25p, 32x32, 1x256X2+1 etc. have been used, but are not considered standard. Catagolue encourages users to use designated "test" symmetries to test modifications to the client,[19] and can be used to as a generic pattern inventory using arbitrary symmetries and rules (see below).

Hauls for official censuses of Life-like rules with at least one trillion objects are subject to statistical verification and peer review before being committed in order to avoid false data being added to the census. As of December 28, 2018, this includes all official symmetries for Conway's Game of Life as well as B38/S23/C1 (Pedestrian Life), B3/S01367/C1, B35/S136/C1, B3/S12/C1 (Flock), and B3/S2/C1.

As of January 2019, all symmetries for hexagonal neighbourhood rules have been implemented with the exception of C3_3 and D6_3.[20]

Catagolue does not currently support D8_2 symmetry, nor any form of gutter or skewgutter symmetries.

Results in higher symmetries

As of February 9, 2019, at least 3,862,612,198,335 soups have been investigated in higher symmetries[note 7] of B3/S23, yielding a combined total of at least 82,285,115,809,572 objects of 514,369 distinct types, including:[note 8]

Patterns seen but not properly recognized by the client (see Limitations below) include a D8_1-symmetric variant of the p29 pre-pulsar shuttle.

Plots

Scatter plot of total still life counts vs. populations in B3/S23 (higher symmetries) as of July 15, 2017.
Scatter plot of distinct still life counts vs. populations in B3/S23 (higher symmetries) as of July 15, 2017; the blue line indicates the total number of distinct still lifes per population (OEISicon light 11px.pngA019473).

Slow salvos

Catagolue started collecting data on objects created by slow salvos on January 13, 2017, using the SS pseudo-symmetry; data was generated by the HoneySearch utility.

As of February 9, 2019, slow salvos have yielded a total of at least 556,856,180,742 objects of 2,667 distinct types, including:

Plots

Scatter plot of total still life counts vs. populations in B3/S23 (slow salvos) as of July 15, 2017.
Scatter plot of distinct still life counts vs. populations in B3/S23 (slow salvos) as of July 15, 2017; the blue line indicates the total number of distinct still lifes per population (OEISicon light 11px.pngA019473).

Other rules

Main article: List of rules investigated on Catagolue

Catagolue also collects census data on various rules other than Conway's Game of Life. In practice, only non-exploding rules can reasonably be investigated unless a certain symmetry can be assured to never explode.

As of January 15, 2019, Catagolue officially supports the following types of cellular automata:

The Moore neighbourhood and hexagonal neighbourhood are the currently the only directly supported neighbourhoods, although the von Neumann neighbourhood can be indirectly simulated by isotropic Moore rules and the Margolus neighbourhood (specifically block cellular automata) can be simulated by inflated soups on specific rules.

6,844 rules have been looked at as of February 9, 2019.

Rules investigated on Catagolue include multiple close Life variants:

Other notable rules investigated include:

Catagolue as a generic pattern inventory

Although primarily used for soup-searching in practice, Catagolue can be used as a generic pattern inventory/warehouse, as shown by e.g. the slow salvo data it collected (see above). Users are encouraged come up with their own rulestrings, symmetry types, and object codes:

[Catagolue] basically accepts anything that you choose to pass off as a rule name, symmetry type, and apgcode. If you make a search program which produces haul files for your favourite CA, then Catagolue will happily build a distributed census [...]
The search program needn't even be a soup search: if you have a depth-first search program such as gfind or zfind, and you have a correspondence between positions in the search tree and alphanumeric strings (where prefixes correspond to ancestors), then you can conduct a distributed search for (say) width-20 c/6 spaceships using the existing Catagolue framework. If you incorporate all of zfind's command-line hyperparameters (period, offset, memory size, etc.) into the beginning of this string, then you can simply have a 'symmetry' called zfind whose tabulations will include things such as xq7, xq10, xq19 (potentially!), etc. And this will work without changing Catagolue in any way.
Adam P. Goucher[22]

Contributor engagement

Contributors to Catagolue have user pages tracking their contributions to the main Conway Life census, B3/S23/C1.[endpoint 4] In addition to providing an overview of number of objects submitted recently compared to other users, user pages list important discoveries and awarded badges.

Users are credited for discoveries if they find one of the first 20 occurrences of an interesting object: any spaceship (other than the glider), any oscillator, any linear growth pattern, or any sufficiently small (14-bit) or large still life. Certain other types of still lifes, such as Eater 2 precursors, are also credited.

The following badges are currently awarded for contributions to B3/S23/C1:

Interesting new objects are additionally announced on Twitter by an unofficial Twitter bot.

Backups

Catagolue census data for the main Conway Life census, B3/S23/C1, is backed up remotely every day at 17:29;[note 14] the first such backup was made on September 24, 2015. For other symmetries or rules, a remote backup may be instigated manually by calling the backupcron endpoint,[endpoint 5] with the desired rule and symmetry. Remote backups can be viewed by appending the date to the main census URL.[endpoint 6]

Local backups of Catagolue census data may be made by calling the textcensus endpoint for the desired rule and symmetry.[endpoint 7] The list of objects returned can be sorted by object frequency[endpoint 8], but this should be avoided when possible to reduce server load.[24] It is also possible to restrict objects returned to a certain prefix,[endpoint 9], or to query the number of objects, grouped by prefix and including a total.[endpoint 10]

Limitations

Server

Catagolue does not accept hauls exceeding 1 MiB; additionally, hauls must contains a minimum of 10,000 soups or 250,000 objects.[25]

Client

Although the apgsearch family of programs has bespoke support for flotillae composed of two standard spaceships in Conway's Life, it can fail to properly separate larger non-interacting groups, or groups of any size in non-Life rules. Pseudo still lifes composed of many constituent parts may also fail to be separated properly.[26]

The maximum period for spaceships and oscillators is 1,000 in apgsearch 1.x, 4,000 in apgnano (apgsearch 2.x), 1,280 in apgmera (apgsearch 3.x), and 1,048,576 in apgluxe (apgsearch 4.x); higher-period objects are classified as PATHOLOGICAL. The maximum bounding box for any spaceship, oscillator or still life is 40×40; larger objects are classified as ov_ (oversized). High-period linear-growth patterns may not be identified and instead reported as zz_LINEAR.

Web frontend

Although Catagolue verifies that an object in a given rule behaves as specified by its code, the site makes no attempt to reject non-canonical codes (e.g. xp2_222 rather than xp2_7 for the blinker); furthermore, the site accepts various anomalous prefixes (e.g. xp0 and xq0). No attempt is made to normalize or reject anomalous rules (e.g. "b33s23"), although a feature is planned to clear out censuses which do not adhere to the Catagolue naming conventions.

See also

Notes

  1. All users who contributed to any rule/symmetry.
  2. Soups with density 0.25 and 0.75 were also investigated to a minor extent; see the "Higher Symmetries" section.
  3. The name "Catagolue" is an amalgam of "Catalogue" and "GoL" (Game of Life).
  4. 4.0 4.1 Data on ordinary methuselahs is only collected by apgsearch v4.54 and above, and diehards by v4.69 and above.
  5. 5.0 5.1 apgsearch estimates the lifespan of each soup before testing it more precisely, and is not guaranteed to detect all methuselahs with a lifespan of less than 26,000 generations.
  6. The 25% pseudo-symmetry was also briefly used but abandoned due to conflicts with percent-encoding for URIs/URLs.
  7. I.e. all symmetries except C1, SS, "DankMemes" and any symmetry suffixed "_Test".
  8. This list excludes oversized patterns (ov_), unusual-growth patterns (zz_), and pathological patterns (PATHOLOGICAL); see Limitations.
  9. Due to technical limitations, this is a lower bound rather than an exact figure.
  10. Not properly recognized by apgsearch < 4.0; see Limitations.
  11. The "Conchita" badge is named after Conchita Wurst, the Austrian singer who won the 2014 Eurovision Song Contest with the song "Rise Like a Phoenix".
  12. The "Hitchhiker" badge has not been awarded as of March 5, 2018.
  13. Sic; a deliberate reference to this post on MathOverflow and the comments it attracted.
  14. Ramanujan time, after the Hardy–Ramanujan number (1729) of G. H. Hardy's and Srinivasa Ramanujan's.

Endpoints

  1. https://catagolue.appspot.com/census/<rule>/<symmetry>
  2. https://catagolue.appspot.com/object/<apgcode>/<rule>
  3. https://catagolue.appspot.com/attribute/<apgcode>/<rule>/<symmetry>
  4. https://catagolue.appspot.com/user/<user name>
  5. https://catagolue.appspot.com/backupcron/<rule>/<symmetry>
  6. https://catagolue.appspot.com/census/<rule>/<symmetry>-<year>-<month>-<day>
  7. https://catagolue.appspot.com/textcensus/<rule>/<symmetry>
  8. https://catagolue.appspot.com/textcensus/<rule>/<symmetry>/sorted
  9. https://catagolue.appspot.com/textcensus/<rule>/<symmetry>/<prefix>
  10. https://catagolue.appspot.com/textcensus/<rule>/<symmetry>/objcount

References

  1. Adam P. Goucher (February 20, 2015). "apgsearch 1.0". ConwayLife.com forums. Retrieved on June 23, 2016.
  2. Billabob (April 24, 2015). "Re: Soup search results". ConwayLife.com forums. Retrieved on June 23, 2016.
  3. Adam P. Goucher (September 2, 2015). "Re: Soup search results". ConwayLife.com forums. Retrieved on June 23, 2016.
  4. Apple Bottom (June 20, 2016). "Re: apgsearch v3.1". ConwayLife.com forums. Retrieved on June 23, 2016.
  5. Adam P. Goucher (June 28, 2016). "Statistics". Catagolue. Retrieved on June 28, 2016.
  6. Adam P. Goucher (August 26, 2014). "Re: Thread For Your Accidental Discoveries". ConwayLife.com forums. Retrieved on June 12, 2016.
  7. Richard Schank. Re: Soup search results (discussion thread) at the ConwayLife.com forums
  8. gameoflifeboy (September 28, 2015). "Re: Soup search results". ConwayLife.com forums. Retrieved on June 12, 2016.
  9. Apple Bottom. Re: Soup search results (discussion thread) at the ConwayLife.com forums
  10. thunk. Re: Soup search results (discussion thread) at the ConwayLife.com forums
  11. Ivan Fomichev. Re: Soup search results (discussion thread) at the ConwayLife.com forums
  12. Apple Bottom. Re: Soup search results (discussion thread) at the ConwayLife.com forums
  13. Aidan F. Pierce. Re: Soup search results (discussion thread) at the ConwayLife.com forums
  14. Aidan F. Pierce. Re: Soup search results (discussion thread) at the ConwayLife.com forums
  15. Ian07. Re: Soup search results (discussion thread) at the ConwayLife.com forums
  16. Matthias Merzenich. Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  17. Re: Hacking apgsearch (discussion thread) at the ConwayLife.com forums
  18. Adam P. Goucher. Re: apgsearch v4.0 (discussion thread) at the ConwayLife.com forums
  19. "Census results for B3/S23/"Saka_Test"". Catagolue. Retrieved on December 21, 2016.
  20. Adam P. Goucher. Re: apgsearch v4.0 (discussion thread) at the ConwayLife.com forums
  21. thunk (November 12, 2016). "Re: Soup search results". ConwayLife.com forums. Retrieved on November 12, 2016.
  22. Re: Extending apgcodes to larger patterns (discussion thread) at the ConwayLife.com forums
  23. Re: Hacking apgsearch (discussion thread) at the ConwayLife.com forums
  24. Adam P. Goucher (January 29, 2017). "Re: Catagolue Oddities". ConwayLife.com forums. Retrieved on January 29, 2017.
  25. Adam P. Goucher (June 30, 2016). "Re: B3/S12-ae34ceit". ConwayLife.com forums. Retrieved on July 5, 2016.
  26. Bag Sinhwan (박신환) (November 28, 2016). "Re: Soup search results". ConwayLife.com forums. Retrieved on November 28, 2016.

External links

Results

Client software

Server software

Unofficial browser extension

Unofficial Twitter bot

  • Twitter bot (discussion thread) at the ConwayLife.com forums