Who proved the universality of the GoL ?

For general discussion about Conway's Game of Life.
Post Reply
Maqnine
Posts: 2
Joined: May 2nd, 2021, 8:14 am

Who proved the universality of the GoL ?

Post by Maqnine » May 2nd, 2021, 9:25 am

Hello everyone,

I am writing an article from the French online magazine Interstices : https://interstices.info/
I would like to know who proved that the Game of Life is Turing-universal.

Until recently I thought that the proof was first published in Winning ways, vol. 4 by Berlekamp, Conway & Guy ; then I discovered an article by Robert Wainwright which dates back to 1974 : "Life is universal!", see : https://dl.acm.org/doi/10.1145/800290.811303

It is probably difficult to tell who made the proof since it is a collective effort but any clarification about this point would be welcome!

cheers

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Who proved the universality of the GoL ?

Post by dvgrn » May 2nd, 2021, 12:27 pm

Maqnine wrote:
May 2nd, 2021, 9:25 am
Hello everyone,

I am writing an article from the French online magazine Interstices : https://interstices.info/
I would like to know who proved that the Game of Life is Turing-universal.

Until recently I thought that the proof was first published in Winning ways, vol. 4 by Berlekamp, Conway & Guy ; then I discovered an article by Robert Wainwright which dates back to 1974 : "Life is universal!", see : https://dl.acm.org/doi/10.1145/800290.811303

It is probably difficult to tell who made the proof since it is a collective effort but any clarification about this point would be welcome!

cheers
Yes, this is a somewhat difficult question. Both John Conway's group and Bill Gosper's group were able to conclusively demonstrate the universality of the Conway's Life rule in the early 1970s -- sometime in 1971, even, by all accounts (see below). Did they produce complete proofs? Maybe they did -- but if so, those proofs were never published.

The 1974 paper by Bob Wainwright that you mention had similar limitations. For example, at one point it says
In 1974, Robert Wainwright wrote:From here on, it is just a matter of engineering to construct an arbitrarily powerful (albeit slow) computer. Our engineer has been given the tools - let him finish the job!
...
It is known that both eaters and guns can be constructed by crashing suitable patterns of gliders. Using this fact, and also some additional information about the directions in which these gliders travel, we can now show that it is possible to build a computer simply by crashing some enormously large initial pattern of gliders. Moreover, we can design a computer whose sole aim in life is to 'throw' just such a pattern of gliders into the air. In this way, one computer can give birth to another, which can be if we like an exact copy of the first.
There are some technical difficulties with this argument. There are no insurmountable difficulties -- but (as far as I can see) they might have turned out to be insurmountable -- and therefore the "Life is Universal" paper can't be considered to be a complete proof, any more than the surviving descriptions of Conway's and Gosper's proofs.

With the methods outlined in the "Life is universal!" article, it's certainly possible to place one glider, traveling in any direction, at any chosen point in the Life plane. But those mechanisms were not necessarily sufficient to precisely synchronize the huge number of gliders that would have had to be placed simultaneously, to construct a computer that could then re-construct that exact same huge set of synchronized gliders. In particular, if you tried to complete this project as the article outlines, some gliders' initial positions would have been quite close to each other, and no explicit mechanism was provided that would have worked to create those very closely packed groups of gliders at very far-away locations.

In one sense that's "just an engineering problem" -- but not all engineering problems turn out to be solvable!

In the decades since then, that engineering problem has in fact been solved... but those solutions have been used to create working universal Life computers and self-replicating patterns, rather than to complete any formal published proofs! We still could not come close to building a self-replicator or universal-constructor spaceship using any of the blueprints from the early proofs -- those methods turned out to be much too inefficient to be usable in practice.

A Relevant Conversation from 1999
I'm going to venture to reproduce here an excerpt from a long email by Nick Gotts on this issue. The full email was much longer. It pointed out among other things that the discussion of Life universality in _Winning Ways_ and _Recursive Universe_ (William Poundstone's book) were also not really complete proofs -- there were significant gaps at various points.
On 14 April 1999, Nick Gotts wrote: ...
Published proofs and arguments
==============================

The most complete published proof of Life's computational
universality, so far as I know, is in `Winning Ways' (Berlekamp,
Conway and Guy 1982). I think there are a couple of points where this
could do with a bit more detail (see below), but the main question
with regard to this proof is how far it could be simplified using
discoveries made since its publication. However, the `Winning Ways'
argument for self-replicating (and self-transporting) universal
computers (p.848) is sketchy:

