Open access peer-reviewed chapter

Hard, firm, soft … Etherealware:Computing by Temporal Order of Clocking

By Michael Vielhaber

Submitted: March 23rd 2018Reviewed: July 20th 2018Published: November 5th 2018

DOI: 10.5772/intechopen.80432

Downloaded: 403


We define Etherealware as the concept of implementing the functionality of an algorithm by means of the clocking scheme of a cellular automaton (CA). We show, which functions can be implemented in this way, and by which CAs.


  • cellular automaton
  • etherealware
  • asynchronous
  • update rule
  • universality
  • temporal order
  • clocking-computable

Your task: Compute a lot of different functions on n-bit inputs.

Your device: A (fixed!) cellular automaton (CA) on the (fixed!) ring or torus topology with ncells, is capable of holding one bit each.

You may not change the CA (its update rule) nor the topology. You may not enter additional information in the form of parameters (there would be no space to store them anyway)—and yet you are supposed to evaluate many different functions. The available degree of freedom is the clocking scheme of the cells, anything from synchronous to completely asynchronous is allowed.

Can you do it?

The perhaps surprising answer is: yes!

Every bijective function on the set 012n1, which acts as an even permutation is clocking-computable, as well as many non-bijective functions.

1. Introduction

1.1. What is etherealware?

Computation takes place in dedicated hardware or on general-purpose hardware by dedicated software. Different functionality requires either changing the hardware (think ASIC, FPGA) or changing the software running on it. Firmware is an intermediate concept, where the hardware is modified by microprogramming a CPU or personalizing an FPGA.

Etherealware is the first way to use fixed hardware (certain cellular automata (CA) in this case), run fixed software (the same update rule for all cells, for all time, for all purposes), and still deliver diversity in the resulting function: by changing only the clocking scheme, the order in which the CA’s cells are updated.

1.2. State-of-the-art

The study of synchronous CAs starts with Wolfram [1]. We use asynchronous CAs as deterministic devices with a finite number of computation steps, which is a new point of view.

Previously, asynchronous CAs have been treated as dynamical systems, where infinite computations are considered, and the focus lies on concepts like orbits, fixed points, ergodicity, transients, cycles and their periods, and long-term behavior. Also, randomness can be introduced to average over many possible asynchronous schemes. Papers in this respect are:

Ingerson and Buvel [2], 1984, distinguish synchronous, random (completely asynchronous), and periodic clocking, which yield clearly distinguishable behavior.

Barrett et al. [3, 4, 5, 6], 1999–2003, consider sequential dynamical systems (SDS), including CAs with arbitrary toplogy and neighborhoods. They cover random graphs as topology and dynamical systems topics such as fixed points and invertibility.

Siwak [7], 2002, gives an overview of simulating machines, including CAs and SDSs, and unifies them under the concept of “filtrons.”

Lee et al. [8], 2003, give an asynchronous CA on the two-dimensional grid Z×Z, which is Turing universal.

Laubenbacher and Pareigis [9], 2006, build upon [3, 4, 5, 6] and observe that not all n!permutations of the cells lead to different temporal rules. Their equivalence classes coincide—for our setting, CAs on the torus—with our result ([10], Thm. 1]).

Fatès et al. [11], 2006, consider ECAs with quiescent states (0000,1111, i.e., with even Wolfram rule 128). They show that 9 ECAs diverge, while the other 55 converge to a random fixed point, in 4 clearly distinguishable time frames Θnlogn,Θn2,Θn3,or Θn2nwith characteristic behavior per time frame.

Macauley, McCammond, and Mortveit [12, 13], 2007–2010, also treat SDSes, in particular ECAs. For each ECA, [13] gives the periodic states and the dynamics group. Conjecture 5.10 in [13] about Wolfram rule 57 coincides with our finding that ECA-57 generates the alternating groups on patterns of nbits. They verified this claim for nup to 8, while in [14] this is extended to n10and in this paper up to n28.

Dennunzio et al. [15, 16], 2012–2013, consider ACAs, every turing machine can be simulated by an ACA, with quadratic slowdown. Introducing a certain fairness measure, they show that injectivity and surjectivity are equivalent (μ-a.a.), and the existence of a diamond is equivalent to not μ-a.a. injectivity.

Salo [17], 2014, shows that nonuniform CA generates all SFTs (subshifts of finite type) and several non-SFT sofic shifts.

