Hello Ramon!

The so called incompleteness refers to Peano Arithmetic or to every recursive axiom system trying to axiomatize the structure (N, +, x, 0, 1). I prefer to read it in the following form: """The first order theory of (N, +, x, 0, 1) is undecidable""". This means that there is no "mechanical" algorithm to decide if formal first order statements in this language are true or false in this structure. This means simply that one needs an infinity of non-trivial ideas in order to do number theory (or generally, to do mathematics). I understand this fact in at least two ways. (1) Mathematics becomes self-aware. This is always to expect from really big and relevant sciences. And it does it in a mathematical way (with proofs!) (2) The positive aspects of this negative result are much more important than the result itself. It is to understand that an infinity of non-trivial ideas is there, waiting for us to discover them. So the result does not speak about the limits of mathematics, but much more about its unboundedness and richness.

The Halting Problem is just another way to express the same things.

What P =/= NP concerns, I am not sure that it is true. Maybe it was a common sense conjecture, that will prove to be false. Maybe P = NP but Ptime =/= Pspace -- and so on. These finer questions (very important and quite difficult, of course) do not change too much the reality described by Goedel's theorem.

The short answer is, I think, not at all. 

The long answer is manifold - first, Gödel, and the halting problem and P vs NP etc are very different animals, so any answer cannot be universal.

This being said, the question as worded here seems to imply an underlying assumption that is not proven at all: to wit, it assumes that reality itself is complete, or in other words not 'open' nor open-ended. In other words, inasmuch as mathematics is reputed to map onto physical reality, the question here is since math is open, does not this prove that there are unfortunate limitations to math. 

But there is, however, overwhelming evidence that reality itself is open. Therefore, Gödel does not describe nor impose limits to mathematics in itself: rather, it accurately describes the open-endedness of reality itself.

Jonathan, that is a fascinating question, but if we do the math  we end up with answers that have a quality of non-observability.

Take for instance Cantor's anomaly - the fact that mathematics demonstrably breaks down at infinity - you can interpret the math and the breakdown in several ways - for instance by saying that it's proof that infinities do not exist, or, by saying that infinities do exist but that they take on a special quality (ineffability as per Cantor), etc. etc. This all demonstrates that Cantor was right when he said that you demonstrably cannot apprehend all of reality through an exclusively left-brain approach - you need some right brain component, which unfortunately will then unavoidably have a non-observable or even non repeatable component. 

So that the question ' can we know everything' breaks down into 2 sub-questions : 1- can we do so individually (the answer being a possible yes) and 2- can we share this knowledge with all, the answer being almost certainly no

Turing's halting problem applies to physical machines of any type.  Therefore any physical system that can convey information suffers from Gödel.  I think Chaitin shows Turing and  Gödel are equivalent.

https://www.cs.auckland.ac.nz/~chaitin/georgia.html

Turing halting problem appears to conform to certain syntactic systems (regular grammars and possibly context-free grammars). Context dependence seems to be out of scope of Turing machine. Moreover, meaning of symbols (semantics) appears to be out of definition (and consideration) within Turing-type models of algorithmic complexity. To my knowledge predicate logic is the only formal system in which semantics can be defined solely by available syntax. As far as descriptions of factual (or formal) reality are concerned, we need semantics and pragmatics of the language we employ. Ergo, intuitively, I would say that Turing-Goedel-Solomonoff-Chaitin-Kolmogorov approaches to modeling factual reality will be inadequate (or impertinent) to modeled situations.

Ramon.

Computable means that computation must terminate.  This means that no irrational is computable, not even  π.  Also, I would say that the real values are not generated by the physical world.  For instance, every measurement is rational.  Irrational values are not witnessable.  I like your notion of the physical universe computing itself. This is exactly what I believe is happening.  I could not have put it better.

On gödel's theorem, my SEP entry might be useful:

http://plato.stanford.edu/entries/goedel-incompleteness/

For more philosophical implications (incl. Chaitin), see 

http://philpapers.org/rec/RAAOTP

"Computable means that computation must terminate."

I have done some work on the limits of an extended notion of computability:

http://philpapers.org/rec/RAASSU

Just a word about non-computability if I may. There is artificial non-computability and natural non-computability (which itself breaks down into trivial and non trivial.)

Artificial non-computability occurs when it is dependent on metrics chosen (such as the base of a reckoning system - base 2, base ten, base hexadecimal etc. ) As an example of artificiality, the numerical value of sin(α)/α, when the angle α is made to approach zero, depends on the unit used to measure the angle : when the angle is measured in radians, the limit value for α=0 is 1 but when measured in degrees, the limit for α=0 becomes then a non-computable (pi/180) or approximately 0.017453 - i.e. the result is computable or not depending on the metric used.

