Site Info

Authors
  • H.Koenig
  • Adam Goucher
  • Dave Greene

« 2010^2 | Main | Turing machine update »

2011 March 09

Breeders
These are not just breeders

image
Exploded diagram of Paul's SSS breeder.

To celebrate Paul Tooke's 50th birthday, this article is dedicated to one of his recent discoveries. Happy birthday, Paul!

Paul has recently been assembling patterns to defy common intuition about breeders, and thus help to determine a valid definition for what constitutes a breeder.

He has used the principles behind Gemini -- glider loops and universal construction -- to build unusual breeders with obscure properties. For example, he has engineered a SSS breeder, which amounts to a slide puffer (slide gun with stationary output) constructing more slide puffers. Moreover, he has designed it to have O(t^1.5) growth, rather than the O(n^2) typical of most breeders.

Paul's breeders, including a related SMS breeder, are available on the relevant forum thread. Rather than using the original Gemini construction arm, he has used an alternative construction arm known as the 'Pianola'. In the SMS version, this lays down block-laying switch engines; in the SSS version, this produces slide puffers instead.

Bounded-population objects fall into two categories: moving and stationary (henceforth abbreviated to M and S, respectively). Linear-growth objects can be categorised according to the bounded-population and linear-population components. For example, a blinker puffer is considered to be 'MS', as it has a moving part, which periodically produces stationary blinkers. A rake is considered to be 'MM', for obvious reasons; and a gun, 'SM'.

Breeders can then be classified as MMM, MMS, MSM, or SMM, by extending the above classification scheme. MMM refers to rake puffers, MMS to puffer puffers, MSM to gun puffers, and SMM to rake guns. This has been the standard classification scheme for breeders, and applies to most breeders, including spacefillers. However, it breaks down when attempting to classify slide-breeder (available in the Golly patterns folder), which is SSM.

Also, certain linear-growth patterns cannot be classified using the original system. The glider-producing switch engine emits both gliders and stationary objects, so is both MM and MS. A possible extension, capable of supporting these hybrid puffers, is 'M(S&M)'. Obviously, it could also be called 'M(M&S)', as '&' is commutative. In this scheme, slide-breeder becomes (S&M)(M&SM). The initial 'S' refers to the stationary arrangement of shotguns; the first 'M' represents the mobile beehives; the next 'M' indicates the *WSSes; the final 'SM' denotes the Gosper glider guns.