Examples of cellular automata that perform real-world tasks

Question

I've been reading about one-dimensional cellular automata and am intrigued with the idea that they can solve real-world problems.

However, I have not found a single example.

I'm not talking about approximations of prey-predator populations since they just look like what we think a population should look like - I am unaware of any real basis in reality.

Instead, I'm talking about something measurable. Is there an example that adds? Multiplies? Pattern-matches?

Or do automata that do these sorts of things require scads of special case rules that violate the simplicity of the concept?

Answer 1

This Wireworld computer computes prime numbers:

http://www.quinapalus.com/wi-index.html

Answer 2

I've been using cellular automata to create some very interesting fractal art:

With each iteration, I've magnified the original image, and then applied a cellular automaton rule by hand after each magnification. In theory, at least, it would be possible to write a computer program that would replicate these images that I've created by hand.

My own profile picture is another example of a fractal that I have created using cellular automata - this fractal generation technique is very straightforward, but it could possibly be used to create very convincing fractal landscapes for video game terrain generators.

Answer 3

Check out http://is.ifmo.ru/english/ (Most of the website is in Russian; you can use automated translation, I suppose.) I know professor Shalyto personally. He has spent many, many years doing research on various applications of finite automata including cellular automata. In particular, he has worked with many very bright computer science students, perhaps some of the brightest in Russia, and they have created lots of various projects using finite automata in various ways to solve real-world tasks.

Professor Shalyto did some other very useful things, including his efforts towards promoting open project documentation as well as his perseverance in supporting computer science education in Russia. However, as far as finite automata go, I became convinced that they are good for nothing practical, except maybe compiler programming, ATM transactions, controlling production processes on large factories, and a number of other niche applications. Also, as far as cellular automata go, I became convinced, again from observing the efforts of prof. Shalyto and his many talented students, that they (cellular automata) are basically good for nothing. Except, of course, for their mathematical beauty.

Answer 4

Inspired by Stephen Wolfram's work on cellular automata in the early 1980s, there was a surge of interest in applied use of CA algorithms. Before interest petered out after about a decade, quite a lot of articles were published demonstrating how CA (usually 1-D, binary) could be used for pseudorandom sequence generation, error-correcting codes, cryptography, FSM testing, signal processing, and a bunch of other stuff. These articles were generally just mathematical sketches, though, and there is little code that you could dig up to look at.

If you want examples that do something practical but are still small and easy to understand, I'd suggest random number generators. CA-based crypto systems dropped out of sight because they were found to be insecure and computationally inefficient. The simplicity of implementing RNGs, though, seems to have made them popular for hobby projects and I have seen several.

You said you aren't interested in simulations, but if you want to see CA used in a significant real-world application, look into traffic flow simulation. This is probably the area in which CA methods have come the closest to being accepted as a useful tool. Check out chapter 13 in the recent book, Traffic Flow Dynamics: Data, Models and Simulation.