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

[D H]

In the absence of evidence for a hypercomputable entity, it's indeed more parsimonious to not assume its existence; and frankly, I don't think it's possible to produce such evidence -- as I said, you have to be an oracle to recognize an oracle.

That is not how science works. The burden is not upon science to disprove some radical concept. The burden is upon you as the proponent of some concept to offer proof of the validity of that concept.

That said, there have been a growing number of papers in the last ten years or so that question the applicability of the Church-Turing thesis to physical reality and that discuss the concept of hypercomputation with respect to the physical universe. Here are just a couple; I'll dig some more up over the weekend.

Hajnal Andréka, István Németi and Péter Németi, "General relativistic hypercomputing and foundation of mathematics", Natural Computing, 8:3 499-516 (2009)
http://www.renyi.hu/pub/algebraic-logic/uc08.pdf

Oron Shagrir and Itamar Pitowsky, "Physical Hypercomputation and the Church–Turing Thesis", Minds and Machines, 13:1 87-101 (2003)
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.112.6817&rep=rep1&type=pdf

 

[qsa]

I had understood it as a mathematical representation of the kinds of processes going on in the physical universe possibly involving continuous quantities themselves varying continuously according to partial differential equations. Though demonstrably representable mathematically, such systems do not necessarily correspond to Turing machines.

Apologies if I got you wrong.

As a matter of fact it is known that monte carlo/random walk methods are used to solve PDE (especially the tough ones) by arriving at the solution via statistical methods. You can look at it as the other way around, nature works via the statistical route, and PDE's are nothing but approximation to how the universe actually works.

 

[yossell]

Well, as I argued earlier, whatever the universe actually does must be representable by some definition of computation. Whether or not that definition is the same as Turing computability is another question, but I strongly suspect it is.

If you just define computable as what the universe does, then it's trivial that what the universe does is computable. But that is not the standard definition of computable. And there are well defined, mathematically representable physical processes that do not evolve in a Turing-computable way.

 

[Lievo]

In the absence of evidence for a hypercomputable entity, it's indeed more parsimonious to not assume its existence; and frankly, I don't think it's possible to produce such evidence -- as I said, you have to be an oracle to recognize an oracle.

I don't think so. Zero knowledge proofs show that we can test the claim of someone who pretend to have more computing power that we have. Similarly, they must be some way to check whether someone can truly found a busy beaver -which would demonstrate he has access to hypercomputing.

 

[yossell]

As a matter of fact it is known that monte carlo/random walk methods are used to solve PDE (especially the tough ones) by arriving at the solution via statistical methods. You can look at it as the other way around, nature works via the statistical route, and PDE's are nothing but approximation to how the universe actually works.

what has this to do with my post?

 

[S.Daedalus]

That is not how science works. The burden is not upon science to disprove some radical concept.

I'm not sure where you think I said it was.

The burden is upon you as the proponent of some concept to offer proof of the validity of that concept.

I can readily demonstrate the existence of computers; I'd be surprised if anybody could say the same about hypercomputers.

The thing is, you're proposing the existence of an entity that we have no evidence for, and that is not necessary in any way to formulate a theory in accord with all observations to date. So since it can be done without, it should be done without.

Of course, if someone manages to demonstrate actual hypercomputation occurring in nature, all of this is falsified. But still, my question stands: If somebody puts a device on my desk and claims it to be a hypercomputer -- how do I test this claim?

 

[S.Daedalus]

I don't think so. Zero knowledge proofs show that we can test the claim of someone who pretend to have more computing power that we have. Similarly, they must be some way to check whether someone can truly found a busy beaver -which would demonstrate he has access to hypercomputing.

Of course, you can convince another on a statistical basis that you possesses a hypercomputation-capable device, but never in any absolute sense; in any given scenario, you need only more conventional computational power than your opponent has access to, to convincingly fake having a hypercomputer.

