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

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

 

[D H]

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

Exactly. This thread is really just a quibble over what exactly constitutes a TOE. Would a theory that unites the electroweak interaction, strong interaction, and gravitation qualify as a TOE? Would it be a TOE even if it leaves the particle zoo in more or less the same shape as in the standard model? Would it be a TOE if it cannot definitively answer when the last atom in a pile of ¹⁴C decays to nitrogen? Would it still be a TOE if it cannot definitively answer if, when, and where, a perfectly round ball perfectly balanced on Norton's dome reaches the bottom of the dome?

 

[bcrowell]

edit: I could be wrong, but I'm pretty confident that arithmetic can be embedded in first order geometry

I'm pretty sure you're wrong about that. See #38.

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

Sire, no sire.

D H is correct. http://en.wikipedia.org/wiki/Turing_machine

 

[yossell]

Hurkyl, I'm not following you. I'm not interested in convenience. I've already said there are limitations in what can be done in Tarksi's system. Your posts seemed to be arguing the contrary, but now it seems they are not.

I pointed out that there are first order systems of geometry, which allow quantification over first order definable regions, in which arithmetic can be embedded. Is this what you disagree with?

 

[yossell]

I'm pretty sure you're wrong about that. See #38.

I thought we'd discussed this, and I explained that I thought that Tarski's system did not capture everything that is meant by first order geometry. This could come down to semantics - if by first order geometry you just mean Tarksi's theory, fine. But if you modify Hilbert's original theory, replacing the second order axioms with first order schemas, then I believe you have a system in which you can get arithmetic.

I'm willing to admit this could be wrong, but post 38 alone doesn't show it.

 

[Lievo]

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

D H is correct.

No sire. Technically speaking, a Turing memory do not have an infinite-long tape. Please give wikipedia a closer look.

Additional details required to visualize or implement Turing machines (...)
The tape can be finite, and automatically extended with blanks as needed (which is closest to the mathematical definition)

 

[yossell]

If you're interested, a first order versions of Hilbert's `Foundations of Geometry' were developed in a book by Hartry Field called `Science Without Numbers.'