2. Notations: ECA and update rules

Here, continuing the work in [10, 14], we again employ CAs as computing devices, whose work comes to an end, when the pattern transformation or function evaluation has been obtained. Also, the clocking, the temporal update rule, is completely deterministic and replaces the usual ways of representing an algorithm, either in software (initial data) or in hardware (choice of ECA and connecting graph). Thus, the algorithm resides exclusively in the clocking scheme. We therefore call functions computable in this way as “clocking-computable functions.” The main additional contribution of this paper is the introduction of unfair clocking schemes.

2.1. Cellular automata: Neighborhoods and local update rules

We consider cellular automata (CA) on a torus or ring of ncells, that is index set Z/nZ, over the binary alphabet 01. Cell index wraparound, that is, ci=cjfor ijmodn, and the canonical cell names are cn1,cn2,,c1,c0. We deal with elementary CAs (ECA) with three input cells, where the middle one is also the output cell.

The neighborhood (ci+1, ci, ci−1) can have eight different values from F23. Let k  4ci+1+2ci+ci107. Then ciis replaced by ci+  pk01, where p0,,p7are defined via Wolfram’s rule [1] k=072kpk0255.

The 223=256ECAs can be arranged into 88 equivalence classes under the symbolic symmetry 0/1 and the chiral symmetry left/right (ci+1ci1); see ([14], Appendix A). It is sufficient to consider one member per class.

We considered quad CAs (QCAs) with four inputs and nonstandard neighborhoods in ([10], Section 1.2).

Local bijectivity requires that ECA a0c=1ECA a1c. This is equivalent to requiring that the hexadecimal digits of the rule be from3, 6, 9, C.

Example: The behavior of the ECA with Wolfram rule 57=001110012=3916:

1110, 1100, 1011, 1001, 0111, 0100, 0010, 0001, in other words 0ci1ci+=ci, for all other contexts we have 0ci0,1ci0,1ci1ci+=c¯i.

2.2. ECA: Global update rules on the torus

2.2.1. Fair update schemes

We repeat the definition of asynchronicity rules from ([10], Section 2).

The set ASnof asynchronicity rules over Z/nZconsists in all words of length nover the alphabet <>such that both “<” and “>” occur at least once. We also include the word “,” the synchronous case, and have.

ASn=<>n\<n>nnwith ASn=3n2n+1+2.

A rule AS=ASn1AS0ASndefines the firing order as follows:

<Cell cifires after cell ci1
>Cell cifires before cell ci1
Cell cifires simultaneously with cell ci1

To ensure bijectivity, we must first have a locally bijective CA, and, furthermore, no two adjacent cells may fire simultaneously. Why this is so will be dealt with in Chapter 5. There are exactly 2n2bijective fair rules, those from <>n\<n,>n; see also ([10], 4.1]).

A fair update step (bijective or not) can be decomposed into a sequence of elementary steps such that all cells fire exactly once during the execution of that sequence; see [3].

2.2.2. Unfair update schemes

We now include unfair updates, where some cells may fire less often than others (even not at all).

We start with elementary steps (μsteps in [10]). During one elementary step, any nonempty subset In1n2,1,0of indices may define the active cells.

These cells fire simultaneously, hence ci+=ECAci+1cici1,iI,ci,i I.

We define elementary steps as words s=sn1s1s001n, with the meaning si=1, if cell cifires, and si=0if cell ciis inactive in this step.

A sequence of such elementary steps is upper indexed by the time step t.

A fair update rule consists in a number of elementary steps such that every cell fires exactly once. The fair rule as=<><><>” for n=6can be decomposed into (s1=010101,s2=101010), while the sequence (s1=010001,s2=101010) is unfair, since cell c2does not fire at all.

The number of bijective elementary steps is the number of words of length nover the alphabet 01, such that no adjacent 1’s occur to ensure bijectivity. For n=3,4,5,6there are 3, 6, 10, 17 such steps, respectively. The sequence obeys the law nk=nk1+nk2+1. At least for n=3,,7, the sets are as follows: prepend a 0 to each pattern of length k1, prepend a 10 (a 01) to each pattern of size k1terminating in 0 (in 1), and add the new pattern 10k1. The sequence is used again in Section 5 and has been verified to coincide with OEIS A001610 up to n=24.

