Re: does sqrt(2) exist in CM?
From: Torkel Franzen (torkel_at_sm.luth.se)
Date: 02/16/05
- Next message: arturo: "How to solve a simple quadratic system of 3 equations?"
- Previous message: jstevh_at_msn.com: "Critics. How many have there been?"
- In reply to: examachine_at_gmail.com: "Re: does sqrt(2) exist in CM?"
- Next in thread: examachine_at_gmail.com: "Re: does sqrt(2) exist in CM?"
- Reply: examachine_at_gmail.com: "Re: does sqrt(2) exist in CM?"
- Messages sorted by: [ date ] [ thread ]
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.
- Next message: arturo: "How to solve a simple quadratic system of 3 equations?"
- Previous message: jstevh_at_msn.com: "Critics. How many have there been?"
- In reply to: examachine_at_gmail.com: "Re: does sqrt(2) exist in CM?"
- Next in thread: examachine_at_gmail.com: "Re: does sqrt(2) exist in CM?"
- Reply: examachine_at_gmail.com: "Re: does sqrt(2) exist in CM?"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
