Register to reply

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

by PhysDrew
Tags: gödel, impact, incompleteness, theorems
Share this thread:
bcrowell
#73
Dec13-10, 06:55 PM
Emeritus
Sci Advisor
PF Gold
bcrowell's Avatar
P: 5,582
Quote Quote by yossell View Post
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
#74
Dec13-10, 07:06 PM
Emeritus
Sci Advisor
PF Gold
bcrowell's Avatar
P: 5,582
Quote Quote by Coin View Post
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.

Quote Quote by D H View Post
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
#75
Dec13-10, 07:06 PM
P: 268
Quote Quote by D H View Post
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.

Quote Quote by Coin View Post
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 begining to be fed up of stating the obvious. Last time I comment this.
D H
#76
Dec13-10, 07:09 PM
Mentor
P: 15,061
Quote Quote by Lievo View Post
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
#77
Dec13-10, 07:11 PM
Sci Advisor
P: 4,782
Quote Quote by Lievo View Post
-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
#78
Dec13-10, 07:38 PM
P: 268
Chalnoth, as you previously teach me some stuff I should not refuse to answer you.

Quote Quote by Chalnoth View Post
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
#79
Dec13-10, 08:01 PM
Mentor
P: 15,061
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
#80
Dec13-10, 08:15 PM
P: 587
We are getting a little off topic. But.

Quote Quote by Lievo View Post
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
#81
Dec13-10, 09:06 PM
P: 965
Quote Quote by bcrowell View Post
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
#82
Dec13-10, 09:12 PM
Sci Advisor
P: 4,782
Quote Quote by friend View Post
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
#83
Dec13-10, 09:12 PM
Mentor
P: 15,061
Quote Quote by friend View Post
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
#84
Dec13-10, 09:35 PM
P: 268
Quote Quote by Lievo
I should not refuse to answer you.
I should not refuse to answer anyone. My apologies for this misbehavior.

Quote Quote by D H View Post
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 wikipedia 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.

Quote Quote by Coin View Post
In fact your statement here is basically tautological (..) Do you disagree?
Well said (...) 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.
yossell
#85
Dec13-10, 10:49 PM
P: 341
Quote Quote by Hurkyl View Post
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
#86
Dec13-10, 10:58 PM
P: 965
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?)


Quote Quote by D H View Post
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
#87
Dec13-10, 11:08 PM
P: 965
Quote Quote by Chalnoth View Post
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.

Quote Quote by Chalnoth View Post
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
#88
Dec13-10, 11:16 PM
P: 268
Quote Quote by friend View Post
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 writings about this.
yossell
#89
Dec13-10, 11:17 PM
P: 341
Quote Quote by bcrowell View Post
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
#90
Dec13-10, 11:27 PM
P: 965
Quote Quote by Lievo View Post
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 text book 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.


Register to reply

Related Discussions
Creating a vert. drop impact that is equivalent to a faster, but lighter hor. impact General Physics 5
On Gödel General Math 12
Kant, Gödel, Tarski - help General Discussion 6
Gödel and physical theories General Discussion 0