Impact of Gödel's incompleteness theorems on a TOE

[Chalnoth]

I think the axiomatizability of physical theory is a bit of a red herring -- if the predictions of the theory are such that they can be computed (which they are typically, at least implicitly, taken to be), then the theory can be recast into an axiom system, because of the one-to-one correspondence between Turing machines and formal systems. Whether or not that's actually a useful, or even practically possible, thing to do doesn't affect the question. If the theory is strong enough to give an account of universal computation, it'll be subject to undecidability, whether or not it's easily captured by some 'nice' set of axioms.

One might even suspect that it is impossible for a correct TOE to not be computable, because, well, the universe actually is able to go through its motions. After all, how would the universe ever accomplish anything incomputable?

 

[tom.stoer]

One might even suspect that it is impossible for a correct TOE to not be computable, because, well, the universe actually is able to go through its motions. After all, how would the universe ever accomplish anything incomputable?

This is a very important and interesting aspect. Instead of Turing machines one could suspect that the universe is equivalent to a certain cellular automaton. Someof them are too simply, some of themare equivalent toTuring machines (e.g. Game of Life). Then the evolution of the universe IS simply the evolution of the cellular automaton.

There is one problem, namely that we do not know how to formulate this - not even in principle - when taking quantum mechanics into account - which we should :-)

Even if the wave function (which would have to be discretized somehow) is computable, that does not mean the an individual result ("measurements") is computable - simply because all results are subject to randomness. Even worse, quantum randomness is not identical to classical randomness; I think this is one result of the Kochen-Specker theorem.

 

[S.Daedalus]

If I may quote Paul Davies - "It is important to realize, however, that the limitation exposed by Godel's theorem concerns the axiomatic method of logical proof itself, and is not a property of the statements on is trying to prove (or disprove). One can always make the truth of a statement that is unprovable in a given axiom system itself an axiom in some extended system. But then there will be other statements unprovable in this enlarged system, and so on."

Well, that's true of course, but I'm not sure as to what its significance is to what I said...?

One might even suspect that it is impossible for a correct TOE to not be computable, because, well, the universe actually is able to go through its motions. After all, how would the universe ever accomplish anything incomputable?

Dunno. You'd probably have to ask an oracle for an answer...

 

[Fra]

One might even suspect that it is impossible for a correct TOE to not be computable, because, well, the universe actually is able to go through its motions. After all, how would the universe ever accomplish anything incomputable?

From my perspective I even think that a non-computable theory relative to it's host, is useless and lacks survival value. So it seems to me as well that we are unlikely to observe abundany systems in nature, behaving AS IF they obey an non-computable strategy. Becase it would be a true mystery as to why non-computable structures has emerged and been preserved.

This is why I think, from the perspective of inference, beeing able to "compute" an expectation as a basis for further rational responses and learning seems like a basic requirement.

However, the correctness or objectivity in computation is a different question. Here I expect disagreement, which may be considered as inconsistencies, but then we need something that generates the flow of time anyway, so why not this? Seems natural to me.

/Fredrik

 

[D H]

One might even suspect that it is impossible for a correct TOE to not be computable, because, well, the universe actually is able to go through its motions. After all, how would the universe ever accomplish anything incomputable?

It appears to me that you are implicitly assuming here that the universe is digital. As S.Daedalus just noted, the answer to that may require consulting an oracle -- or waiting until someone develops a TOE.

Even if the wave function (which would have to be discretized somehow) is computable, that does not mean the an individual result ("measurements") is computable - simply because all results are subject to randomness. Even worse, quantum randomness is not identical to classical randomness; I think this is one result of the Kochen-Specker theorem.

I raised this issue way back in post #61. Also note that even classical physics is subject to indeterminism (also raised in post #61). However, where indeterminism does arise in classical physics is, as far as I can tell, a space of measure zero, so one could argue that the theoretical existence of classical indeterminism is a moot point in the real world.

 

[Fra]

when taking quantum mechanics into account - which we should :-)

I fully agree that we mst not forget QM.

But my expectation is that all this once worked out properly, will show that quantum mechanics is naturally emerging. The step from classical to quantum logic might be explained as a more fit inference model; and therefor we should not be surprised that we see systems behaving as per this logic in nature.

So I don't think we need to "manually" try to put in QM like we usually do.

I think this structure might appear in the reconstruction. I think the elements of computability, bounded computing power and memory, equating "actions" with the computation itself take us a long way.

/Fredrik

 

[tom.stoer]

The step from classical to quantum logic might be explained as a more fit inference model

