Cellular Automata FAQ/Archive

From LifeWiki
Jump to navigation Jump to search

Cellular Automata FAQ

Edited by Tim Tyler. Originally edited by Howard Gutowitz.

Autobiography

About this FAQ;

What is the status of the Cellular Automata FAQ?

This FAQ was originally edited by Howard Gutowitz in the mid 1990s.

It has not been updated much over the years.

It vanished from view for an extended period. This was caused by the Santa-Fe "alife" webserver - where it used to live - being taken down.

In July, 2002, Tim Tyler adopted it.

It is hoped that it will slowly be edited into a state where it is useful again.

Currently the FAQ should be regarded as being "under construction".

Much of the material presented here is out-of-date.

Many modern FAQs are not answered - and many of the questions which are answered here are no longer FAQs.

Maintaining such a FAQ is a big job - and the project may take some time. Please be patient in the interim.

Will there be a text version of the FAQ?

Probably, eventually.

However if it ever happens, it will be automatically produced from the HTML version - and consequentially may be rather lacking.

Is the original FAQ still available?

You should find the original FAQ is partially preserved here.

Why are Java applets stealing my CPU cycles?

Java has a contribution to make to the site. However, for those who don't like it, every page with a Java applet on is mirrored by another page which has no Java on at all.

Start at http://nojava.cafaq.com/ and you should not encounter any Java applets.

Will there be diagrams and applets all over the place?

That is unlikely to happen much in the short term.

Other maintenance activities on the FAQ seem to be of more pressing importance.

However, I expect such things will happen eventually.

Any Java applets will be confined to the Java version of the site.

Is this the FAQ for comp.theory.cell-automata?

It is a FAQ. Hopefully it will come to be useful to comp.theory.cell-automata residents.

Will this FAQ be posted to comp.theory.cell-automata?

That is unlikely to happen. Pointers, yes. Snippets, perhaps. The whole thing - almost certainly not.

What questions can we expect to see answered by the FAQ in the future?

General

  1. What books are available about cellular automata?
  2. Where can I read some reviews of books about cellular automata?
  3. Which people are involved with cellular automata?
  4. What hardware solutions are available for running cellular automata?
  5. What interesting open questions are there in the field?
  6. Who invented cellular automata?
  7. Who were the pioneers in the field?
  8. What happened in the early history of the field?
  9. What recent progress has been made in the field?
  10. Are cellular automata popular?
  11. Do large cellular automata necessarily run more slowly?
  12. What is "crystalline computation"?
  13. What is "the firing squad synchronisation problem"?
  14. What is "the synchronisation problem"? - and what has it got to do with fireflies?
  15. What is "the forward problem"?
  16. What is "the inverse problem"?
  17. What did Jarkko Kari prove in 1990?
  18. Is it true that cellular automata are more powerful than Turing machines?
  19. How is the term "cellular automata" defined?
  20. Are cellular automata finite? or infinite?
  21. Is "cellular automata" singular? or plural?
  22. What techniques are available for constructing reversible cellular automata?
  23. I have a reversible cellular automata? How do I find the inverse automata?
  24. What tools are available for automatic evaluation of cellular automata properties?
  25. How can you tell whether a rule will support gliders?
  26. If a rule will support gliders, how can you find them?
  27. How can you tell whether a rule is capable of universal computation?
  28. Is the question of whether a rule is capable of universal computation undecidable?
  29. How do you make a rule which can be proved to be capable of universal computation?
  30. Are cellular automata fractals? Are fractals cellular automata?
  31. What cellular automata fractals are there?
  32. How do I model <system x> with a cellular automata?
  33. What is "the speed of light"?
  34. How do you measure distance in a cellular automaton?
  35. What are the most common neighbourhoods?
  36. Are cellular automata used in image processing?
  37. Are cellular automata used cryptography?
  38. Are cellular automata used in digital circuit design?
  39. Are cellular automata used to create random numbers?
  40. Can you run cellular automata over a network?
  41. What are "asynchronous" cellular automata?
  42. What are "linear cellular automata"?
  43. What are "totalistic" cellular automata?
  44. What are "stochastic" cellular automata?
  45. What are "non-uniform" cellular automata?
  46. What are "voting rules"?
  47. What are "decay rules"?
  48. What is "Bank's computer"?
  49. What are "Ising spin systems"?
  50. What is "the speed-up theorem"?
  51. What is "computational irreducibility"?
  52. Have wave equations been simulated?
  53. What rules have been proven to be capable of universal computation?
  54. What is a "billiard ball machine?"
  55. What does "CAM" stand for?
  56. How are the 1D elementary rule numbers calculated?
  57. What does the abc/def notation mean?
  58. What does the abc/def/ghi notation mean?
  59. What cellular automata file formats are there?
  60. What is special about rule 30?
  61. What is special about rule 110?
  62. Can cellular automata be enumerated?
  63. Does anyone make money out of cellular automata?
  64. Why do people use Forth for programming cellular automata?
  65. Do cellular automata exhibit conservation laws?
  66. Do cellular automata have analogues of the second law of thermodynamics?
  67. How do I caluclate the radius of this neighbourhood?
  68. Is it true that modelling with cellular automata is like trying to create sculpture with quarks?
  69. Are cellular automata "chaotic"?
  70. Does complexity arise from simplicity in cellular automata?
  71. Why do computers run CAs so slowly?
  72. Is there a link between cellular automata and the game of go?
  73. Cellular automata were invented before computers - were they originally updated by hand?
  74. Have cellular automata been used to create art?
  75. Where are good places to study cellular automata?

