Talk:Matiyasevich's theorem
From Wikipedia, the free encyclopedia
You wrote "Later work has shown that the question of solvability of a Diophantine equation is undecidable even if the number of variables is only 6". This is not accurate! Matijasevic showed that the number of variables over N={0,1,2,...} may be 9 (not 6), this appeared in J. P. Jones' paper in J. Symbolic Logic. And in 1992 Zhi-Wei Sun proved (in his Ph. D. thesis and some related papers) the undecidablity even if the number of variables over the integers is only 11.
- Could the anonymous person who wrote the words above edit the article itself? That's how Wikipedia works. Michael Hardy 02:20, 4 Dec 2003 (UTC)
Does anyone have a source for this statement? I'm curious what it's referring to.
- Matiyasevich's theorem has since been used to prove that many problems from calculus and differential equations are unsolvable.
Walt Pohl 18:55, 24 Oct 2004 (UTC)
"One can also derive the following stronger form of Gödel's incompleteness theorem from Matiyasevich's result: Corresponding to any given axiomatization of number theory, one can explicitly construct a Diophantine equation which has no solutions, but such that this fact cannot be proved within the given axiomatization."
Is there a logical mistake or could someone explain it to me: if one can explicitily construct an equation that has no solutions then he knows that there are no solutions so "the construction itself is a proof that this equation has no solutions". Shouldn't this statement be given as:
"Corresponding to any given axiomatization of number theory, there exists a Diophantine equation which has no solutions, but such that this fact cannot be proved within the given axiomatization." ?
MS 00:01, 03 Jun 2005
- Nope. "Construction" by itself does not prove anything, and the fact that we know a concrete equation to have no solutions does not imply we can prove within the given axiomatization that it has no solutions. Indeed, the proof of Gödel's incompleteness theorem and of the MRDP theorem are both constructive, thus in principle, one could write down such an unsolvable equation explicitly. (No one does that in practice, as the resulting equation is awfully long and complicated, and there is little value in doing that.) -- EJ 13:22, 10 July 2005 (UTC)
-
- Thank for you answer EJ, appreciated. It was my misunderstanding of words within given axiomatization. Precisely - I omitted the fact that construction is not an object from first-order logic world. Since that time I've read a couple of chapters from Papadimitriou's "Computational Complexity" and it became clearer to me :)Geee... The World is so Strange... Thanks again, see you in the future -- MS 01:56, 18 September 2005 (GMT+1)
[edit] Example?
And how about an example of a Diophantine equation with no solutions in standard axiomatization (perhaps with a note describing how it is constructed)? oneismany 21:04, 16 February 2006 (UTC)