One might argue that this is similar to never being able to tell whether a theory is true in an 'absolute sense', but there is in some sense an infinite difference between a device being actually a hypercomputer and merely pretending to be, while the difference between a strictly false, but approximately right theory and the true behaviour of some system is small, and can be gauged by experiment. In other words, the statistics tell you 'how right' or 'how wrong' your theory can at most be, while they don't tell you 'how hypercomputational' some gadget is.

 

[Chalnoth]

If you just define computable as what the universe does, then it's trivial that what the universe does is computable.

Well, as I stated earlier, if the universe does something, then you can build a "computer" that calculates what the universe does simply by setting up the system and measuring it later.

 

[qsa]

what has this to do with my post?

I was not criticizing you. I was just clarifying the concept of the use of differential equations(which you mentioned as a possibility through your rough understanding of MUH) in describing nature. In my opinion nature is made of math (more like random numbers with logic), but the system is inherently statistical by which we use all sorts of math to approximate it, especially using differential equations (equivalently path integrals).

 

[yossell]

Well, as I stated earlier, if the universe does something, then you can build a "computer" that calculates what the universe does simply by setting up the system and measuring it later.

And this is not what is meant by computable in computability theory, and certainly doesn't guarantee that whatever it is you are calculating is Turing-computable.

 

[tom.stoer]

Well, as I stated earlier, if the universe does something, then you can build a "computer" that calculates what the universe does simply by setting up the system and measuring it later.

No, you can't (not in all cases). Let me explain what I have in mind (it's not yet formal).

Suppose the universe is an axiomatic system that produces a theorem (according to Gödelization) or that produces a "number" on a tape (where the tape = the number = the universe) according to some algorithm. Now one can measure the complexity of the algorithm; and b/c the universe is a nice guy it decided to use the shortes and most efficient algorithm to do that. So unfortunately there is no shortcut to verify the calculation, there is no "simulation" of what the universe is doing.

Think about one specific algorithm A and about the set of all possible Turing machines {T}. There is certainly one Turing machine T_A that does the calculation for A in the most efficient way (with the minimum number of steps). If this pair (A, T_A) is our universe, you will never be able to prove this within our universe. You can't be faster than the universe itself with its calculation.

In addition (as we mentioned earlier) it is not clear whether the universe is (equivalent to) a Turing machine, as the latter one has (by definition) found a solution as soon as it stops (the solution is what has been written on the tape). But the universe may not stop - nevertheless it produces some output, namely its own time evolution. I am still not sure whether one has to generalize the concept of Turing machines slightly.

 

[Lievo]

you need only more conventional computational power than your opponent has access to, to convincingly fake having a hypercomputer.

Well, in fact, no. 0K proofs allow you to check that your opponent have access to PSPACE power, even if there are many logical steps between you and her. But I recognize I don't know a 0K proof proving hypercomputable power.

If somebody puts a device on my desk and claims it to be a hypercomputer -- how do I test this claim?

Look at Benett's writings on the Maxwell' demon. What prevents the demon to give you free enthalpy is the fact that he needs to clear is memory. So if you have an hypercomputable device, let's talk to your favorite demon:
-Give me free energy.
-I can't, I don't have enough memory space
-Just compress the information you have on your tape to have some free space
-that wouldn't work my dear, compression is not computable.
-here's a device that make hypercomputation
-cool! Then I can I create free energy! And I'll keep it for me, because I'm a demon AHAHAHA!

 

[Lievo]

If somebody puts a device on my desk and claims it to be a hypercomputer -- how do I test this claim?

One other way to say the same: give her a random series of boolean vectors of size n. If she's able to answer a series of TM of size n'<n that output your boolean vectors, you can be exponantially confident that she has access to hypercomputing. This is not a 0K proof, but it works.

 

[S.Daedalus]

Well, in fact, no. 0K proofs allow you to check that your opponent have access to PSPACE power, even if there are many logical steps between you and her. But I recognize I don't know a 0K proof proving hypercomputable power.

Eh, I was writing up a long reply to you, but the computer ate it; it's probably for the best, since it's taken us too far off topic, and I've become a bit over-argumentative on the issue (sorry if I stepped on anybody's toes, I sometimes get a bit too excited).

