Site Info

Authors
  • H.Koenig
  • Adam Goucher
  • Dave Greene

« February 2011 | Main | May 2011 »

2011 March 26

Engineered Objects
Turing machine update

Paul Rendell has now completed his Universal Turing Machine, by adjoining two stack constructors to the bounded version of the pattern. The patterns are available here, including the c/2 orthogonal and c/5 diagonal variants of the pattern.

The new Turing machine emulator is period-23040, which makes it more HashLife-amenable than the previous UTM and TM emulators (p18960 and p11040, respectively). Additionally, the diagonal stacks run faster in Golly than the oblique analogues. The c/2 version outperforms the c/5 version, apparently, despite having a larger growth coefficient.

This is the first universal computer in Life to emulate a Turing machine in linear time (Chapman's URM takes exponential time; my UCC takes quadratic time), and therefore the most efficient to date.

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.