[amelius]

I wonder how you come to that conclusion, because physics is not proven to be of "infinite complexity" (loose statement).

Some things that we are used to from mathematics might not be true in physics. Take for example the fact that in mathematics the real numbers are uncountable. Now in reality (physics), the whole set of real numbers may not exist. It is only an abstract concept from mathematics. And while it may be possible to reproduce any real number in physics as some quantity, you are reproducing them as you go, making the "real" (physical) real numbers countable.

[yohanatan]

It doesn't take 'infinite complexity' [your term] to encode the natural numbers. Rather it is only a handful of axioms. See: http://en.wikipedia.org/wiki/Primitive_recursive_arithmetic

Pretty much any system of logic worth looking at (including any which the sciences may be based on and the one running inside each human brain) is going to at least be as complex as this set of axioms.

Also, you really should read the JR Lucas material-- it explains this. And, I'd suggest Nagel & Newman's _Godel's Proof_ for a great introductory explanation of the Incompleteness Theorems.

[j2kun]

We don't know that the physical world has infinite precision. In particular, time doesn't even seem to be continuous as far as we can tell (cf. Planck constant). And we think there's a finite amount of mass in the universe, so how could we encode arbitrarily large natural numbers (as is required to model Peano arithmetic)?

[yohanatan]

We don't have to encode arbitrarily large natural numbers. Rather we have to encode the rules that allow us to construct them (which is quite simple actually). And, I think 'digital physics' is more compatible with Incompleteness implications than the alternatives; not less.

[j2kun]

How can you construct something which is larger than the amount of mass in the universe?

[yohanatan]

Downvoters: if you disagree, feel free to post an attempt at a refutation or somehow otherwise explain your vote.

[eli_gottlieb]

Yeah, but he was talking about the real numbers.

[yohanatan]

But the reals are irrelevant as far as Incompleteness is concerned. He's obviously confused.