Digital physics

  1. Is the universe a cellular automaton?
  2. Who is Stephen Wolfram, and what is "A New Kind Of Science"?
  3. Who is Ed Fredkin, and what is "Digital Philosophy"?

Lattice gasses

  1. Why is there no equivalent of hexagonal tiling in 3D?
  2. What can be done to make 3D gasses more isotropic?
  3. Can I discuss lattice gasses on sci.physics.computational.fluid-dynamics?

Game Of Life

  1. That Garden Of Eden is huge. How can anyone possibly know it has no precursors?
  2. I want to find a Garden Of Eden. How do I do that?
  3. Is the game of life useful? Isn't it just a toy?

Google maintains an up-to-date list of pages that link to this FAQ [here].

An old list of pages that link to this FAQ is available at here.

Generalities

Definitions - and general references on cellular automata;

What are Cellular Automata (CA)?

Contributions by: Lyman Hurd <hurd@math.gatech.edu>

Here is one physicist's view of the relevant definitions:

A cellular automaton is a discrete dynamical system. Space, time, and the states of the system are discrete. Each point in a regular spatial lattice, called a cell, can have any one of a finite number of states. The states of the cells in the lattice are updated according to a local rule. That is, the state of a cell at a given time depends only on its own state one time step previously, and the states of its nearby neighbors at the previous time step. All cells on the lattice are updated synchronously. Thus the state of the entire lattice advances in discrete time steps.

Here is one mathematician's view of the relevant definitions:

Conventions d=dimension, k=states per site, r=radius (all explained below).

For simplicity, assume d=1 for the moment.

A d-dimensional cellular automaton takes as its underlying space the lattice Sℤ (ℤ=integers, infinite in both positive and negative directions) where S is a finite set of k elements. The dynamics are determined by a global function

F: Sℤ → Sℤ. (1)

whose dynamics are determined ``locally'' as defined below.

f: S2r+1 → S. (2)

A ``local (or neighborhood) function'' f is defined on a finite region

The all-important property of cellular automata, is that this function is determined by a finite lookup table. Both the domain and range of f are finite.

The global function F arises from f by defining:

F(c)i=f(ci-r,...,ci+r) (3)

