¿Hay alguna conjetura famosa de la teoría de números que se haya demostrado indecidible?
¿Hay alguna historia al respecto?
Me gustaría conocer alguna conjetura de teoría de números por los tipos de indecidibles.
Respuestas
¿Demasiados anuncios?
Quizás El décimo problema de Hilbert y Teorema de Matiyasevich es lo que tiene en mente. Aquí hay algunos puntos particulares tomados de las dos páginas web:
Correspondiendo a cualquier axiomatización consistente de la teoría de números, se puede construir explícitamente una ecuación diofantina que no tenga soluciones, pero tal hecho no se puede demostrar dentro de la axiomatización dada. El décimo problema de Hilbert pide un algoritmo general que decida la resolubilidad de las ecuaciones diofantinas. La conjunción del teorema de Matiyasevich con resultados anteriores conocidos colectivamente como el teorema MRDP implica que la solución del décimo problema de Hilbert es imposible.
Harold N. Shapiro y Alexandra Shlapentokh demuestran que el décimo problema de Hilbert es irresoluble para el anillo de enteros de cualquier campo numérico algebraico cuyo grupo de Galois sobre los racionales es abeliano.
Trabajos posteriores han demostrado que la cuestión de la resolubilidad de una ecuación diofantina es indecidible incluso si la ecuación sólo tiene 9 variables de números naturales (Matiyasevich, 1977) u 11 variables de números enteros (Zhi Wei Sun, 1992).
user8269
Puntos
46
[referencias añadidas, en la parte inferior]
Conoces el problema de Collatz, ¿verdad? Empezar con un entero positivo, si es par, dividir por 2, si es impar, multiplicar por 3 y sumar 1, iterar y ver qué pasa? ¿Las posibilidades son que eventualmente entres en un ciclo, o que nunca entres en un ciclo?
Bien, puedes encajar ese problema en una familia de problemas donde fijas un módulo $m$ y $m$ diferentes funciones lineales $f_0,f_1,f_{m-1}$ y, a continuación, dado un número entero positivo, se mira cuál sería el resto si se dividiera por $m$ y si ese resto fuera $r$ se aplica la función $f_r$ al número entero positivo; se itera este procedimiento, y de nuevo la cuestión es si se entra en un ciclo. Las funciones $f_i$ tienen que ser elegidos para que siempre se obtengan números enteros en los cálculos.
Se ha demostrado que existe un módulo $m$ y una colección de funciones $f_0,f_1,f_{m-1}$ tal que la cuestión del ciclo es indecidible.
No sé si esto se puede calificar. Para el Collatz original, la conjetura estándar es que siempre se termina en el ciclo $4,2,1,4,2,1,\dots$ . Pero el Collatz original no se ha demostrado indecidible. No sé si alguien ha escrito un ejemplo explícito de un problema de esta familia para el que se pueda demostrar la indecidibilidad, y no sé qué conjeturas hay sobre los miembros de la familia.
Esto probablemente se trate en el libro de Lagarias sobre $3x+1$ .
EDIT: Puede obtener el sabor del argumento aquí aunque parece un preimpreso que necesita algo de trabajo. La versión publicada de ese artículo es Kurtz, S. A. y Simon, J. "The Undecidability of the Generalized Collatz Problem", en 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. La versión publicada está disponible en http://www.springerlink.com/content/e03333g2u28450q5/ pero creo que está detrás de un muro de pago.
El artículo de Conway sobre esto es Conway, J. H., Unpredictable iterations, Proc. 1972 Number Th. Conf., University of Colorado, Boulder, Colorado, pp. 49-52, 1972. Está en el libro de Lagarias.
