Complex behavior generated by simple computation

Stephen Wolfram gave a fascinating talk at TED about his work with Mathematica and Wolfram Alpha. Amongst other things, he pointed out how very simple computations can yield extremely complex behaviors. (He goes on to discuss his ambition for computing the entire physical universe. Say what you will, you gotta give the guy some credit for his wild ideas...)

As an example he 开发者_Python百科showed several cellular automata.

What other examples of simple computations do you know of that yield fascinating results?

Well, the obvious answer is fractals, starting with Mandelbrot Set.

The Hénon Map:

• Start with a point (x, y) in the real plane.
• Repeat the assignment (x, y) := (y + 1 - ax², bx), for some constants a and b.

Often, a = 1.4 and b = 0.3 are used. For these values, the behaviour is chaotic, and all points appear to eventually converge to the following shape, called the Hénon Attractor:

This shape appears to have fractal properties.

I say "appear" twice, because neither of these observations have been mathematically proven.

The original one was Conway's game of life.

The Collatz Conjecture:

• Start with any positive integer.
• If the current number is even, divide it by 2. If it's odd, multiply by 3 and add 1.
• Repeat until you reach 1.

The Conjecture is that you'll eventually reach 1, and this has been experimentally verified for large numbers (up to 5.7 * 10^18) , but never been mathematically proven.

Even for fairly small numbers, this can grow very big until eventually collapsing to 1.