A concrete example with k=2,r=1 would take a doubly infinite string of zeroes and ones to a new string at which each site is replaced by the logical and of its two neighbors (Wolfram's elementary rule 90).

Some relevant facts from a topological standpoint are:

  1. The base space Sℤ is compact and the global function F is continuous.
    To insert an editorial comment, this makes CA an ideal meeting point between continuous dynamics and complexity theory, since they are discretely defined but exhibit continuous dynamics.
  2. The map F commutes with the shift operator which takes ci to ci+1.

In fact cellular automata are characterized completely by properties 1) and 2) (Hedlund).

The transition to more dimensions is straightforward. The only difference is that the global function F is defined over Sℤd (functions from a d-dimensional lattice to S) and the local function f is determined by enumerating the image of all patches of size (2*r+1)d.

For an introduction to CA, some of the more well-known references are:

[Wol86] [TM87] [Gut91] [Wol94]

How do I contribute bibliographic material to the FAQ?

Currently, bibliographic submissions are not being accepted.

Where are cellular automata discussed?

The Usenet newsgroup comp.theory.cell-automata is a good place for discussing cellular automata.

Archives of this group are available on Google.

Archives from before 1995 are available here.

What should I work on in CA for my Ph.D. thesis?

Contributions by:

Bruce Boghosian <bruceb@conx.bu.edu>
Stephen Wolfram <sw@wri.com>
Harold McIntosh <mcintosh@servidor.dgsca.unam.mx>

This question sparked an interesting discussion on the CA list a while back. Some, noting the difficult job market for scientists, and the ill-repute of CA in some circles, replied, "Nothing, if you want to get a job." Some more upbeat and constructive remarks follow.

Boghosian: Lest today's funding realities make us too somber and cynical, I offer some words from George Bernard Shaw:

"The reasonable man adapts himself to the world; the unreasonable man persists to adapt the world to himself. Therefore, all progress depends on the unreasonable."

I certainly agree that grad students should be well informed about their options if they elect to pursue a dissertation in a nontraditional field such as cellular automata. I would, however, strongly disagree with the allegation that nontraditional research tends to be of lower quality.

For every one "free thinker" that succeeds, there may be fifty that do not and retreat to the mainstream, but there are many examples of key advances in science that would simply never have happened if those fifty people had not been willing to stick their necks out a bit and try something new.

Wolfram:

Here is a list of questions about cellular automata that I discussed in my 1984 paper: "Twenty Problems in the Theory of Cellular Automata", published in the proceedings of the 59th Nobel Symposium, and reprinted in my book: "Cellular Automata and Complexity: Collected Papers" (Addison-Wesley, 1994):

  1. What overall classification of cellular automata can be given?
  2. What are the exact relations between entropies and Lyapunov exponents for cellular automata?
  3. What is the analog of geometry for the configuration space of a cellular automaton?
  4. What statistical quantities characterize cellular automaton behavior?
  5. What invariants are there in cellular automaton evolution?
  6. How does thermodynamics apply to cellular automata?
  7. How is different behavior distributed in the space of cellular automaton rules?
  8. What are the scaling properties of cellular automata?
  9. What is the correspondence between cellular automata and continuous systems?
  10. What is the correspondence between cellular automata and stochastic systems?
  11. How are cellular automata affected by noise and other imperfections?
  12. Is regular language complexity generically non-decreasing with time in one-dimensional cellular automata?
  13. What limit sets can cellular automata produce?
  14. What are the connections between the computational and statistical characteristics of cellular automata?
  15. How random are the sequences generated by cellular automata?
  16. How common are computational universality and undecidability in cellular automata?
  17. What is the nature of the infinite size limit for cellular automata?
  18. How common is computational irreducibility in cellular automata?
  19. How common are computationally intractable problems about cellular automata?
  20. What higher-level descriptions of information processing in cellular automata can be given?

