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, the result being e.g. 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 neigborhood 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.

Here we can observe that in the next generation, a new line of three cells at the boundary must again be born. In other words: a TI engine is capable of regenerating itself, provided that the conditions can be re-met.

Maintaining condition #1

For the five cells marked ‹…› in the first generation of the diagram above, certain restrictions can be derived. 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).

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, only the cells marked 4 can have been alive; the empty cell between them and the I is

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
2. Tʹ
3. R-pentomino
4. Century (C)
5. +-pentomino (+)
6. +ʹ
7. Generation 2 of the prepond
8. The C-heptomino (Bʺ)
9. Rʹ
10. The A-hexomino
11. The B-heptomino (B)
12. Pʹ
13. The bullet heptomino
14. R+
15. Tʺ
16. Bʹ
17. +ʺ
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. Hence any c/2 ship or puffer based on the engine must exclusively make use of these phase subtypes. It can be furthermore quite simply proven that for c/2 ships, the TI engine will also be a generator of the ship.

The first four 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 __ subtypes.

	B	Bʹ	Bʺ	C	H-	Φ-	others
B
Bʹ
Bʺ
C
H-
Φ-

The c/3 compatible subtypes are the ones for which at least some secondary subtypes give birth to a new TI engine in three generations. This necessarily excludes the previous six. Any period-3 c/3 ship containing the engine must exclusively make use of these 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).

T
Tʹ
R
+	√
+ʹ	X
P
Rʹ
A
Pʹ
U
R+
Tʺ	√
+ʺ

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