We also can define unfair bijective rules (full steps), where we first fix some subset of size 1kn1of active cells by a word afrom 01n\0n1n, ai=1meaning that cell ciis active.

We next order adjacent active cells by the usual <,>signs. Hence, a run of rconsecutive 1’s (with wraparound) has 2r1ways to fix the internal firing order. This order is independent of the other 1-runs, since the cells are separated by at least an inactive cell with ai=0. The number of bijective unfair rules on a torus of size nis


where the pattern pavoids 0nand 1nand then the 1-runs in the pattern have lengths r1,r2,, considering wraparound.

For n=3,,7, we have 9=3+6,30=4+10+16,90=5+15+30+40,257=6+21+50+84+96,and 714=7+28+77+154+224+224,such unfair rules, respectively. The terms count how many patterns with k=1,2,,n1active cells are feasible. These terms can be found in OEIS [18] as subsequences of A209697.

3. Patterns

We consider pattern conversions F2nvwF2n, where F2ncan be identified with the set 012n1. From Definition ([10], Def. 3), by ECAASv=w, we mean that the elementary CA with rule ECA maps v01nto w01nvia the asynchronicity scheme AS. We define ECAASτv=ECAASECAASτ1vrecursively for τN, starting with ECAAS1v=ECAASv.

In [10, 14], we considered five universality properties oto iv, where each vwmakes use of a certain update rule AS applied several times. We only give a summary here. Property ivis ruled out for any nN, while properties oto ivhave only been verified experimentally, for n15.


Some vis mapped to every wby varying the rule AS and the required number of time steps. There are 44 ECAs doing this.

ivF2n,wF2n,τN, ASASn:ECAASτv=w.

All vare mapped to all wby varying the rule AS and the required number of time steps. There are 6 ECAs (rules 19, 23 (for n 0 mod 2), 37 (for n 0 mod 3), 41, 57, 105 (for n 0 mod 4)) doing this (checked for n15).


All vare mapped to all wat the same time, which time may vary for vbut not for w, for different rules AS .

ECA-57 realizes this for n=5,,15(no further nhas been considered).

ECA-105 realizes this for odd n=7,9,11,13,15(no further nhas been considered).


All vare mapped to all wat the same time, varying the rule AS. This is actually possible for the two survivors of property ii; see Table 1. The required time roughly decreases with growing n, since we have 3n2n+1+1rules to choose from for 2npatterns w. Thus for higher nthe probability to meet the conversion early on increases.


Table 1.

Minimum time τrequired to satisfy iii.

Eventually, all conversions may happen at all times for some update scheme. This property cannot be satisfied, for no ECA; see ([14], Thm. 2).

For more details and results for QCAs consult Section 2 of [14] and Section 3 of [10].

4. Bijective functions

We first introduce the computer algebra system GAP and then give several examples.

4.1. GAP: Graphs, algorithms, programming

4.1.1. GAP and the alternating group A2n

GAP [19] is a system for computational discrete algebra, in particular computational group theory. We use GAP to decide, whether certain fair or unfair update rules generate the full symmetric or alternating group S2nor A2n, respectively.

Our results so far:

Theorem 1.

  1. The fair update rules for ECA-57generate the full symmetric group S8for n=3.

  2. The fair update rules for ECA-57generate the full alternating group A2nfor n=4,,11.

  3. The (unfair)elementary update rules with exactly one active cell for ECA-57generate the full alternating group A2nfor n=4,,28.


iBy exhaustive generation of all 8!=40320permutations on 000, 001111.

iiiiiFirst observe that all these rules consist of an even number of transpositions. Hence, we will at most obtain the alternating group A2n. This group comprises those bijective functions on 012n1which have positive sign as a permutation.

We checked iiwith GAP for certain sets of 5 fair rules for each of these sizes n, and GAP’s functionIsNaturalAlternatingGroup(G) returned true.

For iiiwe have the canonical set of nelementary unfair update rules, with exactly one cell active in each rule. This set generates all fair and unfair update rules and hence is sufficient to decide on the group generated by all rules.

Again, GAP shows that indeed the alternating group is generated, for n=4,,28. We used 144 GB of RAM, which was sufficient for n=28but not so for n=29. □

We believe that, apart from the special case n=3, we always obtain the alternating group.


For every torus size nN,n4, both the 2n2fair update rules, as well as the nelementary unfair update rules with a single active cell, are a generating set for the full alternating group on 2nelements, using ECA-57.