Most of these questions have now received at least some attention, but still none can really be considered solved. My own research over the past several years would lead to me to formulate slightly different questions, but I think the ones above are nevertheless a useful starting point.

And if anyone manages to come up with a definitive solution to any of these questions, I can say that I at least will be very interested in hiring them!

- Stephen Wolfram

McIntosh: Possibly the field is less active than it used to be, something which can be judged by the volume of CA-Mail in comparison with past years. For one thing, lattice gasses have split off from cellular automata, and then the support for the kind of hydrodynamics which requires lattice gasses may have diminished. For another, the a-life group was created, carrying with it an activity which was related to cellular automata, although not strictly a part of it. And then there are neural networks, Petri nets, Lindenmayer systems, and so on. So there is much to choose from, in areas generally related to automata.

The topics which Howard Gutowitz covered in his own thesis have still not been exhausted; there was another similar thesis (published as Wilbur, Lippman, Sharma, "on the prediction of local patterns in cellular automata" in the same time frame of ten years ago), but things seem to have been left where they were back then.

To a certain extent, everyone managed to show that a sophisticated treatment was considerably harder (or at least computationally more involved) than the naive treatment. Gutowitz, Victor, and Knight also ventured to two dimensions, again finding that the problems there were harder, especially in dealing with Kolmogoroff's requirements for subdividing probabilities.

Now that time has elapsed, understanding has grown, machines are faster, and programs are better, there could be an opportunity to return to the topic - which consisted in getting good probability measures to describe automata and their evolution. How good? Studies on binary automata exist; would anything (like better statistics) be gained by working with more states? Is the Wolfram classification scheme adequate for these automata? Can we make do with mean field theory, especially by recognizing its limitations (avoid totalistic rules)?

And speaking of the avoidance of totalistic rules, is there a reason why someone should not concentrate on totalistic rules and try to derive their special characteristics? For starters, sums might be thought to obey a Gaussian distribution, but empirical evidence suggests a more nearly uniform distribution.

The (not now so recent) work of Chat� and Manneville opens up a whole new world of automata, both experimentally and theoretically. Phenomonologically they have something like semiconductors, wherein a small amount of impurities can substantially modify the overall evolution of an automaton. Someone who wanted a nice project could try to find out more about the kinds of automata exhibiting the effect, practical ways to manage the impurities, and above all try to find an adequate theory to describe them and predict their behavior.

The problem is that classical iteration theory just doesn't apply to this class of automata, but yet there is regularity to be seen at work. One loses the theorems about conservation of fixed points and counterimages of critical points, but surely there is something which could take their place for composite rather than iterated functions?

Even for classical automata like Life, there are practical and philosophical problems which could be approached by having available an adequate theory of composite functions. Questions of long term evolution - not hundreds or millions, but zillions, of generations - need an adequate theory of limits before speculations can be tested and made reliable. Will a Universal Life computer EVER evolve spontaneously, under any reasonable (or unreasonable) conditions?

This is probably way beyond the range of a Ph.D. thesis.

Even if the thesis project were not to explore new theories or new aspects of old theories, there is certainly a use for programs which will calculate answers to all the questions which can be asked about automata. This might result in a project more worthy of Computer Science than Mathematics. Of course it is true that several programs already exist; nevertheless computer technology keeps advancing, bringing with it the possibility of having better programs, or even just programs with better interactive potential. Or more widely available for different platforms (to use a buzz word).

Visual display keeps getting better and better, so effective presentation of three dimensional automata is more feasible than it used to be. Not only might this aid the seardh for three-dimensional Life, it is also the proper domain of the Chat�-Manneville automata. Not to mention carrying Belusov- Zhabotinsky reactions into three dimensions. Again this may be more of an engineering or computational thesis than one in physics or mathematics; well, the request was for topics, without specifying with which faculty or school.

