Stephen Wolfram's book A New Kind of Science (CERN Courier Jan/Feb 2003 p55) made the case that many complex things could be created by very simple algorithms running as cellular automata. While perhaps philosophically attractive, this is also rather intimidating as it suggests that many things we may want to calculate could just take a very long time to work out. Now, however, Navot Israeli and Nigel Goldenfeld of the University of Illinois at Urbana-Champaign have some good news for those who don't mind if their answers, while not being quite right, are basically correct. In an analysis similar in feel to renormalization, they show that all the cellular automata in Wolfram's classification can be "coarse grained" into much simpler systems that are computationally tractable. While the price is a loss of fine detail, the result is a good description of the large-scale behaviour. One of the automata is equiv- alent to a universal Turing machine and could compute anything that could be computed, so the claim is very broad and far-reaching.

Further reading

N Israeli and N Goldenfeld 2004 Phys. Rev. Lett. 92 074105.