Re: does sqrt(2) exist in CM?

examachine_at_gmail.com
Date: 02/16/05 

Date: 16 Feb 2005 13:06:21 -0800

Torkel Franzen wrote:
> examachine@gmail.com writes:
>
> > What does this mean to a mathematician not very familiar with
theory of
> > computation? Chaitin's view is that his incompleteness theorem
(e.g.
> > irreducibility of Omega) is directly exhibited in elementary number
> > theory by this construction, in similar vein to the demonstration
of
> > Godel's incompleteness theorems as arithmetic facts.
>
> > This is what I mean by a "diophantine problem", it is a diophantine
> > equation with a free variable "K". To "solve" this "diophantine
> > problem" means plugging an arbitrary K and trying to solve it.
>
> Actually in Chaitin's result, it's an exponential Diophantine
> equation. And it is indeed the case that there is such an equation
> D(x,y)=0 such that D(n,y)=0 has infinitely many solutions iff the
n-th
> bit of Omega is 1. This is a fairly easy inference from a theorem by
> Jones and Matiyasevich. But why do you think this particular result
is
> especially significant? After all, we know from the MRDP theorem that
> for any recursively enumerable set A, and in particular e.g. for a
> simple set in Post's sense, there is an (ordinary) Diophantine
> equation D(x,y)=0 such that D(n,y)=0 has at least one solution iff n
> is in A.

Hard to tell that Torkel :( If my explanation didn't make any sense, I
don't think I'll achieve anything further. I appreciate that it might
not sound impressive to you.

Intuitively, I think the relation stems from the fact that the number
Omega, by this way of construction, has "occured" in number theory,
e.g. the randomness does not occur "artificially". The equation which
you cite shows that in number theory, too, there is "universal
computer". I don't mean to say that showing Omega is the weirdest or
the most important thing you can do in number theory, the more
important suggestion is that uncertainty naturally emerges even in the
supposedly most fundamental form of mathematics.

Beyond these, I honestly cannot tell what philosophical implications to
draw from these. I agree that it may not be possible to draw all the
conclusions that Chaitin draws, but as I understand it, he believes in
digital philosophy, and hence what he says is probably not a great
exaggeration on those assumptions.

I think the really great contribution he's bringing on the table is the
irreducibility of the halting problem, I see that he's explicating the
structure of the halting problem in good detail.

Regards, 

--
Eray Ozkural

Relevant Pages

  • Re: does sqrt(2) exist in CM?
    ... >> What does this mean to a mathematician not very familiar with ... Chaitin's view is that his incompleteness theorem ... > bit of Omega is 1. ... I agree that it may not be possible to draw all the ...
    (sci.math)
  • Re: does sqrt(2) exist in CM?
    ... >> What does this mean to a mathematician not very familiar with ... Chaitin's view is that his incompleteness theorem ... > bit of Omega is 1. ... I agree that it may not be possible to draw all the ...
    (comp.theory)
  • Re: does sqrt(2) exist in CM?
    ... Chaitin's view is that his incompleteness theorem (e.g. ... D=0 such that D=0 has infinitely many solutions iff the n-th ... bit of Omega is 1. ...
    (sci.math)
  • Re: does sqrt(2) exist in CM?
    ... Chaitin's view is that his incompleteness theorem (e.g. ... D=0 such that D=0 has infinitely many solutions iff the n-th ... bit of Omega is 1. ...
    (sci.logic)
  • Re: does sqrt(2) exist in CM?
    ... Chaitin's view is that his incompleteness theorem (e.g. ... D=0 such that D=0 has infinitely many solutions iff the n-th ... bit of Omega is 1. ...
    (comp.theory)
Quantcast