X-Message-Number: 4405 Date: Mon, 15 May 1995 23:14:03 +0200 (MET DST) From: Eugen Leitl <> Subject: RandomRamblingsII cot'd One final effort: the (strange) attractors in CA spaces. In physics, the concept of _state_ or _phase space_ is used to visualize the temporal _evolution_ of a system. The total state of a system at time t is entirely represented by a single point in n-space, e.g. 6N-dimensional (three position coordinates and three momentum coordinates for each particle) for N unconstrained particles. A _Hamiltonian_ (the rule in our terminology) defines a vector field, a mapping on that system. Differently put, the Hamiltonian is an _energy gradient_, a pathway for a system to slide towards a (local) minimum. In our version of finite binary integer CAs with quantized time, each vector at t is mapped by the rule to the future vector at t+1. Nothing new, so far. Now consider a initial _region_, a contigous block of vectors. Each element of the block at t gets mapped by the rule to another set of elements at t+1. Obviously, the _volume_, the total number of cells in a given region cannot grow bigger, it can shrink or remain constant, at most. Due to the Liouville theorem a true Hamiltonian system's region volume remains invariant (constant) during temporal evolution (note that the CA rule is a superset of a Hamiltonian as it does _also_ allow volume reduction). This has profound implications: for a majority of systems the elements of an contigous regions diverge with each evolution step, loosing their coherence they are getting spread over increasingly larger volumes. The extreme cases of this system behaviour is referred to as _ergodic_. The "gas" phase type CAs are excellent specimens of this behaviour. As a minimal disturbance in the starting vector produces a maximal deviation within a few iterations, the gaseous CAs are thus an excellent illustration of the "butterfly" effect. Another important theorem states that exists only one _trajectory_ to pass through each point of the state space. The _periode_ of the trajectory, the number of transitions until the randomly walking vector hits upon itself by chance is _very_ long in high-dimensional CAs (there are a great many directions to go). This property, coupled with the lack of attractors/high path entropy at equidistributed statespace point visit probability makes this class for CAs particularly attractive for cryptography. A truly ergodic system performs a random walk through its state space with the probability of visiting each point being equidistributed. Additionally, the systems's evolution velocity (the fraction of transition length over time step) along its trajectory using the euclidian distance metric (square root of the sum of quadrates of the element's differences) gets increasingly evened out with increasing size of the space, the mean translational velocity is roughly a constant. The bigger the system, the less detectable is the individual's contribution to the whole picture, an obvious parallele to the "billiard table" ideal gas picture. Though subsystem components may experience vigorous brownian motion, the whole system stands rock firm. One should remark, however, that for Morse-modulated-potential-type ideal gases boxes there _are_ constraints, as introduced by the shape of the potential function. One can calculate some kind of crazy Schroedinger-square, telling which points are likely to be visited and which not. A system can also be seen as a state-space balett of interacting subsystems of smaller dimensionality, choreographed by higher-order rule. Particularly, using binary subsystem clustering may appear constructive in implementation/analysis. The dull_1 (solid) CAs are remain trapped in single points or constrained to tiny volumes ping-pongying to and fro. If we start to melt the solid rule, thus drawing nearer and nearer to the liquid phase edge, the traversed regions become increasingly larger and larger, the paths more and more complex. A liquid system may stay liquid for a long while or make an expedition into the chaos region, either to stay there indefinitely (there is no way to tell) or returning back, eventually. It might also freeze out, remaining trapped in a solid forever. A typical liquid CA will also show special points (typically, many), called _attractors_, around which on complex trajectories the system will revolve. In a finite system, several convergent paths will congeal into a single one, which might eventually be trapped in a single point, the attractor. (This would never happen in a continous system, of course). The entire volume belonging to converging trajectories is called the _basin of attraction_, a simile to basins of drainage in a montainous massive. A system, released within its basin of attraction, will remain there forever, unless disturbed by an outside force. Two basins of attraction are meet at a ridge, called _separatrix_, a region with one degree of freedom fewer than the number of variables in the system. Instead of being a point, an attractor might be a loop, a toroid (of course, it's higher-dimensional analogues) or any such thing. Moreover, there is a class of _strange_ or _chaotic_ attractors. Their main property is that two very close systems let loose within the basin remain on the attractor surface but float forth _diverging from each other_. Tiny initial deviations gets amplified with time. For obvious reasons, real systems featuring these strange attractor (or ergodic) property are virtually noncomputable as they would require infinite precision both at measurement and simulation stage. Both are unattainable. The main distinction between ergodic systems and these containing strange attractors is that a strange attractor/its basin is tiny in relation to the total statespace size. By now you must think I must be strangely attracted to those attractors, but these beasts are actually useful. There is _heavy_ experimental/theoretical evidence (both direct and indirect) that the brain uses state-spaces and generic mappings (coordinate transforms) to represent and process information (see Churchland for an excellent introduction). Particularly, the existance of attractors in the EEG ascertained (Nicolis/Prigogine). Most, maybe all, part of machinery of the brain does calculations utilizing trajectories and attractors in state space according to Churchland et al. . Actually, I believe any system (including us) which does any kind of computation/life must be an edge-of-chaos one to be efficient. Our computers, alas, reside quite firmly in the solid region. 4.2 What Are They Good For? A good question. Are CAs just another irrelevant theoretical construct? I think not. - CAs are great for applied cryptography, both for rnd-stream and public-key. Sadly, CA are largely unknown among cryptographers as yet. - CAs are great for efficient modeling (e.g. fluid dynamics), reducing the amount of necessary computation by many orders of magnitude. A modest fluid dynamic package will run on a PC in realtime. (I've seen some). Systems with purely local interactions (essentially all systems fall within this class) and (best) a noticeable number of constraints are prior candidates for CA modeling. Sadly again, most scientists haven't heard about CAs yet. - neural nets (NNs) are special cases of CAs, which are special cases of automata networks (ANs). Knowledge transfer seems to be possible. - CAs and ANs are great for self-organization and non-linearity science. Intuitive reasoning and/or a well-developed body of mathematical machinery is readily available. - CAs can help up to understand embryonal morphogenesis. - CAs are great toy systems for artificial life (AL). - A family of CAs is computationally universal. They compare favourably (in time/space-complexity) to the Turing machine/von Neumann architectures. CAs might be computationally equivalent to Turing engines, but not in terms of time complexity. Their implementation in silicon is straightforward. Achievable computing power with the same transistor resources is several orders of magnitude higher than current architectures. Being redundant arrays of identical, extremely primitive elements, they are the major candidates for molecular electronics implementations. Achievable integration density and computation performance are of all architectures the highest theoretically possible. - CAs are interesting candidates for universe theories. They mimic a lot (reversibility of the time arrow, particles, light speed, anthropic principle, edge of chaos theories, information conservation, etc.) of the real-world properties. 4.3 A Recipe for a CA XOR-Rnd-Stream Cryptosystem. - Choose a CA which does very good rands. Most CAs from the gas region will do nicely. - Define all the boundary conditions. Code it. - Choose a random space vector as initial key. Give the key to your partner via a safe channel. - XOR your data stream with CA output stream to obtain cypher text. Your partner does the same to retrieve plain. Of course, this works also the other way round. Why bother? CA's form a _family_ of random generators, which are well-behaved, produce excellent rands and run fast even on von-Neumann machines. Internet nodes will be able to crypt TCP/IP packets individually via a different crypt for each target node. Routine eavesdropping will become much more difficult this way, as the cryptoattacker will have to know the right crypt method for each packet. Since crypt is transparent (hidden somewhere in the lower OSI levels), top level applications could (and should) use a different/better cryptosystem, such as: 4.4 A Recipe for a CA Public Key Cryptosystem. - Search CA (automaton network space, actually) space (_not_ rule space) for a cryptography-suitable automaton family. Choose one member. Implement it in C, give away code. Invite people to try cryptoattacks. - Fill rule table with very good rands. Do _not_ use compiler built-int rands. Hardware rnd generator or another CA may do. - Construct the inverse rule. - Decide, which rule table to be your public key. Give it into the net. Keep the other in your safe. All data sent to you, transformed n times (you must agree upon how many) with your public key can be only decoded applying your private key n times. All data encoded by your private key, can be only read with your public key. You want to know whether the sender is the person it purports. Choose a big pseudo random number (best CA rnds, again), encode it with your friend's public key and send cypher to the pretender. Pretender codes the number with its private key, then sends it back to you. You decode it using your friend's public key. Is the obtained the same random number you chose initially? If yes: Pretender=Friend. Bingo! No? Pretender=bad guy. Call the police! Why bother, again? Robust trapdoor cryptosystems with two inverse keys are not exactly frequent in cryptology. The only one I know of is based on large prime factoring, is supposed to be breakable with a finite effort (and might become even more fragile with further advances in number theory). Moreover, it takes a lot of horsepower to compute. Using CAs might come quite handy here. 4.5 Two Simulations \ 4.5.1 Fluid Dynamics \ though extremely interesting 4.5.2 Protein Folding / these chapters are ommited due / to lack of relevance to uploading If there are doubts CAs to be instrumental for large-scale scientific simulations I will supplement. --- to be continued ---------------------------------------------- Literature/References [1] Roger Penrose, "The Emperor's New Mind", Vintage (1990). [2] Stephen Hawking, "A Brief History of Time", Bantam (1989). [3] Hans Moravec, "Mind Children", Harvard University Press (1988). [4] Stuart A. Kaufmann, "The Origins of Order", Oxford University Press (1993) [5] Gregoire Nicolis, Ilya Prigogine (ed.), "Die Erforschung des Komplexen", Piper (1987) [6] Dawkins, "The Blind Watchmaker", (1986) [7] R. Vollmar, "Algorithmen in Zellularautomaten", B.G. Teubner Stuttgart (1979). [8] G. E. Gorelik, "Rasmernost' Prostranstva", Isdatel'stvo Moskovskogo Universiteta (1983). [9] Andrew Hodges, "Alan Turing: the enigma", Vintage (1992). [10] Koch/Segev (ed.), "Methods in Neuronal Modeling", MIT Press, 2nd printing (1990) [11] Yoh-Han Pao, "Adaptive Pattern Recognition and Neural Networks", Addison Wesley (1989). [12] Igor Aleksander (ed.), "Neural Computer Architectures", North Oxford Academic (1989) [13] Paul M. Churchland, "Representation and high-speed computation in neural networks" in "Foundation of artificial intelligence, a sourcebook", by Derek Patridge and Yorick Wilks, (ed.), Cambridge University Press (1990). [14] P.W. Atkins, "Physical Chemistry", Oxford University Press (1987) Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=4405