4.1.2. Example for GAP usage with n=4

We replaced 0 by 2n, since GAP only uses numbers from N. P00 to P03 are the permutations generated by the elementary steps s=0001,0010,0100, and 1000, respectively.

mjv@Panda ∼/GAP $gap -b

gap> P00 := (16,1)(2,3)(4,5)(6,7)(10,11)(14,15);


gap> P01 := (16,2)(4,6)(5,7)(8,10)(12,14)(13,15);


gap> P02 := (16,4)(1,5)(8,12)(9,13)(10,14)(11,15);


gap> P03 := (16,8)(1,9)(2,10)(3,11)(5,13)(7,15);


gap> G04 := Group(P00,P01,P02,P03);;

gap> IsNaturalAlternatingGroup(G04);


gap> Size(G04);


4.1.3. Example for GAP usage with n=5

mjv@Panda ∼/GAP $cat G5

P00 := (32,1)(2,3)(4,5)(6,7)(8,9)(10,11)(12,13)(14,15)


P01 := (32,2)(4,6)(5,7)(8,10)(12,14)(13,15)(16,18)


P02 := (32,4)(1,5)(8,12)(9,13)(10,14)(11,15)(16,20)


P03 := (32,8)(1,9)(2,10)(3,11)(16,24)


P04 := (32,16)(1,17)(2,18)(3,19)(4,20)(5,21)(6,22)


G05 := Group(P00,P01,P02,P03,P04);

mjv@Panda ∼/GAP $gap -b

gap> Read(“G5”);

gap> IsNaturalAlternatingGroup(G05);


gap> Size(G05);


gap> quit;

Here, 1.3151035=32!/2.

4.1.4. Example for GAP usage with n=28

We define the permutations P00 to P27 via a C++ − program; see Appendix A. Using it like gap.out 28 > G28, its output, the file G28, is then read in by GAP.

mjv@turing:/var/GAP$ gap -b -m 140G

gap> Runtime();Read(“G28”);Runtime();IsAlternatingGroup(G28);Runtime();









Times are in milliseconds. Therefore, reading in the 56 GB of permutations P00 to P27 generating the group G28 took 1640 seconds, or about half an hour, while actually checking the resulting group for A228took another 7280 seconds or 2 hours. The same procedure for G29 resulted in lack of memory; 140 GB of RAM are not sufficient.

Recall that, according to Stirling’s formula, A228has 228!/2228e22810109elements, a number with about 1 billion (10003) digits. Amazingly, GAP gets it done!

4.2. Examples for bijective functions

4.2.1. Multiplication by 9 mod 16

We give two realizations of the function byNine:x9x mod 16in Table 2.

First realization in hexadecimal1. Active cells2. Active cellsSecond realization in hexadecimal

Table 2.

Multiplication x9xin Z/16Z.

Observe that the first 23 steps only implement the permutation 082A, consisting of two transpositions. The final 24th step is almost identical to the whole function.

Hence byNine=(19)(3B)(5D)(7F) = [(08)(2A)][(08)(19)(2A)(3B)(5D)(7F)], where the first bracket requires 23 steps, and the second is the elementary rule 1000 (only the leftmost cell is active). The difference between the two realizations (sequences s124in hex), where the outer parentheses are inverses of each other and the inner part is self-inverse, and their difference:

1.: (5A581248)1(A5A5A)4(842185A5)8

Diff 124–81A——-A18–421-

2.: (48181A52)1(A5A5A)4(25A18184)8

4.2.2. Exponentiation and logarithm in F17

Identifying 16 with 0b0000, we can map F17to 014. Here is the exponentiation x3x; see Table 3.

Active cellsFED…210 62C…931 some patterns in binaryAll values F…0 in hexadecimal

Table 3.

Exponentiation x3xin F17.


s124= [0001, 1010, 0101, 1010, 0101, 1000, 0100, 1000, 0001, 1000, 0100, 1010, 0100, 1010, 0001, 1000, 0101, 1000, 0100, 1000, 0100, 1010, 0100, 1010]


The inverse function xlog3xis therefore computed by the inverse update sequence s124= [1010, 0100, 1010, 0100, 1000, 0100, 1000, 0101, 1000, 0001, 1010, 0100, 1010, 0100, 1000, 0001, 1000, 0100, 1000, 0101, 1010, 0101, 1010, 0001].

