sirchasm said:
However, it certainly appears to be 'computational'; this is demonstrable: if we can write a program that simulates a real physical process (the gas laws, say), and do this for all of the processes we know about (so all the simulations then prove that we do know, if they exactly reproduce these processes in "computer-space", i.e. virtually), then a simulation of the known universe exists.
So there are several problems with this line of thinking.
First off: We don't know what the laws of the universe are. We therefore cannot say whether the laws of the universe are computable or not. You do specify "known" physical processes. I don't think "known" processes are very interesting for this purpose. For example, imagine you came up with a really ingenious proof that gas dynamics are computable. But it might be that gas dynamics are just a computable process that exists inside of a non-computable universe; similar to how (as Chalnoth points out) a
computer is a computable mechanism, but this doesn't tell us the universe it exists inside is computable.
Second off: Even some of the physical processes which are "known" defy accurate calculation given the mathematics we have available to us right now February 2009. For example, quantum physics is part of "known" physics, and relativistic gravity is part of "known" physics. But no one knows how to construct a calculation where the two interact, and there will be nobel prizes handed out on the day someone demonstrates a workable way of doing so. So it is going to be very difficult to make any meaningful statements about the behavior of a hypothetical program which simulates even these known parts of physics.
Finally, consider your suggestion that we write a program that simulates "a" physical process, and use the failure or success of such an attempt to judge whether the universe is computable, and consider that your recommended target is the gas laws. But, there are people who write simulations of the gas laws already! They call it climate modeling. To put things a bit vaguely, what I would point out is that these people
don't simulate the gas laws exactly. Simulating the gas laws exactly is not something that is even talked about. What is talked about is simulating the gas laws over some period of time within some bounded error, such that the bounded error gets worse and worse the longer the computation runs.
Looking at this from the perspective of a CS person rather than a cosmologist, there really seems to be only one possible answer: Maybe the laws of the universe are computable, and maybe they're not, it depends on what those laws are. There are different possible completions of our physical laws which are computable, aren't computable, or which are computable by different models of computation (TM, probabilistic TM, hypercomputer). But we don't know which completion of our physical laws is the correct one.
Certainly if we limit ourselves to the more naive systems of physical laws, say Newtonian physics, this makes computability seem impossible. The point zankaon raises can't just be brushed off: The immediate, "known" physical laws concern things which are
smooth, which appear to incorporate real numbers. These things just aren't suitable for computation (under any nonexotic model of "computation"). You can only approximate, and the error in your approximation will compound on itself with time until it is completely out of control. Now, you seem to be suggesting that by eschewing all rounding and assuming all physical quantities to be limited to some computable subset of the reals (surely not the rational numbers-- the algebraic numbers maybe), something like
these people seem to be trying to do, you could create a simulation which may be computationally impractical but which can in principle precisely simulate some physical law or other. Um, maybe? I don't know. I would not discount such a possibility out of hand, but I DEFINITELY wouldn't make a statement like "it's possible" either without seeing some very specific discussion of models and proofs. If you want the universe to be computable, what you really want to hope for is that the smoothness is only
apparent, that all the seemingly-uncomputable "known" physical laws are emergent from large-scale interactions of some simpler, discrete structure. There are some theories of quantum gravity that seem to me to hint such a thing could be true. But maybe those theories of quantum gravity are not the right ones.