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

[Kevin_Axion]

Calculation and experiment I'm assuming.

 

[yossell]

Calculation and experiment I'm assuming.

I take it we're talking past each other. The methodology of how you discover a correct theory - whether by experiment, calculation, inspired intuition - seems a different question from how that theory is to be expressed and formulated. There's nothing in the nature of an axiom system that prevents it from being arrived at via experiment.

 

[S.Daedalus]

It's quite easy to see that those searching for a theory of everything need not be disturbed by Gödel's incompleteness theorems -- take, for instance, Conway's Game of Life: it's computationally universal, and thus, there are undecidable statements about its evolution; however, it nevertheless has a simple TOE -- its evolution rule.

But really, for anyone curious about the subject, Franzen's book, which I think bcrowell has already mentioned, is the single best resource I ever encountered.

 

[unusualname]

This thread should be in philosophy.

Gödel's theorem is just a result about mathematical logic and meta language, you might as well argue whether physics can refute idealism,

In fact physics theories are even finite in their construction, or can be sufficiently well approximated by a finite algorithm and predict all required physical behaviour, they don't even need the countable infinity of natural numbers.

Physics tries to find a concise instruction set to predict nature, it doesn't say anything about philosophical problems which aren't much more relevant than religion.

 

[Lievo]

Conway's Game of Life: it's computationally universal, and thus, there are undecidable statements about its evolution; however, it nevertheless has a simple TOE -- its evolution rule.

A very concise and clear cut way to show that TOE is possible despite incompleteness.

those searching for a theory of everything need not be disturbed by Gödel's incompleteness theorems

I'm not sure to buy this conclusion however. Incompleteness means that there'll always exist some configuration that Conway Game of Life can reach, altough we can't prove it. Conversely, that seems to mean that someone looking for evidence of a TOE can face data that one cannot prove is allowed by a candidate TOE -even if it's the good one.

 

[Chalnoth]

I'm not sure to buy this conclusion however. Incompleteness means that there'll always exist some configuration that Conway Game of Life can reach, altough we can't prove it. Conversely, that seems to mean that someone looking for evidence of a TOE can face data that one cannot prove is allowed by a candidate TOE -even if it's the good one.

Well, this is just the good ol' problem of inference. In general, we can only prove a theory to be false. There is no observational way to say that a theory is genuinely true.

So while we cannot prove everything in a TOE that falls under Goedel's incompleteness theorem, we can prove some things. And if we prove some things that then turn out to be contrary to observation, the theory is falsified. In the way we typically deal with inference, then, we would progressively gain confidence that the TOE is the correct TOE as repeated attempts to falsify the theory fail, and no alternative TOE that also fits those observations is produced.

Let me state, however, that it may be exceedingly difficult, perhaps even impossible in practice, to falsify a TOE. Our current only existing candidate TOE, string theory, is so far in practice unfalsifiable. I should mention that the mathematical basis of string theory really isn't solid yet. A lot of work has been done, but a lot of work remains.

 

[Lievo]

Well, this is just the good ol' problem of inference. In general, we can only prove a theory to be false. There is no observational way to say that a theory is genuinely true.

Yeah of course, good point.

So while we cannot prove everything in a TOE that falls under Goedel's incompleteness theorem, we can prove some things. And if we prove some things that then turn out to be contrary to observation, the theory is falsified.