Given a model of reality adequate to the situation at hand, I would intuitively say that a "thing" (it can be a number) is computable if there exists a Turing machine capable of deriving it. In terms of algorithmic complexity (Chaitin's version) it would mean that there exists an algorithm that will halt after deriving the "thing". As far as I recall a probability that a given randomly generated program/algorithm will halt is an example of a non-computable number. In a more semantic vain, decision if a given program does what it was meant to do is also an example of non-computable problem.

The question of computability probably does not represent potential effectiveness of mathematics in solving well-posed problems. Mathematics can be changed and the problems can be re-formulated. Effectiveness of tools to solve a given problem will likely increase when the questions (problems) will be formulated within a model that is adequate to both: the tools and a factual reality.

Great discussion thus far! The problem is non-trivial indeed.

Hi Ramon,

In the "trial-and-error" computablitity, (or computability-in-he-limit), which I discuss in a couple of my papers, the algorithm is finite, but the computation is not required to terminate (in a sense): the final sequence is achieved in a finite time, but we never know whether it is already at  hand or not. (in that sense, the computation goes on infinitely)

This allows a more comprehensive notion of computable (and also of a computable real). Still, there are many non-computable strings also in this extended sense of computable (and that is all I wanted to point out).

I discuss all this, in relation to Chaitin, in my:

http://www.mv.helsinki.fi/home/praatika/AIT.pdf 

Ramon,

"I am also wondering whether physical laws are computable"

The project I have been working on is designed to reveal logical structure in quantum theory.  The example I have been working on is the quantum system known as the free particle.  The method involves the derivation of pure mathematics that replicates quantum theoretical formulae.  The starting-point for this derivation is the axioms of arithmetic.  By arithmetic I mean what would be more casually understood to be elementary algebra, or school algebra  --  The algebra of scalars.  The idea is that there is information in the mathematics, representing quantum theory, that is not physical, but is of mathematical nature.  The question is, "Is quantum theory mathematics computable from this set of axioms?".  The answer is no.  Self-reference is needed in one certain place.

I am writing up this work in a paper.  It is very close to finished.  Ramon,  you are so close to asking the same questions I have been asked, I feel very inclined to send you a copy of my paper in its unfinished state.  Please let me know if you are interested.

Steve.

Hello Ramon!

The so called incompleteness refers to Peano Arithmetic or to every recursive axiom system trying to axiomatize the structure (N, +, x, 0, 1). I prefer to read it in the following form: """The first order theory of (N, +, x, 0, 1) is undecidable""". This means that there is no "mechanical" algorithm to decide if formal first order statements in this language are true or false in this structure. This means simply that one needs an infinity of non-trivial ideas in order to do number theory (or generally, to do mathematics). I understand this fact in at least two ways. (1) Mathematics becomes self-aware. This is always to expect from really big and relevant sciences. And it does it in a mathematical way (with proofs!) (2) The positive aspects of this negative result are much more important than the result itself. It is to understand that an infinity of non-trivial ideas is there, waiting for us to discover them. So the result does not speak about the limits of mathematics, but much more about its unboundedness and richness.

The Halting Problem is just another way to express the same things.

What P =/= NP concerns, I am not sure that it is true. Maybe it was a common sense conjecture, that will prove to be false. Maybe P = NP but Ptime =/= Pspace -- and so on. These finer questions (very important and quite difficult, of course) do not change too much the reality described by Goedel's theorem.

My initial take on the answer to this question ("in what sense is the World computable?") would begin with the statement (kind of obvious) that laws do not determine observations, measurements, and events. The latter are presumably expressed as initial and/or boundary conditions  that need to be observed/measured but by no means could be determined from the laws. So, if computing is a way of determining (I tend to think it is), I would say the World is not computable. Any Turing machine would halt trying to match the laws with an unknown semantics of observed events. The laws would be still inexorable, as they should, but initial and boundary condition would be too complex to be adequately computed. (Forced computation would give results that would be inadequate or impertinent to the observed World; For example describing an elephant atom by atom, electron by electron, cell by cell appears to be inadequate for someone who actually sees this animal in nature.)

“if f is simulable, then there is a Turing machine T such that, for any word w in the domain of f, suitably inscribed on an input tape to T, and for a suitably chosen initial state of T, the machine will halt after a finite number of steps, with f(w) in its output tape.” says Robert Rosen in his book "Life Itself" (Rosen, R. 1991. Life Itself. Columbia Univ. Press.)

It seems that simulability and computability of models of a system is the same thing. The problem is (according to Rosen) that complex systems cannot be characterized by a single (largest) model and thereby entail the existence of non-computable models of themselves. [It is not clear to me if "physical theories" and "models of (physical) systems" refer to the same thing but I assume they do as far as computability is concerned.]

A critique of Rosen's claim of existence of non-computable models has reportedly been published in:

Wells, A.J. “In Defense of Mechanism”. Ecological Psychology. 18(1):39-65

(I have not read this paper yet.)