I don't think that there will be a step (transition, ...) from classical to quantum logic. I even suspect that what we call "quantization" is not fundamental b/c it is like building a 3D house based on a 2D drawing (which does never work except somebody has already seen a house :-) Instead it should be the other way round: the drawing is based on the house. Unfortunately often we do not know how to formulate a quantum theory w/o starting from it's classical limit.. Something is missing here.

 

[Fra]

Unfortunately often we do not know how to formulate a quantum theory w/o starting from it's classical limit.. Something is missing here.

I fully agree.

This is why I think it's interesting to study, compare and try to generalise inferences based on boolean logic and classical probability, and quantum logic and the PI.

Its seems to me there is something probably pretty nice that we don't yet get. It's not far away to view the PI as a computational algortihm for expectations. But why does the algorithm look like this and how can this model be understood from a pure inference point of view? What logic of constructing an expectation like that is behind PI?

I think one observation is that it's a method to compute an expectation based on informtion from different non-commuting microstructures, rather that one large microstructure. If we can understand how these microstructures that are the encoding structures are constructed and relate, mayb we can understand how a general inference model evolves as the encoding strucures do.

/Fredrik

 

[Chalnoth]

It appears to me that you are implicitly assuming here that the universe is digital.

Well, if the universe is fully quantized, then this would seem to effectively be the case. In fact, this may be a good argument for it to be fully-quantized, because computability should, it seems to me, be a fundamental requirement for anything to happen at all, as one can think of physical systems as being computers after a fashion, with the behavior of the system "computing" the later state from the earlier state.

 

[suprised]

Indeed there is the widespread point of view that the fundamental theory should be intrinsically quantum and classical physics just happens to emerge in certain limits (this is exemplified by some strongly coupled theories arising within string theory, eg the matrix theory approach to M-Theory, and emergent gravity etc). Trying to quantize some classical theory would be the wrong end to start.

 

[Fra]

Right or wrong,but I do take the notion of distinguishability (which is ~ the elementa of logic) to be fundamental. This is why I also think starting points like uncountable real numbers are somewhat unphysical. To me it represents limits, to which we can indeed get arbitrarily close to, but never hit. This is why I think the continuum is a useful embedding that serves a purpose buy has possibly no physical manifestation.

I think these things are partly responsible for all our headache with failing renormalization, because of apparent counting overflows. It seems also plausible that uncountable options would lead to infinitely slow responsiveness unless you have infinite computing power, neither which seems reasonable to me as I don't see how it leads to any well behaved computable inferene models that match real systems of finite size.

/Fredrik

 

[S.Daedalus]

It appears to me that you are implicitly assuming here that the universe is digital. As S.Daedalus just noted, the answer to that may require consulting an oracle -- or waiting until someone develops a TOE.

The problem with that, though, is the same as the Greeks faced in antiquity: How do you make sense of an oracle's answer if you are not one yourself? Basically, if I were in possession of computational resources that sufficiently exceeded anything you could muster, I could pretend to have access to hypercomputation, and you would be unable to disprove my claim. It's very hard to tell a real oracle from a false one!

So, for any description of nature that required her to refer to an oracle in order to find out how to proceed, it seems that you could find an equivalent one in which the oracle in question is only a pretender, i.e. an ordinarily computable process, and be unable to tell both apart in any experiment of finite precision. And if that is the case, then one should take the thesis of hypercomputation and commit it to the flames as nothing but sophistry and illusion.

(The problem here, though, is that if nature actually does refer to a genuine oracle, one can find a computable theory capturing some phenomenology only ever 'after the fact', so to speak; since while we may be able to match the oracle up to some finite bound, beyond that, we can do no better than guess, using our current theory, which kinda does in the notion that a scientific theory ought to have a certain predictivity, and thus, reduces us to merely trying to find ad hoc explanations for observed phenomena. That's not a state of affairs I personally find very satisfying, but luckily, so far things don't seem to work that way -- as some of our predictions do come out right --, and there are certain developments -- for instance, the holographic information bound constraining the information within a finite volume to a finite value -- that make me hope it stays thus.)

 

[tom.stoer]

Indeed there is the widespread point of view that the fundamental theory should be intrinsically quantum and classical physics just happens to emerge in certain limits ... Trying to quantize some classical theory would be the wrong end to start.

I agree.

But still there is the problem that this does not rule out over-countable elements in such a theory, e.g. Fourier coefficients which are usually taken from the complex numbers.

 

[Dmitry67]

Even very primitive systems ('Game of Life' on an infinite chessboard for example) are imcomplete.