However, this is not the solely way we deal with observations. I remember having heard that Mercure orbital motion had only 5% of being as it is according to the theory (I don't remember the details exactly). This was puzzling even though this does not falsify anything. Then one adds that once we take some chaotic feature into account, the probability reach 66%. Far more satisfacting. So I wonder if Godel incompletness allows some generic statistical feature that we can't compute but we would find odd to be apparently unreachable with one candidate TOE. Just a though, I'm not even sure one can axiomatize the question.

Our current only existing candidate TOE, string theory, is so far in practice unfalsifiable. I should mention that the mathematical basis of string theory really isn't solid yet. A lot of work has been done, but a lot of work remains.

Well I ain't no specialist, but seems to me what you really need is data. Go LHC go

 

[bcrowell]

I think it's not very hard to effectively embed arithmetic in geometry. Using some fairly simple geometric constructions, you can effectively define + and x geometrically, and then prove incompleteness. I think you need at least two dimensions to do this, but it can be done.

You've got it partly right and partly wrong. You can certainly define addition and multiplication geometrically, and that's exactly what Euclid did. However, there is no way in first-order logic in Euclidean geometry to distinguish between integers and non-integers. (The restriction to first-order logic is what is meant by "elementary" geometry.) This is why elementary geometry is decidable; it can't encode enough arithmetic to be subject to Godel's theorem. This is what Tarski showed in "A decision method for elementary algebra and geometry." http://en.wikipedia.org/wiki/Tarski The dimensionality of the space is irrelevant.

The thing is that physics in general doesn't require axioms to have a well-defined theory.

I guess it depends on what you mean by axioms. For example, Newton's Principia and Einstein's 1905 paper on SR are both presented in a style that reads like an axiomatization, but they are not formal systems in the sense of Godel's theorem. What one person considers an axiom (e.g., constancy of c), another might label as an experimental fact. I don't think the labeling really has any serious consequences. There are some very important ideas in physics, e.g., the equivalence principle, that nobody has ever succeeded in stating in a mathematically well defined way.

 

[bcrowell]

I remember having heard that Mercure orbital motion had only 5% of being as it is according to the theory (I don't remember the details exactly). This was puzzling even though this does not falsify anything. Then one adds that once we take some chaotic feature into account, the probability reach 66%.

This doesn't sound right to me. General relativity currently passes all solar system tests: http://relativity.livingreviews.org/Articles/lrr-2006-3/

Far more satisfacting. So I wonder if Godel incompletness allows some generic statistical feature that we can't compute but we would find odd to be apparently unreachable with one candidate TOE.

Godel's theorems don't have anything to do with statistics.

 

[yossell]

Hi bcrowell,

I think it's even more complicated than this.

I do agree that the Tarksi's geometry is complete and not subject to Godel's incompleteness theorem. However, in many respects Tarski's geometry is *very* weak. There's no room, in Tarski's formulation, for lines, planes, volumes and hypersurfaces. The variables of his theory range over points, and only points.

This is even more restrictive than insisting the theory of geometry be first order. There are first order theories of geometry where you're allowed lines, planes and volumes - you need extra vocabulary to introduce the relation of one point lying on a surface or a volume, or a line lying within a plane. But you're not necessarily into a second order theory.

Hilbert's axiomatisation of geometry did involve both second order notions, and allowed quantification over lines, planes and surfaces. But you don't have to go that far. Within first order theories that allow you to talk of more complicated objects than mere points, the Godel construction can be done and there is incompleteness again.

Full disclosure: I have some issues with the wikipedia article you linked to. In particular, it makes it look as though Tarski does talk of line segments by introducing the notation xy. Indeed, there's even the confusing claim made that xyCongzw is an equivalence relation. As is said in the discussion, Cong is a four place relation. In the discussion, somebody complains about this, but is (wrongly, in my view) told that one can trivially add new notation `xy' to mean the line segment or the pair of points <xy>. But it's not trivial - from a strictly logical point of view, this is a new theory, which contains a bit of set-theory, and it's not clear whether all the results that Tarksi proved for the original theory - such as its completeness and decidability - will still hold. In particular, if the theory is given too much ability to talk about regions corresponding to certain, first order definable sets of points, arithmetic will be embeddable again, and the incompleteness result goes through.

 

[Lievo]

This doesn't sound right to me. General relativity currently passes all solar system tests:

If I remember well it was about the 3/2 revolution-rotation coupling that was less natural than the 1/1 at first look... I can be wrong.

Godel's theorems don't have anything to do with statistics.

My question is certainly too vague and may completely lack soundness. However if one counts the number of Turing machine that halts as a function of time... this is a statistic and of course this has a lot to do with Godel's theorems.

 

[Chalnoth]

However, this is not the solely way we deal with observations. I remember having heard that Mercure orbital motion had only 5% of being as it is according to the theory (I don't remember the details exactly). This was puzzling even though this does not falsify anything. Then one adds that once we take some chaotic feature into account, the probability reach 66%. Far more satisfacting. So I wonder if Godel incompletness allows some generic statistical feature that we can't compute but we would find odd to be apparently unreachable with one candidate TOE. Just a though, I'm not even sure one can axiomatize the question.

Sorry, I think you'll need to be a lot more specific.

Anyway, in reality, yes, there is always a question of whether or not we have really falsified a theory. Things are rarely cut and dried. The basic reason for this is just that it's actually not feasible to take into account all of known physics when computing the expected result of all but the most trivial of experiments. So instead of taking everything and anything into account, we make approximations. For instance, if we want to know precisely the orbital motion of Mercury as predicted by Newton's laws, in principle we have to take into account not just the Sun and Mercury, but the motion of every massive object in the entire universe. Obviously we're not going to do that, so we make approximations, and attempt to get some sort of estimate of the effect from the stuff we leave out, so that we can gain confidence that our approximations don't impact the final result.

In the end, this sort of fuzziness just comes down to having to be very careful and very thorough when determining whether or not a theory is falsified (in this case, Mercury's orbit does falsify Newtonian gravity quite well, while General Relativity properly predicts its orbit). It doesn't actually impact the Goedel incompleteness theorem stuff at all, because it's just down to experimental rigor and the messiness of reality.

Well I ain't no specialist, but seems to me what you really need is data. Go LHC go

Well, there is that, but unless the properties of our particular observable region are just right, our chances of detecting string theory at the LHC or any feasible collider we have a chance of building in the next few decades is slim to none.

But string theory itself isn't fully worked-out, so if the theorists really dig deeply into the math and flesh it out in full, they may come up with a new way to interpret existing experiment to determine whether or not string theory is accurate, or they may come up with a new but very feasible experiment that we might potentially use to test string theory. In the mean time, lots of work remains to be done just in terms of understanding the theory itself.

 

[bcrowell]

I do agree that the Tarksi's geometry is complete and not subject to Godel's incompleteness theorem. However, in many respects Tarski's geometry is *very* weak. There's no room, in Tarski's formulation, for lines, planes, volumes and hypersurfaces. The variables of his theory range over points, and only points.

This is even more restrictive than insisting the theory of geometry be first order. There are first order theories of geometry where you're allowed lines, planes and volumes - you need extra vocabulary to introduce the relation of one point lying on a surface or a volume, or a line lying within a plane. But you're not necessarily into a second order theory.

Hmm...interesting. Are these first-order theories that include lines as primitive objects decidable, or not?

I think what's becoming more clear to me, both from this post and from the ones about Conway's game of life, is that there's a vast amount of ambiguity in what it would mean to make a formal theory in the Godel sense out of a physical theory.

Here's another example. If you look through Stephani et al., "Exact solutions of Einstein's field equations," you'll find hundreds of examples. Typically they're stated by giving a metric in closed form, and then they can be checked automatically on a computer. There's a heck of a lot of interesting physics in those solutions. I think anyone who knows the physical significance of all of them knows a heck of a lot of GR. In this sense, you could say that GR is decidable. That is, every statement of the form "[foo] is a solution of the Einstein field equations," where [foo] is a metric written in some formal language, can be shown to be true or false by running computer software.

On the other hand, you might want to prove statements about GR such as the Hawking-Penrose singularity theorems. My guess is that any formalism strong enough to prove these is probably also decidable.

 

[S.Daedalus]

Not replying to anybody in particular, but I don't see how one can hope to have a theory of everything be decidable -- after all, there are real world systems, the most obvious ones being ordinary computers, about which there exist undecidable statements. That even occurs in plain old Newtonian gravity: you can build a system equivalent to a universal computer out of finitely many gravitating bodies, and thus, can't predict its evolution in general.

 

[yossell]

Hmm...interesting. Are these first-order theories that include lines as primitive objects decidable, or not?

I believe so. I think one can just take something like the Hilbert formulation, but replace his second-order formulas with first order schema and treat the different variables as different sorts, rather than of being first or second order.

I think what's becoming more clear to me, both from this post and from the ones about Conway's game of life, is that there's a vast amount of ambiguity in what it would mean to make a formal theory in the Godel sense out of a physical theory.

Does this mean that there's a vast amount of ambiguity in the notion of a physical theory itself?

caveat: I may not have understood what you mean by decidable though - the way you use it in the latter part of your post lost me a little.

 

[Lievo]

If I remember well it was about the 3/2 revolution-rotation coupling that was less natural than the 1/1 at first look... I can be wrong.

That is right finally
http://www.nature.com/nature/journal/v429/n6994/full/nature02609.html

 

[Lievo]

Sorry, I think you'll need to be a lot more specific.

Ok let's give it a try. Suppose you have a TOE that perfectly account for any data so far, and your computations predict that either the mater could have dominated (7%) or the antimatter (93%). (your TOE includes some specific prediction which allows you to disambiguate matter from anti-matter).

This would not be strong enough to refute the theory. Still it would be uncomfortable, in the sense that if you can modify your computation to reach 55%, you'll be happy and confident the modification is sound.

It seems that physics includes some computational procedures that are not based on completely firm mathematics (renormalisaton). If I understand the basic reason is we can't compute sums over the infinite when the function does not behave well. This is quite the same as asking the behavior of a Turing machine, isn't it?

 

[Chalnoth]

Ok let's give it a try. Suppose you have a TOE that perfectly account for any data so far, and your computations predict that either the mater could have dominated (7%) or the antimatter (93%). (your TOE includes some specific prediction which allows you to disambiguate matter from anti-matter).

This would not be strong enough to refute the theory. Still it would be uncomfortable, in the sense that if you can modify your computation to reach 55%, you'll be happy and confident the modification is sound.

It seems that physics includes some computational procedures that are not based on completely firm mathematics (renormalisaton). If I understand the basic reason is we can't compute sums over the infinite when the function does not behave well. This is quite the same as asking the behavior of a Turing machine, isn't it?

Sorry, but I just don't get what this has to do with Goedel's incompleteness theorem.

 

[bcrowell]

That is right finally
http://www.nature.com/nature/journal/v429/n6994/full/nature02609.html

But as far as I can tell this has nothing to do with Godel's theorems.

 

[bcrowell]

Not replying to anybody in particular, but I don't see how one can hope to have a theory of everything be decidable -- after all, there are real world systems, the most obvious ones being ordinary computers, about which there exist undecidable statements. That even occurs in plain old Newtonian gravity: you can build a system equivalent to a universal computer out of finitely many gravitating bodies, and thus, can't predict its evolution in general.

I think it may depend on what kinds of theorems you hope to be able to prove about this hypothetical TOE that can hypothetically be made into a formal system. In your example of a computer as a physical system, consider the following two statements that could conceivably be translated into propositions in the hypothetical formal language:

P1. When the computer is put into an initial state S1 at time t=0, its state at time t=1 hour will be S2.

P2. When the computer is put into an initial state S1 at time t=0, it will eventually halt.

P1 is clearly decidable, and it corresponds to a definite prediction that can be tested by experiment.

You might be tempted to say that P2 is undecidable (for generic S1), and therefore the TOE contains undecidable propositions. I think there is both a mathematical objection and a physical objection to this. The mathematical objection is that when Turing proved that the halting problem was undecidable, he did it for Turing machines, but Turing machines have infinite storage space, as well as various other mathematically idealized properties, that may be incompatible with a TOE. The physical problem is that P2 does not correspond to any definite prediction that can be tested by experiment, because no experiment can ever establish that P2 is false.

 

[Lievo]

Sorry, but I just don't get what this has to do with Goedel's incompleteness theorem.

The connection is the following: if your TOE is powerfull enough so that Goedel incompleteness applies, then you have some Turing machines that don't halt. That the same statement.

So the question is: does some of these machines compute something you care about? I think renormalisation is in effect an approximation physicist do because they can not compute the function directly. Which may well be because the function is not computable. I don't think it has been proven yet, so it still may be because we don't know the proper way to deal with these computations, but so far I know this is an actual possibility.

 

[Lievo]

But as far as I can tell this has nothing to do with Godel's theorems.

I don't see either, nor why you ask. This was an exemple of an observation that is used in science without fitting the Poperian framework, https://www.physicsforums.com/showpost.php?p=3035121&postcount=37" to a statement Chalnoth made.

 

[Lievo]

You might be tempted to say that P2 is undecidable (for generic S1), and therefore the TOE contains undecidable propositions.

I don't see how you could conclude otherwise...

The mathematical objection is that when Turing proved that the halting problem was undecidable, he did it for Turing machines, but Turing machines have infinite storage space, as well as various other mathematically idealized properties, that may be incompatible with a TOE.

If something is undecidable with as much time as you want, of course it's still undecidable using limited time. What are the various other mathematical idealized properties you're talking about? PS: technically speaking, TM don't have infinite storage space.

The physical problem is that P2 does not correspond to any definite prediction that can be tested by experiment, because no experiment can ever establish that P2 is false.

How could that prevent the TOE to contain undecidable proposition?

 

[D H]

Technically speaking, Turing machines do have an infinitely-long tape.

 

[Lievo]

Technically speaking, Turing machines do have an infinitely-long tape.

Sire, no sire.

 

[Hurkyl]

Hi bcrowell,

I think it's even more complicated than this.

I do agree that the Tarksi's geometry is complete and not subject to Godel's incompleteness theorem. However, in many respects Tarski's geometry is *very* weak. There's no room, in Tarski's formulation, for lines, planes, volumes and hypersurfaces. The variables of his theory range over points, and only points.

...

In particular, if the theory is given too much ability to talk about regions corresponding to certain, first order definable sets of points, arithmetic will be embeddable again, and the incompleteness result goes through.

I think first-order logic is more powerful than you give it credit for -- without adding extra power, you can have variables ranging over classes of ordered pairs, subtypes defined by a predicate, or types constructed as the quotient of another type by an equivalence relation.

Even if you prefer a stripped-down version of first-order logic, there is a mechanical way to transform any statement involving these more convenient concepts into one that does not.


EDIT: First-order Euclidean geometry is sufficiently powerful that I don't think you need to explicitly add in equivalence relations or products -- once you throw in classes you get everything you need.

e.g. an ordered pair of points in the plane can be encoded as a point in 4-space. And rather than define "line in the plane" to be a pair of points modulo an equivalence relation, you can instead define it to be a point in the punctured projective plane, and such points can be defined as being a point of 4-space satisfying a polynomial equation.

 

[Coin]

I don't think decidability is a necessary or even particularly desirable property for a TOE. A couple of observations.

- The "undecidable" statements in an incomplete system are often not important or useful. Usually these statements wind up being arcane and have to do with self-referential or "vicious circle" type statements.

- If you somehow find that you actually do care about a particular undecidable statement, you can make the undecidable statement decidable by just picking a more expressive axiom system, something analogous to going from first-order to second-order logic. The new axiom system can make the undecidable statements decidable, at the cost of introducing new undecidable statements (which, in the previous system, would not have even been expressible). However this is still progress from any practical perspective because the new undecidable statements will be more arcane than the old ones.

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

The Franzen book sounds interesting, thanks to bcrowell for recommending it.

 

[Coin]

A TM which lacks access to unbounded storage space can be represented with a sufficiently ugly DFA; therefore, the set of languages recognized by such a machine is decidable. This is the case even for TM variants with what seems like very generous abilities. For example, LBAs are decidable (i.e. linear bounded automata, machines which solve O(N) problems).

 

[yossell]

I think first-order logic is more powerful than you give it credit for -- without adding extra power, you can have variables ranging over classes of ordered pairs, subtypes defined by a predicate, or types constructed as the quotient of another type by an equivalence relation.

Even if you prefer a stripped-down version of first-order logic, there is a mechanical way to transform any statement involving these more convenient concepts into one that does not.

I'm not sure what in my post you're taking issue to. Are you saying that, contra my post, the existence of lines, planes and volumes does follow in Tarksi's formulation? Are you saying that the theory can already speak of first order definable regions?

edit: I could be wrong, but I'm pretty confident that arithmetic can be embedded in first order geometry, and I'm pretty confident that Tarksi's formulation of geometry is complete - so there must be some limitation to the amount you can do in his formulation.

 

[Hurkyl]

I'm not sure what in my post you're taking issue to. Are you saying that, contra my post, the existence of lines, planes and volumes does follow in Tarksi's formulation? Are you saying that the theory can already speak of first order definable regions?

Yes -- and this is a property of first-order logic itself, rather than having anything to do with the specific formal theory we're considering. (Although Euclidean geometry does allow you to do things in a more convenient way)

Anything that can be named by a fixed-size finite ordered tuple of numbers satisfying a polynomial condition, and for which equality is a polynomial condition on the numbers can be described using Tarski's formulation.

How convenient it is to do so depends on whether you are using the niceties one can develop for formal logic -- it's sort of like the difference between programming in assembly language and programming in a high-level language, if you're familiar with that sort of thing.

edit: I could be wrong, but I'm pretty confident that arithmetic can be embedded in first order geometry, and I'm pretty confident that Tarksi's formulation of geometry is complete - so there must be some limitation to the amount you can do in his formulation.

Yes -- bcrowell already pointed it out: you cannot define what it means to be an integer. Your sentence is pretty much the entire proof. This includes any analytic technique for which there is not an algebraic substitute for algebraic curves -- e.g. no transcendental number can be proven to exist, which in turn implies that you generally cannot talk about things like "the length of a curve".