5. Non-bijective functions

5.1. Non-bijective global rules and in-degree distributions

In Section 2.2, we have said that, in order to ensure bijectivity, we must first have a locally bijective CA, and furthermore, no two adjacent cells may fire simultaneously. Here is why:


We start with the effect of AS i= “” for the locally bijective ECA-57. We consider four adjacent cells and the effect of between the two middle cells, which are thus updated simultaneously, s=0110.


We obtain the patterns 0011 and 0101 twice, while missing 0001 and 0111. Hence the image is smaller than the full 24by 2 or by a factor 7/8 in general.

We have the following in-degree distribution (loss pattern 4 of [[10], Table 8]):

#(domain)#(range)In-degreeDistribution φ

Twelve patterns map bijectively (1,1) to 12 patterns, 4 patterns map 2:1 to 2 patterns, while 2 patterns of the range are not met at all (0,1).

We have #(domain) = in-degree×#(range) for every in-degree. Also, the overall sum is


Any additional simultaneous firing may increase the losses. Additional in-degree distributions (loss patterns) for ECAs and QCAs may be found in ([10], Table 8).

We restate Theorem 3 (i) from [14]:

Theorem 2.

We assume an ECA that generates at least the alternating group A2n, when using temporal rules from <>n\<n,>n. Let f:F2nF2nbe any non-bijective function on nsymbols, where we require n  4for ECA.

Let #w=vfv=wbe the number of configurations vleading to configuration w. Then fis clocking-computable by an ECA with in-degree distribution φ0,1,2=12,2,2or 24,4,4, if and only if


Proof. See [14], Theorem 3. □

5.2. Algorithm for non-bijective functions

The computation of a non-bijective function can be decomposed into 3 steps:

Step I. We start in the middle: Shrink the 2nsingletons of the domain to the desired distribution on the range. Find a sequence of elementary steps, necessarily including non-bijective ones, which generates the same distribution of counts in the image space as for the original function. Usually there are more than one of these sequences with the same complexity. Values/patterns as such do not yet play a role; therefore the requirements are usually easy to meet in a variety of ways, and the sequence of necessary elementary steps is short.

Step II. Bijectively map the input of the original function to the input of any of the results of Step I in such a way that the desired image counts are matched. Only the occurence counts must be observed, while, within this restriction, pattern values can be permuted.

Step III. Bijectively map the output from Step I to the output of the desired function, considering the flow within Steps II and I in that order. Now all values matter and cannot be permuted. However, this step takes place on a subset of size Imfinstead of 2n.

In Steps II and III we use the meet-in-the-middle approach, applying update rules starting both from the input (identity) and the desired function values to take advantage of the birthday paradox: In this way, 2#patterns are sufficient to generate ##=#potential matches in the middle (here #A2n), a considerable saving in both space and time.

5.3. Example of a non-bijective function
multiplication up to 3 × 3 = 9on the torus of size n = 4

The 4-bit input is interpreted as a pair of numbers from the set 0,1,2,3, whose product, the output, lies within the set 0,1,2,3,4,6,9.


5.3.1. Step I

The image consists of 7 patterns with occurence counts 7 (0000), 2 (0010,0011,0110), and 1 (0001,0100,1001).

In Step I, we thus have to shrink the set of patterns present from 16 to 7 in such a way that (any) 7 patterns are mapped to the same one, and additionally 3 sets of two patterns are joined within each set. Finally, the three remaining input patterns stay on their own.

An exhaustive search over sequences with 4 update rules, starting and ending with a non-bijective one, yields 72 such sequences with the desired shrinking factor, one example is the sequence s14=0011,1101,0110,0111of active cells.

All patterns in hexActive cellsOccurrence counts

5.3.2. Step II

After Step I, the output pattern 2 has frequency 7. Therefore, 2 has to match 0 in Step III, while 0,1,2,3,4,8,C are matched to 5,7,8,9,A,B,E in any order in Step II. Thus, we already have 7!different possibilities for Step II.

Similarly, we can maps 0110 and 1001 to either 14, 3C, or 6Fand so forth. Let crun through the occurrence counts, here c=7, 2 and 1 are actually taken, and let then pcbe the number of output patterns with in-degree c, here p7=1, p2=p1=3. We get