A person seeking a thesis topic might do well to see what topics have proven successful in recent years, either to use them as a model or even to decide on what to avoid. Two more which come to mind were written by Lyman Hurd and Jarkko Kari, respectively. The former was concerned with the limit sets which could arise under long time evolution, mostly of one dimensional automata, and so related to the limiting evolution problem already mentioned.

The latter made a highly regarded analysis of decidability problems in two dimensions (and, by inference, beyond). This may or may not have exhausted the topic, but one thinks not.

Maybe some final words on the politics of thesis choice are in order. Obviously it would be prudent to take into account the interests of the faculty members of the Department in which one intends to write the thesis. A sympathetic advisor is evidently a considerable asset. On the other hand, it is one's own life and education which is at stake, not the professor's. There will be far fewer opportunities to study something in which one is particularly interested outside of the university environment than within it. Therefore the selection of a thesis topic ought to reflect one's own interests; it is alright to ask around for ideas or suggestions, but in the end it is the person who writes the thesis who is going to have to make the decisions as to what it will contain, what its orientation is to be and so on.

As far as the choice of a thesis topic affecting job opportunities, there is no doubt that there is going to be some correlation. Still, there is always the question of why one is studying in the first place? Is it to learn something about the world, or is it to get some preliminary job training? How many people have the opportunity (or the desire) to follow up their thesis work in later life?

Somehow, a thesis is supposed to culminate a program of graduate studies by demonstrating that its author has dominated several skills, such as making a sensible choice of level and theme, the ability to make a survey of the literature, the ability to write a scientific document with a certain minimum of literary merit, and, of course, to make an original contribution to the body of scientific knowledge.

A sensible employer will judge the degree to which these criteria have been met; offering employment in kind will probably seem less important than trying to judge whether the prospective employee is alert, intelligent, versatile, ... . If the original goal was to prepare for technical employment, there should be no conflict. Having grown fond of the thesis topic and wanting to specialize immediately in following it up, the recent graduate is likely going to have to be more aggressive and persistent. Does this come as a surprise?

See also:

Grad Student - a grad student's experiences.

What are some good general references for CA?

Contributions by:

  • Mark A Biggar <mab@dst17.wdl.loral.com>
  • John Baez <baez@guitar.ucr.edu>
  • Mark Randell <markar@psy.uwa.oz.au>
  • [TM87]
  • [FTW84]
  • [Gut91]
  • [SZ90]
  • [WL92]
  • [Ada94]

Description of Adamatzky's book

Description of Voohees' book

What is the Complex Systems Journal?

A journal devoted to the rapid publication of research on the science, mathematics, and engineering of systems with simple components but complex overall behavior.

Editor: Stephen Wolfram, Wolfram Research, Inc., and University of Illinois

What is the AMS classification for CA?

Contributions by: Mike Hurley <mgh3@po.cwru.edu>

68Q80 is Computer Science / Theory of computing / Tessellation automata, iterative arrays, cellular structures

58F 08 is Global analysis, analysis on manifolds / dynamical systems / point mapping properties; ...; dynamics of cellular automata.

References

Ada94

Andrew Adamatzky. Identification of Cellular Automata. Taylor and Francis, London, Bristol, 1994.

FTW84

J. D. Farmer, T. Toffoli, and S. Wolfram, editors. Cellular Automata: Proceedings of an Interdisciplinary Workshop at Los Alamos, New Mexico, March 7-11, 1983, Amsterdam, 1984. North-Holland.
A collection of papers on the theory and applications of cellular automata.

Gut91

Howard Gutowitz, editor. Cellular Automata: Theory and Experiment, 1991. Published as Physica D45 (1990) Nos. 1-3, and as MIT press book.

SZ90

R. Serra and G. Zanarini. Complex Systems and cognitive processes. Springer-Verlag, 1990. see Chapter 3.

TM87

Tommaso Toffoli and Norman Margolus. Cellular Automata Machines. MIT Press, London, 1987.

WL92

