Re: does sqrt(2) exist in CM?

examachine_at_gmail.com
Date: 02/16/05 

Date: 16 Feb 2005 03:41:24 -0800

tchow@lsa.umich.edu wrote:
> In article <1108500848.830038.313970@z14g2000cwz.googlegroups.com>,
> <examachine@gmail.com> wrote:
> >I read the proofs and studied the construction a long time ago.
Should
> >I be now "proving" that to you, because of Torkel's silly posts?
>
> I've studied lots of mathematics a long time ago that I later forgot
the
> details of. But when the time comes to discuss them, I have to go
back
> and review the material to make sure I don't spout nonsense.
>
> What does it matter whether Torkel is a gadfly or if you thought I
was
> being condescending? Getting the statement of Chaitin's theorem
right
> is a worthwhile thing, so why not do it?

There is no need for me to explain anything. Chaitin already explains
the theorems perfectly well. The significance of his most refined
incompleteness result, that you need n+c bits of algorithmic entropy to
calculate n scattered bits of Omega (where c depends on universal
computer chosen) is closely tied to the diophantine construction for
Omega. This is best explained by Chaitin himself:

http://www.umcs.maine.edu/~chaitin/unknowable/ch6.html

------------------------------------------------------------------------
 I use the work of M. Davis, H. Putnam, J. Robinson, Y. Matijasevic and
J. Jones on Hilbert's 10th problem to encode the bits of O in a
diophantine equation. My equation is 200 pages long and has 20,000
variables X1 to X20000 and a parameter K. The algebraic equation

L(K, X1, ..., X20000) = R(K, X1, ..., X20000)

has finitely or infinitely many natural number solutions (each solution
is a 20,000-tuple with the values for X1, ..., X20000) if the Kth bit
of O is, respectively, a 0 or a 1. Therefore determining whether this
equation has finitely or infinitely many solutions is just as difficult
as determining bits of O.
--------------------------------------------------------------------------

There is another construction that's easier, but this will do.

As you can see this definition is not bombastic at all, perhaps people
prefer dull mathematicians, I personally find his writing style well.

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.

Assuming that the mathematician who wants to solve this problem for
arbitrary K is a finite mechanism, IT TRIVIALLY FOLLOWS that Chaitin's
incompleteness theorem means that there is an absolutely undecidable
problem in elementary number theory. Furthermore, it exhibits
randomness in elementary mathematics, because the solution not governed
by a rule (although it is computable in the limit, here computable
meaning the precise definition which Ramsay and others gave). Is this
more drastic than Godel's and Turing's construction? In one broad
sense, these all deal with the same problem: halting problem, but I
find the theorems of Chaitin stronger than Godel's, because they
quantify what you can do "at best" (e.g. they are upper bounds).

On the other hand, since I see you as an interested person, I would
like to point out that Raatikainen's critique of one of the lower bound
results of Chaitin (akin to Godel's theorem) is not justified, because
it depends on a "philosophical" point of view that is downright
ignorant of computation. The examples in that paper are fairly trivial
cases that are covered by AIT, even if some logicists cannot understand
that. The discussion on this thread was much more informed than the
unwarranted talk about infinite-size universal computers, and all the
nonsense in that paper that Raatikainen managed to publish.

Regards, 

--
Eray
Regards,
--
Eray

Relevant Pages

  • Re: does sqrt(2) exist in CM?
    ... >>I read the proofs and studied the construction a long time ago. ... diophantine equation. ... Chaitin's view is that his incompleteness theorem (e.g. ... randomness in elementary mathematics, ...
    (sci.math)
  • Re: does sqrt(2) exist in CM?
    ... >>I read the proofs and studied the construction a long time ago. ... diophantine equation. ... Chaitin's view is that his incompleteness theorem (e.g. ... randomness in elementary mathematics, ...
    (sci.logic)
  • Re: Understanding the quotient ring nomenclature
    ... It does not serve as a motivation in the definition of ring. ... neither willing to try and work out why this interpretation must be ... student in mathematics who, being uninterested or, most likely, unable ... I do not believe that you will find the inverse cone construction nor ...
    (sci.math)
  • Re: Contradiction or paradox
    ... mathematics -- not, as you like to imply, because it runs contrary to ... example of a Quine atom, in particular, is not so much that it is ... What's missing is the specification of a framework ... everyone to the construction you seek in Barwise and Moss's Vivious ...
    (sci.logic)