Acta Biotheoretica 40: 195-204, 1992. © 1992 KluwerAcademic Publishers. Printed in the Netherlands.

MODIFIABLE AUTOMATA SELF-MODIFYING AUTOMATA

J.-P. Moulin L a b o r a t o i r e de R e c h e r c h e e n I n f o r m a t i q u e (L.R.I.), Universit6 Paris Sud Orsay.

ABSTRACT One of the most important features of living beings that seems universal is perhaps their ability to be modified in a functional way. In order to modelize this characteristic, we designed automata with a finite number of instantaneous internal descriptions, with input(s) and output(s) and which are able to be functionally modified. The rules which govern the evolution of these automata (and the initial conditions) are randomly chosen at the beginning and once and for all. When such an automaton is linked by its input and output to a deterministic process, it always stabilizes and it then has the property to rebuild itself. Thus it made a function which is inverse of the external function. We demonstrate the prevalence of p = 1 length period and of r = 0 transient length for automata with m instantaneous internal descriptions.

1. INTRODUCTION O n e o f the m o s t i m p o r t a n t , p e r h a p s universal, features o f living b e i n g s is their ability to b e m o d i f i e d in a functional way. In o r d e r to m o d e l these characteristics, we designed asynchronous deterministic systems linked b y their input(s) and output(s) to a deterministic process and w h i c h are

capable to be functionally modified, T h e initial c o n d i t i o n s and the rules g o v e r n i n g the d e v e l o p m e n t o f these systems are randomly chosen. T h e s e systems always stabilize and then h a v e the p r o p e r t y to m a i n t a i n their program. T h i s k i n d o f stability explains the s e l f - p r o g r a m m i n g properties o f living b e i n g s in a g e n e r a l w a y a n d o f the n e r v o u s system in particular.

196

1.1. Functional modifications of living beings An essential property of living beings is their capability for functional modification whenever stimuli occur. The neuron has two simultaneous functions: to transmit the nerve impulses and to modify the transmission of the nerve impulses. When a sensory organ sends impulses through the nervous system, the transfer of the subsequent impulses is modified. Authors have shown that the spatial organization of the neurons in the kitten's visual cortex is set up by the nerve impulses its brain receives from the retina in the first weeks o f its life (Kalil et al., 1986). Usually, scientific models use stable functions. Apart from Kahlmann's filters and all adaptative systems, e.g. neural networks, the circuit remains the same after the signal has gone through it.

1.2. Capacity to self-programming Living beings have the capacity to: A. Understand a new message In the telecommunications domain, data transmission between an emitter and a receiver always presupposes a coding convention, whereas living beings find a meaning in the message while having no knowledge of the emitter's cipher. A meaningful example is to set Dove's prisms in front of both eyes of a man. These devices inverse vision: the left side becomes the right one, and the top part of the visual field becomes the bottom part. After a few weeks, the landscape is normally perceived (Gonshor & Melvill Jones, 1976). B. Have appropriate reactions Let us quote the following experience: one cuts an ape's ocular muscles, crosses them and then sutures: The oculo-motricity is then reversed, i.e. when the animal wants to look to the right side, the eyes turn toward the left, and a command to turn toward the top adjusts toward the bottom. After a few weeks, ocular motility and balance of the animal are normal. Our examples are chosen in the field of neurology which is more familiar to us; we could also have quoted convincing examples in other domains such as the ability of the reticulo-endothelial system to synthetize antigens, of white ants to dig their gallery according to the galleries they have already dug, or even of the ability of plants to react in an appropriate way after complex mechanical stimuli. It seems that living beings possess the capacity to program themselves without any programmer (self-programmation). This self-programming property should be explained by the particular type of stability of functionally modifiable systems.

1.3. Other modelizations A. Some authors have studied the dynamics of automata networks where connections and truth tables are randomly chosen at the beginning and once and for all, which implies that internal rules remain fixed (Quenched model) (Kaufman, 1969;

197 Fogelman Souli6, 1985). B. Other authors have studied the dynamics of automata networks where rules are randomly modified at each step. (Annealed model) (Derrida & Stauffer, 1986). C. The recent connectionist models (threshold automata networks) (Fogelman Souli6, 1985) are networks where automata are functionally modified by inputs, but the program which functionally modifies the networks is outside the network (back propagation of the gradient for example). According to our views, we would prefer this network, which is functionally modifiable by its inputs to stabilize by itself. D. Finally, von Neumann (1966) and other authors (Codd, 1968; Thatcher, 1965; Greussay, 1988) have built self-reproducing automata, in order to continue von Neuman's last work. In this paper, we introduce a new framework which will allow us to model those properties. We present self-modifying automata (SMA) in section 2 and their dynamics in section 3, we then introduce modifiable automata (MA) in section 4 and show their equivalence to SMA in section 5. Section 6 gives results on the dynamical behaviour of MA.

2. SELF-MODIFYING AUTOMATON (S.M.A.) 2.1. Components Let 5irbe the set of mappings applying to N into N. (N is the set of integers)

~r= (f: N -- N} 1. Let ~ be the subset of o~rcontaining the mappings of ~rapplying a finite subset of N into A. ~rA = {f: A --- A} 2. We call s the set of ranges of mappings of ~A. s=