Andrew Wuensche and Mike Lesser. The Global Dynamics of Cellular Automata, volume Reference Vol 1 of Santa Fe Institute Studies in the Sciences of Complexity. Addison-Wesley, 1992. IBSN 0-201-55740-1.

Wol86

S. Wolfram, editor. Theory and Applications of Cellular Automata. World Scientific, Singapore, 1986.
Collection of papers on CA's. Contains an extensive bibliography.

Wol94

Stephan Wolfram. Cellular Automata and Complexity: Collected Papers. Addison-Wesley, 1994. revision of [Wol86] Paperback: ISBN 0-201-62664-0, Hardcover: ISBN 0-201-62716-7.

Cellular automata software

Packages for running cellular automata - and related systems;

Cellular automata hardware

Running cellular automata in hardware;

Conway's game of life

All about Conway's Game of Life [life-specific software here];

Where do I start?

What is the Game of Life? - by Paul Callahan DMOZ Conway's Game of Life links Alan Hensel's Conway's Game of Life applet Life32 by Johan Bontes - Conway's Game of Life - Windows Freeware Conway's Game of Life - Links Life Info - Links

Where do I find a simulator for the Game of Life?

There is a comprehensive list of life simulators on Alan Hensel's site.

Can I see the Game of Life in action?

Here is a DHTML/JavaScript implementation of Conway's Game of Life:

Archivist's note: Unfortunately not embeddable here

Where do I find Game of Life patterns?

Contributions by:

Alan W. Hensel <alanh@digital.net>

lifep.zip. Claimed to be the best 152 patterns from the first quarter-century of Conway's Game of Life. Note that this collection has no included program.

The weird pattern collection covers rules other than Conway's standard 23/3.

Who is interested in Life?

Is Martin Gardner's Scientific American article on Conway's life available?

Yes - see here.

References

[Dew87]
[Dew88]

Can you do computations with the Game Of Life?

Yes. The Game Of Life was proved to be computation-universal in the classic work [BCG82].

Has anyone actually built a computer in the Game Of Life?

Yes.

For example see the Turing machine in the game of life implementation.

How do you do computations with the Game of Life?

Contributions by:

  • Chris Langton <cgl@t13.lanl.gov>

The constructive proof that the game of life is capable of supporting universal computation is built around colliding glider streams into one another. colliding glider streams form the basic AND, OR, and NOT gates, out of which one then goes on to engineer a general purpose computer. However, one need not construct a general purpose computer, one could arrange the same computational primitives into a device that computes only a specific function.

One example, computing the logical NOT of a byte, is straightforward. Arrange for a stream of gliders (the input stream) to collide with the output of a glider gun at right-angles in such a way that the gliders in the input stream occur with the same spacing as the gliders coming from the glider gun. Furthermore, time the arrival of gliders in the input stream so that they collide with gliders in the output of the glider gun and annihilate each other. Then, encode the byte you want to compute the logical NOT of in the following way: For every 0 in the input byte, remove a glider from the input stream, for every 1, leave a glider. Thus, the input byte 10110010 will be represented by the glider stream:

glider noglider glider glider noglider noglider glider noglider

where the "nogliders" are spots where gliders in a regular periodic stream of gliders have been removed.

When this stream is collided into the regular stream of gliders coming out of a glider gun, observe what happens. For every 0 in the input byte, the missing glider in the input stream allows a glider from the glider gun to pass, whereas for every 1 in the input byte, a glider in the input stream annihilates the corresponding glider coming from the glider gun. Thus, looking at the output stream from the glider-gun DOWNSTREAM of the collision site, there is a glider (a 1) for every "hole" in the input stream (a 0) and there is a hole (a 0) for every glider (1) in the input stream. Thus, the filtered output of the glider-gun is the logical NOT of the encoded input stream.

And not a universal computer in sight!

