Re: Turing vs math

From: Marchal <marchal.domain.name.hidden>
Date: Tue Nov 16 03:28:42 1999

Juergen Schmidhuber wrote:

>There seems to be some confusion concerning Goedel etc.
>
>All formal proofs of number theory are computable from the axioms
>describable by a few bits. So what about Goedel's theorem? We cannot
>derive it from the axioms. But what does that mean? It just means we
>can add it as an axiom. It just means the proof of Goedel's statement
>requires more bits than those conveyed by the original axioms.

Either you mean by "Goedel's theorem" Goedel's theorem, in which case
you are wrong. For exemple Goedel's theorem is provable in Peano
Arithmetic. Or you mean "the Goedelian sentence", i.e. the statement
constructed from the formal system saying that it will not be proved
in the system, in which case you are correct.
I guess you have just done a lapsus here. But this will not help making
confusion disappear :-)

To sum up (with Peano Arithmetic (PA) as the system, but it works for any
self-referentially correct machine): (and remembering that PA is
consistent)

- Goedel's theorem is provable in PA.
- Goedel's sentence (which is the one saying that itself is not provable
by PA) is not provable by PA.

Of course when I say that ``Goedel's theorem is provable in PA", I
mean by ``Goedel's theorem" a recursively number-theoretic equivalent
formula. PA deals only with numbers. But that is contingent.

>In other words, Goedel used additional information. In many of the UTM's
>universes his theorem will be proven by those willing to do the same.

This is false for the first incompleteness theorem: PA is able to prove
Goedel's theorem.
But, indeed, Goedel does know (as us) that the Goedelian sentence is true.
In that case (but here we talk about the second incompleteness theorem) we
are using the additional information that PA is consistent.
Poor PA cannot prove it, indeed. Nor can any self-referentially machine
prove its own consistency.

>The UTM-based universes are the formally describable ones. If some
>vague "set of all mathematical structures" is supposed to contain more
>than that (e.g., non-computable real numbers as opposed to mere finite
>proofs concerning their properties) then it cannot be a subset of the
>UTM set. Neither will it be formally describable.

This is true only from a third person perspective. From a first person
perpective, uncomputable things arise inescapably from the UTM-based
universe. In particular quantum-like form of indeterminism and random
objects is easily derivable from comp.


Bruno
Received on Tue Nov 16 1999 - 03:28:42 PST