Questions for Asynchronous CA

[shouldsee]

There doesn't seem to be much discussion on asynchronous CA (ACA), so I shall start a general thread here.

I have a specific question on alpha-asynchrony

Background:asynchrous cellular automata (ACA) can be seen as a probablistic mixture between a deterministic cellular automata(t) and the identity automata(e). Every cell has a probability p to transit to t(ng) or (1-p) to transit to e(ng)=s (by definition).

When p->0, an ACA can be effectively viewed as carrying sequential updating, according to a random order. Interestingly, it seems such behavior can be modelled by another deterministic CA.

*s is the cell being updated.
*ng is the neighborhood of s

Report:
If the default transition is identity CA (e), then
As p->0, ACA based on B01278/S034 behaves similarly as B1678/S236
rewritten as -
ACAe B01278/S034 -> DET B1678/S236
ACAe B3/S23-> DET squared-strip
ACAe B0238/S123->DET squared-strip, ordered
ACAe B0235/S1234->DET long-strip
ACAe B0167/S14->DET dot-stable
ACAe B01235/S02346->DET dynamic-strip
ACAe B01238/S01236 -> DET strip-stable CA,ordered
ACAe B3457/S567 -> DET dot-stable CA
ACAe B0123/S01345-> DET xxx-stable CA

If the default transition is inverse CA (i), then
As p->0, we have
ACAi B01568/S0-> DET convuluted strips-stable CA
ACAi B3/S238->DET chaotic CA
ACAi B013478/S01-> DET crystals
ACAi B0238/S123->DET dot-stable with parity
ACAi B0235/S1234->DET dynamic dot-stable

Question:
By inspection, asymptotic behavior of ACA at p->0 seems equivalent to some DCA(deterministic CA) at a lower speed. Then, what will be the ACA that simulate B3/S23 as p->0?



Appendix:
An excerpt from (Nazim Fatès 2014)


"Nakamura was among the first authors to investigate how to compute with an asynchronous cellular automaton [81, 82]. He described several techniques to construct a universal rule and showed how to simulate a given q -state deter- ministic rule with an asynchronous rule that has the same neighbourhood and whose state space is extended to 3 q 2 states (see also Lipton et al. [70], Tof- foli [126] and Nehaniv [84] for similar constructions). The construction relies on the idea that when a cell is updated, it then waits the neighbouring cells to “catch up” and makes the next transition only when all its neighbours are up to date. Additionally, it keeps its old state available for the neighbouring cells in order for them to perform the “right” transitions. This construction was later improved by the use of only q^2 + 2 q states by Lee, Peper et al. [67, 89]. Peper et al. also proposed to consider the case where a cell can “activate” their neighbouring cells and showed that the cost in the number of states for the simulation of q -state rule could be reduced to O ( q p q ) states [90]."

[Bullet51]

Question:
By inspection, asymptotic behavior of ACA at p->0 seems equivalent to some DCA(deterministic CA) at a lower speed. Then, what will be the ACA that simulate B3/S23 as p->0?

It seems that the equivalent of ACAe B345678/S678 is DCA B35678/S4678.
Unfortunately, there may be no DCA equivalence in some cases, namely B2/S.
Consider this pattern in ACAe B2/S:

Code: Select all

x = 2, y = 2, rule = B2/S
bo$o!

As p->0 and t->∞, the pattern will evolve to

Code: Select all

x = 2, y = 2, rule = B2/S
bo!

and

Code: Select all

x = 2, y = 2, rule = B2/S
2o$o!

,each with 1/2 probability.
Thus no DCA can simulate it.

[shouldsee]

,each with 1/2 probability.
Thus no DCA can simulate it.

One biggest question is whether ACAe could support glider. It's plausible that random sequential updating might induces a near-equilibrium achievable by some other DCA. However it seems illusive to me whether ACAe can indeed supports glider. As Bullet51 pointed out, a given configuration can evolve to different end-result. I tend to think ACAe don't support any glider, but I am not so sure about this yet, due to occasional soliton-like dynamics exhibited in some ACAe.

[Bullet51]

I tend to think ACAe don't support any glider

If there is any glider, there will be a positive probability for it to be swallowed, by updating it from the "tail" of the glider.

[apg]

An asynchronous CA can indeed support gliders which move in a lock-step fashion. Here's a glider in a 3-state 1D ACA:

000010000 -->
000012000 -->
000002000 -->
000001000 --> ...

The rules are:

100 --> 2
012 --> 0
020 --> 1