That is to say that in order of the time-evolution of anything in the universe to proceed "correctly," the physical processes themselves must be able to, and in real-time, keep up with the complexity of their actual evolution.
This is only true if the universe itself is computable, right? In fact, it's trivial if the universe is computable because any physical process could be determined by using the final physics- so of course an uncomputable piecemeal theory wouldn't be the only law that could describe the phenomenon.
EDIT at Karma -5: Could the next "good citizen" to vote this down leave me a comment as to why it is getting voted down, and if other "good citizens" to pile on after that, either upvote that comment or put another comment giving your different reason?
My guess is that the down votes are coming because it sounds like you're making deep and important claims about the universe based computability theory while also revealing a lack of understanding of computability theory. It also isn't clear what your point is. Then you bring up the Singularity and people here are pretty sensitive to Singularity talk mixed with rambling about science the writer doesn't really understand.
It isn't really my field though, so someone who understands computability theory better than I should confirm my suspicion.
What I am wondering is, where does this kind of consideration break with traditional computability theory? Is traditional computability theory limited to what Turing machines can do, while perhaps it is straightforward to prove that the operation of this Universe requires computation beyond what Turing machines can do?
There's a large set of computability models, but if you don't get into hypercomputation they all produce the same set of computable functions. Quantum computation doesn't change this picture; anything computable by a quantum algorithm is computable by a classical algorithm, although often less efficiently.
Whether or not the physical laws of the universe involve any uncomputable operations is an open question, although none, as far as I know, have been proven to exist.
I voted it up as not unsuitable for the discussion section, for what it's worth. There aren't a lot of comments, but they're decent enough. It's not against the mission statement.
There is a whole field of hypercomputation. Obviously any Turing-computable program can be run by a Turing-complete computer and a hypercomputable program can be run by a hypercomputer of the same place in the arithmetical hierarchy. The Church-Turing thesis can be expressed as stating that the universe is Turing-computable, which is a question about the universe, not just about computation. You may also be interested in Banana Scheme, which provides an short introduction to hypercomputation.
Wouldn't a program (like a computation of the laws of physics) written within the confines of the universe be necessarily less complex than the universe itself, or am I missing the point of your post?
I don't know enough to know why this topic is downvoted. Is it because no uncomputable physical laws have been discovered, or is it because the last paragraph doesn't make much sense, or something else?
EDIT at Karma -5: Could the next "good citizen" to vote this down leave me a comment as to why it is getting voted down, and if other "good citizens" to pile on after that, either upvote that comment or put another comment giving your different reason?
Original Post:
Questions about the computability of various physical laws recently had me thinking: "well of course every real physical law is computable or else the universe couldn't function." That is to say that in order of the time-evolution of anything in the universe to proceed "correctly," the physical processes themselves must be able to, and in real-time, keep up with the complexity of their actual evolution. This seems to me a proof that every real physical process is computable by SOME sort of real computer, in the degenerate case that real computer is simply an actual physical model of the process itself, create that model, observe whichever features of its time-evolution you are trying to compute, and there you have your computer.
Then if we have a physical law whose use in predicting time evolution is provably uncomputable, either we know that this physical law is NOT the only law that might be formulated to describe what it is purporting to describe, or that our theory of computation is incomplete. In some sense what I am saying is consistent with the idea that quantum computing can quickly collapse down to plausibly tractable levels the time it takes to compute some things which, as classical computation problems, blow up. This would be a good indication that quantum is an important theory about the universe, that it not only explains a bunch of things that happen in the universe, but also explains how the universe can have those things happen in real-time without making mistakes.
What I am wondering is, where does this kind of consideration break with traditional computability theory? Is traditional computability theory limited to what Turing machines can do, while perhaps it is straightforward to prove that the operation of this Universe requires computation beyond what Turing machines can do? Is traditional computability theory limited to digital representations whereas the degenerate build-it-and-measure-it computer is what has been known as an analog computer? Is there somehow a level or measure of artificiality which must be present to call something a computer, which rules out such brute-force approaches as build-it-and-measure-it?
At least one imagining of the singularity is absorbing all the resources of the universe into some maximal intelligence, the (possibly asymptotic) endpoint of intelligences desiging greater intelligences until something makes them stop. But the universe is already just humming along like clockwork, with quantum and possibly even subtler-than-quantum gears turning in real time. What does the singularity add to this picture that isn't already there?