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

[Chalnoth]

Read posts #68 and #80 by Coin. Read some more on what a Turing machine is and is not. And finally, stop posting your misunderstands as fact. You are derailing this thread, and given that this thread is already on a pretty thin set of rails, further attempts at derailing are not good, not good at all.

I'll have to add my support to this, as post #80 is particularly relevant.

 

[Lievo]

as post #80 is particularly relevant.

If you care about post #80, I pointed the (small) mistakes in a previous post. I'm curious to see if coin will recognize and thank it or behave as the one you have to support.

Do you disagree?

No, except for some details: decidable and recognizable that's the same, I think it's usefull to know that BB(n) is the bound because basically, this is what separate computing from hypercomputing, and finally the fact that the bound is uncomputable doesn't make it an infinite. But I begin to desesperate here.

 

[friend]

So how would Godel's incompleteness theorem be relevant to physics? Do we suppose that each particle is a separate axiom so that we might not be able to prove the existence of all particles? Or do we suppose that complex combinations of molecules are theorems of the systems so that we might find structures that are not reducible to particles? What?

It seems to me that theoretical physics is about finding one equation that describes it all, and it is not an effort to find every equation derivable. Is this not right?

 

[D H]

So how would Godel's incompleteness theorem be relevant to physics?

In my [blunt] opinion, typically by misconstruing what constitutes a "theory of everything". As you later noted,

It seems to me that theoretical physics is about finding one equation that describes it all, and it is not an effort to find every equation derivable. Is this not right?

Misconstrue a theory of everything to mean something other than describing the particle zoo and the interactions amongst the particles, and yes, you might have a messy straw man, depending on how you misconstrue things. So what? It is a straw man argument.

The one possible avenue where Gödel's theorem's might apply is if that the development of that TOE (which does not yet exist) necessarily entails that the theory be able to encode itself inside the body of the theory.

 

[Coin]

No, except for some details: decidable and recognizable that'shttp://xw2k.nist.gov/dads/html/decidableLanguage.html"

I'm trying not to monopolize this thread but I think this must be responded to. Decidable and recognizable are not the same.

A turing machine decides a language if it halts in an accepting state for all input strings which are in the language, and halts in a rejecting state for all input strings which are not in the language.

A turing machine recognizes a language if it halts in an accepting state for all input strings which are in the language.

A language is decidable if there exists a turing machine which decides it; the language is recognizable if there exists a turing machine which recognizes it. $$Recognizable \supset Decidable$$. An example of a language which is recognizable but not decidable would be: the set H of all turing machine descriptions which have some input for which they halt.

This language H has relevance to our discussion about turing machine tapes. It is easy to construct a turing machine T which recognizes this language H; T will always halt and accept, and therefore always consume a finite amount of tape, when run on an input which is in the language H. When run on an input which is not in H, however, maybe sometimes it will halt and reject (depending on how you constructed it); but sometimes it will run forever, and sometimes it will run forever and consume an infinite amount of tape in the limit. It is only because T consumes infinite tape in some of these cases where it does not accept, that T is able to recognize H. Any possible modification of T such that these cases where it consumes infinite tape are avoided, will cause it to no longer recognize all of H.

Looking around I find a pretty good writeup of decidable/recognizable/co-recognizable languages http://www.cs.uwaterloo.ca/~watrous/360/handouts/undecidable-examples.pdf .

 

[Fra]

So how would Godel's incompleteness theorem be relevant to physics?

I already say I think it's mainly inspirational and suggestive, but to be a little more specific and flesh out a the wild personal fantasy:

For me the connection is when you consider interacting physical systems as interactin axiom systems. Where each axiom system more or less encodes; implicitly, all expectations the system has on it's own environment, and thus influences it's actions. Thus the quest to understand the action of matter; amounts to understanding

1. how axiom systems interact (but adding & removing axioms; like genes are added and lost in darwins biology)

2. how to, based on bounded information, the possible axiom systems _of given complexity_ could be counted and ideally as we increase the complexity, new subsystems appear. And we MAY get and hierarchy of axiom systems that may correspond in some weird yet unclear way to the microstructure and action of the known interactions.

So the connection I made is

