Difference between revisions of "Universal constructor"
(Added paragraphs on modern universal construction methods) |
(all possible glider fleets _can_ be constructed, but there are other things that are vague about the definition of "universal"...) |
||
| Line 1: | Line 1: | ||
{{Glossary}} | {{Glossary}} | ||
A '''universal constructor''' is a [[pattern]] that is able to construct | A '''universal constructor''' in Conway's Life is a [[pattern]] that is able to construct any pattern that has a [[glider synthesis]]. The general definition is a bit vague, since it can also be applied to other cellular automata, including rules such as Von Neumann's original 29-state rule that may not even have simple gliders, and so construction is more readily done via signals traveling through "wires". In any case, to qualify as universal, a constructor should be able to construct itself as well as an unlimited variety of other configurations, depending on what instructions are given to it. | ||
[[John Conway]] proved that such a pattern exists in [[Conway's Game of Life|Life]], and an outline of the proof can be found in ''[[Winning Ways for Your Mathematical Plays]]'' and ''[[The Recursive Universe]]''. The key mechanism for the production of gliders with any given path and timing is known as side-tracking, and is based on the [[kickback reaction]]. | [[John Conway]] proved that such a pattern exists in [[Conway's Game of Life|Life]], and an outline of the proof can be found in ''[[Winning Ways for Your Mathematical Plays]]'' and ''[[The Recursive Universe]]''. The key mechanism for the production of gliders with any given path and timing is known as side-tracking, and is based on the [[kickback reaction]]. | ||
| Line 16: | Line 16: | ||
*The constructor could be programmed to make just one copy of itself, translated by a certain amount, and then delete itself. Such a pattern would be a (very large, very high [[period]]) [[spaceship]]. Any translation is possible (except that it must not be too small), so that the spaceship could travel in any direction. It could also travel slower than any given speed, since we could program it to perform some time-wasting task (such as repeatedly constructing and deleting a block) before copying itself. Of course, we could also choose for it to leave some debris behind, thus making a puffer. | *The constructor could be programmed to make just one copy of itself, translated by a certain amount, and then delete itself. Such a pattern would be a (very large, very high [[period]]) [[spaceship]]. Any translation is possible (except that it must not be too small), so that the spaceship could travel in any direction. It could also travel slower than any given speed, since we could program it to perform some time-wasting task (such as repeatedly constructing and deleting a block) before copying itself. Of course, we could also choose for it to leave some debris behind, thus making a puffer. | ||
*It is also possible to show that the existence of a universal constructor implies the existence of a stable reflector. This proof is not so easy, however, and is no longer of much significance now that explicit examples of such reflectors are known. | *It is also possible to show that the existence of a universal constructor implies the existence of a stable reflector. This proof is not so easy, however, and is no longer of much significance now that explicit examples of such reflectors are known. | ||
*In 2009, [[Adam P. Goucher]] built the [[Spartan universal computer-constructor]], which could theoretically accomplish the above tasks. | *In May 2004, Paul Chapman published a prototype Spartan universal constructor which could construct any glider-constructible object, given the correct input (which would have been in most cases very difficult to find in practice.) This [[Chapman-Greene construction arm]] was used without any improvements in several later projects, including the next two items on this list. | ||
*In 2009, [[Adam P. Goucher]] built the [[Spartan universal computer-constructor]], which could theoretically be programmed to accomplish any of the above tasks. | |||
*In 2010, Andrew Wade built [[Gemini]], the first spaceship, that moves by building a copy of itself, except the instruction tape. | *In 2010, Andrew Wade built [[Gemini]], the first spaceship, that moves by building a copy of itself, except the instruction tape. | ||
*In 2013, Dave Greene built the first | *In 2013, Dave Greene built the first self-replicating pattern in Conway's Game of Life. Due to its very simple linear reproduction method, it should arguably be classified as a [[linear propagator]] rather than a true [[replicator]]. | ||
==See also== | ==See also== | ||
*[[Turing machine]] | *[[Turing machine]] | ||
Revision as of 20:22, 5 September 2016
A universal constructor in Conway's Life is a pattern that is able to construct any pattern that has a glider synthesis. The general definition is a bit vague, since it can also be applied to other cellular automata, including rules such as Von Neumann's original 29-state rule that may not even have simple gliders, and so construction is more readily done via signals traveling through "wires". In any case, to qualify as universal, a constructor should be able to construct itself as well as an unlimited variety of other configurations, depending on what instructions are given to it.
John Conway proved that such a pattern exists in Life, and an outline of the proof can be found in Winning Ways for Your Mathematical Plays and The Recursive Universe. The key mechanism for the production of gliders with any given path and timing is known as side-tracking, and is based on the kickback reaction.
Much simpler universal construction techniques have since been found. A universal construction arm produces gliders on a fixed set of lanes aimed at a construction elbow. A universal toolkit for a construction arm consists of recipes for at least three elbow operations: a PULL and a PUSH operation, which cleanly move the elbow object diagonally toward or away from the source of the gliders, and a FIRE reaction which produces a 90-degree glider output (while optionally moving the elbow some distance.)
It has been convincingly shown (though not yet formally proven) that just one FIRE operation is sufficient to construct any object that can be constructed by gliders. Including two FIRE operations in the toolkit, one for each output glider color, greatly increases the construction efficiency but does not add anything to the set of objects that can be constructed. Multiple elbow types and multiple PUSH, PULL, and FIRE operations also improve efficiency, as shown for example in the 10hd and 0hd Demonoid spaceships.
A universal constructor can also function as a universal destructor -- it can delete any pattern that can be deleted by gliders.
With a universal computer
A universal constructor is most useful when attached to a universal computer, which can be programmed to control the constructor to produce the desired pattern of gliders. The existence of a universal constructor/destructor together with a universal computer has a number of theoretical consequences.
- The constructor could be programmed to make copies of itself; such a pattern is known as a replicator.
- The constructor could be programmed to make just one copy of itself, translated by a certain amount, and then delete itself. Such a pattern would be a (very large, very high period) spaceship. Any translation is possible (except that it must not be too small), so that the spaceship could travel in any direction. It could also travel slower than any given speed, since we could program it to perform some time-wasting task (such as repeatedly constructing and deleting a block) before copying itself. Of course, we could also choose for it to leave some debris behind, thus making a puffer.
- It is also possible to show that the existence of a universal constructor implies the existence of a stable reflector. This proof is not so easy, however, and is no longer of much significance now that explicit examples of such reflectors are known.
- In May 2004, Paul Chapman published a prototype Spartan universal constructor which could construct any glider-constructible object, given the correct input (which would have been in most cases very difficult to find in practice.) This Chapman-Greene construction arm was used without any improvements in several later projects, including the next two items on this list.
- In 2009, Adam P. Goucher built the Spartan universal computer-constructor, which could theoretically be programmed to accomplish any of the above tasks.
- In 2010, Andrew Wade built Gemini, the first spaceship, that moves by building a copy of itself, except the instruction tape.
- In 2013, Dave Greene built the first self-replicating pattern in Conway's Game of Life. Due to its very simple linear reproduction method, it should arguably be classified as a linear propagator rather than a true replicator.