Is there any famous number theory conjecture proven undecidable?
Is there any history about it?
i would like to know any number theory conjecture by the types of undecidable.
Is there any famous number theory conjecture proven undecidable?
Is there any history about it?
i would like to know any number theory conjecture by the types of undecidable.
Perhaps Hilbert's Tenth Problem and Matiyasevich's Theorem are what you have in mind. Here are some particular points taken from the two wikipages:
Corresponding to any given consistent 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. Hilbert's tenth problem asks for a general algorithm deciding the solvability of Diophantine equations. The conjunction of Matiyasevich's theorem with earlier results known collectively as the MRDP theorem implies that a solution to Hilbert's tenth problem is impossible.
Harold N. Shapiro and Alexandra Shlapentokh prove that Hilbert's tenth problem is unsolvable for the ring of integers of any algebraic number field whose Galois group over the rationals is abelian.
Later work has shown that the question of solvability of a Diophantine equation is undecidable even if the equation only has 9 natural number variables (Matiyasevich, 1977) or 11 integer variables (Zhi Wei Sun, 1992).
[references added, at bottom]
You know the Collatz problem, right? Start with a positive integer, if it's even, divide by 2, if it's odd, multiply by 3 and add 1, iterate and see what happens? The possibilities being that you eventually go into a cycle, or that you never go into a cycle?
Well, you can fit that problem into a family of problems where you fix a modulus $m$, and $m$ different linear functions $f_0,f_1,f_{m-1}$, and then given a positive integer you look at what the remainder would be if you were to divide it by $m$, and if that remainder would be $r$ you apply the function $f_r$ to the positive integer; you iterate this procedure, and again the question is whether you ever get into a cycle. The functions $f_i$ have to be chosen so that you always get integers out of the computations.
It has been proved that there is a modulus $m$ and a collection of functions $f_0,f_1,f_{m-1}$ such that the cycle question is undecidable.
I don't know whether this qualifies. For the original Collatz, the standard conjecture is that you always wind up in the cycle $4,2,1,4,2,1,\dots$. But original Collatz has not been proved undecidable. I don't know whether anyone has written down an explicit example of a problem in this family for which undecidablity can be proved, and I don't know what conjectures are out there about members of the family.
This is probably covered in Lagarias' book about $3x+1$.
EDIT: You can get the flavor of the argument here, although that looks like a preprint that needs some work. The published version of that paper is Kurtz, S. A. and Simon, J. "The Undecidability of the Generalized Collatz Problem," in Theory and Applications of Models of Computation: Proceedings of the 4th International Conference (TAMC 2007) held in Shanghai, May 22-25, 2007 (Ed. J.-Y. Cai, S. B. Cooper, and H. Zhu), Springer, Berlin, pp. 542-553, 2007. The published version is available at http://www.springerlink.com/content/e03333g2u28450q5/ but I think that's behind a pay wall.
Conway's paper on this is Conway, J. H., Unpredictable iterations, Proc. 1972 Number Th. Conf., University of Colorado, Boulder, Colorado, pp. 49-52, 1972. It's in the Lagarias book.