one observer ~ one axiom systems (here the hierarchy of particles, are related in an evolution hierarchy like biology, from more and more complex axiom systems. So I think the unification means = seeking the basic axioms that seem common to all systems (as in revelaed indirectly from their action; the idea is that you can infer from monitoring a systems actions, it's axioms or premises)

observer-observer interactions ~ negotiating axiom systems
observer evolution ~ optimization of the axiom systems, loose useless axioms, add new ones (analogy with biology), basically rational information updates

I think of the logic more as an evolving inductive logic that has both decidable and undecidable elements. So if we think that nature, and physical interactions as like "communication" then to understand the laws of physics I personally think we need to understand the rules of inference - in the format that are likely to be relevant considering bounded computational capacity AND bounded information capacity.

/Fredrik

 

[Chalnoth]

The one possible avenue where Gödel's theorem's might apply is if that the development of that TOE (which does not yet exist) necessarily entails that the theory be able to encode itself inside the body of the theory.

Actually, it would have to, for the simple reason that we, who are describing the theory, would be described by that same theory!

 

[Lievo]

Decidable and recognizable are not the same.

Coin, thank you for correcting the mistake I made here.

While you're at it, I'd like you to decide the correctness of the following statements:

-the fact that a bound is uncomputable doesn't make it an infinite.
-the result of a computation is defined as what remains on the tape when the TM halts.
-Pi is computable, but there is no single Turing machine that can compute all the digits.

 

[Chalnoth]

-Pi is computable, but there is no single Turing machine that can compute all the digits.

I don't get this point. There is no Turing machine period. A Turing machine is an abstract construct that cannot exist in reality, due to the requirement of an infinite length tape.

 

[bcrowell]

Why not?

They haven't been reformulated as sets of axioms, but that does not mean that this is not possible in principle (I agree that it is not usefull in order to make progress in physics). Up to now physical theories are a collection of rules instead of sound axioms; physical theories are mathematically ill-defined partially , but nevertheless what you are describing is the current status, not necessarily the future one.

You're equating "ill-defined" to "not expressed as an axiomatic theory in the way required by Godel's theorem." They are not the same thing.

 

[Lievo]

-Pi is computable, but there is no single Turing machine that can compute all the digits.

I don't get this point. There is no Turing machine period. A Turing machine is an abstract construct that cannot exist in reality, due to the requirement of an infinite length tape.

My point is that there is no mathematical requirement for an infinite length tape, only a requirement for an unbounded length tape.

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.

In other words, it's not computable because there exists a single TM that can find all digits. It's computable because for any integer n there always exists a finite terminating TM that can find the n first digits of Pi. But none of these finite terminating TM requires an infinite length tape -because all terminate.

 

[tom.stoer]

You're equating "ill-defined" to "not expressed as an axiomatic theory in the way required by Godel's theorem." They are not the same thing.

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

 

[Coin]

Well...

While you're at it, I'd like you to decide the correctness of the following statements:

-the fact that a bound is uncomputable doesn't make it an infinite.

I don't really know how to interpret this. 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, because otherwise how do you know if you have crossed over your bound yet?

-the result of a computation is defined as what remains on the tape when the TM halts.

No, I don't agree with this at all. The result of a computation is either "reject" or "accept". (Or some computations may fail to produce a result at all, for example by failing to halt.)

When we are talking about turing machines, my default assumption is that we are working in the arena of formal languages and which formal languages a given machine accepts/rejects. Most of the fundamental proofs you will find using TMs are working in this arena, because it is easy to reason unambiguously about problems constructed this way, and because it is often easy to reduce more complex notions of "computation" to statements about formal languages. In this arena the TM's "output" is one bit and the tape contents are thrown out.

Now, armed with the TM formalism you can very well define a more sophisticated notion of computation, something like function problems say. 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. But this is a statement about the thing you defined, not about TMs in general.

-Pi is computable, but there is no single Turing machine that can compute all the digits.

"Compute" seems ambiguous to me. What I would say is that there exists a turing machine which will write all the digits of pi to its tape in the limit as runtime approaches infinity.

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. And I might tend to say that which operational definition is better would actually depend on what you're doing. For example I might prefer to use wikipedia's definition of a computable number if we were trying to prove things about computable numbers, as it seems a little more rigorous. However let's say that for some reason we were interested in the Kolmogorov information measure of infinite sequences. In this case the give me a precision and I will terminate with your number calculated to that precision definition might get quite awkward to work with, and it might be more useful to in some way talk about the long-term "output" of a nonterminating turing machine.

Second off, I would hesitate before treating wikipedia as an authoritative source as to the precise definition of terms from advanced academic subjects.

 

[S.Daedalus]

You're equating "ill-defined" to "not expressed as an axiomatic theory in the way required by Godel's theorem." They are not the same thing.

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.

Whether or not this amounts to questions of physical interest being unanswerable is perhaps a matter of debate, and probably of taste, however. Personally, I take a sort of constructive approach to what I expect a TOE can do for me (though, perhaps I should not ask what a TOE can do for me, but...): if I am given some configuration of a (closed) physical system, I expect to be able to apply the TOE to (in principle) calculate the evolution of that system -- and this is possible for a TOE, even one that is subject to Gödelian incompleteness, as the Game of Life example shows.

However, there are some questions that one might reasonably ask of a physical system that in general can't be answered -- such as, 'will such-and-such a configuration ever be reached?'. But this is nothing in principle new, or shocking: it's just a reflection of the fundamental epistemological fact that one can't draw up a list of all the facts about the universe (and know that one has done so). There always, at least in principle, might be a black swan, even if everybody has only observed white ones so far: the problem of induction, as noted by Chalnoth, I believe. Analogous to that, the set of facts about the universe is only semi-deciable: if something is indeed part of that set, our TOE will eventually, at least in principle, tell us that it is; however, we can never be quite sure that something isn't part of this set.


----------------------
By the way, those that are looking for a possible physical significance of logical independence (in general, not limited to the Gödelian kind) may be interested in a paper by Paterek et al, http://arxiv.org/abs/0811.4542" , in which they show that for a set of axioms encoded in a quantum state, measurement on that state will yield random outcomes exactly if the proposition encoded in the measurement is independent of the axioms.

 

[PhysDrew]

There always, at least in principle, might be a black swan, even if everybody has only observed white ones so far: the problem of induction, as noted by Chalnoth, I believe. Analogous to that, the set of facts about the universe is only semi-deciable: if something is indeed part of that set, our TOE will eventually, at least in principle, tell us that it is; however, we can never be quite sure that something isn't part of this set.

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."

 

[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.