Cellular Automata by Rudy Rucker

A cellular automaton (CA) is a mechanism for modelling systems with local interactions. A cellular automaton is a regular lattice of cells with local state, which interact with their neighbours subject to a uniform rule which governs all cells. The neighbourhood (the set of cells whose state can affect a given cell at one instant) can be classified by the dimensionality of the automaton (most experimentation is done with one- or two-dimensional automata), and by the geometric fashion in which cells are interconnected.

The rule is the "program" that governs the behaviour of the system. All cells apply the rule, over and over, and it is the recursive application of the rule that leads to the remarkable behaviour exhibited by many cellular automata. When experimenting with cellular automata, one is primarily engaged in defining new rules which lead to interesting or useful behaviour.

Cellular automata appear to be abstract and devoid of practical applications, much as was said of computer graphics not long ago. If you want to model a universe which seems to be made up of particles which interact locally, there are two basic ways to go about it. The first is to create a huge array of numbers that represents the interacting items, then find the biggest number cruncher you can lay your hands on and set it gnawing away at the problem. The supercomputer boom, fuelled by applications of this approach to weather prediction, computational fluid dynamics in the transonic and hypersonic regimes, plasma dynamics, and an almost endless list of other applications testifies to the effectiveness of this approach.

But maybe there's another way. Until recently, cellular automata were primarily a theoretical tool. The price of a cellular automaton with uniform edge size increases as the nth power of its size, where n is the dimensionality of the cellular automaton. This gets out of hand rapidly, even if you're only working with two dimensional cellular automata. Therefore, although they may be the way the universe is really assembled and therefore worthy of study, no one would consider building one!

For cellular automata need only to find a concrete, compelling application to a real-world problem to burst into silicon and totally change the way we think about computing. Consider this: inside the computer you're using now are ranks and ranks of RAM chips. A 256K×1 static RAM chip has a memory cell consisting of four to six transistors, connected in rows and columns to circuitry on the periphery of the chip. Even when the computer is running flat-out, you're using precisely one cell at a time. This is the classic bottleneck in the von Neumann computer architecture (John von Neumann was very aware of this problem; in fact, he and Stanislaw Ulam invented cellular automata precisely as a tool for modelling complex systems), which has led to proposals such as Backus' functional programming, neural systems, and many other architectural proposals, such as SIMD machines, which seem to be more effective ingenerating Ph.D.s than numbers.

If a two-dimensional cellular automaton with 256K cells were realized in silicon, it could compute 262,144 times faster than a serial processor accessing data bit-by-bit from a memory array. Yet, engineered for volume production, made in comparable volumes, and given time to slide down the learning curve, it need cost no more than a RAM chip. This is the potential of cellular automata. The beauty of two-dimensional cellular automata is that they map perfectly into our semiconductor manufacturing technology: they need the things it does best as opposed to, say, neural systems where the number of connections exceeds the capability of two layers of metal.

Some of the brightest minds of our century have been involved with cellular automata because they comprehended what cellular automata can do. John von Neumann, Stanislaw Ulam, John Horton Conway, Stephen Wolfram, and Edward Fredkin do not spend their time on nonsense. With CA's, you can begin to explore the potential that attracted those men to create and research this new way to compute.

The human mind works a lot better than blind search (one imagines a middle manager reporting, "Nothing much yet-we need more monkeys, more typewriters."). CA's unleash your creativity in a virtually infinite domain, where your discoveries may be not only interesting or rewarding, but may create a whole new world. The challenges in cellular automata are clear: how to realize them in hardware, how to apply them to useful tasks, and how to make money doing it. Rudy Rucker

We created a cellular automata model to mimic the waves of excitable energy (pressure) that pass through a crowd and waves of electrical energy that pass through the cells of heart tissue. It can also be used to model how information passes through a system such as a financial market.

What is interesting is the effect of a defect such as an area which does not propagate the wave front. This can be either a gap/hole in the lattice or an area where the cells do NOT propagate their information.

Below we can see the "shadows" in the wave front caused by the defect.

Using this type of model I calibrated the fractal analysis technique by producing a range of defects types and monitoring the resultant pulse train as it passed through the lattice. From that source I could then compare the heart data from patients samples.

This mapping process (when displayed as a phase space diagram) produced a surprisingly high correlation to the patient data in a field trial. Click here for Heart Rate Analysis.

If you want further information - click here to send email

Visitors