May 9, 2003
One unsettling aspect of NKS is computational irreducibility—the idea that you can’t predict what will happen with a program. Can you define what you mean?
Well, [let’s say] you want to predict where Earth is going to be a million years from now. We don’t have to follow each orbit a million times. We just have to plug a number into a formula, and immediately we can work out where Earth will be in a million years from now. The question is: can we do that kind of thing in general? The principle of computational equivalence says no, in fact, you can’t. A system like this will be computationally irreducible in the sense that to work out what some bit will be down here, you really can’t do that any more efficiently than by just running each step explicitly to see what happens.