By colliding this output stream (call it NOT A if the input steam is A) with another input stream, B, one gets A AND B in the continuation of the input stream B after the collision site. If one collides the downstream portion of the NOT A stream from this latter gate with the output of another glider gun, one obtains A OR B as the continuation of the second glider gun output downstream of the collision.

By hooking up a sequence of AND, OR, and NOT gates built in this way, one can compute any function that can be expressed by these logical operations (a great many functions indeed....;-)

For complex functions, involving many gates, one needs to cross glider streams, redirect glider streams, and so forth. This leads to more complication. However, the basic idea is as sketched out above.

Contributions by:

  • Wentian, Li <wli@cshl.org>
  • McIntosh, Harold V. <mcintosh@redvax1.dgsca.unam.mx>

Using the interaction of glider streams, the Game of Life can be programmed to perform computations. Indeed, it is a universal computer.

References [BCG82] [Pou85]

Must one use all of the logical gates to perform computations in the Game of Life?

See: [Jay00] The three logical gates AND, OR, NOT are sufficient for all logical functions, but not necessary. not only two basic gates are enough, one basic gate is also enough! for example, gate NAND, which is ``negation of AND,'' can lead to all three previously considered ``basic'' gates: NOT(a) = (a NAND a)
AND(a,b) = (A NAND B) NAND (A NAND B)
OR(a,b) = (A NAND A) NAND (B NAND B) another example is the NOR (negation of OR): NOT(a) = (a NOR a)
OR(a,b) = (A NOR B) NOR (A NOR B)
AND(a,b) = (A NOR A) NOR (B NOR B) the relevance to CA/Game of Life is that the requirement for having three logical gates in a CA rule so that it can do all computations can be (two) too much. at least in principle, having one NAND should be enough for constructing all logical functions.

Is the Game Of Life reversible?

No. Many states lead to an empty universe - so information is clearly lost during the evolution of the automaton.

Garden-of-Eden patterns exist in Conway's Game of Life. Do they exist in other automata?

Harold McIntosh <mcintosh@servidor.unam.mx>

They exist for the great majority of cellular automata, and there is a considerable theory concerning the criteria according to which they exist or not, which in turn is related to the question of whether the automaton is reversible or not.

A quick criterion is that the rule of evolution has to be "balanced" for an automaton to be reversible and thus not have Garden-of-Eden configurations. Life fails this, because many more neighborhoods lead to zeroes than to ones.

A more precise criterion is one called "mutual erasibility" introduced by Edward F. Moore, to be found in books on automata theory.

This state of affairs notwithstanding, several persons have programmed a search for Life GOE's and found some; I think an example is shown in Poundstone's book. So, of course, a Turing machine could undertake a similar calculation. As an aside, note that it is a Minsky register machine which has been shown to be a universal computer in Life, but that some people have tried to make a more traditional Turing Machine using glider streams.

See:

Edward F. Moore, ``Machine models of self-reproduction,'' in A. Burks (ed), Essays on Cellular Automata, University of Illinois Press, Urbana, 1970.

The same volume also contains a discussion (by J. W. Thatcher) of the relation between Turing Machines and Cellular Automata, another topic of recent interest for this newsgroup.

What is the smallest known Garden of Eden in the Game Of Life?

It consists of 143 living cells, and fits in a 14x14 bounding box.

You can see it here.

Where can I learn about Spaceships in the Game of Life?

Contributions by:

  • Bruce Stangeland <tbest@rrc.chevron.com>

See Spaceships in Conway's Life, by David I. Bell <dbell@pdact.pd.necisa.oz.au>.

Texinfo version of above by J�rg Heitk�tter <joke@santafe.edu> in the CA archives at think.com.

There have also been a series of articles on CA that have appeared in Scientific American, in the Computer Recreations section. See, for example: 10/70, 8/88, 8/89, 9/89, and 1/90.

Are variable-speed spaceships possible?

Yes - this follows from the existence of construction universality.