It is hard to believe that TOE ould be complete.

 

[Lievo]

I would say that if you have something whose bound is unknown (as the values of the busy beaver function are) then you need infinite space to hold it

Ok thank you. What is this infinite: aleph 0, more than aleph 0, or less than aleph 0?

In your more complex notion of computation, something like "the result of the computation is what remains on the tape when the TM halts" might be a perfectly valid definition.

Ok thank you. Does my more complex notion of computation gives my TM more power or it's strictly the same?

If the length could actually be infinite, then the computable numbers could be defined as the numbers for which there exists a TM that compute all the digits. But the actual definition is: the numbers that can be computed to within any desired precision by a finite, terminating algorithm.

First off, these are equivalent definitions. I think I can actually mechanically translate between the TMs produced under each definition

Ok thank you. Please do. Here is the TM I'd like you to translate: it successively checks all TM of size t to see how many stop in t time and how many don't. Then it does the same for t+1, t+2, etc.

What I would say is that this machine will write all the digits of omega to its tape in the limit as runtime approaches infinity.

However wikipedia states that omega is not computable. Should I trust wikipedia on this?

 

[Lievo]

One might even suspect that it is impossible for a correct TOE to not be computable, because, well, the universe actually is able to go through its motions. After all, how would the universe ever accomplish anything incomputable?

By allowing faster than c communication?

 

[Lievo]

On second though, faster than c communication or time travel or naked singularities or free energy. I think it's all the same, and the puzzling question is: does the existence of free energy in our universe (mostly in the form of low entropy from big bang area) implicates uncomputability?

 

[Chalnoth]

On second though, faster than c communication or time travel or naked singularities or free energy. I think it's all the same.

In other words, all you require is an unstable theory that predicts nonsensical results?

 

[Lievo]

In other words, all you require is an unstable theory that predicts nonsensical results?

Absolutly. I think it's basically the requirement for a uncomputable TOE.

Which is a way to say that on first sight I don't give it a s... but on second sight, we know there exists free energy from the (likely) beginning of our time. I don't see how a computable TOE can produce it.

 

[Chalnoth]

Which is a way to say that on first sight I don't give it a s... but on second sight, we know there exists free energy from the (likely) beginning of our time. I don't see how a computable TOE can produce it.

No, we don't know that at all. In the Hamiltonian formalism, the total energy of a closed FRW universe is identically zero, so you don't need any energy to produce a universe like our own.

If you'd rather use the more standard formulation of GR, then energy isn't a conserved quantity anyway.

 

[suprised]

But still there is the problem that this does not rule out over-countable elements in such a theory, e.g. Fourier coefficients which are usually taken from the complex numbers.

Why would be this a problem? I mean, why should countability and computability play any role at all?

 

[Lievo]

you don't need any energy to produce a universe like our own.

Sorry I was not clear: I was talking about thermodynamical free energy. I don't see how to account for that using a computable TOE. Do you have some cues?

 

[Lievo]

If you'd rather use the more standard formulation of GR, then energy isn't a conserved quantity anyway.

One thing: equation of relativity, as far as I know, are http://en.wikipedia.org/wiki/Wormhole#Traversable_wormholes" with time travel and other monsters. Or I fool myself here?

 

[D H]

Ok thank you. Does my more complex notion of computation gives my TM more power or it's strictly the same?

Making the tape finite in length is not more complex. Your concept is that of a "linear bounded automaton". Linear bounded automata are simpler than but less powerful than Turing machines. For example, the halting problem is solvable for linear bounded automata (but is not solvable for Turing machines).

 

[bcrowell]

I don't eqate them. I only wanted to say that physics fails to be a an axiomatic system for several different reasons currently.

Well, I don't want to be unnecessarily argumentative, but it's very clear from your #99 that you did equate them.

The recent string of comments on quantum mechanics versus classical mechanics shows that we have a lot of people here who don't understand the relationship between formal logic and the rest of mathematics. Please take a look again at my #10, S.Daedalus's #33, and Coin's #57. These three posts pretty much encapsulate the reasons why Godel's theorems have no relevance to physics.

Any theory of physics can be expressed in a formalism that is equiconsistent to real analysis, and it doesn't matter whether the theory is quantum or classical. For example, complex analysis is equiconsistent to real analysis, because you can build a model of complex analysis using the reals. Since the Schrodinger equation can be written using complex analysis, the formalism you need for the Schrodinger equation is equiconsistent with real analysis. That means that to a logician, there is no difference between the mathematical foundations needed for quantum mechanics and Newtonian mechanics.

