Hunting for Complexity in RD Systems

I've always found reaction-diffusion simulations fascinating, I first read about the BZ reaction in the book: Frontiers of Complexity by Coveney and Highfield. It also discusses fractals and cellular automata such as the well-known (and very well explored) Game of Life. It introduces Turing's work on morphogenesis that led to the development of the field of reaction-diffusion too. I was happy to hear recently that Turing has posthumously received a royal pardon of his 1952 conviction for homosexuality. I think if he were still alive he would be relieved by that, and very proud to see how far and how well his amazing ideas have travelled.

As far as I know, it's never been proved that any RD system is Turing-complete (ie capable of universal computation). Universality has been shown for the Game of Life and a few other automata, but it would be a great deal harder to show that an RD system was universal.

Robert Munafo has done brilliant work in discovering and exploring a thin sliver of the parameter space of Gray-Scott RD that he's dubbed 'USkate world'. USkate has some of the hallmarks of Wolfram Class-4 complexity, so it looks like it could potentially be universal.

What is Class-4 complexity? to paraphrase Wikipedia:

""The primary classifications of cellular automata as outlined by Wolfram are numbered one to four.

The classes are: 

Class 1: In which patterns generally stabilize into homogeneity.

Class 2: In which patterns evolve into mostly stable or oscillating structures. 

Class 3: In which patterns evolve in a seemingly chaotic fashion.

Class 4: In which patterns can become extremely complex and may last for a long time, with stable local structures. This last class are thought to be computationally universal, or capable of simulating a Turing machine.""

USkate has plenty of potential for long-lasting complexity, it regularly remains active across huge numbers of iterations. I playfully suggested to Rob that one day someone will make a Turing machine in USkate world, knowing that that would be a herculean task. It's not at all obvious how one would start to construct and align the primitives (simple logic gates and so on) required to do it. Unlike Game of Life where interactions are definite and the building blocks are predictable, tiny differences in initial state values or alignment could have a critical impact on the ultimate behaviour or outcome. That said, uskate is resistant to noise, so it might not be as hard as it seems

You'd probably have more luck just searching for a proof-pattern than building one, but it still feels like it should be doable, merely very difficult and time (and resource) consuming.

I was inspired by USkate world so I decided to go on a bit of an expedition, to see what kinds of behaviour I could find by adding extra reagents to existing RD formulae, or inventing new ones (which I'll cover in a later post).

I added a 'diffusible-history' reagent to Gray-Scott's usual two (u and v). This led to several interesting discoveries. Nearby to USkate, and with an additional history reagent, I found this pattern of negatons that spontaneously divide, and get wiped out when they get overcrowded or stay in the same place for too long:

 

Perhaps not the most visually exciting thing ever, but it has some interesting parallels to Game of Life.

I also noticed that Gray-Scott settings that produce broken wavefronts make an attractive looking trail in the history reagent, as in this example where the history is used as a displacement map:

 

Here's another example, which has additional wave-reagents (described below):

 

The further two reagents couple a wave-equation system to gray-scott. This takes the total number of reagents to five: u, v, history, wave and wave-derivative. The new reagents have controllable amounts of u and v added to them on each step, and the evolved values of the new reagents are in turn used to offset the parameters and diffusion coefficients of the Gray-Scott formula.

The following is a nice looking result in which glider-soliton wavefronts expand and collide with each other like fireworks. The wave component gets particularly active where wavefronts are being created (rendered as blue in this video), and the solitons respond to these high wave values by becoming softer and dividing more, encouraging a cascade of division:

 

Progressing along from here I found this super-history avoiding setting, which as Hiroki Sayama observed behaves a bit like TRON light cycles! :)

And here's the most curious thing I've found using this system so far:

This formula and settings produce vibrating solitons that become worms or glider-solitons under certain conditions. When hit by a prolonged stream of soliton-gliders, worms tend to oscillate and eventually break. When worm tips are oscillated, they can go into a state in which glider-solitons are emitted in a continuous stream. Streams of glider-solitons move in self-attracting trains along interesting wiggly paths, avoiding whilst influencing each other and perturbing the worms.

Another interesting and somewhat similar example is this:

In which stationary solitons spontaneously form worms that move orthogonally to their length like wavefronts, breaking or disappearing when they get too dense. Eventually the frame is filled with moving solitons and worms. The main setting that makes things move like this is feeding the wave reagent negatively back into F and k. When this runs for a long time, everything tends to end up moving in the same direction uniformly.

I've been on the lookout for life-like behaviour, which should have a good chance of being programmable. The clip below is the most life-like thing I've found so far:

It's another gray-scott with history and wave-equation, and it has quite a few parallels with life. Obviously gliders, but also temporary blinker-like objects and stable blocks that do things when gliders hit them.

These last three systems are in the recent Ready-0.6 release, under Patters/Experiments, if you would like to play with them.