From: Eliezer S. Yudkowsky (sentience@pobox.com)
Date: Tue Apr 03 2001 - 11:21:32 MDT
hal@finney.org wrote:
>
> Eliezer writes:
> > If the Goldbach Conjecture is true as a consequence of an infinite number
> > of independent mathematical facts, it would mean that there's a *specific*
> > problem that *no* Turing machine can solve.
>
> That doesn't sound right, as you can always add the GC or some equivalent
> theorem to your axiom base. I don't see how a fact like the GC can be
> true only as a consequence of an infinite number of facts. It seems for
> that to be true that your fact would have to carry an infinite amount of
> information, like the value of Chaitin's Omega.
The reason why this keeps coming up for the Goldbach Conjecture is that,
by the time you get into large numbers, any given even number is the sum
of two primes in hundreds of thousands of different ways. The larger a
number, the more infinitesimal the probability that it's not the sum of
two primes; *that* can be demonstrated. But it's quite possible that -
even though one could demonstrate, using a finite amount of computation,
an arbitrarily small probability that the Goldbach Conjecture is false -
there's no way to prove that the Goldbach Conjecture is true. GC would be
true as a consequence of an infinite number of facts distributed over all
the even numbers and all the primes. Someone (I think Hofstadter) said
that arithmetic and multiplication don't relate well in this instance.
The higher you go, the more primes you get, so it's not surprising that
larger and larger even numbers can be expressed as the sum of two primes
in more and more ways. Nor is it surprising that the probability of an
exception gets smaller and smaller. But that doesn't mean that there's
any coherent rule relating primes to even numbers. So it's quite possible
that the Goldbach Conjecture happens to be one of the easiest sentences to
state that's true, and statistically "proveable", but mathematically
unproveable.
(But it should now be clear why the Fifth Postulate is a bad analogy, and
also why I talked about the Goldbach Conjecture rather than the Riemann
Hypothesis.)
-- -- -- -- --
Eliezer S. Yudkowsky http://singinst.org/
Research Fellow, Singularity Institute for Artificial Intelligence
This archive was generated by hypermail 2.1.5 : Sat Nov 02 2002 - 08:06:49 MST