Structures auto-répliquantes dans les automates cellulaires - Passe-science #27

Retour dans le monde étonnant des automates cellulaires peu connus. Parcourons ensemble la grande famille des constructeurs universels et des structures auto-replicantes!

https://www.tipeee.com/passe-science
  / thomascabaret84  
  / passescience.youtube  

Videos:
Fourmi de Langton:    • La fourmi de Langton  
Jeu de la vie:    • Le Jeu de la Vie  
D'autres automates cellulaires    • Les Automates Cellulaires réversibles - Pa...  

Web:
Sexyloop: https://www.researchgate.net/publicat...
CBlock: https://www.researchgate.net/publicat...
Von Neumann: https://en.wikipedia.org/wiki/John_vo...
0E0P wiki: http://www.conwaylife.com/wiki/0E0P_m...
Von Neumann Machine: https://en.wikipedia.org/wiki/Von_Neu...
Golly program: http://golly.sourceforge.net/
Will Stevens CBlock: http://www.srm.org.uk/home.html
Mayotomata.com: http://www.mayotomata.com/

Milestones to 0E0P (Thx to A.P.Goucher):
---
1940s: J. V. 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: E. F. Codd, develops an 8-state 5-neighbor rule as a simpler alternative to
Von Neumann's cellular automata. (It took until 2010 for T.Hutton to actually
build the self-replicating machine.)

1969: J. 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: P. 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: S. Silver found a stable reflector with a recovery time of 497,
which fits within a 64-by-81 box.

2004: D. Greene and P. 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 didn't
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: M.Playle discovers the 'Snark', an incredibly small and fast
stable reflector.

March 2015: T. 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 aren't Spartan, though,
which made people initially reluctant to use them in self-constructing circuitry.

January 2016: Simon Ekstroem 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 particularly useful recipes. The Syringe
and Snark were too complicated to occur naturally during this search, though.

March 2017: M Grant and C Cain built constructions for the Snark
and Syringe, using sample soups on Catalogue (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 enough 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 continued 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).
---

Musics:
https://www.musicscreen.org/Royalty-f...
https://www.jamendo.com/track/20236/a...
https://incompetech.com/music/royalty...
"observer" https://www.youtube.com/audiolibrary/...
Decisions: http://incompetech.com/music/royalty-...
Sci fi bensound: https://www.bensound.com/royalty-free...