User:Tropylium/TI engine

Conway's Game of Life allows for a pattern to increase its bounding box in exactly one case: a series of three live cells occuring along the edge of its bounding box will give birth to a new cell outside it.

Spaceships and related patterns (puffers, wickstretchers, spacefillers – a general term is growth pattern) can, therefore, be classified according to their growth typology. It will be productive to limit the discussion in the extension of the bounding box in one direction only. I will call the bounding box's side of interest the boundary. Any phase of a pattern where three cells occur together at the boundary will inevitably lead to new cells being born beyond it in the next generation, i.e. boundary being pushed back one cell. These can be called growth events.

Sets of three cells may of course overlap: a line of four cells giving birth to two new cells outside the boundary, a line of five cells giving birth to three cells outside the boundary… or more generally, a line of n+2 cells giving birth to n cells outside the boundary, for any n ∈ ℕ. Hence we can attach a width to growth events.

This article discusses a special class of those spaceships whose growth events are exclusively of width one. These are spaceships making use of the TI engine.

Definition and motivation

If

1. all the parents of a newly born boundary-extending cell (henceforth: the bow) survive; and if
2. these have no lateral neighbors, neither after nor before a growth event

then the neighborhood of the bow will resemble a T-tetromino:

. . . . .   . . . . .
. . . . . → . . O . .
. O O O .   . O O O .
… … … … …   … … … … …

We define these instances of growth events the TI engine. A pattern that fulfills the conditions for the first generation may be called an I-phase; a pattern that fulfills the conditions for the latter generation may be called a T-phase.

The important observation is that in the next generation, a new line of three cells at the boundary must again be born; and a new growth event will therefore occur in two generations. A TI engine is even capable of regenerating itself, provided that the conditions can be re-met.

Maintaining condition #2

A TI engine will provably fulfill the first part of condition #2 in the next generation. Consider the right side of the engine (by symmetry, the same argument applies on the left):

. . . . . .   . . . . . .    . . . . . …
. . . . . . → . O . . 2 …  → O O O 1 … …
O O O . 4 4   O O O . 3 …    … … … … … …
… … … … … …   … … … … … …    … … … … … …

• In the last generation, in order for a new cell to have been born in position marked 1, it needs to have three parents in the center generation.
• In the center generation, the uppermost row in the diagram is beyond the pattern's boundary, i.e. contains no live cells. Hence we require the two cells marked 2 and 3 to have been alive.
• In the first generation, the second row is beyond the pattern's boundary. This means that cell 2 must have been born at that generation. However, since the rightmost lateral neighbor of the I is dead in the first generation, at most the two cells marked 4 can have been alive; hence there is no way for cell 2 to have been born, and none for cell 1 either. ∎

I-phase subtypes

For the five cells marked ‹…› in the first generation of the diagram above, certain restrictions can be derived from condition #1. Let us label the cells ABCBA, respectively. Then:

1. B and C cells may not be simultaneously present: this would kill the center cell of the I.
2. Both B cells may not be present, for the same reason.
3. At least one letter type must be present on both sides: otherwise the side cells of the I will die.

Hence five I-phase variants of the engine can be distinguished: AA, AB, ABA, AC, ACA (of these AB, ABA and AC are not bilaterally symmetric)

. . . . .    . . . . .    . . . . .    . . . . .    . . . . .
. O O O .    . O O O .    . O O O .    . O O O .    . O O O .
O . . . O    O . . O .    O . . O O    O . O . .    O . O . O
 type AA      type AB      type ABA     type AC      type ACA

T-phase subtypes

A TI engine in its T phase may be classified to 20 subtypes depending on the five cells in the next row (this implies 32 subtypes, but 12 of these are reflections of others):

1. Bare T-tetromino (T)
2. T-tetromino with one diagonally adjacent cell (Tʹ)
3. T-tetromino with two diagonally adjacent cells (Tʺ)
4. R-pentomino (R)
5. Century (C)
6. +-pentomino (+)
7. +-pentomino with one diagonally adjacent cell (+ʹ)
8. +-pentomino with two diangonally adjacent cells (+ʺ)
9. Generation 2 of the prepond (P)
10. The C-heptomino (Bʺ)
11. Rʹ
12. The A-hexomino
13. The B-heptomino (B)
14. Pʹ
15. The bullet heptomino (U)
16. R+
17. Bʹ
18. [untitled]
19. A common parent of the house (H-)
20. Full triangle: a grandparent of the phi spark (Φ-)

The T-phase subtype will uniquely determine whether a pattern will give birth to a new TI engine, moved one cell forward. This can be seen from the subtype of the newly born would-be I-phase, for which the previously noted restrictions apply. Only six subtypes turn out to adhere to them: B, Bʹ, Bʺ, C, H- and Φ-. The first four all give birth to an I-phase engine of type AB; the last two give birth to an I-phase engine of type AA.

These may be called the c/2 compatible subtypes. Any c/2 ship or puffer based on the engine must use these phase subtypes only. It can be furthermore quite simply proven that for c/2 ships, the TI engine will also be a generator of the ship.

The c/3 compatible subtypes are the four ones for which at least some secondary subtypes give birth to a new TI engine in three generations: these are T, Tʹ, Tʺ, +. Any period-3 c/3 orthogonal ship based on the engine must use of one of these T-phase subtypes. (This does not hold for higher periods: it is possible to imagine e.g. a 2c/6 ship whose bow first progresses two cells in four generations, then stands still for two generations).

Additionally, a 2c/5 orthogonal ship making use of the engine must alternate between c/2 compatible and c/3 compatible engine types.

Secondary subtypes

The first four c/2 compatible subtypes can be divided to 128 secondary subtypes in terms of the cells in the next farthest row of cells from the engine, and the last two (being mirror-symmetric) in 72 subtypes. The distribution of these sub-subtypes according to what subtype they generate turns out to be quite uneven:

	c/2 compatible						c/3 comptbl.				others
	B	Bʹ	Bʺ	C	H-	Φ-	T	Tʹ	Tʺ	+	+ʹ	+ʺ	R	Rʹ	A	P	Pʹ	U	R+	?
B	12 12	26	-	8	12	-	-	16	-	-	-	-	8	22	12	-	-	-	-	-
Bʹ	24 6	48	-	2	24	-	-	4	-	-	-	-	2	12	12	-	-	-	-	-
Bʺ	16 16	32	-	-	16	-	-	-	-	-	-	-	-	32	16	-	-	-	-	-
C	16 12	32	-	4	16	-	-	8	-	-	-	-	4	24	6	-	-	-	-	-
H-	-	4	-	-	-	6	-	-	7	-	-	13	-	4	-	-	12	6	8	12
Φ-	-	-	-	-	-	6	-	-	-	-	-	20	-	-	-	-	16	6	8	16

B, Bʹ, C and Φ- are capable of regenerating themselves. This is convenient, as the existence of such an engine subtype is a necessary condition for the existence of a period-2 or glide-period-2 c/2 spaceship with a single TI engine.