`Eaters and guns can be made by crashing suitable fleets of gliders,
so it's possible to build a computer simply by crashing some
enormously large initial patterns of gliders. Moreover, we can design
a computer whose sole aim in Life is to throw just such a pattern of
gliders into the air. In this way, one computer can give birth to
another, which can, if we like, be an exact copy of the
first. Alternatively, we could arrange that the first computer
eliminates itself after giving birth; then we would regard the second
as a reincarnation of the first.'

`The Recursive Universe' (Poundstone 1985) includes a rehash of the
computational universality proof in `Winning Ways', followed by an
outline of `A Life Universal Constructor'. Poundstone says (p.213 in
the OUP edition):

`The second part of Conway's proof shows how to construct any Life
pattern that can result from a glider collision.'

The methods Poundstone then describes (as I noted in a 19 October 1998
message to the list), are not shown to be sufficient to achieve this
(and I note that no such claim is made in `Winning Ways', nor is it
necessary to prove that `any Life pattern that can result from a
glider collision' can be constructed in order to show that
self-replicating and self-transporting universal computers
exist). However, as I'll argue below, there are significant gaps in
the argument Poundstone presents. Presumably (but please correct me if
I'm wrong, anyone who knows), some form of the argument came from
Conway via Bob Wainwright, who is named as having provided computer
consultation to Poundstone).


Information From Martin Gardner's Writings
==========================================

The third of the Game of Life chapters in Gardner (1983) (the first
two are derived from articles in the October 1970 and February 1971
Scientific Americans but the third contains more recent material)
contains the following (Ch.22, pp.252-254):

`In 1981, in a letter telling me he had found `Life' to be universal,
Conway added a note on the back of the envelope: "If (ask Gosper)
gliders can crash to form a pentadecathlon, then I can produce
self-replicating machines, and it's undecidable whether a given
machine is self-replicating."

I cannot remember if I asked Gosper this question, but at any rate,
gliders *can* crash to form pentadecathlons, and Conway states flatly,
in Winning Ways, that self-replicating machines can be constructed in
"Life" space... if Conway is right (his proof has not been published),
it is possible to build them. Conway also asserts in winning Ways that
he has proved that "Life" patterns exist which move steadily in any
desired direction, recovering their initial forms after a fixed number
of moves.'

Perhaps the most interesting point here is the mention of
pentadecathlons. I can see that they might be useful in constructing a
proof, but not why the issue might hang on their
glider-constructability. I suspect Gardner's date of 1981 for the
letter should read 1971, particularly as he also states (p.250) that
Conway and Bill Gosper `independently "universalised" the "Life" space
by showing how gliders could be used as pulses to simulate a Turing
machine.', and that he reported this information in Scientific
American of March 1971.


Information From `Lifeline'
===========================

There are a few useful and/or historically interesting references in
`Lifeline'. In Lifeline 3 September 1971), p.5, we have:

`More significantly, several basic puffer trains... have been
discovered, including two that create gliders!! These discoveries made
by the group at the Artificial Intelligence Laboratory at
M.I.T. (R. William Gosper, Jr., Rici Liknaitzky, Bill Mann and Michael
Speciner) have significance in the theory of turing machines and
universal constructors which will be discussed in the later part of
this newsletter.'

No such discussion follows, except that on p.32, we have:

`Conway mentioned that universality implied the existence of a finite
arrangment which emits an infinite glider stream representing all the
digits of pi.'

This statment appears without prior context -- we're not told when of
where Conway mentioned this. Did something possibly get left out of
this issue of Lifeline (or even out of my copy!)?

In Lifeline 10 (June 1973) p.6, there is a letter from Doug Petrie
beginning:

`By now ways are known to form from glider collisions almost all of
the "significant" objects or patterns, including eaters,
pentadecathlons, both major types of shuttle, the three basic
orthogonal spaceships, both glider guns, and two of the three types of
puffer train... "Significant" in this case refers to all objects which
might prove essential to such large-scale constructions as...
glider logic circuitry, or a pattern capable of self-replication.'

In Lifeline 11 (September 1973), there is `An Introduction To
Glider Logic' by V. Everett Boyer (Boyer 1973), `with counsel from Doug
Petrie and
J.H. Conway'. Among the interesting points from this article are:

* A list of those right-angled two-glider collisions `simple enough to
be good for glider logic' along with a naming scheme for these
collisions. The most useful are said to be the `kickback reaction',
the `vanish reactions' (only 10 are listed -- there are actually 11,
but one takes a long time), and three `ternary reactions', in which
the result of the collision will mutually annihilate with another
glider approaching along the path of either of the first two.

* Methods of turning a glider stream through 90 degrees without
complementing it are suggested (using a junkie or twin bee). The
`Winning Ways' proof does not use these.

* `Special effort is also required to make streams arrive at just the
right time. Inserting pairs of NOT gates preserves the information,
and the number of vanish reactions (4+, 11+, 5-, 6-, 7-, 8- for P-30
logic) provides the freedom to reposition and time information
exactly.'