bijective functions consistent with the count distribution to choose from in Step II. One of these is given in the left column of Table 4.

Step IIStep IStep III

Table 4.

Steps II, I, and III for multiplication up to 3×3=9.

5.3.3. Step III

The outcome of Steps I + II completely fixes the necessary permutation for Step III. However, we do not have to deal with 2nvalues, but only Imfare relevant, in our example 7 instead of 16. Again, meet-in-the-middle yields a match. Be aware that the necessary effort does not drop from 16! to 7! but only to 16!167!11!or 2n!2nImf!in general.

In total, 13 + 4 + 15 = 32 steps are required to compute this multiplication function (Table 5).

INStep IIStep IStep IIIINStep IIStep IStep III

Table 5.

Steps II, I, and III by output patterns.

6. Efficiency

In the case of unfair bijective functions, any subset of cells may fire simultaneously, provided that no adjacent cells are contained in the set.

We define local efficiency of a bijective update sequence by two properties:

  • No cell is active during two consecutive time steps (these two would cancel each other).

  • No active cell can be moved to the previous time step.

Global efficiency—which shortest update sequence generates a certain function/permutation—is beyond the scope of this paper (it is dealt with implicitly by brute force in a breadth-first manner).

Lemma 3.

A sequence of rules is bijective and efficient, if skt=1(cell ckactive in step t)implies that.

  1. sk1t=0and sk+1t=0(both inactive),

  2. skt1=0(inactive), and.

  3. at least one of sk1t1and sk+1t1equals 1, active.


iis required for and then ensures bijectivity.

If skt1was active, both skt1and sktcould be removed, since each single-location action is an involution. Thus iiis required.

If sk1t1and sk+1t1were both inactive, the active cell sktcould be moved to skt1, maintaining bijectivity. Hence iiiis required. □

Using this lemma, we now can compute an upper bound on the number of bijective functions realizable with tupdate steps: We define a matrix Awith rows and columns indexed by the bijective elementary update rules, here named s1,s2,. Set aij1, if rule sifollowed by rule sjis efficient, aij0otherwise.

Let λnbe the largest eigenvalue of A.


Aijfor n=5:
s1= 000010100000110
s2= 000101011000000
s3= 001000100101000
s4= 001010100101110
s5= 010000010000101
s6= 010010110000111
s7= 010101011000101
s8= 10,0001000110000
s9= 10,0101011110000
s10= 10,1001100111000

Observe that 10,100 followed by 00001 is efficient, while the other way round 00001 leaves room to move s22up to s21. Hence, Ais not symmetrical for n5.

In Table 6, we denote several figures describing the number of efficient bijective update schemes (including unfair ones). The number of rules is denoted by #Sn; it can be found as A001610 in OEIS [18]; see also Section 2.2.2. The number of nonzero entries in the matrix A is #An. The quotient #An/#Snis the average number of 1’s in each row/column.

173570688,02419291.32196.4731.413e + 06313,092
1857771,519,586263124.57155.6993.008e + 06623,547
1993483,354,944358156.098156.3146.380e + 061.26e + 06
2015,1267,405,058489212.93281.3131.348e + 072.51e + 06
2124,47516,341,254667266.822250.5022.842e + 075.08e + 06
2239,60236,056,154910363.969118.3365.976e + 071.01e + 07
2364,07879,547,6161241456.085397.7581.253e + 082.04e + 07
24103,681175,485,4421692622.138171.9422.623e + 084.07e + 07

Table 6.

Efficiency related values for n=3,,24.

We denote by #ntthe number of effective bijective update schemes of length ton a torus of size n. Essentially, #nt=Θλnt.

Let ρn=limt#ntλnt. Then ρngives the constant hidden in the Landau symbol Θ.

We have #nt/λntρn1.



is the number of steps necessary such that #nTnA2n=2n!/2. Invoking the birthday paradox by the meet-in-the-middle approach, we therefore expect to require Tn/2steps each, starting from the initial identity permutation and backwards from the desired function, to achieve a match yielding the function evaluation.

The asymptotic behavior, as far as we can infer from the range n=3,,24, is



We can compare the asymptotic number Tnof elementary steps necessary for unfair update rules with the lower bound on the (full) steps for fair rules.

Lemma 4 ([10], Section 5, Lemma 1(i)).

There are clocking-computable bijective functions that require at least


steps or evaluations per cell.