As a last comment, note that I don't deny the possibility of a probabilistic proof of hypercomputation, which your examples amount to, but claim that one never can be absolutely certain of the hypercomputational capacities of some device.

 

[friend]

Godel's incompleteness theorem only applies to systems that include math. But math is an abstract construction developed for our convenience. But I consider that it might not be applicable to physical things. For example, when counting sheep, you can start counting with any of them. There isn't anyone particular sheep that must be labeled "one", etc. And so it would seem that you cannot assign an axiom to anyone particular physical thing. So you can't say this thing is represented by a axiom that is already included in your theory or is represented by an axiom that is not yet proven by your theory.

If the laws of physics can be represented in a coordinate independent fashion and reduced to algebraic expressions that do not depend on any units of measure, then it doesn't seem to dependent on counting anything, distance or particular units when measuring. And if particular units are not required, then can Godel's incompleteness theorem still be applied? You still have addition, subtraction, multiplication, and division as in math, but the particular numbers don't seem to be physically meaningful. And if you cannot assign a definate number value to some measurement (since you can always change the units of measure being used), then is incompleteness still a possiblity? Thanks.

 

[Lievo]

As a last comment, note that I don't deny the possibility of a probabilistic proof of hypercomputation, which your examples amount to, but claim that one never can be absolutely certain of the hypercomputational capacities of some device.

Well I won't argue that. But if you follow the protocol above, it will quickly have become far more likely that you had an heart attack, toke a meteorit on your head, experienced a Richter 12 earthquake, and fall into a black hole formed from spontaneous vacuum fluctuation, all at the same time, than to see your opponent being able to answer by chance. But yes, this would still be just a probabilistic proof.

To be honest, if I was really seeing someone (statistically) demonstrating hypercomputation, I won't interpret this as hypercomputation on first sight. I'd interpret this as a clear indication that my understanding of the math involved sucks. ;-)

If the laws of physics (...) then is incompleteness still a possiblity? Thanks.

In my view, if the TOE really depends on real numbers, then it's not computable, not consistent, and then Godel's incompletness of course won't apply.

 

[D H]

In my view, if the TOE really depends on real numbers, then it's not computable, not consistent, and then Godel's incompletness of course won't apply.

Not a very good view. An inconsistent theory is utterly worthless. There's nothing wrong per se with an incomplete theory.

 

[Lievo]

then Godel's incompletness of course won't apply

There's nothing wrong per se with an incomplete theory.

With all due respect, D H, you don't read me. From the begining, in fact.

 

[Fra]

Then, it would be much better to have an approximation of hte differential equation, that may be less accurate but a least computable.

This is precisely what I doubt for the reasons explained above.

Mmm.. This thread is getting about as stirred up as one could expect. I had to rethink what exactly we are discussing here.

About the chaotic dynamical systems I agree, I have nothing to add there.

For me, in the inference perspective I've chosen, a theory is an interaction tool = an inference model, not an ontological statement of reality. So a theory in this sense is valued after how well it serves it's purpose as an interaction tool.

I consider the theory, to be part of the hidden prior information. Theory is like "condensed" information. This doesn't mean it can't melt down and revise.

A theory that doesn't allow computations of expectations with reasonable effiency, are simply useless.

An inference system based on a complex dynamical system sensitive to initial conditions are simply uselsess and lack of predictive value unless a solution can be computed. Then encoding such a model is a waste of resources. The more fit inference would probably be based on statistical models and finding the stable macroscopic variables.

So what's important is not just computability, but computing effiency as well.

Clearly for a computer with limited time and memory, the set of computable algorithms are smaller. This is why computability in the physical sense, must be depend on the observer. There is IMO, not objective meaning of what's computable and what's not, that's what I mean with treating a theory as an interaction tool for a given observer.

The idea (IMHO) is that this relative computability, is that a given observer is simply indifferent to any non-computable causations, and this idea may also explain unification in the sense that the set of possible interactions are bound to shrink as we scale down the computational complexity. Also some "interaction types" are simply invisible to a sufficiently "simple" observer, since it can never compute and hence infer it's existence.