Stuart Shapiro (the same Shapiro who wrote `Foundations without Foundationalism' - quite a nice reference on second order logic), in a paper called `Conservativeness and Incompleteness' (Journal of Philosophy 1983) argued that arithmetic was embeddable in Field's geometry, and so the system contained a Godel sentence. Since the consistency of arithmetic was provable in ZFC, Shapiro took this to undermine Field's claim that mathematics was conservative. Field responded in a paper called `On Conservativeness and Incompleteness' (Journal of Philosophy 1983), effectively admitting the technical point, but arguing that it did not have quite the conceptual significance.

Unfortunately, these papers don't seem to be freely available.

 

[D H]

No sire. Technically speaking, a Turing memory do not have an infinite-long tape. Please give wikipedia a closer look.

Additional details required to visualize or implement Turing machines (...)
The tape can be finite, and automatically extended with blanks as needed (which is closest to the mathematical definition)

Nice job of quote mining, Lievo. You omitted the very next sentence.

The tape cannot be fixed in length, since that would not correspond to the given definition and would seriously limit the range of computations the machine can perform to those of a linear bounded automaton.

 

[Coin]

No sire. Technically speaking, a Turing memory do not have an infinite-long tape. Please give wikipedia a closer look.

Additional details required to visualize or implement Turing machines (...)
The tape can be finite, and automatically extended with blanks as needed (which is closest to the mathematical definition)

This dodge is common, and it's why I used the word "unbounded" rather than "infinite" in my post on the last page. The thing is though that even if you are using this dodge, the TM tape is still infinite from the perspective of the mathematical formalism. Within the formalism, we have an infinite series of blank boxes, any of which we may move to and write over. Whether this formal property of the tape is implemented in the real world by somehow acquiring an infinitely long strip of paper, or implemented using a finite tape which additional sections are periodically spliced onto by an army of human servants, these different implementation details are equivalent and unimportant from the formalism's perspective. (Especially since in the real world, people generally don't build literal turing machines at all...)

 

[PhysDrew]

One more thing I would like to propse which was brought up earlier, is what the everything in the TOE actually means? I've heard it discussed that a TOE may have predictive power, but however I have also heard by other physicists that the TOE will be nothing more than a joining of mathematical realtionships to give one unique 'formula' with little to no predictive power, rendering it to low importance in the grand scheme of things. I think Godels theorem/s may or may not apply depending on which scheme it is applied to?
By the way has anyone noticed the self referential hint I put into the title?!

 

[Fra]

I wasn't sure wether to bother entering the discussion, because maybe it's not possible to be brief so maybe I should keep quiet, but I'll just throw in my wet socks and be done with it.

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.

If you believe in that information is bounded and that any observer process and hold only finite info, there is a limit of the amount of confidence any information processing agent/observer can accumulate. At some point there is a saturation and you can't inflate the theory by adding the gödel scentences as another axiom, where the progression ends, and all the TOE means is an effective basis for further actions. Also there is not guarantee that there is any convergence to a unique TOE, it may be that it just keeps evolving by destruction of axioms and generation of new ones.

I'll just make the story short and att my OPINION that I think an analysis of all this, decidability, inference, incompletness theorems support by plausability (but not imply in any logical sense) the idea of evolving law and that it's impossible to distinguish cleanly between law and state, simply because they are both merely results of inference, and the limit of infinite confidence in a unique limit seems seems highly unphysical.

If you think about the limits of a TOE, it seems to be at least that is subject to constraints similar to the information state. The TOE represents the observers "state of information" of the expected laws of evolution of the information state. So it's another layer of information.

The more common idea that laws of physics are eternal, correspond as I see it to the "infinite confidence" limits in the progression mentioned. But this limit may not exists, for two reasons (unknow non-uniqueness/convergence) and the lack of information capacity to encode this limit/confidence (if at hand).

This can be expanded alot, but I agree it does enter philosophy, and it's also not very conclusive therefor I think it's value is mainly suggestive and inspirational. Therefor there is a limit to how much it makes sense to elaborate. This is already a long thread but I've added my short input.

/Fredrik

 

[Hurkyl]

Hurkyl, I'm not following you. I'm not interested in convenience. I've already said there are limitations in what can be done in Tarksi's system. Your posts seemed to be arguing the contrary, but now it seems they are not.

I'm stating that Tarski's system is not as limited as you make it out to be. There are clear limitations -- e.g. that the theory of integer arithmetic cannot be expressed in it -- but it is not as limited as you claim -- e.g. it is able to discuss lines.

The objection you had against lines was that you were rejecting the syntactic tools of first-order logic. Constructing the type of Euclidean Lines from the type of Euclidean Points, for example, is pure first-order logic -- you are not creating a new theory by doing so.

 

[Chalnoth]

If you believe in that information is bounded and that any observer process and hold only finite info, there is a limit of the amount of confidence any information processing agent/observer can accumulate. At some point there is a saturation and you can't inflate the theory by adding the gödel scentences as another axiom, where the progression ends, and all the TOE means is an effective basis for further actions. Also there is not guarantee that there is any convergence to a unique TOE, it may be that it just keeps evolving by destruction of axioms and generation of new ones.

Yes, this is pretty obvious.

Basically our only hope of finding the TOE is if it turns out that mathematical consistency severely limits the possible TOE's so that the correct one can be experimentally distinguished from the others. There is obviously no guarantee that this is the case. And there is certainly no guarantee that we will be able to genuinely demonstrate that there aren't any TOE's that are also consistent but experimentally indistinguishable.

The more common idea that laws of physics are eternal, correspond as I see it to the "infinite confidence" limits in the progression mentioned. But this limit may not exists, for two reasons (unknow non-uniqueness/convergence) and the lack of information capacity to encode this limit/confidence (if at hand).

Well, you can make any laws of physics eternal simply by having the laws of physics describe any changes that occur. But in any event, obviously infinite confidence isn't possible, and I wasn't attempting to imply it was.

 

[bcrowell]

I thought we'd discussed this, and I explained that I thought that Tarski's system did not capture everything that is meant by first order geometry. This could come down to semantics - if by first order geometry you just mean Tarksi's theory, fine. But if you modify Hilbert's original theory, replacing the second order axioms with first order schemas, then I believe you have a system in which you can get arithmetic.

I'm willing to admit this could be wrong, but post 38 alone doesn't show it.

Like Hurkyl, I'm not convinced by your assertion, and I haven't seen you offer any evidence for it. My #38 does offer evidence for my assertion, in the form of a reference to Tarski's paper "A decision method for elementary algebra and geometry." Anyway, I don't know if any of this even matters for the purposes of this thread. It seems that we all agree that there are weaker and stronger formulations of geometry, that the weaker ones don't give enough arithmetic for Godel to apply, and that the stronger ones do.

 

[bcrowell]

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

I agree disagree only because IMO this is putting it too mildly. I don't think there is even any clearly defined notion of what it would mean for a physical theory to be decidable.

This thread is really just a quibble over what exactly constitutes a TOE.

And again I disagree only because IMO this is putting it too mildly. I think it's even less than a quibble over what constitutes a TOE. If we get a TOE, we'll know it's a TOE because it will unite the four forces, reconcile GR with quantum mechanics, and make testable predictions that are verified by experiment. That's how we'd know what constituted a TOE. We can't use decidability to define what a TOE would be, because the notion of decidability is fundamentally inappropriate for talking about physical theories.

 

[Lievo]

Nice job of quote mining, Lievo. You omitted the very next sentence.

Which states that the tape is unbounded, and that's not the same, technically speaking, as infinite.

the TM tape is still infinite from the perspective of the mathematical formalism.

This is just making no sense! Ok two ways to see it:
-the tape of any TM that halts is bound by the busy beaver function. It's large, it's unbounded, and it's finite. If the TM doesn't halt, you don't need any tape at all, because you'll never get the result of the TM -which is define as what remains when the TM stops. Of course you can't, in general, know if your TM belong to one or the other class. Doesn't change the tape you need is finite.
-if you think it's infinite, then precise what infinite you're talking about. Is it aleph 0? No, or you'd enter hypercomputation. Is it more? No, that's worse! Is it less than aleph 0? Well, if you believe there is such a thing as an infinite less than aleph 0, go and publish!

Sorry, I'm beginning to be fed up of stating the obvious. Last time I comment this.

 

[D H]

Which states that the tape is unbounded, and that's not the same, technically speaking, as infinite.

Technically speaking, saying that the length is unbounded exactly the same as saying it is infinite.

 

[Chalnoth]

-the tape of any TM that halts is bound by the busy beaver function. It's large, it's unbounded, and it's finite. If the TM doesn't halt, you don't need any tape at all, because you'll never get the result of the TM -which is define as what remains when the TM stops. Of course you can't, in general, know if your TM belong to one or the other class. Doesn't change the tape you need is finite.

If you don't know whether or not the program halts, then you don't know beforehand how much tape is required, which means you need infinite-length tape or risk your computer crashing.

 

[Lievo]

Chalnoth, as you previously teach me some stuff I should not refuse to answer you.

If you don't know whether or not the program halts, then you don't know beforehand how much tape is required, which means you need infinite-length tape or risk your computer crashing.

What you need, mathematically speaking, is at most the busy beaver corresponding to the number of non blank in the initial state. Nothing more, and that's finite. Pratically speaking, be sure your computer will crash before reaching it.

 

[D H]

Baloney. Busy beavers halt. Halting is not a requirement of a Turing machine program. 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.

 

[Coin]

We are getting a little off topic. But.

What you need, mathematically speaking, is at most the busy beaver corresponding to the number of non blank in the initial state. Nothing more, and that's finite. Pratically speaking, be sure your computer will crash before reaching it.

I think some of this disagreement might be avoidable if we speak precisely.

1. A turing machine must have access to an unlimited amount of tape in order to capture the full power of the turing machine formalism.

2. Any given turing machine, when run on an input for which it terminates, will only use a finite amount of that tape.

The lack of a limitation on space can't be waved away by saying "but that's only for terminating programs", because a significant portion of the power of turing machines in the first place comes from the fact that turing machines have the option of never terminating. The decidable languages are a smaller set than the recognizable languages. If there is a known bound on either runtime or space used, then all programs are "decidable" and you have something weaker than a turing machine.

You are correct that the busy beaver function does define an upper bound on space usage for halting programs. However this statement is not useful to know, because BB(n) is noncomputable. (In other words, BB(n) is a bound, but it is an unknown and unknowable bound). In fact your statement here is basically tautological, because BB(n) is defined as the maximum number of tape squares used up by an eventually-terminating program of a given complexity. So what you are saying is that the number of squares used by a terminating program will be equal to or less than the number of squares it uses.

Do you disagree?

 

[friend]

I think it's even less than a quibble over what constitutes a TOE. If we get a TOE, we'll know it's a TOE because it will unite the four forces, reconcile GR with quantum mechanics, and make testable predictions that are verified by experiment. That's how we'd know what constituted a TOE. We can't use decidability to define what a TOE would be, because the notion of decidability is fundamentally inappropriate for talking about physical theories.

A Theory of everything would at least explain why there are particles, fields, and even spacetime to begin with. Are we going to be fully satisfied if we predict and/or discover smaller, higher energy particles? No, we'll wonder where those came from, and so on, etc, etc. I think we will not be satisfied until we have explained everything in terms of the principles of reason. Once you derive physics from logic alone, then what is there left to question? There would be nothing left except to maybe question your sanity. But to predict the properties of things does not explain where they came from.

I think a theory of quantum gravity would probably be a TOE, because it would unit QM with GR, particles and fields with spacetime. And to unite spacetime and particles fields would probably require a theory from reason alone. For physically, there is nothing more fundamental than spacetime and particles/fields. And to explain something more fundamental than what is physical would have to rely on complete, abstract, generality about anything true; it would have to rely on principle alone.

So here we are discussing whether physics can be reduced to a complete axiomatic system. The question is not even relevant unless we can derive physics from a system of reasoning. I don't think it will reduce to the axioms of geometry because we would still have to explain why there is geometry, or spacetime, to begin with. It would have to reduce to reason, or we would still have questions and it would not be complete. (am I using "complete" equivocally here?)

 

[Chalnoth]

A Theory of everything would at least explain why there are particles, fields, and even spacetime to begin with. Are we going to be fully satisfied if we predict and/or discover smaller, higher energy particles? No, we'll wonder where those came from, and so on, etc, etc. I think we will not be satisfied until we have explained everything in terms of the principles of reason. Once you derive physics from logic alone, then what is there left to question? There would be nothing left except to maybe question your sanity. But to predict the properties of things does not explain where they came from.

I think a theory of quantum gravity would probably be a TOE, because it would unit QM with GR, particles and fields with spacetime. And to unite spacetime and particles fields would probably require a theory from reason alone. For physically, there is nothing more fundamental than spacetime and particles/fields. And to explain something more fundamental than what is physical would have to rely on complete, abstract, generality about anything true; it would have to rely on principle alone.

So here we are discussing whether physics can be reduced to a complete axiomatic system. The question is not even relevant unless we can derive physics from a system of reasoning. I don't think it will reduce to the axioms of geometry because we would still have to explain why there is geometry, or spacetime, to begin with. It would have to reduce to reason, or we would still have questions and it would not be complete. (am I using "complete" equivocally here?)

The difficulty is that there is no guarantee that there exists only one unique TOE. There may be a great many potential ones. Even after discovering a potential TOE, we would still need to determine whether or not it applies to our reality. Pure rational deduction can never ever tell us whether or not a TOE applies to our reality.

 

[D H]

It would have to reduce to reason, or we would still have questions and it would not be complete. (am I using "complete" equivocally here?)

You are using complete incorrectly here. This is a thread on Godel's incompleteness theorems, and whether they have any relevance to a TOE.

 

[Lievo]

I should not refuse to answer you.

I should not refuse to answer anyone. My apologies for this misbehavior.

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.

In fact your statement here is basically tautological (..) Do you disagree?

Well said (...) No, except for some details: decidable and recognizable that'shttp://xw2k.nist.gov/dads/html/decidableLanguage.html" , 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.

 

[yossell]

I'm stating that Tarski's system is not as limited as you make it out to be. There are clear limitations -- e.g. that the theory of integer arithmetic cannot be expressed in it -- but it is not as limited as you claim -- e.g. it is able to discuss lines.

The objection you had against lines was that you were rejecting the syntactic tools of first-order logic. Constructing the type of Euclidean Lines from the type of Euclidean Points, for example, is pure first-order logic -- you are not creating a new theory by doing so.

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.

 

[friend]

Originally Posted by friend
It would have to reduce to reason, or we would still have questions and it would not be complete. (am I using "complete" equivocally here?)

You are using complete incorrectly here. This is a thread on Godel's incompleteness theorems, and whether they have any relevance to a TOE.

I'm not so sure. "reduce to reason" is a reference to logic which is relevant to Godel's Theorems. "still have questions" asks about how the subject in question is proven, which goes to Godel's incompleteness theorem. So it might be my use of the word "complete" is on topic.

 

[friend]

The difficulty is that there is no guarantee that there exists only one unique TOE. There may be a great many potential ones.

As I understand it, if two systems of complete and consistent sets of axioms agree at any point, then they are equivalent. If reality is completely logical and rational in every detail, then it can be reduced to logic.

Even after discovering a potential TOE, we would still need to determine whether or not it applies to our reality. Pure rational deduction can never ever tell us whether or not a TOE applies to our reality.

Are you suggesting that reality is somewhere, somehow not completely logical? I think you'd have a hard time actually proving that.

 

[Lievo]

Are you suggesting that reality is somewhere, somehow not completely logical?

In my view he's just suggesting that pure logic is not powerfull enough to find the TOE. There have been some https://www.amazon.com/dp/0521657296/?tag=pfamazon01-20about this.

 

[yossell]

Like Hurkyl, I'm not convinced by your assertion, and I haven't seen you offer any evidence for it.

So my citation of papers doesn't count? Ok - what would you like?

My #38 does offer evidence for my assertion, in the form of a reference to Tarski's paper "A decision method for elementary algebra and geometry."

But I've acknowledged the existence of this paper, and everything you say about it. I've not denied this. What I questioned is that every first order theory of geometry reduces to Tarski's formulation. I've even given the theory that I have in mind: the first order weakening of Hilbert's theory in his Foundations of Geometry. #38 just doesn't speak to this.

I'll sketch the idea, but it's going from memory so, as ever, I could be wrong.

If you like, think of Hilbert's second order axioms as being replaced with schemas, plus axioms asserting the existence of first order definable regions to give us the points to give us the lines, planes and regions of the theory (I disagree with Hurkyl that these regions exist as a matter of first order logic from the theory of points). Then one can define a region R which consists of an infinite sequence of points p1, p2, p3..., such that all points lie on the same line, p1p2 Cong p2p3, p2p3Congp3p4..., there is no point p on R such that p1 lies between p2 and p...

Basically, we can define the existence of a region using the points of an arbitrarily, infinite spaced region with one endpoint, and these then behave like the natural numbers. Certain geometric constructions allow us, within this theory, to define addition and multiplication on this points of this region, and then we have enough material to do the Godel construction.

 

[friend]

In my view he's just suggesting that pure logic is not powerfull enough to find the TOE.

The other criticism is that logic is too powerful and applies to more than just physical situations. But the fact that logic can apply to fiction as well as to fact means nothing. For all physical laws apply to fictional situations as well as to factual situations. Every problem in a physics textbook does not refer to any actual facts in nature, but they refer to fictional situations invented in the imagination of the author.

Your response still sounds to me like you're suggesting that reality is not completely logical. I don't think that is the view of science. I think that we go off in search of answers because we think things are rational. I don't think that any credible scientist is trying to prove that reality is illogical.

 

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