The Theory of Computation
Back before WWII, Alan Turing proved that a very simple device, much simpler than the cellphone in your pocket, can in principle emulate any other computing device and hence perform *any* computation, no matter how complex. This device (now called a Turing machine) consists of a simple printer that can print and/or erase a single letter at a time, on a simple piece of paper "tape" that shuffles along under the printer. It operates by reading the tape and deciding what to do next given the value of the current symbol. It's basically the tickertape device you see spitting out stock prices (one of the official Stereotypes used by movies and TV)3, except it can back up and rewrite. If you're clever (i.e. nerdy) about it, you can set up this contraption to chug through any possible calculation whatsoever -- even an incredibly realistic simulation of the entire universe and everything in it. It'll take a while (and yards of tape), but you could do long division on it. Another mile of tape, and you could check your gmail.
So if time and tape supply are no object, you can do anything you want on a Turing machine -- all those G5 pentiums just save you a pile of tape. And if a little tape-chewer can do whatever a supercomputer can do (albiet inefficiently), that means that very simple mechanisms can be set up to do arbitrarily complex patterns. (Sound like I'm repeating myself? At least I'm not as bad as Wolfram.) You don't in principle *need* anything more complicated than a Turing machine, since a Turing machine can be set up to emulate anything more complicated that you might need. It's only for convenience that we bother to build computers and electronics -- anything, from your TV, to a Cray supercomputer, even the most complex computer that conceivably could be built in the future. Pretty remarkable.
And from this idea, the next cognitive leap was to consider the entire universe as kind of a "natural" computer. After all, if a Turing machine can simulate a computer that can simulate the universe, then basically you're saying that a Turing machine could be *making* the universe. If we simulate the universe using a computer program, the little simulations of you and me would be programmed not to realize they were part of a computer program. And if you did the simulation on a Turing machine, the little simulated people wouldn't realize they exist only as letters on a piece of tape. Now nobody seriously thinks that all our universe is done on a big steam-powered paper tape printer -- but the cool thing is, the entire universe *could* be created by something just as simple, and we'd never know. Something, perhaps, like a cellular automaton?