When I insist on this computability, I don't mean that the entire universe is computable in the sense of a gigantic cellulaor automata. This is what some other people thing, but it's not what I talk about. I see it as interacting systems where EXPECTATIONS follow cellular automata, but where some things are simply not computable.

OK, maybe his is the confusion: With computable, then I mean that EXPECTATIONS are computable. I do not mean that ACTUALY evolution is computable. The Actual future is always in principle non-computable, from the point of view of a given observer. But the trick is that I think that the actions of any system only responds to it's expectationsof the future, not to the actual future.

I feel like I just get deeper into the mud or mutual confusion here so may I should stop. Maybe we can consider this thread a collective painting.

/Fredrik

 

[Fra]

OK, maybe his is the confusion: With computable, then I mean that EXPECTATIONS are computable. I do not mean that ACTUALY evolution is computable. The Actual future is always in principle non-computable, from the point of view of a given observer.

I'm not sure if this helps, but note the similarity to this and to the unitarity of evolution IN BETWEEN measurements (ie. the EXPECTED evolution), and the possible non-unitary evolution of actualy evolution - plenty of measurements included)

In my picture this similarity isn't a conicidence.

/Fredrik

 

[Hurkyl]

Tarksi's system doesn't contain quantification over classes or types, doesn't contain quantification over the cartesian product of classes or types and doesn't contain an abstraction operator,

*sigh* Last time: these things^* are part of first-order logic itself, and has absolutely nothing to do with the formal language and axioms Tarski chose to present a theory of Euclidean geometry.

*: except I don't know what you mean by "abstraction operator". When I said abstraction, I was using it as the natural language term describing a quality of how mathematicians develop mathematics

While formulations of first-order logic vary, these features are always present. Some forms of Type theory or an approach to logic based on Category theory would have all of these explicitly. Even untyped has them in the sense that any statement involving these features can be algorithmically converted into a formula in the untyped logic's language.

And since you are perpetually worried about whether or not all of these bells and whistles change things relative to a stripped-down version of logic, allow me to ease your worry by stating the following theorem:

Let T be a formal theory of untyped logic. Let C be its syntactic category, and T' be the theory described by C (which has product types, subtypes defined by predicates, quotient types, and all of those extra features I've been talking about). Let S be a statement in the language of T. Then S is a theorem of T if and only if its analog in the language of T' is a theorem of T'.

Furthermore, there is^* a one-to-one correspondence between models of T and models of T'.​

*: Generally, definitions are usually to be more relaxed -- so that the correspondence is not strictly one-to-one, but still remains one-to-one in every relevant way. However, strict definitions are possible so that this truly is one-to-one.

 

[yossell]

*sigh* Last time: these things^* are part of first-order logic itself, and has absolutely nothing to do with the formal language and axioms Tarski chose to present a theory of Euclidean geometry.

