Re: does sqrt(2) exist in CM?

From: Torkel Franzen (torkel_at_sm.luth.se)
Date: 02/16/05 

Date: 16 Feb 2005 13:13:22 +0100

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.

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 ...
    (comp.theory)
  • 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 ...
    (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. ...
    (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. ...
    (comp.theory)
Loading