Remarkably, as far as the experimental results for n24indicate, the number Tnof elementary steps is only a constant factor (2.4) higher than the lower bound for full update steps. If that result remains valid for all nN, and the reported values strongly suggest this, this would mean that the typical full step can be replaced by no more than 2..3 elementary unfair steps, independent of n.

As can be appreciated, n=5might be feasible for an attack by meet-in-the-middle, but n=6and above is certainly no candidate for this brute-force approach. Dealing with these sizes will require a more intelligent approach, for instance using group-theoretic techniques like representation theory, applied to the alternating group.

7. Conclusion

We have seen that many functions are clocking-computable, namely, the even bijective ones and the non-bijective ones with enough “loss” in their image.

The elementary cellular automaton ECA-57 can be used to implement an etherealware computing device: The computed function is a result only of the clocking order.

Temporal order of activating the CA cells is thus a new way to encode algorithms, a “volatilization of information”.

We increased the size for example programs from n=3in [10, 14] to n=4and are confident to also be able to tackle the case n=5.

From n=6onwards, we shall need more mathematical concepts, e.g., from group theory.


My thanks go to Dr. Mónica del Pilar Canales Chacón for proofreading, commenting, and all the rest. Furthermore, the anonymous referee gave valuable comments concerning the first draft of the paper, pointing out a substantial error and several occasions for clarifying the intended meaning.

#include <stdlib.h>

#include <iostream>

#include <fstream>

#include <iomanip>

using namespace std;

int main(int argc, char** args) {

     long long N = atoi(args[1]); // size of torus

     const long long EN = 1LL<<N; // 2^N

     long long ix;

     cout << “P00˽:=˽(“ << (1LL<<N) << “,1)”;

     ix = 0; // rightmost cell active, n=0

     for (long long i = 1; i < EN; i++) {

          if (((i ^ 1LL) > i) (((5LL<<(N-1LL))

                   & (i ^ (i<<N))) != (1LL<<(N-1LL)))) {

               cout << “(“ << i << “,” << (i^1LL) << “)”;


               if ((ix%6LL) == 0) {cout << endl ;}



cout << “;” << endl;

for (long long n = 1; n < N; n++) { // active cell/bit

     long long En = 1LL<<n;

     ix = 0;

     cout << “P” << (char) (0x30+((n/10)%10))

               << (char) (0x30+(n%10)) << ”˽:=˽(”

               << (1LL<<N) << “,” << (1LL<<n) << “)”;

     for (long long i = 1; i < EN; i++) // all 2^N patterns

          if (((i ^ En) > i) && (((0x5LL<<(n-1LL)) & (i ^ (i<<N)))

                    != (1LL<<(n-1LL)))) {

               cout << “(” << i << “,” << (i^En) << “)”;


               if ((ix%6LL) == 0) {cout << endl ;}



      cout << “;” << endl;

} // n

cout << “G” << (char) (0x30+((N/10)%10))

          << (char) (0x30+(N%10)) << ”˽:=˽Group(P00” ;

for (int n = 1; n < N; n++) {

     cout << “,P” << (char) (0x30+((n/10)%10)) << (char) (0x30+(n%10));


cout << “);” << endl;

//remainder, what to put interactively in GAP, no use as part of file

cout << “#IsNaturalAlternatingGroup(G“<< (char) (0x30+((N/10)

          << (char) (0x30+(N/10)%10)) << ” ); ” << endl ;

cout << “#IsNaturalSymmetricGroup(G“<< (char) (0x30+((N/10) %10))

          << (char) (0x30+(N%10)) << ” ); ” << endl ;

cout << “#Size(G“<< (char) (0x30+((N/10)%10))

          << (char) (0x30+(N%10)) << ” ); ” << endl ;


© 2018 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Michael Vielhaber (November 5th 2018). Hard, firm, soft … Etherealware:Computing by Temporal Order of Clocking, From Natural to Artificial Intelligence - Algorithms and Applications, Ricardo Lopez-Ruiz, IntechOpen, DOI: 10.5772/intechopen.80432. Available from:

chapter statistics

403total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Some Commonly Used Speech Feature Extraction Algorithms

By Sabur Ajibola Alim and Nahrul Khair Alang Rashid

Related Book

First chapter

BOLD fMRI Simulation

By Zikuan Chen and Vince Calhoun

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us