2. Numerical Solution

3. Memory Effects

The natural framework to model autonomously updated Boolean systems is the Boolean Delay Equations (BDE). It expresses the evolution of *n* Boolean variables *x _{i}* as functions of the values of those variables at past times:

(1) | x_{1}(t) = f_{1}(t, x_{1}(t-τ_{11}), x_{2}(t-τ_{12}), … , x(_{n}t-τ_{1n})) |

(2) | x_{2}(t) = f_{2}(t, x_{1}(t-τ_{12}), x_{2}(t-τ_{22}), … , x(_{n}t-τ_{2n})) |

⋮ | |

(3) | x(_{n}t) = f(_{n}t, x_{1}(t-τ1), _{n}x_{2}(t-τ2), … _{n}x(_{n}t-τ_{nn})) |

where the functions *f _{i}* are Boolean valued and the time delays τ

To illustrate the rich behavior that may be described in this framework, let us assume that the functions *f _{i}* are autonomous (don't depend explicitly on time) and linear, which in the definition given by Ghil and collaborators [4] means

(4) | f(_{i}x_{1}(t), _{1}x_{2}(t), … _{2}x(_{n}t)) = _{n}c ⊕ ∑_{i0} 1 ^{n}_{j =}c(_{ij} x_{j} t ), _{j} |

The simplest case is the XOR element with two delayed inputs:

(5) | x(t) = x(t-τ_{1}) ⊕ x(t-τ_{2}), |

Fig. 1: Diagram for the XOR with two delays. |

Without loss of generality, assume τ

To calculate a trajectory, we construct a queue of the times *t _{m}*, at which transitions occur. When

The above algorithm is implemented below, using the Python interpreted language (version 2.x), which is very similar to a pseudo-code description or a Matlab or Mathematica script. The code uses the decimal module to calculate fixed point arithmetic in base 10 with arbitrary, user-specified precision. (Right click here and choose "save link as" to download the code as a text file).

""" Calculates the transition times for the XOR with two delays with arbitrary precision """ #imports from decimal import * import os #constants Prec = 12 # number of decimal places getcontext().prec=Prec iterations = 1000 # counts the number of transitions Verbose_level = 1 # 1 = normal messages, 2 = debug mode, 0 = silent mode # tau1 = 1 tau1 = Decimal(1) # tau2 = 1/phi , the golden ratio tau2 = Decimal(2)/(Decimal(1)+Decimal(5).sqrt()) # Minimum allowed pulse width w_min = Decimal("0.000") # choices of initial conditions: #ic = Decimal(0) ic = -tau2 #tn = [ic-max(tau1,tau2),ic-min(tau1,tau2),ic] tn = [ic] # list of transitions # The programs starts here: # open outputfile f = open("xor_2delays_"+str(Prec)+"digits.dat",'wt') if Verbose_level>0: print "output file: ", "xor_2delays_"+str(Prec)+"digits.dat" f.write("#tau1 = %s, tau2 = %s\n" % (str(float(tau1)), str(float(tau2))) ) f.write("#Prec = %d, iterations = %d\n" % (Prec, iterations) ) # main loop: for i in range(iterations): collided1 = False collided2 = False # calculates the two candidates of future transitions from the first tn # using tn[0], instead of min(tn), could be faster next_t_candidate_1 = min(tn)+min(tau1,tau2) next_t_candidate_2 = min(tn)+max(tau1,tau2) if Verbose_level>1: # optionally prints debug information # print "Processing ", min(tn) # print "list = %f " % tn[0], # for t in tn[1:]: # print ", %f" % float(t), # print "\nt1 = %f, t2 = %f" % (next_t_candidate_1, next_t_candidate_2) # if len(tn)>0: # if we have transitions in the list ... for t in tn: # ... checks, for all of them, if they collide ... if (abs(next_t_candidate_1-t) <= w_min): # ... with candidate 1 ... collided1 = True # remembers a collision occurred if Verbose_level>1: print "removing ", float(t) tn.remove(t) # removes colliding transition else: if Verbose_level>0: print "empty list, stopping now" f.close() exit() if len(tn)>0: for t in tn: if (abs(next_t_candidate_2-t) <= w_min): # ... and/or candidate 2 collided2 = True # remembers a collision occurred if Verbose_level>1: print "removing ", float(t) tn.remove(t) # removes colliding transition else: if Verbose_level>0: print "empty list, stopping now" f.close() exit() if not(collided1): # if the first candidate did not collide if Verbose_level>1: print "saving transition at", float(tn[0]) #f.write("%s\n" % str(float(tn[0]))) f.write("%s\n" % str(tn[0])) # saves generating transition as good one tn.append(next_t_candidate_1) # appends the good candidate do the list if not(collided2): # if candidate 2 did not collide tn.append(next_t_candidate_2) # appends the good candidate do the list if collided1: # if candidate 1 collided, we haven't saved the good transition yet if Verbose_level>1: print "saving transition at", float(tn[0]) #f.write("%s\n" % str(float(tn[0]))) f.write("%s\n" % str(tn[0])) # saves the transition now tn = tn[1:] # removes the processed transition tn.sort() # sorts the list, to make sure of the right ordering # we have almost finished after the main loop f.close() if Verbose_level>0: print "finished!"

The resulting time series can be displayed in gnuplot, for instance, using the following commands:

> set style data steps > set xlabel "time" > set ylabel "x(t)" > set xrange [-0.5:13] > set yrange [-0.1:1.1] > parity(n) = (n/2>floor(n/2)) ? 1: 0 > plot "xor_2delays_12digits.dat" using 1:(parity($0))

Fig. 2: Segment of a time series from the XOR with two delayed inputs. |

As discussed in the references [4], the number of transitions per unit time may grow without limits in the Boolean delay equation we just presented. This behavior is not expected to occur in physical systems, because finite response speed of the logic elements prevent two transitions that come in a too fast succession from being processed. In the program above, this memory effect, called pulse filtering or short-pulse rejection, is controlled by the parameter w_min, which sets the minimum allowed interval between two processed transitions. In the particular w_min = 0 there is no pulse filtering (except for transitions that are rigorously identical, up to the specified precision), and the number of transitions per unit time may grow until it reaches the resolution determined by the specified time precision. Whenever a non-zero short-pulse rejection is considered, the XOR system will end up in a periodic orbit, but the period may be very long. Other memory effect are discussed in the next section.

As discovered in experiments and proved in Ref. [5], deterministic chaos is only possible in simple Boolean networks when another memory effect is present: the degradation effect, which bears its name from the distortion caused in short pulses when they propagate through digital electronic gates. The delay time for a transition depends on the time that the Boolean element remains in it previous state. To model the degradation effect, we start calculating transition candidates, as described in the previous section, for a given candidate *t _{m}* we calculate the pulse width

Another memory effect observed experimentally is the asymmetry between the delays for rises and falls, as if the logic elements remembered whether the state before a transition is 1 or 0. This can be taken into account using a piecewise constant term in the degradation function *g*(*p*) described above, whose value depends on the logic state *x*(*t*) immediately before the transition, or equivalently, on the parity of the number of transitions. With non-constant time delays, care should be taken to prevent the trailing edge of a pulse to overtake the leading edge. This situations should be identified by a negative pulse width.

The author(s) do not assume any responsability for the use of the programs or algorithms presented here.