Uf(A)

s c A according to the very definition of "~A. 3. We call encoding mapping a function C from s into ~ :

C:s--,~ 2.2. Functioning We now define a self-modifying automaton (SMA) as a mapping A from ~ x A into itself by: Al(ft,e~ = (ft+l,et+l) = [C o ft(e0,ft(e0]

(1)

198

I c

I

f,.l I f,

et

input

ea+t

output

Note that A~ only requires C for its definition.

3. DYNAMICS 3.1. Initialisation At the beginning of the process and once and for all: 1. We randomly build the mapping C creating an arbitrary correspondence between the elements of the set s and the mappings of the set ~A" This defines a SMA A~. 2. We randomly choose an element (fo,eo) of the set ~AAXA.

3.2.

Trajectory

The behaviour of the self-modifying automaton A~ is characterized by a trajectory composed of points (ft,%) of the set ~AXA.

3.3. Convergence Let (fo,eo) E ~ × A

be the initial point of the trajectory.

Definition. A self-modifying automaton converges whenever a point of its trajectory (fk, e0 is identical to a previous point (fk-p, %-p). It then indefinitely goes through a limit cycle composed of the point (fk, e0 and (fk-p, ek-o)A self-modifying automaton is a deterministic device, and the cardinality of set ~AA× A is finite. Therefore such an automaton necessarily converges. We will study two values: 1. The length p of the limit cycle; i.e. its period. 2. The transient length 7" = k-p.

3.4. Fixed point We call fixed point a cycle of length p = 1. Ending in a fixed point is the most frequent event as we shall see further: Let (f,e) E ~A × A The sufficient condition for (f,e) to be a fixed point is:

199 f(e) = e) C o f(e) = f

(2) (3)

Combining expressions (2) and (3), we obtain: C(e) = f

(4)

Let us consider the transformation C-l: C-'(f) = {s E s : C(s)=f} ( 4 ) ~ e E C-I(f) Hypothesis: From now on, we suppose that C-~(f) is identical to {e}: c-'(f) = e

(5)

Substituting value e of equality (5) in (3), we infer: m

C o f o C-l(f) = f

] I

4. MODIFIABLE AUTOMATON (M.A.) 4.1.

Definition

In the previous description, the output value of the self-modifying automaton is reentered at the input: e t st_I. Let g be an element of the set ~ defining a combinatorial automaton (G). Its input value eCA and its output value SeA are linked together by the mapping g: =

ScA= g(ecA) Let us connect a self-modifying automaton with the fixed external automaton (G): et = SeA and ecA = st. G will play the role of an external source, e.g. environment, sending signals to the SMA.

c~ New mapping ft+l [ Input

[

Mapping ft

I Output

ea

st External world: Combinatorial automaton

g SCA

eCA

200 W e can write:

Cof,(e,) =

(6)

LI g o ft(e0 = et+ l

(7)

These equalities define a new dynamics D: D ( f t , e t) = (ft+l,et+l) = [C o ft(et), g o t~(et)l

4 . 2 . F i x e d point W e can write:

(8) (9)

s, = f, o g(s~_,) c ( s o = f,+,

Icl s Let uw suppose that (f,e) E ~ × A s. T h e n the equalities (8) and (9) become:

defines a fixed point, and let f(e) be equal to

s = f o g(s) C(s) = f

(10) (11)

Let us consider as before the transformation C-1:

c - ' ( 0 = {s ~ s : C(s) = f} (11) = s E

c-l(f)

Hypothesis: W e suppose C -~ (f) to be identical to {s}, then we can write: s =

Cl(f) W e eliminate s in equality (10): C-l(f) = f o g o C-l(r")

(12)

and we finally get: C o f o g o C-l(f) = f

5. S E L F - M O D I F Y I N G A U T O M A T O N E Q U I V A L E N T MODIFIABLE AUTOMATON

TO A

The same notation as in the previous paragraph will be used here, except for a new encoding mapping e 2 which is defined as follows:

v s E s, C2(s) = C(s)o g

201 Equalities (8) and (9) of the previous paragraph now become:

st = f, o g(st-0

(13)

C2(s0 = C(s0 o g = ft+l o g

(14)

The equalities (13) and (14) define the dynamics .42: A2(ft o g, st_,) -- (ft+, o g,st)

= ICE o f,

o

(15)

g(St_l),ft O g(s,_,)l

Suppose that in equality (1) of paragraph 2: A,(ft,et) = (f,.t, et.,)

(1)

= [C 0 f,(et),ft(e,)] we replace et --" st_i, f~ --) fto g and C --- Ca, then we obtain (15). Therefore the dynamics At of the self-modifying automaton is identical to the dynamics A= of the modifiable automaton connected with a combinatorial automaton.

Fixed point. Using the same method as in paragraphs 3 and 4, we obtain the equality characterizing a fixed point:

C2 o g o f o C~t(g o f) = g o f

6. PERIOD A N D T R A N S I E N T L E N G T H OF MA 6.1. Stabilization after k changes of input value Let B A be the class of all M A on the set ~AXA of cardinality m. By choosing, for each MA, its associated function C at random, we endow BA with a probability distribution. We are interested in various probabilities within that class BA. Let us first denote Prt(m,k) the probability for a M A in class BA to stabilize after k steps. That M A will necessarily have its first k points different and the k + l th point identical to one of the previous points. By evaluating the probabilities of the various events, it is easy to show that: Prt(m,k) = [ ( m - 1 / m ) l l ( m - 2 / m ) l . . . I ( m - k + l / m ) l l k / m l =

Prl(m,k ) = P(m,k)*k / m k+l

where P(m,k) represents the number of arrangements of m objects taken k by k. It is possible to show that the distribution Prl(m,k ) has its maximum for k = m 'a. We display below an example of Prl(m,k) for m = 16:

202

0,2

I

o I, l 0,0

I l

I,

II,

. . . . . . . . . .

Y-llxis:Pr I (m,ofk)k X-axis"values I,u,

,

,-,-,-,

1 2 5 4 5 6 7 8 9 10 11 12 15 14 15 16 This figure shows that: Most probably a M A will stabilize after very few states.

6.2. Stabilization in a loop o f length p after a transient length 7" k being given, the period p can take any of the k values on [1,k] while 7" takes any o f the k values in [ 0 , k - l l . Let us consider a M A stabilized in a limit cycle after k changes of its input value. The probability in the set of all possible M A for this event is equal to Prl ( m k ) . Then the k + 1 th point is equal to one of the k previous points. Let us call e~, the event "stabilization in a limit cycle of length i after k changes of the input value" and Pr(ea0 the probability of event e~, in the class BA of all MA. Then Pr(etk) = Pr(~20 = ... = Pr(c-~_,) = Pr(e,k) because all stages in [1,k] are equally probable candidates for being reentered at step k + 1. ~lkfhezkfh ... Aekk_l~ekk = 0 / a n d Pr(e,0 + Pr(ez0 + ... + P r ( ~ _ , ) + Pr(e~) = Pr,(m,k) Therefore, Pr(~,k) = ... = Pr(ek-10 = Pr(qd,) = Pr,(m,k)/k. Let us call Prz(m,p) the probability of period p in the class of M A on a set ~ × A of cardinality m . Then the distribution Prz(m,p) is obtained from P h ( m , k ) :

m

Prz(m,p) = ~ ] Pr,(m,k)/k = k~p

P(m,k)

*

~ tk+l

k=p

By a similar reasoning we obtain the probability of transient length z in the class

B A.

m-I

m-I

Pr~(m,z) = ~ Pr,(m,k)/k = ~ P(m,k) * mTM k=r

k=,r

203 W e display below an example of Pr2(m,p), and Pr3(mo') for m = 16:

0.4 ] •

Y-sxis: Pr2(m, p) end Pr3 (m. ~) for m = 16

0,20.3

°01 •

0 1

1 2

2 3 :5 4

4 5

5 6

6 7

7 8

8 9

9 l0 11 12 15 14 15 X-axis2: values of 10 11 12 15 14 15 16 X-axis l: values of p

This figure shows that most MAs will enter a limit cycle after a very short transient time (85 % of chance to enter a limit cycle after only 4 iteration steps). Furthermore, the period of the limit cycle will be very small (85 % of chance to have one smaller than 5). These stabilisation properties do arise for small values of m. For larger values, the distributions tend to be uniform. This implies that self-programmable automata must operate on reduced dimensions sets A. In that case, a M A most probably will stabilize in a fixed point.

8. C O N C L U S I O N W e have shown: - The equilvalence between self-modifying and modifiable automata. - The prevalence of p = 1 length period and of T = 0 transient length for automata on low-cardinality space. This work demonstrates that the self-programming capability can be obtained easily from the dynamical behaviour of modifiable automata on low-cardinality space.

REFERENCES Codd, E.F. (1968). Cellular Automata. Academic Press. Derrlda, B. & D. Stauffer (1986). Phase transition in two-dimensional Kauffman cellular automata. Europhysic letters 2: 739-745. Fogelman Souli6, F. (1985). Th~se. Grenoble. Gonshor, A. & Melvill Jones, G. (1976). Extreme vestibulo-ocular adaptation induced by prolonged optical reversal of vision. J. Physiol. London 256: 381-414. Greussay, P. (1988). Self-reproducing automata. Lecture at I.R.C.A.M. June 1988. Hopcrott & Ulmarm (1972). Introduction to the Theory of Languages, Automata and Computation. Addison Wesley. Kauffman, S.A. (1979). Metabolic stability and epigenesis in randomly contructed genetic nets. Theoretical Biology 22: 437-467.

Kalil, R.E., Dubin, M.W., Scott, G. & Stark, L.A. (1986). Elimination of action potential blocks the structural development of retinogeniculate synapsas. Nature 323: 156-158. Thatcher, J.W. (1965). Self-describing turing machine and self-reproducing cellular automata. In: A.W. Burks, ed. Essays on Cellular Automata, p. 103-131. University of Illinois Press. yon Neumann, J. (1966). Theory of Self-Reproducing Automata. University of Illinois Press.