S.Daedalus's #33 gives a good example of how you can't equate a physical theory to the underlying foundation of mathematics that it needs. Conway's game of life can be described by an evolution rule, which plays the same role as, say, the Schrodinger equation or the Einstein field equations. There are certain things that you can't prove *about* the game, but you can always determine the evolution of the system from one state to another. This means that you can always predict the outcome of experiments. If you're developing a theory of this game, is the theory just the evolution equation, or is it that plus statements that you want to prove about the game? Well, basically the theory includes whatever people have figured out about the game. It doesn't have a strict boundary where you can say that everything inside the boundary is part of the theory and everything outside it is not part of the theory. The theory is whatever physicists have agreed is interesting and related to the topic. This is why my objection to com.stoer's conflation of physical theories with axiomatic systems is not just a quibble. It's a crucial point.

Coin's #57 explains why, even if you express a TOE in terms of a certain mathematical foundation, that doesn't mean that Godel's theorems say anything of physical interest about the TOE, e.g., that certain interesting physical questions are undecidable. They don't even say that interesting questions in the theory's underlying mathematical foundation (such as real analysis) are undecidable.

 

[friend]

Godel's incompleteness theorem only applies to systems that include math. But math is an abstract construction developed for our convenience. But I consider that it might not be applicable to physical things. For example, when counting sheep, you can start counting with any of them. There isn't anyone particular sheep that must be labeled "one", etc. And so it would seem that you cannot assign an axiom to anyone particular physical thing. So you can't say this thing is represented by a axiom that is already included in your theory or is represented by an axiom that is not yet proven by your theory.

 

[D H]

Please take a look again at my #10, S.Daedalus's #33, and Coin's #57. These three posts pretty much encapsulate the reasons why Godel's theorems have no relevance to physics.

So let's look at those. #33 talks about Conway's game of life. Using the game of life as an analogy to a TOE, a physicist's job is done by describing the transition rules for the game. That the game has undecidable configurations is irrelevant.

#57 is particularly relevant. Rather than paraphrasing, here it is (in part):

The standards that we would demand to colloquially qualify something as a "theory of everything" are very, very low compared to the lofty, abstract heights of the incompleteness theorem. People will happily (and fairly) declare, for example, string theory a TOE simply because it includes a graviton and and standard-model-like constructions at once, even though we don't know how to calculate many things in it or whether important series produce finite results. Physicists can and do get by without being able to actually calculate basic things, even in sub-TOE theories like QFT or Newtonian gravity (n-body problem anyone?). Compared to this "are there statements about our TOE which can be formulated, but are neither provable nor disprovable?" is not a particularly relevant concern.

My only quibble with this is the allusion to the n-body problem. Except for a space of measure zero, the n-body problem is solvable (just not in the elementary functions). Indeterminism/acausal behavior does arise in classical physics, but again this is restricted to a space of measure zero.

That's just a side issue, though. The take-away point is that those working toward a "theory of everything" are not working toward developing a theory that perfectly predicts all outcomes. They just want to describe all interactions. Big difference.

 

[Chalnoth]

Sorry I was not clear: I was talking about thermodynamical free energy. I don't see how to account for that using a computable TOE. Do you have some cues?

Fundamentally, this is down to entropy, not energy. The question is how a low-entropy state could arise, not how energy could pop into existence. And that is still an open question at this time, though my personal favorite hypothesis at the moment is this one from Sean Carroll and Jennifer Chen:
http://arxiv.org/abs/hep-th/0410270

The basic idea is that you can sort of skirt around the Boltzmann Brain argument by proposing that there is no equilibrium state, and entropy always increases. The low entropy density of a late universe makes it not quite so unlikely that a small but low entropy universe would be generated from a random fluctuation: it's a small, temporary reduction in entropy that allows for a much greater increase in entropy down the line.

 

[Chalnoth]

One thing: equation of relativity, as far as I know, are http://en.wikipedia.org/wiki/Wormhole#Traversable_wormholes" with time travel and other monsters. Or I fool myself here?

Most people seem to think that this is probably wrong. But it is known that GR isn't a fully-consistent theory anyway.

 

[S.Daedalus]

Why would be this a problem? I mean, why should countability and computability play any role at all?

Not sure if I get understand this right -- I mean, basically, you'd want your theory to be computable because you want to compute things with it, no? If you start with a system in state x and your theory tells you that its evolution is given by f(x) where f is not a computable function, what are you going to do? Ask some old hag with a crystal ball?

Or did you mean something else?