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

[tom.stoer]

Basically one can derive from Gödel's theorem(s) that given X is the ToE
- one can neither derive X nor can one show that X is consistent;
- one cannot derive all results of X

 

[Fra]

Calnoth, I think your post was reasonable also to me, but I mainly used your post as a handle to connect my input to a context, rather that picking specifically on you.

Well, you can make any laws of physics eternal simply by having the laws of physics describe any changes that occur.

Actually I disagre strongly here. This is IMHO at least, exactly what you can not do, because to do this, you need even more information capacity. To even encode the evolution of one theory, you need to at least partially be able to encode a history of such theories and that takes much more capacity.

If you think about, how to go about to acquire CONFIDENCE in how a given theory, does evolve is should be quite clear that you need a BIGGER theory. My conjecture based on information bounds is that such bigger theory simply won't fit and can't be encoded.

This is why I arrive at tha plausible conclusion that all information evolves, and the difference between STATES and LAWS are that the most fundamental laws evolve in a undecidable way, while that STATE evolve in a decidable way (relative to laws).

This connects to the Smolin/Unger discussion about evolving law: then isn't there again a law that governs the evolution of law? My *opinion* to that idea is no. That LAW isn't even decidable, and it's due to incompleteness forced by the information bound, *and* also sometimes because the law changes to fast that information process never gets around to reach maximum confidence before input again has changed.

/Fredrik

 

[tom.stoer]

This is IMHO at least, exactly what you can not do, because to do this, you need even more information capacity. To even encode the evolution of one theory, you need to at least partially be able to encode a history of such theories and that takes much more capacity.

Fredrik, perhaps I missed something, but this need not be the case. A universal Turing machine is a very simple counter example. It acts on an infinite strip and it can store both data and program code on that strip. Essentially it does not distinguish between reading data and reading code. Therefore it does not distinguish between writing data and writing code, either. It can modify its input (it will read later). Therefore one can interpret this (from a different perspective) is changing the algorithm.

Of course the example is not perfect b/c it is a Turing machine and may therefore be not powerful enough to describe (or be) a ToE, and b/c there remains a fixed part of the algorithm which is not stored on the strip and can therefore not be modified.

 

[bcrowell]

Basically one can derive from Gödel's theorem(s) that given X is the ToE
- one can neither derive X nor can one show that X is consistent;
- one cannot derive all results of X

No, because Godel's theorems only apply to formal axiomatic systems, and physical theories aren't formal axiomatic systems.

 

[Fra]

Tom, it's hard to tell if we are focusing on different details but if we remove the information capacity constraint, the the story is different but...

It acts on an infinite strip and it can store both data and program code on that strip.

My point is that the abstractions that considers infinite (or even unbounded) tapes, simply doesn't correspond to a physical system. My perspective is that any given observing system, encoding a theory and processing information about it's environment has a given finite information capacity. This can grow and shrink, presumable related to the process that is responsible for the origin of inertia and mass, but it doesn't charge arbitrarily.

So IMO, what we have here is a "natural truncation". This truncation is also what limits decidability.

If we consider a larger theory, they it's possible, I agree, but then this also corresponds to a different (more complex) observer. This is IMO somewhat analgous to the gödel expansion. But this expansion is IMO a physical process and is constrained by inertia. That's why we have saturation and overflow of data. I think all these things have interesting connections to physical interactions, radiation etc. But now we get into more speculaton. I mainly wanted to add "my line of association" to Gödel theorem. I do not find that abstractions of information, and computability that makes use of unbounded tapes, or infinite computational times to be physically useful.

As I see it, expectations are produced analogous to computations, and what's interesting IMO is that the computation is completed/halted at a rate that is on par with the rate of new input. This suggest that the constrainst of information capacity and computing power, determine what is the optimum algorithm. As a simple mind, needs simple rules. A complex mind will use more complex rules.

As I see it there is a highly dynamical interaction here that involes evolution of algorithms, and there is from the point of view of a given observer a limit as to what's decidable. And this can ideally be exploited by a larger observer, to predct how two smaller systems interact, by revealing "their logic".

But any given observer has a decidability limit, and this IMHO at least, is very likely to show up (as observable effects) in the ACTION of this observer, as this is effect a natural cutoff, that is systme dependent.

/Fredrik

 

[D H]

An algorithm to compute the decimal representation of an irrational computable numbers such as the square root of 2 will not stop. The decimal representation of course requires an infinitely-long tape.

In case you care, please notice there is no such thing. Precisely because you can't compute something that need an infinitely-long tape. You may wish to read http://en.wikipedia.org/wiki/Computable_number" on this.

the computable numbers (...) are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm.

...I hope this is not quote mining too much.