Sigh - for the *last* time the existence of types is not a first order consequence of Tarksi's theory. Sigh - a first order theory which says there are exactly three objects has models which contain only three objects - the models don't contain further types (I say this because I sometimes try to explain your persistent misreadings of my posts by your thinking I don't think there can be first order theories of types or sets). Sigh - you can add a first order axioms saying that certain types or type like things exist or sets or sums exist. Sigh - but this is an extension of the theory.

From your last paragraph it looks as though you're saying that this extra machinery is added in such a way so that it is conservative over the language of the original theory. It can be so added - but if you remember that, in a first order language, we're typically replacing second order axioms which induction schemas, these schemas have more instances if the language of the theory is expanded. If it is expanded, the new theory is not necessarily conservative over the original theory. And, indeed, as Shapiro showed, you can embed the numbers into geometry.

But I too am tired of repeating myself, and I can live without your sighs, so goodnight.

 

[PAllen]

I think Hawking was reasoning by analogy, not necessarily proposing that Godel's theorem literally applies to the universe. Instead, that the unexpected (previously) fact that a large class of finite systems of axioms must be incomplete makes it plausible that the universe cannot be completely described with a finite set of laws. Adding to this plausibility is that, so far, all probings into further distances and times and energy regimes have uncovered new laws. So far, there is no sign of an end to this.

Turning the question around, I asked myself: Have I ever seen even the slightest actual evidence that the universe can be described by a finite set of laws (let alone laws motivated by encompassing just known phenomenology, e.g. 4 forces) ? My answer is that I am not aware of *any* evidence *at all* that this should be expected. Thus I conclude that the only basis for this expectation is hubris and wishful thinking.

 

[Lievo]

Have I ever seen even the slightest actual evidence that the universe can be described by a finite set of laws (let alone laws motivated by encompassing just known phenomenology, e.g. 4 forces) ?

If Godel incompletness applies and you assume that the universe is consistent, you can't have less than an infinite number of laws/axioms in your TOE for a complete description.

Thus I conclude that the only basis for this expectation is hubris and wishful thinking.

Does this change your conclusion?

 

[PAllen]

If Godel incompletness applies and you assume that the universe is consistent, you can't have less than an infinite number of laws/axioms in your TOE for a complete description.


Does this change your conclusion?

No, it supports it.

 

[Lievo]

No, it supports it.

So, if there is a finite number of law, this supports your view. And if there is an infinite number of laws, this also supports your view. Well, good for your view.

 

[S.Daedalus]

Turning the question around, I asked myself: Have I ever seen even the slightest actual evidence that the universe can be described by a finite set of laws (let alone laws motivated by encompassing just known phenomenology, e.g. 4 forces) ? My answer is that I am not aware of *any* evidence *at all* that this should be expected.

Well, the existence of a finite set of laws describing the evolution of systems that manifestly are subject to incompleteness constitutes such evidence, as in the Game of Life example for instance. In fact, if the universe can in principle be simulated on a computer, since we can finitely describe computers, we can finitely describe the universe, as well. This may of course be intractable, or even in principle impossible -- as there's no guarantee that the universe can be simulated on a computer --, but the possibility exists, and it's arguably the conservative one: only if we are certain that no such description can be found (a state I can't see how to arrive in) should we abandon the attempt.

 

[PAllen]

So, if there is a finite number of law, this supports your view. And if there is an infinite number of laws, this also supports your view. Well, good for your view.

Where do you get this from? My original post motivated the plausibility of no end to new phenomena and laws, and then proposed that there is no evidence for a finite number. Was there something unclear in my post??

 

[PAllen]

Well, the existence of a finite set of laws describing the evolution of systems that manifestly are subject to incompleteness constitutes such evidence, as in the Game of Life example for instance. In fact, if the universe can in principle be simulated on a computer, since we can finitely describe computers, we can finitely describe the universe, as well. This may of course be intractable, or even in principle impossible -- as there's no guarantee that the universe can be simulated on a computer --, but the possibility exists, and it's arguably the conservative one: only if we are certain that no such description can be found (a state I can't see how to arrive in) should we abandon the attempt.

Ok, that is a substantive response. However, all it says is that it is possible there are a finite number of laws, which I don't doubt (actually, I never thought about these questions until this thread appeared). I still don't see it as evidence in favor of a finite number of laws. I also don't see that assuming finite until proven otherwise is the conservative position. It feels more like the wishful thinking position.

I also don't see that admitting the plausibility or likelihood of no finite number has much effect on the practice of physics, any more than Godel's theorem had much effect on the practice of number theory. The only significant case I know of where a meaningful hypothesis turned out to be independent of other axioms is the continuum hypothesis. People speculate about Goldbach's or P<>NP, but these are just that - speculations. Similarly, I would expect the phenomena outside the scope of some finite set of laws to be ever more exotic as physics advances, with exceedingly small contribution to the universe.

[EDIT] Actually, I can see one positive effect: less wrangling about a search for a TOE, and more focus on effective theories for known phenomena that also make some new predictions. The attitude that a 'theory of everything so far' is worthwhile and all you can really know, I think is good for physics.

 

[S.Daedalus]

Ok, that is a substantive response. However, all it says is that it is possible there are a finite number of laws, which I don't doubt (actually, I never thought about these questions until this thread appeared). I still don't see it as evidence in favor of a finite number of laws. I also don't see that assuming finite until proven otherwise is the conservative position. It feels more like the wishful thinking position.

It's conservative in so far that we know scores of examples of systems that can be simulated on a computer (up to arbitrary finite precision given enough computing power), and none that can't. So assuming that there exist such systems is unwarranted.

 

[PAllen]

It's conservative in so far that we know scores of examples of systems that can be simulated on a computer (up to arbitrary finite precision given enough computing power), and none that can't. So assuming that there exist such systems is unwarranted.

Assuming no end to laws, it would still be true that all phenomena within the scope of of some finite set could be simulated. Thus, at all times, it would be true that everything we currently understand could be simulated. Unless I misunderstand your point, I don't get its significance.

 

[S.Daedalus]

Assuming no end to laws, it would still be true that all phenomena within the scope of of some finite set could be simulated. Thus, at all times, it would be true that everything we currently understand could be simulated. Unless I misunderstand your point, I don't get its significance.

There's no meaning to claiming that nature 'actually' is described by an inexhaustible set of laws if we can capture it to arbitrary precision with a finite one; no experiment would be able to tell the difference.

 

[PAllen]

There's no meaning to claiming that nature 'actually' is described by an inexhaustible set of laws if we can capture it to arbitrary precision with a finite one; no experiment would be able to tell the difference.

An example of how this could play out is that in the first moments of the universe, and final moments of collapse, there are a plethora of fundamentally new laws that become significant, that otherwise are not. Given the limited information content of cosmic microwave background and other residual signals, and absence of information from inside event horizons, we could find ourselves unable to simulate such things with any precision until such conditions could be reproduced and studied; and we might never get a complete description / simulation.

Just one example of how my statement might not be without meaning.

 

[S.Daedalus]

An example of how this could play out is that in the first moments of the universe, and final moments of collapse, there are a plethora of fundamentally new laws that become significant, that otherwise are not. Given the limited information content of cosmic microwave background and other residual signals, and absence of information from inside event horizons, we could find ourselves unable to simulate such things with any precision until such conditions could be reproduced and studied; and we might never get a complete description / simulation.

Just one example of how my statement might not be without meaning.

But then, we have the case that experiment disagrees with expectation, and hence, a violation of the condition that we should be able to capture nature to arbitrary precision; in such a case, of course one would have to add new or revise old laws. But still, this provides no justification for the hypothesis that the actual laws of nature are inexhaustible: the revised laws ought to be taken as fundamental up to experimental falsification.

At every point in this chain, one is in the situation, as stipulated, that the known laws agree with all known experimental data (a situation obviously far removed from the present one). Of course it's always possible that new experimental data might upset this state of affairs, but at any given point, hypothesizing the existence of new laws without experimental necessity is a violation of parsimony.

 

[Fra]

but at any given point, hypothesizing the existence of new laws without experimental necessity is a violation of parsimony.

I fully agree with this viewpoint.

I would have said that an expectation lacking evidence pointing in it's direction, is simply irrational. There is no rationale for maintaining such a expectation in anything but a as a fluctuation because encoding expectations occupy resources. It seems highly unlikel that irrational systems would be observed in nature.

Also the question is not what WILL happen in the future, because no one ones and no one can compute it, period. What we do have, is expectations of the future, and it is what influences our actions. So all we need to decided, is what actions to take, based on our present knowledge. It happens all the time that we are wrong, but then we will revise our information states in a given theory, as well as the theory itself, when new evidence points to an inconsistency of the current theory.

So I think it's not unreasonable to think that any systems, instantly acts AS IF, there are a finite set of laws, simply because it's the self-imposed constraint of that system. But the action will get more complex on a finite scales is it will involve the systems revisions of prior conceptions. I think even this can partly be inductively computed by a much more complex observer that can monitor the system and it's environment as a subsystem.

/Fredrik