Life patterns can construct complex machinery in a vaccuum, destroy it again, and process delay units. It follows that arbitrarily slow spaceships can be constructed.

Has a variable-speed spaceship been constructed?

No. At the time of writing, eight distinct space-ship speeds are known.

What are the known spaceship speeds?

c/2, c/3, c/4, c/5, 2c/5, c/6, 2c/7 and c/12.

Where can I find the meaning of terms like 'spaceships', 'blinkers' and 'beehives'?

In the Life Lexicon.

Are self-reproducing organisms possible in the Game Of Life?

Yes. [BCG82] contains the proof that the Game of Life can contain self-reproducing organisms.

Has anyone built a self-reproducing organism in the Game Of Life?

No - that challenge still remains.

How big is a self-reproducing organism in the Game Of Life likely to be?

That is not known in any detail. We can say that it is not likely to be very small - or it would have been found by now.

On the other hand, any constraction following the approach detailed in [BCG82] is likely to be huge.

What published work relates to the Game of Life?

[Mci90] [GV87] [BCG82] [SS78] [BB91] [BCC89] [Dew87] [Bay92] [Bay87b] [Bay87a]

What is 3D Life?

Contributions by:

  • Anthony Wesley <awesley@canb.auug.org.au>
  • Harold V. McIntosh <MCINTOSH@unamvm1.dgsca.unam.mx>
  • John Pedersen <jfp@GOEDEL.MATH.USF.EDU.>

There have been a number of attemps at finding a 3D version of Conway's life.

Many of the current attepts can be seen here.

Carter Bays gives a new rule for 3D Life in [Bay92].

References

Bay87a

Carter Bays. Candidates for the game of life in three dimensions. Complex Systems, 1(2):373-400, April 1987.

Bay87b

Carter Bays. Patterns for simple cellular automata in a universe of dense packed spheres. Complex Systems, 1(6):853-875, December 1987.

Bay92

Carter Bays. 3D life (?). Complex Systems, 6(5):433-442, 1992.

BB91

Bennett and Bourzutschy. Nature, 350:468, 1991.

BCC89

Bak, Chen, and Creutz. Soc/game of life (??). Nature, 342:780, 1989.

BCG82

Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy. Winning Ways for your Mathematical Plays, volume 2. Academic Press, ISBN 0-12-091152-3, 1982. chapter 25.

Dew87

A. K. Dewdney. The game life aquires some successors in three dimensions. Scientific American, 224(2):112-118, February 1987.

Dew88

A. K. Dewdney. The hodgepodge machine makes waves. Scientific American, 225(8), August 1988.

GV87

H. A. Gutowitz and J. D. Victor. Local structure theory in more than one dimension. Complex Systems, 1:57-68, 1987.

Jay00

E. T. Jaynes. probability theory-the logic of science. unknown, 1900.

Mci90

Harold V. Mcintosh. Wolfram's class IV automata and a good life. Physica D, 45:105-121, 1990.

Pou85

William Poundstone. The Recursive Universe. William Morrow and Company, New York, 1985. ISBN 0-688-03975-8.

SS78

L. S. Schulman and P. E. Seiden. Statistical mechanics of a dynamical system based on conway's game of life. Journal of Statistical Physics, pages 293-314, 1978.

Applications

Applications in physics, biology, computer science and artificial life;

Properties

Reversibility, universal computation and construction, etc;

Classification

Organization of the space of cellular automata;

Lattice gas automata

Lattice gas automata - as used to model fluid flow;

Particular rules

For example, the hodge-podge rule, vants and the Fredkin rule;

Connections to other types of dynamical systems;

Miscellaneous

Miscellaneous issues;

Bibliography

928 references relating to cellular automata [bibtex] [search];

Threads

Archived mail on various CA-related subjects;

Related web sites;

Retrieved from "https://conwaylife.com/w/index.php?title=Cellular_Automata_FAQ/Archive&oldid=133074"