* `The final problem is of copying information, and Conway and
M.I.T. were greatly troubled, as is seen by Conway's 12-gun solution,
which would copy P-240 data. The problem is better answered with
ternary reactions; branching a P-60 stream takes only a P-30 gun and
twogun.' Again, this approach is not used in the `Winning Ways' proof.
...
John Conway responded to Nick Gotts' email on the same day:
On 14 April 1999, John Conway wrote: 149 From: John Conway
Date: Wed Apr 14, 1999 3:54pm
Subject: Re: Self-reproducing universal computers in Life (long)


On Wed, 14 Apr 1999, Nick Gotts wrote a long letter, from which I extract:

> I am seeking the most detailed proofs in existence that the Game of
> life is computationally universal, and, furthermore, supports
> self-replicating universal computers, and spaceships travelling in any
> rational direction.

> However, doing so would have required me
> to rely on the arguments in `Winning Ways' and `The Recursive
> Universe', and once I looked closely at them, I found I could not
> readily convince myself they were sound.

I think I should explain that the relevant chapter of Winning Ways
was written long after the universality proofs were found, and when I
no longer had any record of them, except in my head. What that chapter
contains is therefore a description of the main outlines of the proof,
rather than a proof itself. "My" proof was actually the result of
a detailed and excited interaction with about half a dozen other
folk (mostly graduate students) over a short period after we were
informed of the Gosper group's discovery of the glider gun. No,
that's not quite correct, because of course we'd already searched
for and found glider-interactions that would serve as logical gates,
even before I first mentioned "Life" to Martin Gardner. So we had
a head start.

This didn't do much good, though, because when I wrote a letter to
Gardner as soon as we'd completed the proof, he wrote back to say that
Gosper et al had independently found their own universality proof. But
he was careful to say that ours preceded theirs, in case there were to
be [any] priority claims! My attitude at that time was that I couldn't
care less, because a result about a particular "game" such as this
wouldn't help my career as a pure mathematician. In fact I'd privately
vowed to myself that I wouldn't write ANYTHING about puzzles and games,
because it would interfere with writing up real mathematics, which I
find it hard enough to do anyway. I half-broke this vow by writing ONAG
(only half, because after all the surreal numbers were genuine
mathematics), but didn't feel too guilty because almost all that book
was written inside one week. Later on, I released myself from it to write
WW, because most of the work on it was done during a sabbatical leave.

> Nor, once I got the archives,
> could I find any alternative published sources. Further study has
> reduced (but not entirely eliminated) my reservations about the
> `Winning Ways' proof of computational universality,

As I said, it was only a sketch of the proof, written long after,
when I had already forgotten many of the details. Let me assure you
that the original proof was produced by half-a-dozen keen mathematicians
who were very careful to criticize any sloppiness on each other's part.
If you'd been there, you probably wouldn't have any reservations at all.

> but not those
> about the `Recursive Universe' argument for self-replicating universal
> computers.

