Difference between revisions of "Polyomino"
(Added info for hexominos) |
(listing all outcomes of the 108 heptominoes) |
||
(15 intermediate revisions by 9 users not shown) | |||
Line 8: | Line 8: | ||
===Haplominoes=== | ===Haplominoes=== | ||
There is only one '''haplomino''' (also called monomino or dot) and by itself it dies after one [[generation]]. Several objects, such as the middleweight spaceship, produce dot [[spark]]s. | There is only one '''haplomino''' (also called '''monomino''' or '''dot''') and by itself it dies after one [[generation]]. Several objects, such as the [[middleweight spaceship]], produce dot [[spark]]s. | ||
===Dominoes=== | ===Dominoes=== | ||
There is also only one '''domino''' and by itself it too dies after one generation. A number of objects, such as the heavyweight spaceship and the pentadecathlon, produce domino sparks. | There is also only one '''domino''' and by itself it too dies after one generation. A number of objects, such as the [[heavyweight spaceship]] and the [[pentadecathlon]], produce domino sparks. | ||
Based upon that instant dying property of the domino, [[Squaredance]] is a low density dominos [[agar]] and [[phoenix]]. | Based upon that instant dying property of the domino, [[Squaredance]] is a low density dominos [[agar]] and [[phoenix]]. | ||
Line 24: | Line 24: | ||
===Pentominoes=== | ===Pentominoes=== | ||
There are 12 distinct '''pentominoes'''. [[ | There are 12 distinct '''pentominoes'''. [[John Conway]] assigned them all letters in the range O to Z, loosely based on their shapes, and they are all shown below in order. | ||
Unlike triominoes and tetrominoes, it has been proven that none of the pentominoes can work as [[induction coil]]s. | |||
{| style="margin-left: auto; margin-right: auto" | {| style="margin-left: auto; margin-right: auto" | ||
Line 57: | Line 58: | ||
===Hexominoes=== | ===Hexominoes=== | ||
There are 35 distinct '''hexominoes''', the majority of which behave | There are 35 distinct '''hexominoes''', the majority of which behave uninterestingly. The most interesting and well-known examples are [[century]], [[stairstep hexomino]], [[table]], [[toad]] and [[Z-hexomino]]. | ||
[[Image:Hexominoes.png|frame|center|The 35 distinct hexominoes.<br />'''Download [[RLE]]:''' [http://www.conwaylife.com/patterns/hexominoes.rle click here] ]] | [[Image:Hexominoes.png|frame|center|The 35 distinct hexominoes.<br />'''Download [[RLE]]:''' [http://www.conwaylife.com/patterns/hexominoes.rle click here] ]] | ||
* The 1st hexomino dies in generation 12. | * The 1st hexomino dies in generation 12. It is hassled in the oscillator [[worker bee]]. | ||
* The 2nd hexomino | * The 2nd hexomino stabilizes into two blinkers at generation 40. | ||
* The 3rd hexomino evolves into a [[block]] in generation 4. | * The 3rd hexomino evolves into a [[block]] in generation 4. | ||
* The 4th hexomino evolves into a [[traffic light]] in generation 9. | * The 4th hexomino evolves into a [[traffic light]] in generation 9. | ||
* The 5th hexomino dies in generation 4. | * The 5th hexomino dies in generation 4. | ||
* The 6th hexomino evolves into a block in generation 4. | * The 6th hexomino evolves into a block in generation 4. | ||
* The 7th hexomino is a [[grandparent]] of the [[boat]] | * The 7th hexomino is a [[grandparent]] of the [[boat]]. | ||
* The 8th hexomino evolves into a block in generation 4. | * The 8th hexomino evolves into a block in generation 4. | ||
* The 9th hexomino is the [[table]]. | * The 9th hexomino is the [[table]], which becomes a line of six in 3 generations and therefore dies in generation 15. | ||
* The 10th hexomino dies in generation 45. | * The 10th hexomino is the [[Z-hexomino]], which dies in generation 45. | ||
* The 11th hexomino dies in generation 5. | * The 11th hexomino dies in generation 5. | ||
* The 12th hexomino dies in generation 7. | * The 12th hexomino dies in generation 7. | ||
* The 13th hexomino | * The 13th hexomino converges to the same evolutionary sequence as the [[pi-heptomino]] and stabilizes at generation 176, leaving behind 6 blocks, 5 blinkers, and two [[pond]]s. | ||
* The 14th hexomino dies in generation 5. | * The 14th hexomino dies in generation 5. | ||
* The 15th hexomino evolves into a block in generation 3. | * The 15th hexomino evolves into a block in generation 3. | ||
* The 16th hexomino is a | * The 16th hexomino is a parent of the [[aircraft carrier]]. | ||
* The 17th hexomino dies in generation 5. | * The 17th hexomino dies in generation 5. | ||
* The 18th hexomino | * The 18th hexomino is a parent of the [[stairstep hexomino]]. | ||
* The 19th hexomino | * The 19th hexomino converges to the same evolutionary sequence as the stairstep hexomino. | ||
* The 20th hexomino | * The 20th hexomino also converges to the same evolutionary sequence as the stairstep hexomino. | ||
* The 21st hexomino is the | * The 21st hexomino is the period-2 oscillator [[toad]]. | ||
* The 22nd hexomino evolves into a boat in generation 4. | * The 22nd hexomino evolves into a boat in generation 4. | ||
* The 23rd hexomino dies in generation 6. | * The 23rd hexomino dies in generation 6. | ||
* The 24th hexomino | * The 24th hexomino is the century and stabilizes at generation 103, leaving behind 3 blocks and a blinker. | ||
* The 25th hexomino dies in generation 6. | * The 25th hexomino is the [[ghost Herschel]] and dies in generation 6. | ||
* The 26th | * The 26th hexomino is the generation 1 of an R-pentomino and stabilizes at generation 1,102, leaving behind 8 blocks, 4 blinkers, 4 beehives, two boats, a ship, and a loaf and having created six escaping gliders. | ||
* The 27th hexomino is a parent of the loaf. | * The 27th hexomino is a parent of the loaf. | ||
* The 28th hexomino dies in generation 4. | * The 28th hexomino dies in generation 4. | ||
* The 29th hexomino is a parent of the beehive. | * The 29th hexomino is a parent of the beehive. | ||
* The 30th hexomino dies in generation 4 | * The 30th hexomino dies in generation 4 | ||
* The 31st hexomino is a great grandparent | * The 31st hexomino is a great grandparent of the pond. | ||
* The 32nd | * The 32nd hexomino dies in generation 3. | ||
* The 33rd hexomino dies in generation 9. | * The 33rd hexomino dies in generation 9. | ||
* The 34th hexomino is a parent of the [[pi heptomino]] | * The 34th hexomino is a parent of the [[pi-heptomino]]. | ||
* The 35th hexomino is the stairstep hexomino | * The 35th hexomino is the stairstep hexomino and lasts 63 generations, leaving a [[blockade]]. | ||
===Heptominoes=== | ===Heptominoes=== | ||
There are 108 distinct '''heptominoes'''. Those with names in common use are the [[B-heptomino]], the [[bullet heptomino]], the [[C-heptomino]], the [[E-heptomino]], the [[F-heptomino]], the [[Herschel]] and the [[pi-heptomino]]. | There are 108 distinct '''heptominoes'''. Those with names in common use are the [[B-heptomino]], the [[bullet heptomino]], the [[C-heptomino]], the [[E-heptomino]], the [[F-heptomino]], the [[I-heptomino]], the [[Herschel]] and the [[pi-heptomino]]. | ||
Of the 108 heptominoes: | |||
* 26 die completely. | |||
* 16 become [[beehive]]s. | |||
* 10 become [[block]]s. | |||
* 10 become [[honey farm]]s. | |||
* 6 become [[loaf|loaves]]. | |||
* 6 follow the [[pi-heptomino]] sequence. | |||
* 5 become [[traffic light]]s. | |||
* 4 become [[lumps of muck]]. | |||
* 3 become [[blinker]]s. | |||
* 3 follow the [[butterfly]] sequence. | |||
* 3 become [[glider]]s. | |||
* 1 becomes a [[boat]]. | |||
* 1 follows the [[century]] sequence. | |||
* 1 becomes a [[pulsar]]. | |||
* 1 becomes an [[R-pentomino]]. | |||
* 2 become two blocks: one with spacing (4,1) and another with offset (5,0). | |||
* 1 becomes two blinkers. | |||
* 1 becomes two loaves. | |||
* 1 becomes 2 traffic lights plus 2 blocks. | |||
The remaining 7 have their own names due to being common methuselah sequences: the B, C, E, F, [[H-heptomino|H]], and I heptominoes and the Herschel. | |||
===Octominoes=== | ===Octominoes=== | ||
There are 369 distinct '''octominoes'''. Despite the abundance of octominoes, the following fairly common octomino (which evolves into a different octomino after two generations), which stabilizes after 386 generations into two [[traffic light]]s and four [[beehive]]s, is often referred to as simply ''the'' octomino: | There are 369 distinct '''octominoes'''. Despite the abundance of octominoes, [[two-glider octomino|the following fairly common octomino]] (which evolves into a different octomino after two generations), which stabilizes after 386 generations into two [[traffic light]]s and four [[beehive]]s, is often referred to as simply ''the'' octomino: | ||
[[Image:Octomino.png|framed|center|The octomino and its two-generation successor.]] | [[Image:Octomino.png|framed|center|The octomino and its two-generation successor.]] | ||
This leaves a [[toad]] at gen 21, but it does not survive after gen 153. | |||
==Switch | ==Switch engine== | ||
[[Charles Corderman]] discovered the [[switch engine]] by running an exhaustive computer search on all decominoes. The machine that discovered the | [[Charles Corderman]] discovered the [[switch engine]] by running an exhaustive computer search on all decominoes and lower polyominos. The machine that discovered the nonomino seed was unique, possessing an unusual architecture. | ||
==Nomenclature== | ==Nomenclature== | ||
The name is a back-formation from 'domino', which explicitly refers to a pair of orthogonally connected live cells. According to the Life Lexicon, the pluralised name can be spelt two different ways: 'polyominos' and 'polyominoes' are both equally acceptable. The same applies to the systematic names of each of the polyomino sizes. | The name is a back-formation from 'domino', which explicitly refers to a pair of orthogonally connected live cells. According to the Life Lexicon, the pluralised name can be spelt two different ways: 'polyominos' and 'polyominoes' are both equally acceptable. The same applies to the systematic names of each of the polyomino sizes. | ||
Line 114: | Line 138: | ||
==External links== | ==External links== | ||
{{LinkLexicon|lex_p.htm#polyomino}} | {{LinkLexicon|lex_p.htm#polyomino}} | ||
{{LinkForumThread|f=12|t=3978|title=Polyominoes beyond CA}} |
Revision as of 13:41, 24 April 2021
A polyomino (or simply omino) is a finite collection of orthogonally connected cells. The mathematical study of polyominoes was initiated by Solomon Golomb in 1953. Conway's early investigations of Life and other cellular automata involved tracking the histories of small polyominoes, this being a reasonable way to ascertain the typical behaviour of different cellular automata when the patterns had to be evolved by hand rather than by computer. Polyominoes have no special significance in Life, but their extensive study during the early years lead to a number of important discoveries and has influenced the terminology of Life.
During the course of its evolution a polyomino could regain its original form, thereby constituting one phase of an oscillator, as seen in the (infinite) cross family. The only other known examples are the block (which has period 1), the blinker, the toad, the star and (in two different phases) the pentadecathlon. Were a recurring polyomino displaced, it would be participating in a spaceship, though the only known examples are the lightweight spaceship, the middleweight spaceship, and the heavyweight spaceship. Of course, its evolution could follow other trajectories, possibly very long lived.
Sizes of polyominoes
Polyominoes of with n cells for n = 1, 2, 3, 4, ... are called haplominoes, dominoes, triominoes, tetrominoes, pentominoes, hexominoes, heptominoes, octominoes, and n-ominoes in general. The number of distinct polyominoes with n cells for n = 1, 2, 3, ... is given by the sequence 1, 1, 2, 5, 12, 35, 108, 369, 1285, ... (Sloane's A000105).
Haplominoes
There is only one haplomino (also called monomino or dot) and by itself it dies after one generation. Several objects, such as the middleweight spaceship, produce dot sparks.
Dominoes
There is also only one domino and by itself it too dies after one generation. A number of objects, such as the heavyweight spaceship and the pentadecathlon, produce domino sparks.
Based upon that instant dying property of the domino, Squaredance is a low density dominos agar and phoenix.
Triominoes
There are exactly two distinct triominoes. The term is rarely used in Life, because the two objects in question are simply the blinker and the pre-block.
Tetrominoes
There are five distinct tetrominoes, each of which is shown below. The first is the block, the second is the T-tetromino, and the remaining three rapidly evolve into beehives. The fourth is commonly referred to as a tail and is often attached to small still lifes.
Pentominoes
There are 12 distinct pentominoes. John Conway assigned them all letters in the range O to Z, loosely based on their shapes, and they are all shown below in order. Unlike triominoes and tetrominoes, it has been proven that none of the pentominoes can work as induction coils.
- The O-pentomino is a traffic light predecessor, though not one of the more common ones.
- The P-pentomino is a common spark that dies in generation 4.
- The Q-pentomino is a traffic light predecessor.
- The R-pentomino is a methuselah and by far the most well-known pentomino.
- The S-pentomino dies in generation 5.
- The T-pentomino is a common parent of the T-tetromino.
- The U-pentomino dies in generation 4.
- The V-pentomino evolves into a loaf in generation 3.
- The W-pentomino is a common loaf grandparent.
- The X-pentomino is a traffic light predecessor.
- The Y-pentomino dies in generation 3.
- The Z-pentomino dies in generation 3.
Hexominoes
There are 35 distinct hexominoes, the majority of which behave uninterestingly. The most interesting and well-known examples are century, stairstep hexomino, table, toad and Z-hexomino.
- The 1st hexomino dies in generation 12. It is hassled in the oscillator worker bee.
- The 2nd hexomino stabilizes into two blinkers at generation 40.
- The 3rd hexomino evolves into a block in generation 4.
- The 4th hexomino evolves into a traffic light in generation 9.
- The 5th hexomino dies in generation 4.
- The 6th hexomino evolves into a block in generation 4.
- The 7th hexomino is a grandparent of the boat.
- The 8th hexomino evolves into a block in generation 4.
- The 9th hexomino is the table, which becomes a line of six in 3 generations and therefore dies in generation 15.
- The 10th hexomino is the Z-hexomino, which dies in generation 45.
- The 11th hexomino dies in generation 5.
- The 12th hexomino dies in generation 7.
- The 13th hexomino converges to the same evolutionary sequence as the pi-heptomino and stabilizes at generation 176, leaving behind 6 blocks, 5 blinkers, and two ponds.
- The 14th hexomino dies in generation 5.
- The 15th hexomino evolves into a block in generation 3.
- The 16th hexomino is a parent of the aircraft carrier.
- The 17th hexomino dies in generation 5.
- The 18th hexomino is a parent of the stairstep hexomino.
- The 19th hexomino converges to the same evolutionary sequence as the stairstep hexomino.
- The 20th hexomino also converges to the same evolutionary sequence as the stairstep hexomino.
- The 21st hexomino is the period-2 oscillator toad.
- The 22nd hexomino evolves into a boat in generation 4.
- The 23rd hexomino dies in generation 6.
- The 24th hexomino is the century and stabilizes at generation 103, leaving behind 3 blocks and a blinker.
- The 25th hexomino is the ghost Herschel and dies in generation 6.
- The 26th hexomino is the generation 1 of an R-pentomino and stabilizes at generation 1,102, leaving behind 8 blocks, 4 blinkers, 4 beehives, two boats, a ship, and a loaf and having created six escaping gliders.
- The 27th hexomino is a parent of the loaf.
- The 28th hexomino dies in generation 4.
- The 29th hexomino is a parent of the beehive.
- The 30th hexomino dies in generation 4
- The 31st hexomino is a great grandparent of the pond.
- The 32nd hexomino dies in generation 3.
- The 33rd hexomino dies in generation 9.
- The 34th hexomino is a parent of the pi-heptomino.
- The 35th hexomino is the stairstep hexomino and lasts 63 generations, leaving a blockade.
Heptominoes
There are 108 distinct heptominoes. Those with names in common use are the B-heptomino, the bullet heptomino, the C-heptomino, the E-heptomino, the F-heptomino, the I-heptomino, the Herschel and the pi-heptomino.
Of the 108 heptominoes:
- 26 die completely.
- 16 become beehives.
- 10 become blocks.
- 10 become honey farms.
- 6 become loaves.
- 6 follow the pi-heptomino sequence.
- 5 become traffic lights.
- 4 become lumps of muck.
- 3 become blinkers.
- 3 follow the butterfly sequence.
- 3 become gliders.
- 1 becomes a boat.
- 1 follows the century sequence.
- 1 becomes a pulsar.
- 1 becomes an R-pentomino.
- 2 become two blocks: one with spacing (4,1) and another with offset (5,0).
- 1 becomes two blinkers.
- 1 becomes two loaves.
- 1 becomes 2 traffic lights plus 2 blocks.
The remaining 7 have their own names due to being common methuselah sequences: the B, C, E, F, H, and I heptominoes and the Herschel.
Octominoes
There are 369 distinct octominoes. Despite the abundance of octominoes, the following fairly common octomino (which evolves into a different octomino after two generations), which stabilizes after 386 generations into two traffic lights and four beehives, is often referred to as simply the octomino:
This leaves a toad at gen 21, but it does not survive after gen 153.
Switch engine
Charles Corderman discovered the switch engine by running an exhaustive computer search on all decominoes and lower polyominos. The machine that discovered the nonomino seed was unique, possessing an unusual architecture.
Nomenclature
The name is a back-formation from 'domino', which explicitly refers to a pair of orthogonally connected live cells. According to the Life Lexicon, the pluralised name can be spelt two different ways: 'polyominos' and 'polyominoes' are both equally acceptable. The same applies to the systematic names of each of the polyomino sizes.
See also
External links
- Polyomino at the Life Lexicon
- Polyominoes beyond CA (discussion thread) at the ConwayLife.com forums