It is apparently a complete misunderstanding on your part regarding the concept of a Turing machine and computability. About Turing machines: You are right that there is no such thing as an infinitely-long tape. However, there also is no such thing as a "real" (i.e. physical) Turing machine. It is an idealization of computing invented well before the first digital computer. About computable numbers: The square root of 2 most certainly is a computable number, as are pi and e. Here is an algorithm for computing e: e=\sum_{n=0}^{\infty}1/n!

 

[Fra]

I personally see that this discussion also closely connects to the use of real numbers in physics.

The issues is not just information capacity and memory, it's also about time.

As I see it, one of the type-problems that are interesting in relation to physics is this:

How to rationally compute/infer - given available resources - the optimal next move/action. In a real situation decisions need to be made, based not only upon incomplete information, but also equally important - based on incomplete processing time. Fitness will select such information processing agents for a compromise, that is compromising with halting performance and responsiveness.

I think in physical interactions as well as any decision making process, the "optimum" action - ie. the one chosen by nature an evoluton is a balance between optimality and responsiveness, as BOTH traits are important but to increase the level of optimality make reduce responsiveness, and vice versa. This along introduces randomness and variation around expectations in interactions as it takes a certain amount of time, to reach a certain level of confidence even if the memory isnt' limiting. At least if you define the arrow of time in terms of this computational flow.

/Fredrik

 

[Hurkyl]

Don't know what you've got in mind when you talk about the `construction of types'. The existence of lines is not a first order consequence of the existence of points. The existence of first order definable regions is not a consequence of a theory that only talks about points. I Can see what you might have in mind if you've got first order set-theory in the background. But that is to add something to Tarksi's theory.

There is a class Preline which is a subclass of Point x Point of elements satisfying:

Preline(x,y) = x != y​

and the class Line is the quotient of Preline by the relation:

If (x,y) and (u,v) are in the class Preline, (x,y) =_{Line} (u,v) iff Collinear(x,y,u) and Collinear(x,y,v)​

and the incidence relation "lies on" on Point x Line given by

If (x,y) is in the class Line and z is in the class Point, z lies on (x,y) iff Collinear(x,y,z)​

(and this is a well-defined relation, because it respects =_Line)

No set theory involved, just abstraction.

 

[tom.stoer]

No, because Godel's theorems only apply to formal axiomatic systems, and physical theories aren't formal axiomatic systems.

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.

 

[genneth]

I think people are getting far too caught up in the specifics of Gödel's theorems without realising that it is merely the tip of a very large iceberg. Gödel's theorems apply to systems of arithmetic, and as many people have noted, the embedding of arithmetic into other systems is a tricky prospect; that's even ignoring the issues of whether physics is an axiomisable system in the first place.

However, I would argue that the take-away message of Gödel is that systems which can refer to themselves are *interesting*. Compare with Turing's Halting Problem and also Hilbert's Decision Problem. Experts will tell us that there are fundamental differences between these things, and precise embeddings are often controversial. Nevertheless, thy clearly share a common nugget.

Where does self-reference occur in physics? The clearest example I can think of is in quantum measurement --- to measure is to entangle oneself with the system under observation, then inside the observer there has to be a self-referential copy to indicate that measurement has occurred, etc. I've often thought that half of quantum mechanics is really about formalisation of this fundamental inability to represent faithfully one's own physical state (i.e. non-compression of quantum information --- we can store a classical approximation, but no quantum copy is going to be strictly embeddable).

 

[Lievo]

Your response still sounds to me like you're suggesting that reality is not completely logical.

As I didn't toke position, it sounds to me that's what you want to believe.

It is apparently a complete misunderstanding on your part regarding the concept of a Turing machine and computability. About Turing machines: You are right that there is no such thing as an infinitely-long tape.

I guess this is your spicy way to say I didn't know, thank you.

Does any doubts remains (to you) that TM does not use infinite-length tape?

 

[D H]

I guess this is your spicy way to say I didn't know, thank you.

Does any doubts remains (to you) that TM does not use infinite-length tape?

I do know, thanks. The problem is that you do not. Do you have any doubts that pi is a computable number or that a Turing machine can compute all the digits of pi? That the calculation will take an infinite number of steps and an infinite amount of tape (memory) is irrelevant to the concept of Turing machines. That the algorithm used to do the computation is finite is all that matters.

 

[Lievo]

Do you have any doubts that pi is a computable number or that a Turing machine can compute all the digits of pi?

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

That the calculation will take an infinite number of steps and an infinite amount of tape (memory) is irrelevant to the concept of Turing machines.

The result of a computation is defined as what remains on the tape when the TM halts. If it doesn't halt, there is no result. So yes, of course it's relevant.

 

[D H]

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

Baloney.

The result of a computation is defined as what remains on the tape when the TM halts. If it doesn't halt, there is no result. So yes, of course it's relevant.

More baloney.

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.

 

[Lievo]

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.

Is there anything I can do so that you understand that this, in fact, does apply to your posts, not mine? Would you accept a bet for example?

 

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