No wonder - Poundstone wasn't there, and his words are just hearsay.
In fact when his book first appeared I was upset that some of them
weren't even hearsay - he has a habit of saying things like "Conway
thought such-and-such" that I found VERY annoying because usually
I thought no such thing, and in a few important cases, precisely
the opposite. The major case is that according to Poundstone I
"thought" populations would stay bounded (or something roughly
equivalent), which since the whole point of "life" was to find a
universal CA, was nonsense. [In my off moments I might have been
scared by the horrible possibility that populations MIGHT just
turn out to be bounded, but I certainly never thought they WOULD be,
and I can't even remember whether there were any such off moments!]

You might like to know that Poundstone wrote his book without
having consulted me at any time. He did send me a publisher's
pre-publication copy, to which I responded by a letter containing
several criticisms, but which apparently arrived too late to affect
the published version.

However, I hope I can nevertheless still your doubts as to
the existence of universal constructors. This became very clear
to us in Cambridge some time after the universality proofs, mostly
because of Buckingham's work on making objects by crashing gliders,
because we were able to design a "life computer" that could send
out an essentially arbitary pattern of gliders, and so could
construct an arbitrary other "life computer" provided that was
made of "Buckingham bits" (as everything we thought of was).
I say "essentially arbitrary" because in fact they were far from
arbitrary - the gliders had to be formed very far away from each other,
for instance. But we were careful to check that the bits we wanted
could all be built by patterns of gliders that did not contain two
gliders that closely followed each other in the same direction,
which was the essential point.

It's obvious that among the universal constructors of the type
we considered are "spaceships" that travel in directions of
arbitrary rational slopes.

I don't know what contacts Poundstone had with Gosper et al -
if he actually was one of the "al", he might know something of
their universality methods. But he sounds more like a reporter,
and reporters seldom get technical things exactly right. So
ou shouldn't have expected his account to be convincing!

John Conway
And just for completeness' sake, here's Nick's response from two days later:
On 16 April 1999, Nick Gotts wrote: 157 From: Nick Gotts
Date: Fri Apr 16, 1999 9:31am
Subject: Re: Self-reproducing universal computers in Life (long)


Mainly to John Conway,

Thanks very much for the response to my letter - which largely confirms what
I'd either drawn from the archives or guessed, but adds some interesting
information.

John Conway wrote (in part):

>
>
> However, I hope I can nevertheless still your doubts as to
> the existence of universal constructors. This became very clear
> to us in Cambridge some time after the universality proofs, mostly
> because of Buckingham's work on making objects by crashing gliders,
> because we were able to design a "life computer" that could send
> out an essentially arbitary pattern of gliders, and so could
> construct an arbitrary other "life computer" provided that was
> made of "Buckingham bits" (as everything we thought of was).
> I say "essentially arbitrary" because in fact they were far from
> arbitrary - the gliders had to be formed very far away from each other,
> for instance. But we were careful to check that the bits we wanted
> could all be built by patterns of gliders that did not contain two
> gliders that closely followed each other in the same direction,
> which was the essential point.

I didn't make sufficiently clear that I don't doubt that self-reproducing universal
computers exist in Life! Nor that a proof of their existence was produced by
you and your graduate students - but I consider Life sufficiently important
in the study of CA and emergent complexity that I'd like such a proof to be
in the public domain. So I guess I may end up attempting to produce one
myself. If so, I'll post it to the list for criticism and comment.

> It's obvious that among the universal constructors of the type
> we considered are "spaceships" that travel in directions of
> arbitrary rational slopes.

Rich Schroeppel's sketch (archive reference in my previous message) suggests
ways of achieving all speeds up to c/12 as well - but would require the use of
a Cordership.

Nick

Maqnine
Posts: 2
Joined: May 2nd, 2021, 8:14 am

Re: Who proved the universality of the GoL ?

Post by Maqnine » May 3rd, 2021, 4:17 pm

Thank you very much indeed for this clear and well-documented answer.
It seems obvious that we cannot attribute the construction of a universal machine to a single person.

What stroke me when I discovered the article by Wainwright is that it does not attribute the construction to Conway and, on the other side, in Conway's book, the article of Wainwright is not cited! (Even though the last words of Conway's chapter is "Life is universal!", which is exactly the title of Wainwright's paper...)

It also seems that we have to draw a clear line between two properties :a) the Turing-universality of the model, that is, the ability to compute any algorithm, and b) the self-replication ability (including the self-replication of a Turing machine). I have to read again the arguments exposed above but it occurred to me at first sight that the two things were more or less mixed...

Anyway, thank you again for these valuable pieces of documentation on the history of the Game of Life.

Nazim

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Who proved the universality of the GoL ?

Post by dvgrn » May 3rd, 2021, 5:40 pm

Maqnine wrote:
May 3rd, 2021, 4:17 pm
It also seems that we have to draw a clear line between two properties :a) the Turing-universality of the model, that is, the ability to compute any algorithm, and b) the self-replication ability (including the self-replication of a Turing machine). I have to read again the arguments exposed above but it occurred to me at first sight that the two things were more or less mixed...
Computational universality is both much easier to prove for Conway's Life, and much easier to define clearly, than construction universality. Back when neither a programmable universal constructor nor a programmable universal computer had been explicitly constructed in Life, both of these were somewhat theoretical concepts that seemed too large to ever lay out as a complete pattern of cells. It made sense to just combine them, with a little bit of hand-waving.

Now people have completed several different examples of both categories of Life pattern that can be run -- though very slowly in some cases -- on your average personal computer. It seems generally true that it's a lot easier to demonstrate universal computation (i.e., Turing-completeness) in a CA rule, than universal construction. Many rules, such as WireWorld for example, clearly have everything needed for universal computation, but have no hope of ever supporting universal construction.

Even when universal construction seems to be within reach, it often seems just as easy to prove it by example -- actually build a self-replicating pattern -- as to create a non-constructive formal proof of universal construction. It's easy for awkward logical gaps to sneak into formal proofs.

Just for example, in Conway's Life and many other rules there are untold numbers of Garden of Eden patterns -- patterns that can only exist when the universe begins at T=0, because they have no predecessors. Clearly Gardens of Eden can't be constructed, even by universal constructors... so why are we justified in using the word "universal"? ... Well, we just carefully define the term to avoid any claims about being able to construct things that are impossible to construct -- and we show that we don't need to have any Gardens of Eden in our universal-constructor designs.

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Who proved the universality of the GoL ?

Post by dvgrn » May 26th, 2021, 10:42 am

Just checked to see if an article had come out yet on this topic.

There doesn't seem to be one yet, but it appears that the same author wrote an article on cellular automata back in April 2007:

https://interstices.info/a-la-decouvert ... llulaires/

Post Reply