Back in the astonishing world of little known cellular automata. Let's review together the great family of universal constructors and self-replicating structures!
www.tipeee.com/passe-science
/ thomascabaret84
/ passescience.youtube
Videos:
Langton's Ant: • La fourmi de Langton
Game of Life: • Le Jeu de la Vie
Other cellular automata: • Les Automates Cellulai...
Web:
Sexyloop: www.researchgate.net/publicat...
CBlock: www.researchgate.net/publicat...
Von Neumann: en.wikipedia.org/wiki/John_vo...
0E0P wiki: www.conwaylife.com/wiki/0E0P_m...
Von Neumann Machine: en.wikipedia.org/wiki/Von_Neu...
Golly program: golly.sourceforge.net/
Will Stevens' CBlock: www.srm.org.uk/home.html
Mayotomata.com: www.mayotomata.com/
Milestones to 0E0P (Thx to A. P. Goucher):
---
1940s: John von Neumann invents the concept of cellular automata, together with a particular 29-state 5-neighbor rule, as a mathematical model in which universal computation and construction are both possible.
1968: Edgar F. Codd develops an 8-state 5-neighbor rule as a simpler alternative to von Neumann's cellular automata. (It took until 2010 for Tim Hutton to actually build the self-replicating machine.)
1969: John Conway discovers the Game of Life, a 2-state 9-neighbor rule
which he conjectured was capable of universal computation and construction.
1982: Conway, Berlekamp, and Guy finally prove the above ... but the proof
(described in Winning Ways and The Recursive Universe) would lead to an
impractically large and slow machine.
1996: Paul Callahan builds the first example of a 'stable reflector': a circuit
capable of reflecting gliders asynchronously. All of the circuitry in the 1982
proof was composed of oscillating components, so could only manipulate
synchronized gliders. This reflector was large and slow, and the next
two years saw profound improvements in the technology.
1998: Stephen Silver finds a stable reflector with a recovery time of 497,
which fits within a 64-by-81 box.
2004: Dave Greene and Paul Chapman build two universal constructors,
one with a static tape and another with a memory loop. Only very simple programs were written for these machines, so they did not
self-replicate. They restricted themselves to using only 'Spartan' circuitry made of well-separated copies of a few very simple components, to make it easier to build the circuitry by colliding gliders.
April 2013: Mike Playle discovers the 'Snark', an incredibly small and fast
stable reflector.
March 2015: Tanner Jacobi discovers a component dubbed the 'Syringe', which has a 90-tick recovery time and can duplicate signals. Suddenly fast efficient circuitry is possible, using Snarks and Syringes. These are not Spartan, though, which made people reluctant to use them in self-constructing circuitry.
January 2016: Simon Ekström showed that a single channel of gliders, with adjacent gliders separated by at least 90 ticks, can pull / push a block and emit perpendicular gliders. This opened up a whole new possibility of 'single-channel' universal constructors - but the remaining piece of the puzzle was to show that these complex objects could actually be synthesized.
January 2017: Adam P. Goucher wrote a search program called HoneySearch which ran uninterrupted for about three days on 72 CPUs, performing a breadth-first search of 'slow salvo' glider constructions of objects. This used 100 GB of memory and output 13 GB of efficient recipes of over 200 different objects. This was later filtered down to 800 MB of in particular useful recipes. The Syringe and Snark were too complicated to occur naturally during this search, though.
March 2017: Martin Grant and Chris Cain built constructions for the Snark and Syringe, using sample soups on Catagolue (a very large distributed search of random soups in cellular automata):
Using the HoneySearch results together with these bespoke syntheses, it was possible to obtain data for an automated synthesis compiler, slmake,
to build practically anything made of Snarks, syringes, and over 200 simpler
objects.
2017/2018: Adam P. Goucher continues to improve the slmake code to be able to efficiently manage larger and more complicated constructions, up to and including the 0E0P metacell (finished in late 2018).
---
Music:
www.jamendo.com/track/20236/a...
incompetech.com/music/royalty...
"observe" kzitem.info...
Decisions by Kevin MacLeod is licensed under a Creative Commons Attribution-Based License (creativecommons.org/licenses/...)
Source: incompetech.com/music/royalty-...
Негізгі бет Ғылым және технология Cellular Automata - Passe-science # 27
Пікірлер: 102