El décimo problema de Hilbert

Departamento de Ciencias de la Computación e Inteligencia Artificial Trabajo Fin de Grado El décimo problema de Hilbert Realizado por Juan Ángel Calderón Ramos Para la obtención del título de Grado en Matemáticas Tutorizado por Álvaro Romero Jiménez Sevilla, 4 de junio de 2025 Resumen En este trabajo se explicarán los conceptos que fueron necesarios para resolver el décimo problema de Hilbert en su versión original para números enteros ℤ , de forma no cronológica. Así, comenzaremos con una explicación sobre ecuaciones diofánticas y diofánticas exponenciales, correspondientemente para desarrollar distintos conceptos como los de conjunto y representación diofántica y para probar que la exponenciación es una función diofántica. A continuación, presentaremos varios sistemas de codificación de tuplas (entre ellos, el más importante será la codificación posicional) y desarrollaremos el concepto de máquina de Turing, construyendo explícitamente algunas de ellas que probarán su utilidad al resolver el problema. Finalmente, terminaremos probando la equivalencia de conjuntos diofánticos y Turing-semidecidibles, lo que nos valdrá para dar una respuesta al problema décimo a través del problema de la parada. Concluiremos dando un breve vistazo al estado actual del estudio del décimo problema de Hilbert en otros anillos, haciendo hincapié en el anillo ℚde los racionales. Abstract In this work, it will be explained the concepts needed to solve Hilbert’s tenth problem in its original formulation for rational integers ℤ , though not in a chronological order. Thus, We will begin with an explanation of Diophantine and exponential Diophantine equations, correspondingly to the development of different concepts such as Diphantine sets or representations and to prove that exponentiation in a diophantine function. Next, we will introduce various systems of tuple encoding (among them, the most important will be positional coding) and we will also develop the concept of a Turing machine, explicitly constructing some of them which will prove to be useful solving the problem. Finally, we will prove the equivalence between Diophantine sets and Turing-semidecidible sets, which will allow us to give an answer to the tenth problem through the halting problem. We will then conclude with a brief overview of current research of Hilbert’s tenth problem in other rings, emphasizing the ring ℚof rational numbers. Agradecimientos Dar agradecimientos a todas las personas que me han acompañado a lo largo de estos pasados 4 años en mi paso por el grado que se concluye con este trabajo. No solo en referencia a mi familia, sino sobretodo a mis compañeros, que me han rescatado de diversos apuros con su mano amiga; y a mis profesores, que han posibilitado (en la mayoría de casos) el entendimiento de materias más complejas de lo que nunca habría podido prever antes de acceder a la facultad. Por último, también agradecer a mi tutor para este trabajo, que me ha acompañado a través de todo el proceso de estudio y redacción de los temas tratados en el mismo. 1 Índice general 1 Introducción 4 1.1 Ecuaciones y conjuntos diofánticos. . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 Teoría de la computación. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 Recorrido histórico. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.4 Cronología . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2 Conjuntos y relaciones diofánticas 17 2.1 Sistemas de ecuaciones diofánticas . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2 El décimo problema en los números naturales . . . . . . . . . . . . . . 21 2.3 Conjuntos diofánticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4 Propiedades y relaciones diofánticas . . . . . . . . . . . . . . . . . . . . . . . 30 2.5 Ejemplos de relaciones y funciones diofánticas . . . . . . . . . . . . . . 34 3 Representación diofántica de la exponenciación 36 3.1 Ecuaciones diofánticas exponenciales . . . . . . . . . . . . . . . . . . . . . . 36 3.2 Las sucesiones recurrentes 𝛼𝘣(𝑛)........................... 38 3.3 Representación diofántica de las sucesiones recurrentes 𝛼𝘣: idea ..................................................... 41 3.4 Representación diofántica de las sucesiones recurrentes 𝛼𝘣: demostración. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.5 La exponenciación es diofántica. . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4 Codificaciones diofánticas 60 4.1 Numeración de Cantor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.2 Codificación de Gödel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.3 Codificación posicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.4 Coeficientes binomiales, números primos y función factorial . 66 4.5 Comparación de tuplas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4.6 Extensión de funciones a tuplas. . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 2 5 Máquinas de Turing 75 5.1 Composición de máquinas de Turing . . . . . . . . . . . . . . . . . . . . . . . 77 5.2 Máquinas para realizar operaciones básicas. . . . . . . . . . . . . . . . . 79 6 Resolución del décimo problema de Hilbert 89 6.1 Reconocimiento de conjuntos diofánticos por máquinas de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 6.2 Simulación diofántica de máquinas de Turing . . . . . . . . . . . . . . . 92 6.3 Resolución del décimo problema de Hilbert . . . . . . . . . . . . . . . . . 100 6.4 La tesis de Church-Turing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 7 El décimo problema en los racionales y otros anillos 109 7.1 Caso particular 𝑅=ℚ...................................... 109 7.2 Generalización a anillos arbitrarios 𝑅. . . . . . . . . . . . . . . . . . . . . . . 114 8 Conclusiones y trabajo futuro 120 3 1Introducción Año 1900. David Hilbert, durante la conferencia Mathematische Probleme (Problemas matemáticos, en español) que impartió en el Congreso Internacional de Matemáticos celebrado en París, presenta por primera vez una lista de 10 problemas, que pronto pasarían a extenderse a 23 (la lista completa se publicó, en alemán, en [2, 3], siendo posteriormente traducida al inglés en [1]. Generalmente es reconocida como una de las listas más exitosas y estudiadas producidas por un solo individuo y, aunque algunos de sus problemas fueron rápidamente resueltos, varios de ellos se mantuvieron abiertos y en profundo estudio durante años. Incluso algunos siguen abiertos hasta la fecha. En este trabajo se estudiará en profundidad el único de los 23 problemas de la lista que es (en terminología moderna) un problema de decisión: Décimo problema de Hilbert Determinación de la resolubilidad de una ecuación diofántica Dada una ecuación diofántica con cualquier número de incógnitas y coeficientes racionales enteros: idear un proceso a través del cual pueda determinarse, en un número finito de operaciones, si la ecuación tiene solución en los racionales enteros. Nótese que el término «racionales enteros» hace alusión tan solo a los números enteros, o al menos así se entendió el enunciado en los años posteriores y en la solución que se le dio eventualmente al problema. No obstante, lo más probable es que Hilbert esperara una solución positiva (en el sentido de encontrar el proceso pedido) de su décimo problema, que sería fácilmente trasladable a la determinación de la resolubilidad de las ecuaciones polinómicas en muchos otros anillos, en particular en el cuerpo 4 de los números racionales, que sería en el que realmente estaría interesado. Lamentablemente, como veremos en este trabajo la solución al décimo problema de Hilbert es negativa (en el sentido de haberse demostrado la no existencia del proceso pedido) y ese resultado no es directamente trasladable a los números racionales. En el enunciado del décimo problema de Hilbert hay dos conceptos de vital importancia que tendremos que manejar con soltura para poder acercarnos a la solución del problema. Por un lado, trataremos con las ecuaciones diofánticas, de las cuales se dispondrá en este trabajo para posteriormente definir el concepto de conjunto diofántico y que jugó un papel protagonista en el desarrollo de la solución del problema. Por otra parte, el «proceso finito» que se menciona en el enunciado alude al concepto de algoritmo que se tiene hoy en día, el cual no estaba correctamente establecido cuando Hilbert planteó su lista de problemas y que se trataría con más rigor a partir de la aparición de las computadoras y gracias a las llamadas máquinas de Turing, que también desarrollaremos posteriormente. Cabe destacar cómo precisamente esta falta de rigor en la descripción del problema fue uno de los impedimentos para la rápida solución del mismo. El problema décimo de Hilbert es de un tipo conocido como problema de decisión. Es decir, consiste de una colección de infinitos problemas individuales (cada ecuación diofántica), cada uno de los cuales requiere una respuesta afirmativa (la ecuación diofántica tiene solución en los enteros) o de una respuesta negativa (la ecuación diofántica no tiene solución en los enteros). Aunque es conocida la existencia de métodos de resolución para ciertos subproblemas, como por ejemplo el formado únicamente por las ecuaciones diofánticas lineales, la clave del problema décimo de Hilbert estriba en que exige un método de resolución aplicable a cualquier ecuación diofántica. Como problema de decisión que es, el décimo problema de Hilbert puede resolverse entonces en un sentido positivo o en un sentido negativo. En el primer caso, sería suficiente con proporcionar un (en terminología moderna) algoritmo que, dada cualquier ecuación diofántica, determinara si tiene solución o no en los enteros. Este algoritmo bastaría incluso con describirlo de manera intuitiva e informal. En el segundo caso, por el contrario, es necesario demostrar que cualquier algoritmo que pudiéramos idear no permite determinar la resolubilidad en los enteros de cualquier ecuación diofántica. Para ello es esencial definir de manera formal y rigurosa el concepto de algoritmo, lo que no fue posible hasta el desarrollo de la teoría de la computación a principios del siglo XX. El desarrollo del concepto formal de algoritmo, junto con una sucesión 5 de reducciones de problemas a otros equivalentes, permitió finalmente obtener una solución negativa al décimo problema de Hilbert. El objetivo de este Trabajo Fin de Grado es proporcionar una demostración rigurosa de la misma, para lo que se tomará principalmente el libro [5] como guía. Antes de ello, completaremos previamente esta introducción con una descripción del recorrido histórico que llevó a la resolución del problema. 1.1 Ecuaciones y conjuntos diofánticos Para poder entender adecuadamente el camino que llevó a la resolución del décimo problema de Hilbert resulta conveniente precisar el concepto de ecuación diofántica, al que hace referencia el problema, y el concepto relacionado de conjunto diofántico, a través de los cuales fue posible obtener la solución negativa al mismo. Definición 1.1 (Ecuación diofántica) Una ecuación diofántica es una ecuación de la forma 𝐷(𝑥𝟣,…,𝑥𝘮)=0 siendo 𝐷un polinomio con coeficientes enteros. Recuérdese que en este trabajo consideramos que el rango de las incógnitas de una ecuación diofántica es el conjunto de los números enteros. En una ecuación diofántica podemos identificar algunas de sus incógnitas como parámetros de la ecuación. Definición 1.2 (Ecuación diofántica paramétrica) Una ecuación diofántica paramétrica es una ecuación de la forma 𝐷(𝑎𝟣,…,𝑎𝘯;𝑥𝟣,…,𝑥𝘮)=0 donde 𝐷 es un polinomio con parámetros enteros 𝑎𝟣,…,𝑎𝘯 e incógnitas 𝑥𝟣,…,𝑥𝘮. Se pueden considerar, de esta forma, familias de ecuaciones diofánticas, que estarían formadas por las ecuaciones diofánticas concretas obtenidas al fijar los valores de los parámetros en una ecuación diofántica paramétrica. A continuación se muestran algunos ejemplos de estas familias de ecuaciones diofánticas. 6 Hipótesis de Julia Robinson Existe un conjunto diofántico 𝐷 de pares de números naturales tal que: 1. Si (𝑎,𝑏)∈𝐷, entonces 𝑏<𝑎𝘢. 2. Para cada 𝑘>0, existe (𝑎,𝑏)∈𝐷tal que 𝑏>𝑎𝘬. Para probar esta hipótesis, tan solo haría falta encontrar un solo ejemplo de conjunto que cumpliese estas propiedades. Pero esto resultó ser mucho más difícil de lo que cualquier matemático de la época podría haber pensado. El siguiente nombre que aparece en esta historia es el de Hilary Putnam, filósofo que se topó con el décimo problema de Hilbert y se encontró fascinado por él. Putnam trabajó en conjunto con Davis y, siguiendo los métodos usados por Gödel unas décadas atrás, como la aplicación del teorema chino del resto al estudio de las funciones recursivas, estuvieron a punto de lograr demostrar que cualquier conjunto semidecidible es diofántico exponencial. De hecho, siguiendo su razonamiento, habrían logrado probarlo por sí mismos, ya que el resultado es cierto suponiendo que existen progresiones aritméticas de números primos arbitrariamente largas, algo que en la actualidad ya está probado, pero que en ese momento no pasaba de ser una conjetura. Es por ello que pidieron la colaboración de Robinson, para finalmente lograr demostrar, en un trabajo conjunto entre los tres, que los conjuntos semidecidibles son diofánticos exponenciales. Reuniendo los resultados obtenidos hasta el momento, la conclusión del trabajo conjunto de Davis, Robinson y Putnam nos permite un acercamiento a la prueba de la conjetura de Davis de modo que se puede probar que la misma es cierta si establecemos una relación entre los conjuntos diofánticos exponenciales y los diofánticos ordinarios. Esta relación pueda apreciarse que está implícita en la hipótesis de Julia Robinson. Como la conjetura de Davis se traslada de forma directa a la resolución del décimo problema, entonces concluimos que tan solo es necesario demostrar la hipótesis de Julia Robinson para resolver el problema. Ahora bien, la dificultad reside precisamente en encontrar el conjunto que verifique dicha hipótesis. Esto resultó ser tan complicado que la respuesta se demoró el suficiente tiempo como para que Putnam dejase de trabajar la teoría de números y Robinson comenzase, en contraste a todo su trabajo previo, a buscar una solución afirmativa para el décimo problema. No fue hasta la aparición de un joven ruso, anecdóticamente profetizado por el propio Davis, que se encontró una respuesta. Yuri Matiyasevich conoció en su temprana juventud el décimo problema 13 de Hilbert y los estudios realizados hasta el momento, y comenzó su propio trabajo. Tras varios años de estudio del problema, considerando los números de la sucesión de Fibonacci descubrió que sorprendentemente los pares (𝑢,𝑣) donde 𝑣=𝜑𝟤𝘶 —para 𝜑𝘯 el n-ésimo término de la sucesión de Fibonacci— resultan ser los tan buscados pares que cumplen la relación expuesta en la hipótesis de Julia Robinson y consiguió dar una representación diofántica para tal relación, es decir, encontró un polinomio 𝐷 con coeficientes enteros tal que 𝑣=𝜑𝟤𝘶 ⟺ ∃𝑥𝟣,…,𝑥𝘬∶𝐷(𝑣,𝑢,𝑥𝟣,…,𝑥𝘬)=0. Gracias a haber finalmente encontrado un conjunto adecuado, se pudo establecer con certeza el teorema que lleva las iniciales de estos cuatro matemáticos en honor de sus aportes. Teorema 1.12 (MRDP) Todo conjunto semidecidible 𝑆 de 𝑛 -tuplas de números naturales es diofántico. Este resultado termina de probar la conjetura de Davis, con lo que podemos entonces establecer Solución negativa al décimo problema de Hilbert No existe un algoritmo que permita determinar la resolubilidad o irresolubilidad de cualquier ecuación diofántica. Para terminar, quisiera destacar cómo este recorrido histórico es un claro ejemplo de la actuación conjunta y necesaria entre la teoría de números y la teoría de la computación, incluso a veces desdibujándose el límite entre la una y la otra, para poder demostrar un resultado tan complejo como el décimo problema de Hilbert y que se mantuvo tantos años sin resolver. 1.4 Cronología Finalizamos esta introducción proporcionando una cronología con los hitos más destacables acaecidos a lo largo de los 70 años que fueron necesarios para resolver el décimo problema de Hilbert. Año 1900 David Hilbert formula el décimo problema en la conferencia Mathematische Probleme que impartió en el Congreso Internacional de Matemáticos en París. 14 Año 1931 Kurt Gödel publica Über formal unentscheidbare Sätze der Principia Mathematica und verwandter SystemeI. Monatsch. donde expone sus estudios sobre funciones recursivas y conjuntos recursivamente enumerables. Año 1948 Alfred Tarsky entrega a Raphael Robinson, marido de Julia Robinson, el problema de definición de los exponentes de base 2. Año 1950 Julia Robinson y Martin Davis se conocen en el Congreso Internacional de Matemáticos, en Cambridge. Año 1952 Julia Robinson publica Existential definability in arithmetic, donde estudia la definición de la exponenciación y enuncia su hipótesis. Año 1953 Martin Davis publica Arithmetical problems and recursively enumerable predicates con parte de los resultados de su tesis y donde enuncia por primera vez su hipótesis audaz. Año 1957 Hilary Putnam coincide con Martin Davis en el instituto sobre lógica que tuvo lugar en la Universidad de Cornell y comienzan a trabajar juntos. Año 1958 En conjunto con su trabajo de 1953, se publica Computability and unsolvability como parte de la tesis doctoral de Davis y se termina de establecer la forma normal de Davis. Año 1958 Se publica Reductions of Hilbert’s tenth problem, trabajo conjunto de Putnam y Davis sobre el décimo problema. Año 1959 Putnam y Davis se topan con el obstáculo de las sucesiones aritméticas de números primos y envían a Julia Robinson el trabajo On Hilbert’s tenth problem, a punto de publicarse, para solicitar su ayuda. Año 1961 En el trabajo conjunto de Putnam, Davis y Robinson The decision problem for exponential Diophante equations se establece la equivalencia entre los conjuntos semidecidibles y los conjuntos diofánticos exponenciales. Año 1965 Sergei Maslov sugiere a Yuri Matiyasevich que investigue sobre el décimo problema de Hilbert, del cual «unos americanos han tenido algunos acercamientos probablemente erróneos». Matiyasevich no lee sus trabajos, pero queda encantado por el problema. 15 Año 1969 Julia Robinson publica Diophantine decision problems, donde dice haber logrado algunos avances. Martin Davis, tras ser preguntado sobre su opinión, responde: «Creo que JR es cierta y que será probada por un inteligente joven ruso». Año 1969 Un compañero de Matiyasevich le incita a que lea el nuevo trabajo de Robinson, pero él se niega en un intento de superar su obsesión por el problema. Sin embargo, le es enviado el trabajo para que lo revise y se ve obligado a leerlo. Año 1970 Yuri Matiyasevich encuentra el conjunto necesario para demostrar la hipótesis JR, usando los números de Fibonacci, y da su primera charla pública sobre el resultado el 29 de enero. 16 2Conjuntos y relaciones diofánticas El objetivo de este capítulo es formalizar algunos de los conceptos superficialmente comentados en la introducción. Específicamente se profundizará en la definición de conjunto diofántico y en la terminología lógica de la que se hará uso posteriormente. Recordemos (definición 1.1) que una ecuación diofántica es una ecuación de la forma 𝐷(𝑥𝟣,…,𝑥𝘮)=0 o, más generalmente, 𝐷𝘓(𝑥𝟣,…,𝑥𝘮)=𝐷𝘙(𝑥𝟣,…,𝑥𝘮) donde 𝐷,𝐷𝘓y𝐷𝘙son polinomios con coeficientes enteros. Cuando nos refiramos a una ecuación diofántica arbitraria tendremos en mente ecuaciones con la primera notación, pero es claro que ecuaciones expresadas con la segunda notación pueden fácilmente pasarse a la primera tan solo transponiendo términos. Es por ello que introducimos esta segunda forma de expresar las ecuaciones diofánticas, puesto que ciertas ecuaciones particulares serán así más sencillas de visualizar, además de poder en esta forma aislar los signos de los términos en uno u otro lado de la igualdad y poder entonces asumir que los coeficientes enteros de los polinomios 𝐷𝘓 y 𝐷𝘙son no negativos. Las ecuaciones diofánticas tendrán normalmente varias variables diferentes, de modo que distinguiremos los conceptos de grado de la ecuación respecto a una sola variable 𝑥𝘪 y grado total de la ecuación. El primero se corresponde con la noción habitual de grado de un polinomio si consideramos que 𝑥𝘪 fuera la única variable, mientras que el último se entiende como el máximo de las sumas, para cada monomio de 𝐷 , de los grados de las variables individuales que aparecen en el monomio. Recuérdese también que solo estamos interesados en las soluciones enteras de las ecuaciones diofánticas. No obstante, en el capítulo 7 haremos 17 un repaso somero de los resultados conocidos acerca del décimo problema de Hilbert para otros anillos, en particular para el cuerpo de los números racionales. 2.1 Sistemas de ecuaciones diofánticas Además de ecuaciones diofánticas individuales, es natural considerar también sistemas de ecuaciones diofánticas. Como veremos a continuación, el correspondiente décimo problema para estos sistemas resulta equivalente al décimo problema original. Esto resultará sumamente útil, ya que permitirá expresar propiedades complejas mediante la agregación de propiedades simples más sencillas de describir con ecuaciones diofánticas. En efecto, si consideramos el sistema de 𝑘ecuaciones diofánticas 𝐷𝟣(𝑥𝟣,…,𝑥𝘮)=0 ⋮ 𝐷𝘬(𝑥𝟣,…,𝑥𝘮)=0 es sencillo comprobar que tiene una solución formada por los enteros 𝑥𝟣 a 𝑥𝘮 si y solo si estos mismos enteros son una solución de la ecuación diofántica 𝐷𝟤 𝟣(𝑥𝟣,…,𝑥𝘮)+⋯+𝐷𝟤 𝘬(𝑥𝟣,…,𝑥𝘮)=0. La demostración de este hecho es trivial: si todas las 𝐷𝘪 son nulas, entonces la suma de sus cuadrados también debe ser nula. Recíprocamente, como el cuadrado de un número entero es no negativo, entonces si se cumple la ecuación tendremos una serie de sumandos todos no negativos y que suman 0 . En consecuencia, los sumandos deben ser todos nulos y también lo serán, por tanto, sus raíces cuadradas, de modo que se satisfacen todas las ecuaciones del sistema. Esta transformación nos permite intuir que el número de ecuaciones de un sistema de ecuaciones diofánticas no será una característica tan relevante como lo es en el caso de los sistemas lineales habituales. Por otra parte, a continuación se describirá un proceso que nos permite realizar la transformación en el sentido opuesto, es decir, la transformación de la ecuación diofántica 𝐷(𝑥𝟣,…,𝑥𝘮)=0 en el sistema de ecuaciones diofánticas 𝐷𝟣(𝑥𝟣,…,𝑥𝘮,𝑦𝟣,…,𝑦𝘯)=0 ⋮ 𝐷𝘬(𝑥𝟣,…,𝑥𝘮,𝑦𝟣,…,𝑦𝘯)=0 18 que contiene, en general, ciertas variables adicionales 𝑦𝘪 . Cabe destacar que la transformación que vamos buscando no necesariamente debe ser la inversa de la descrita previamente, de modo que al comprimir de nuevo el sistema resultante en una sola ecuación usando cuadrados no obtendremos en general la ecuación original. La única relación de interés en este caso será que el sistema tenga solución si y solo si la tiene la ecuación, no requiriéndose, por tanto, que cada solución del sistema contenga una de la ecuación ni que cada solución de la ecuación pueda expandirse, eligiendo valores para 𝑦𝟣,…,𝑦𝘯, a una del sistema. El objetivo de esta transformación es convertir una ecuación que puede ser originalmente compleja en un sistema formado por ecuaciones mucho más simples. Estos sistemas simplificados estarán formadas por ecuaciones del tipo 𝛼=𝛽+𝛾 o bien 𝛼=𝛽𝛾 , donde los parámetros 𝛼 , 𝛽 y 𝛾 serán números naturales o bien ciertas incógnitas elegidas de entre 𝑥𝟣,…,𝑥𝘮,𝑦𝟣,…,𝑦𝘯 . Tales sistemas serán equivalentes, en el sentido explicado previamente, a sus correspondientes ecuaciones base. Explicamos cómo es posible tal transformación con un ejemplo. Ejemplo 2.1 Transformación de la ecuación diofántica 4𝑥𝟥𝑦−2𝑥𝟤𝑧𝟥−3𝑦𝟤𝑥+5𝑧=0 en un sistema de ecuaciones diofánticas equivalente. En primer lugar, obsérvese que la ecuación se puede expresar también como 4𝑥𝟥𝑦+5𝑧=2𝑥𝟤𝑧𝟥+3𝑦𝟤𝑥. Entonces introducimos 15 nuevas variables y construimos el sistema de 16ecuaciones diofánticas 𝑝𝟣=4𝑥,𝑝𝟤=𝑝𝟣𝑥,𝑝𝟥=𝑝𝟤𝑥,𝑝𝟦=𝑝𝟥𝑦 𝑞𝟣=5𝑧 𝑟𝟣=2𝑥,𝑟𝟤=𝑟𝟣𝑥,𝑟𝟥=𝑟𝟤𝑧,𝑟𝟦=𝑟𝟥𝑧,𝑟𝟧=𝑟𝟦𝑧 𝑠𝟣=3𝑦,𝑠𝟤=𝑠𝟣𝑦,𝑠𝟥=𝑠𝟤𝑥 𝑡𝟣=𝑝𝟦+𝑞𝟣,𝑢𝟣=𝑟𝟧+𝑠𝟥 𝑡𝟣=1𝑢𝟣 De esta forma, las ecuaciones que definen 𝑝𝘪 sirven para describir el primer monomio de la ecuación, de la misma forma que 𝑞𝘫 , 𝑟𝘬 y 𝑠𝘭 19 describen, respectivamente, el segundo, tercer y cuarto monomio. Por otro lado, 𝑡𝟣 y 𝑢𝟣 representan los polinomios a cada lado de la igualdad y, finalmente, la ecuación 𝑡𝟣=1𝑢𝟣 es, una vez todas las variables han sido adecuadamente definidas, en esencia igual que la ecuación original. Se ha obtenido, por tanto, un sistema de ecuaciones diofánticas que tiene solución en los números enteros si y solo si la ecuación diofántica inicial también la tiene. De esta forma, se tiene un método para transformar una ecuación diofántica en un sistema de ecuaciones diofánticas y un método para la transformación contraria. Si aplicamos estas transformaciones una a continuación de la otra, es claro que la ecuación inicial tiene solución en los números enteros si y solo si la tiene el sistema intermedio, que a su vez tiene solución si y solo si la tiene la ecuación final. Es decir, dada 𝐷(𝑥𝟣,…,𝑥𝘮)=0 obtenemos con el procedimiento del ejemplo el sistema 𝐷𝟣(𝑥𝟣,…,𝑥𝘮,𝑦𝟣,…,𝑦𝘯)=0 ⋮ 𝐷𝘬(𝑥𝟣,…,𝑥𝘮,𝑦𝟣,…,𝑦𝘯)=0, que volveremos a transformar en una sola ecuación 0=𝐷𝟤 𝟣(𝑥𝟣,…,𝑥𝘮,𝑦𝟣,…,𝑦𝘯)+⋯+𝐷𝟤 𝘬(𝑥𝟣,…,𝑥𝘮,𝑦𝟣,…,𝑦𝘯) =𝐷′(𝑥𝟣,…,𝑥𝘮,𝑦𝟣,…,𝑦𝘯), de modo que 𝐷(𝑥𝟣,…,𝑥𝘮)=0 tiene solución en los números enteros si y solo si 𝐷′(𝑥𝟣,…,𝑥𝘮,𝑦𝟣,…,𝑦𝘯)=0también la tiene. Una vez tenemos esta equivalencia, fijémonos en la última ecuación. Sabemos que, por la forma que tienen las ecuaciones del sistema intermedio, ( 𝛼=𝛽+𝛾o bien 𝛼=𝛽𝛾 ), estas pueden tener a los sumo grado total 2, de modo que sus cuadrados serán expresiones como mucho de grado 4. Esto quiere decir que la ecuación 𝐷′(𝑥𝟣,…,𝑥𝘮,𝑦𝟣,…,𝑦𝘯) = 0 será a lo sumo de grado total 4, independientemente del grado total de 𝐷(𝑥𝟣,…,𝑥𝘮)=0 . Así pues, podemos concluir de la cadena de equivalencias anteriores que, para resolver afirmativamente el décimo problema de Hilbert, bastaría con un método que pueda decidir si una ecuación diofántica de grado 4 tiene o no solución en los números enteros. 20 2.2 El décimo problema en los números naturales En la introducción de esta memoria se comentó que la resolución del décimo problema de Hilbert se alcanzó tras una sucesión de reducciones a distintos problemas hasta alcanzar uno cuya demostración proporcionó finalmente la solución negativa al mismo. En esta sección mostramos la primera de estas reducciones: pasar de considerar soluciones de las ecuaciones diofánticas en los números enteros a considerarlas en los números naturales. Sea 𝐷(𝑥𝟣,…,𝑥𝘮) = 0 una ecuación diofántica arbitraria. Supongamos entonces que estamos buscando sus soluciones no negativas. Construyamos ahora el sistema 𝐷(𝑥𝟣,…,𝑥𝘮)=0 𝑥𝟣=𝑦𝟤 𝟣,𝟣 +𝑦𝟤 𝟣,𝟤 +𝑦𝟤 𝟣,𝟥 +𝑦𝟤 𝟣,𝟦 ⋮ 𝑥𝘮=𝑦𝟤 𝘮,𝟣 +𝑦𝟤 𝘮,𝟤 +𝑦𝟤 𝘮,𝟥 +𝑦𝟤 𝘮,𝟦. Está claro que cualquier solución del sistema en números enteros incluye una solución de la ecuación inicial construida en enteros no negativos, ya que la primera ecuación del sistema establece que tal solución cumple la ecuación inicial, y el resto de ecuaciones se encargan de asegurar que los elementos de la solución no puedan tomar valores no negativos, ya que la suma de cuadrados obviamente es siempre mayor o igual que 0. Para probar el recíproco, vamos a necesitar el siguiente resultado que ya fue comentado brevemente en la introducción: Teorema 2.2 (Teorema de los cuatro cuadrados de Lagrange) La ecuación diofántica 𝑥𝟤 𝟣+𝑥𝟤 𝟤+𝑥𝟤 𝟥+𝑥𝟤 𝟦=𝑎 tiene solución 𝑥𝟣,𝑥𝟤,𝑥𝟥,𝑥𝟦 para cualquier 𝑎no negativo. Demostración del teorema 2.2 Recordemos en primer lugar la identidad de Euler, la cual será de vital importancia posteriormente. Esta nos indica que (𝑥𝟤 𝟣+𝑥𝟤 𝟤+𝑥𝟤 𝟥+𝑥𝟤 𝟦)(𝑦𝟤 𝟣+𝑦𝟤 𝟤+𝑦𝟤 𝟥+𝑦𝟤 𝟦)= (𝑥𝟣𝑦𝟣+𝑥𝟤𝑦𝟤+𝑥𝟥𝑦𝟥+𝑥𝟦𝑦𝟦)𝟤+(𝑥𝟣𝑦𝟤−𝑥𝟤𝑦𝟣+𝑥𝟥𝑦𝟦−𝑥𝟦𝑦𝟥)𝟤+ (𝑥𝟣𝑦𝟥−𝑥𝟥𝑦𝟣+𝑥𝟤𝑦𝟦−𝑥𝟦𝑦𝟤)𝟤+(𝑥𝟣𝑦𝟦−𝑥𝟦𝑦𝟣+𝑥𝟤𝑦𝟥−𝑥𝟥𝑦𝟤)𝟤. 21 Vamos a demostrar el teorema, en primer lugar, para 𝑎 un cierto número primo impar. Fijemos entonces tal 𝑎 y vamos a considerar la ecuación 𝑥𝟤 𝟣+𝑥𝟤 𝟤+𝑥𝟤 𝟥+𝑥𝟤 𝟦=𝑎𝑏 para 𝑥𝟣 , 𝑥𝟤 , 𝑥𝟥 , 𝑥𝟦 incógnitas y 𝑏 un parámetro entero. Comenzamos viendo que la ecuación planteada tiene solución para algún 𝑏=𝑏𝟢 donde 0<𝑏𝟢<𝑎 . Para ello, vamos a considerar la lista formada por los 𝘢+𝟣 𝟤elementos siguientes: 0,1,…,(𝑎−1 2) de la cual sabemos que 𝘢−𝟣 𝟤∈ℤ por ser 𝑎 impar por condición. Llamaremos 𝐴 a la lista anterior, entonces tendremos que para 𝑥,𝑦∈𝐴,𝑥≠𝑦 , se cumple: 𝑥𝟤≡𝑦𝟤(mód 𝑎)⇒𝑥𝟤−𝑦𝟤≡0 (mód 𝑎) ⇒(𝑥+𝑦)(𝑥−𝑦)≡0 (mód 𝑎) de modo que el producto (𝑥+𝑦)(𝑥−𝑦) es divisible por 𝑎 y por tanto al menos uno de sus factores debe serlo, luego 𝑥+𝑦≡0 (mód 𝑎)∨𝑥−𝑦≡0 (mód 𝑎). Si se tuviese el primer caso, entonces seguimos que 𝑥≡−𝑦 (mód 𝑎) , pero como establecimos que 𝑥,𝑦 ≤ 𝘢−𝟣 𝟤∧𝑥≠𝑦 y es fácil ver que 0< 𝑥+𝑦<𝑎 llegamos a una contradicción. Por tanto, se concluye de esto que 𝑥𝟤≡𝑦𝟤(mód 𝑎)⇒𝑥≡𝑦 (mód 𝑎) , y como los elementos de 𝐴 son dos a dos incongruentes en módulo 𝑎 , por el contrarrecíproco se sigue que también lo son sus cuadrados, luego los elemento de la lista 0𝟤,1𝟤,…,(𝑎−1 2)𝟤 son incongruentes dos a dos, y, similarmente, también la lista [−1−0𝟤,−1−1𝟤,…,−1−(𝑎−1 2)𝟤] cumple esta propiedad y de nuevo está formada por 𝘢+𝟣 𝟤elementos. Apreciamos que estas dos listas contienen en conjunto un total de 𝑎+1 números, de modo que deben contener al menos dos elementos que son congruentes en módulo 𝑎, es decir, existen 𝑥𝟣,𝑥𝟤y𝑏𝟢tales que 0≤𝑥𝟣,𝑥𝟤≤𝑎−1 2y𝑥𝟤 𝟣+𝑥𝟤 𝟤+1=𝑎𝑏𝟢 22 con mayor precisión posteriormente los conjuntos diofánticos, puesto que representan una herramienta imprescindible para la resolución del décimo problema. Nótese que en la teoría de números se suele seguir el enfoque de estudiar ciertas ecuaciones para poder describir los conjuntos que definen. En este trabajo, por el contrario, se sigue el enfoque opuesto de estudiar determinados conjuntos para tratar de determinar si son o no diofánticos y, en caso afirmativo, buscar una representación adecuada. En ciertos casos, como por ejemplo el conjunto de todos los números pares, su representación diofántica es sencilla de discernir (por ejemplo, la ecuación 2𝑥−𝑎=0 es una representación de ese conjunto). Pero también se verán casos donde estas representaciones son, en realidad, muy difíciles de hallar. Se dedicará el resto de la sección a mostrar algunas de las propiedades más básicas de los conjuntos diofánticos, así como profundizar en una forma concreta de representar conjuntos de números naturales. La unión de dos conjuntos diofánticos de la misma dimensión es diofántica. Esto se aprecia fácilmente a través de las representaciones de los conjuntos: sean 𝐷𝟣(𝑎𝟣,…,𝑎𝘯;𝑥𝟣,…,𝑥𝘮𝟣)=0 y 𝐷𝟤(𝑎𝟣,…,𝑎𝘯;𝑥𝟣,…,𝑥𝘮𝟤)=0 representaciones de dos conjuntos diofánticos de dimensión 𝑛 , entonces 𝐷𝟣(𝑎𝟣,…,𝑎𝘯;𝑥𝟣,…,𝑥𝘮𝟣)·𝐷𝟤(𝑎𝟣,…,𝑎𝘯;𝑥𝟣,…,𝑥𝘮𝟤)=0 es una representación diofántica de su unión. Esto se tiene porque si una 𝑛 -tupla 𝑎𝟣,…,𝑎𝘯 pertenece a la unión, entonces debe pertenecer a al menos uno de los dos conjuntos y por tanto al menos uno de los dos factores del producto anterior debe anularse, acorde con las representaciones individuales de los conjuntos. La intersección de dos conjuntos diofánticos de la misma dimensión es diofántica y una representación diofántica viene dada por 𝐷𝟤 𝟣(𝑎𝟣,…,𝑎𝘯;𝑥𝟣,…,𝑥𝘮𝟣)+𝐷𝟤 𝟤(𝑎𝟣,…,𝑎𝘯;𝑦𝟣,…,𝑦𝘮𝟤)=0. Esta ecuación, en efecto, representa la intersección porque si una 𝑛 - tupla pertenece a ella entonces debe pertenecer a ambos conjuntos, y se puede ver fácilmente que 𝐷𝟤 𝟣+𝐷𝟤 𝟤=0 si y solo si 𝐷𝟣=𝐷𝟤=0 , con lo que dicha condición se cumple. Notemos que para deducir esta representación se ha usado una técnica de la sección anterior para combinar ecuaciones diofánticas, así como un cambio de variable en las incógnitas de la segunda ecuación. 29 Por el contrario, el complementario de un conjunto diofántico de 𝑛 - tuplas de números naturales (respecto del conjunto de todas las 𝑛 - tuplas de números naturales) no es, en general, diofántico. Esto será probado en secciones posteriores. Con respecto a la definición de representación diofántica que ha sido dada previamente, vemos que no hay ninguna restricción adicional impuesta sobre la forma de la ecuación diofántica correspondiente, a pesar de que, como vimos en la anterior sección, podríamos haber impuesto por ejemplo que la ecuación fuese de grado 4. Finalmente, vamos a definir una nueva posible manera de especializar la forma de la ecuación representante de un conjunto, de la cual podremos tomar ventaja con posterioridad. En particular, vamos a trabajar en el caso 𝑛=1 , es decir, con representaciones diofánticas de conjuntos de números naturales. Así pues, acorde a la situación, vamos a considerar la ecuación 𝐷(𝑎;𝑥𝟣,…,𝑥𝘮)=0, y veremos que esta tiene solución en las incógnitas 𝑥𝟣,…,𝑥𝘮 si y solo si la ecuación (𝑥𝟢+1)(1−𝐷𝟤(𝑥𝟢;…,𝑥𝘮))−1=𝑎 tiene solución en las incógnitas 𝑥𝟢,…,𝑥𝘮 . La implicación directa es trivial, puesto que basta con tomar 𝑥𝟢=𝑎 para expandir cualquier solución de la primera ecuación a una solución de la segunda. Para el recíproco, basta ver que, como 𝑎 es un número natural, entonces el lado izquierdo de la segunda ecuación debe ser mayor que cero, para lo cual es necesario que el factor 1−𝐷𝟤(𝑥𝟢;…,𝑥𝘮) sea positivo. Eso solo sucede si 𝐷(𝑥𝟢;…,𝑥𝘮)=0 , pero entonces la ecuación completa nos indica que 𝑥𝟢=𝑎 con lo cual la primera ecuación también se cumple. Por tanto, lo anterior prueba que un conjunto de números naturales es diofántico si y solo si es el conjunto de todos los valores naturales que puede tomar un cierto polinomio de coeficientes enteros para valores naturales de sus variables. Dicho polinomio es el que hemos descrito antes, 𝑝(𝑥𝟢,…,𝑥𝘮)=(𝑥𝟢+1)(1−𝐷𝟤(𝑥𝟢;…,𝑥𝘮))−1, donde 𝐷está unívocamente determinado por el conjunto. 2.4 Propiedades y relaciones diofánticas Se va a introducir ahora un segundo lenguaje que nos permitirá tratar conjuntos y representaciones diofánticos. Si bien estos pueden tratarse exclusivamente en los términos ya vistos en la anterior sección, a menudo será 30 conveniente referirnos a estos conceptos usando términos más habituales del lenguaje lógico, es decir, usando propiedades y relaciones. Por ejemplo, en lugar de decir que el conjunto de los números pares o el conjunto con representación (𝑎𝟣−𝑎𝟤)𝟤=𝑥+1 son diofánticos podremos hablar de que la propiedad ser un número par o la relación ser distintos son diofánticas, respectivamente. Formalmente, diremos que una propiedad (sobre los números naturales) 𝒫 es una propiedad diofántica si el conjunto de los números que cumplen tal propiedad es diofántico. Acorde a esta definición, se denominará representación diofántica de la propiedad 𝒫 a una equivalencia de la forma 𝒫(𝑎)⇔∃𝑥𝟣,…,𝑥𝘮∶𝐷(𝑎;𝑥𝟣,…,𝑥𝘮)=0. Análogamente, una relación entre 𝑛 números naturales ℛ se denomina una relación diofántica si el conjunto de las 𝑛 -tuplas para las que se tiene la relación es diofántico. Correspondientemente, una equivalencia de la forma ℛ(𝑎𝟣,…,𝑎𝘯)⇔∃𝑥𝟣,…,𝑥𝘮∶𝐷(𝑎𝟣,…,𝑎𝘯;𝑥𝟣,…,𝑥𝘮)=0 se dice que es una representación diofántica de la relación ℛ. Como se mostró anteriormente, la unión y la intersección preservan la propiedad de ser diofántico. En el lenguaje lógico, estas operaciones se señalizan usando las conectivas de disyunción y conjunción, de modo que si ℛ𝟣 y ℛ𝟤 son relaciones (o propiedades) diofánticas, entonces la relación (o propiedad) ℛdada por ℛ(𝑎𝟣,…,𝑎𝘯)⇔ℛ𝟣(𝑎𝟣,…,𝑎𝘯)∨ℛ𝟤(𝑎𝟣,…,𝑎𝘯) es diofántica y se corresponde con la unión, así como también ℛ(𝑎𝟣,…,𝑎𝘯)⇔ℛ𝟣(𝑎𝟣,…,𝑎𝘯)∧ℛ𝟤(𝑎𝟣,…,𝑎𝘯) es diofántica y se corresponde con la intersección. Formalmente, para probar estas afirmaciones tendríamos que partir de las correspondientes representaciones de las relaciones ℛ𝟣 y ℛ𝟤 y, a partir de ellas, construir una representación adecuada para la relación ℛ que estamos tratando. En la práctica, esta fase intermedia será omitida y aceptaremos representaciones en la forma anterior; conociendo que ℛ𝟣 y ℛ𝟤 son diofánticas, llamaremos a una expresión como la previa una representación diofántica generalizada de la relación (propiedad) ℛ . Usando disyunción, conjunción y cuantificación existencial en cualquier orden podemos afrontar fórmulas construidas a partir de ecuaciones diofánticas paramétricas y expresarlas como representaciones generalizadas. Cuando sea necesario, podremos de la misma forma 31 revertir el proceso y transformar las fórmulas diofánticas generalizadas en sus correspondientes formas canónicas. En la próxima sección se expondrán algunos ejemplos de ello. Introduzcamos también la noción de funciones diofánticas, lo cual mostrará su utilidad al simplificar algunas pruebas de que ciertos conjuntos son diofánticos. Así pues, diremos que una función es diofántica si es diofántico su correspondiente grafo. Dicho de otra forma, una representación diofántica de una función 𝐹es una equivalencia de la forma 𝑎=𝐹(𝑏𝟣,…,𝑏𝘯)⇔∃𝑥𝟣,…,𝑥𝘮∶𝐷(𝑎,𝑏𝟣,…,𝑏𝘯;𝑥𝟣,…,𝑥𝘮)=0 con 𝐷un polinomio con coeficientes enteros. Por último, un término diofántico 𝑡 es una expresión construida a partir de números naturales, variables, los símbolos de operaciones ‘+’, ‘-’ y ‘·’ y símbolos correspondientes a determinadas funciones diofánticas. Podemos admitir entonces ecuaciones de la forma 𝑃(𝑡𝟣,…,𝑡𝘬)=0 donde 𝑃 es un polinomio con coeficientes enteros y 𝑡𝟣,…,𝑡𝘬 son términos diofánticos. En efecto, replicando el proceso ya ejemplificado en la sección 2.1 podemos transformar, con el coste de introducir algunas variables nuevas, estas ecuaciones en sistemas equivalentes formados por ecuaciones de la forma 𝛼=𝛽+𝛾 𝛼=𝛽𝛾 𝛼=𝐹(𝛽𝟣,…,𝛽𝘯), donde de nuevo 𝛼,𝛽,𝛽𝟣,…,𝛽𝘯 y 𝛾 son variables o números naturales particulares, y 𝐹 es una función diofántica. Más aún, las ecuaciones en el sistema que tengan la tercera forma expuesta podrán a su vez reemplazarse por expresiones equivalentes en términos de la representación diofántica adecuada de la función 𝐹 , cuya forma fue señalada al definir las funciones diofánticas, tan solo haciendo falta sustituir 𝑎 por 𝛼 , 𝑏𝟣,…,𝑏𝘯 por 𝛽𝟣,…,𝛽𝘯 y 𝑥𝟣,…,𝑥𝘮 por nuevas variables que no hayan sido usadas. El sistema resultante, como ya sabemos, podrá después ser comprimido a una sola ecuación equivalente a la original. De la misma forma, también podemos permitir el uso de términos diofánticos arbitrarios como argumentos de relaciones o propiedades diofánticas en representaciones generalizadas. De hecho, si ℛ es una relación diofántica entonces el enunciado ℛ(𝑡𝟣,…,𝑡𝘯) (con 𝑡𝟣,…,𝑡𝘯 términos diofánticos) es 32 equivalente al enunciado ∃𝑑𝟣,…,𝑑𝘯∶ℛ(𝑑𝟣,…,𝑑𝘯)∧𝑑𝟣=𝑡𝟣∧⋯∧𝑑𝘯=𝑡𝘯 El primer término de la conjunción puede ser sustituido por la representación diofántica habitual de una relación, y el resto de ellos pueden ser tratados como acabamos de ver que se manipulan las ecuaciones diofánticas con términos diofánticos como argumentos. Nótese que las funciones diofánticas no necesariamente tienen por qué estar definidas para cualquier valor de sus argumentos. Es por eso que, por ejemplo, la fórmula 𝐹(𝑎𝟣,…,𝑎𝘯)=0∨𝐹(𝑎𝟣,…,𝑎𝘯)≠0 no es, en general, una representación diofántica generalizada para una relación tautológica (salvo que 𝐹 sí que este definida para cualquier posible entrada). Sí se le requerirá, no obstante, que esté correctamente definida en los valores necesarios para usarla adecuadamente para convertir una ecuación diofántica en un sistema de la forma explicada anteriormente, es decir, con la notación usada, se requiere que 𝐹esté definida en 𝛽𝟣,…,𝛽𝘯. Maticemos para terminar la sección que el concepto representación diofántica generalizada no debe entenderse como un objeto matemático rigurosamente definido. Esto es debido a que una representación de este tipo refleja, aparte de propiedades, relaciones, funciones y cualidades objetivas de conjuntos, un orden particular en el que consideramos todo lo anterior. Por ejemplo, dada una representación diofántica de la propiedad ser un número par como, por ejemplo, 𝐸𝑣𝑒𝑛(𝑎)⇔∃𝑥∶2𝑥=𝑎 se puede derivar directamente la siguiente representación generalizada de la propiedad ser un número impar 𝑂𝑑𝑑(𝑎)⇔𝐸𝑣𝑒𝑛(𝑎+1) Análogamente, dada una representación diofántica de la propiedad ser un número impar como, por ejemplo, 𝑂𝑑𝑑(𝑎)⇔∃𝑥∶2𝑥+1=𝑎 se puede derivar directamente la siguiente representación generalizada de la propiedad ser un número par 𝐸𝑣𝑒𝑛(𝑎)⇔𝑂𝑑𝑑(𝑎+1) Sin embargo, sería incorrecto usar simultáneamente esas representaciones generalizadas para ambas propiedades. 𝐸𝑣𝑒𝑛(𝑎)⇔𝑂𝑑𝑑(𝑎+1) 𝑂𝑑𝑑(𝑎)⇔𝐸𝑣𝑒𝑛(𝑎+1) 33 2.5 Ejemplos de relaciones y funciones diofánticas En la sección anterior introdujimos la expresión (𝑎𝟣−𝑎𝟤)𝟤=𝑥+1 como representación de la relación ≠ , que es por tanto diofántica. Se pueden dar representaciones similares que demuestran que también ≤ y < son diofánticas: 𝑎≤𝑏⇔∃𝑥∶𝑎+𝑥=𝑏 𝑎<𝑏⇔∃𝑥∶𝑎+𝑥+1=𝑏 La relación de divisibilidad también es diofántica: 𝑎∣𝑏⇔∃𝑥∶𝑎𝑥=𝑏 Con estas herramientas, estamos en condiciones de obtener la representación diofántica generalizada para la función que devuelve el resto del cociente de 𝑏entre 𝑐, denotada rem(𝑏,𝑐): 𝑎=𝑟𝑒𝑚(𝑏,𝑐)⇔𝑎<𝑐∧𝑐∣(𝑏−𝑎) que está adecuadamente definida porque ya hemos probado que tanto la desigualdad estricta como la divisibilidad son propiedades diofánticas. A su vez, esto nos permite establecer la representación 𝑎∤𝑏⇔𝑟𝑒𝑚(𝑏,𝑎)>0 lo que prueba de que la relación de no divisibilidad es también diofántica. Nótese que, sin embargo, definida de esta forma la relación de divisibilidad no es la negación de la divisibilidad. Podemos apreciar esta diferencia si nos fijamos en las representaciones que hemos dado para ∣ y ∤ , puesto que en el caso 𝑎=0 y 𝑏>0 ambas relaciones son falsas. Este problema podría salvarse cambiando ligeramente las definiciones dadas, pero esto no será necesario pues tan solo usaremos la relación ∤ cuando se tenga garantía de que el primer argumento es no nulo. Similarmente, podemos considerar la función arem( 𝑏 , 𝑐 )que devuelve el menor valor absoluto |𝜒| entre todos los números 𝜒 congruentes con 𝑏 en módulo 𝑐 , arem(𝑏,𝑐)≡±𝑏 (mód 𝑐)∧0≤arem(𝑏,𝑐)≤𝑐/2 . Dicha función es también diofántica y tiene representación generalizada 𝑎=arem(𝑏,𝑐)⇔2𝑎≤𝑐∧[𝑐∣(𝑏−𝑎)∨𝑐∣(𝑏+𝑎)] 34 Teniendo probado que la función resto es diofántica, podremos también continuar dando representaciones diofánticas generalizadas para la función parte entera de 𝑏/𝑐, 𝑎=𝑏div 𝑐⇔𝑎𝑐+𝑟𝑒𝑚(𝑏,𝑐)=𝑏 y para la relación de congruencia respecto a un módulo positivo, 𝑎≡𝑏 (mód 𝑐)⇔𝑟𝑒𝑚(𝑎,𝑐)=𝑟𝑒𝑚(𝑏,𝑐) Finalmente, como sabemos por la identidad de Bézout que el máximo común divisor de dos enteros positivos 𝑏 y 𝑐 puede expresarse como gcd(𝑏,𝑐)=𝑏𝑥−𝑐𝑦 , para ciertos 𝑥,𝑦 enteros, y está claro que cualquier número expresado en forma de esta diferencia es divisible por gcd(𝑏,𝑐) , entonces tenemos para la función gcd la siguiente representación diofántica generalizada: 𝑎=gcd(𝑏,𝑐)⇔𝑏𝑐>0∧𝑎∣𝑏∧𝑎∣𝑐∧∃𝑥,𝑦∶𝑎=𝑏𝑥−𝑐𝑦 Asimismo, que el máximo común divisor sea diofántico nos permite también mostrar que la función mínimo común múltiplo de los enteros positivos 𝑏y𝑐tiene la representación diofántica 𝑎=lcm(𝑏,𝑐)⇔𝑏𝑐=𝑎·gcd(𝑏,𝑐) luego también es una función diofántica. 35 3Representación diofántica de la exponenciación Tal y como sugiere su título, el propósito de este capítulo es definir adecuadamente la función de dos argumentos 𝑏𝘤 , es decir, la exponenciación, así como también mostrar que dicha función es diofántica bajo las definiciones ahora disponibles. A pesar de ser este proceso técnico y complejo, completar la demostración nos proporcionará un método directo para probar que otras funciones y relaciones son diofánticas, lo cual justifica la labor. 3.1 Ecuaciones diofánticas exponenciales En adelante, las ecuaciones diofánticas exponenciales tendrán un rol imprescindible avanzando en el proceso hacia la resolución definitiva del décimo problema de Hilbert. Estas ecuaciones son aquellas de la forma 𝐸𝟣(𝑥𝟣,…,𝑥𝘮)=𝐸𝟤(𝑥𝟣,…,𝑥𝘮) donde 𝐸𝟣 y 𝐸𝟤 son expresiones construidas a partir de variables y números naturales usando las operaciones de suma, multiplicación y exponenciación. La operación diferencia estará restringida en este tipo de ecuaciones con el propósito de mantener el rango de valores de las incógnitas en el conjunto de los números naturales. No obstante, se usará el signo ‘-’ al describir ecuaciones diofánticas exponenciales tan solo en los casos donde tal signo pueda ser fácilmente eliminado usando transposiciones u otro tipo de transformaciones evidentes. Con este apunte en mente, se recalca también el hecho de que cualquier sistema de ecuaciones diofánticas exponenciales puede comprimirse en una sola ecuación equivalente de la forma descrita en el capítulo anterior para ecuaciones diofánticas ordinarias (a través de la suma de cuadrados). Análogamente a como se desarrolló en la sección 2.3, podemos considerar ecuaciones diofánticas exponenciales paramétricas y definir a partir de 36 ellas representaciones diofánticas exponenciales para conjuntos, propiedades, relaciones y funciones. Más adelante en este capítulo se probará que la exponenciación es, de hecho, una función diofántica, lo cual, de acuerdo con lo visto en la sección referenciada al comienzo, garantiza que podemos transformar ecuaciones diofánticas exponenciales en ecuaciones diofánticas ordinarias equivalentes con los mismos parámetros, tan solo con el coste de aumentar el número de incógnitas. Por tanto, la clase de conjuntos que tienen representaciones diofánticas exponenciales coincide con la clase de los conjuntos diofánticos y sucede lo mismo, respectivamente, para las clases de propiedades, relaciones y funciones con sus adecuadas representaciones. Siguiendo el convenio establecido en el capítulo anterior, consideraremos las representaciones exponenciales como representaciones diofánticas generalizadas. Las representaciones exponenciales, sin embargo, a menudo resultan más sencillas y compactas que las representaciones generalizadas correspondientes, con lo cual pueden despertar un interés por sí mismas. Las representaciones diofánticas exponenciales pueden además verificar ciertas propiedades adicionales no demostradas aún para las representaciones diofánticas. Podemos también considerar una clase de ecuaciones intermedia entre las ecuaciones diofánticas exponenciales y las ecuaciones diofánticas ordinarias. A las ecuaciones de dicha clase las denominaremos ecuaciones diofánticas exponenciales unitarias, las cuales se definen como ecuaciones exponenciales en las cuales tan solo las constantes pueden tener exponentes. Es decir, en lugar de potencias binarias 𝑏𝘤 se tratará en esta clase de ecuaciones con exponenciales de un solo argumento como 2𝘤,3𝘤,… . Si tan solo se usa una de esas exponenciales, por ejemplo 𝑎𝘤 (con 𝑎 fijo), sea una o varias veces, entonces se dir á que la ecuación es una ecuación diofántica exponencial unitaria de base 𝑎. Ejemplo 3.1 (Ecuación de Fermat) Es la ecuación diofántica exponencial (𝑝+1)𝘴+𝟥 +(𝑞+1)𝘴+𝟥 =(𝑟+1)𝘴+𝟥. donde las incógnitas 𝑝,𝑞,𝑟y𝑠toman valores en los números naturales. Nótese que si consideramos 𝑠 como parámetro y 𝑝 , 𝑞 y 𝑟 como incógnitas, entonces la ecuación de Fermat sería una ecuación diofántica exponencial paramétrica que proporcionaría una familia de ecuaciones que serían ecuaciones diofánticas en el sentido habitual. El último teorema de Fermat es, simplemente, la afirmación de que 37 esta ecuación no tiene solución para las incógnitas 𝑝 , 𝑞 , 𝑟 y 𝑠 . Una vez lleguemos, al final de este capítulo, a la conclusión de que la exponenciación es diofántica, será posible construir entonces un polinomio específico 𝒫con coeficientes enteros tal que la ecuación 𝒫(𝑝,𝑞,𝑟,𝑠,𝑥𝟣,…,𝑥𝘮)=0 es resoluble en las variables 𝑥𝟣,…,𝑥𝘮 si y solo si 𝑝 , 𝑞 , 𝑟 y 𝑠 satisfacen la ecuación de Fermat. Por tanto, el último teorema de Fermat resulta equivalente a la afirmación de que una determinada ecuación diofántica, 𝒫=0, es irresoluble en sus 𝑚+4incógnitas. 3.2 Las sucesiones recurrentes 𝛼𝑏(𝑛) Como se comentó al comienzo del capítulo, el objetivo que se busca es probar que la función 𝑏𝘤 es diofántica. Equivalentemente, también podemos afrontar este problema en el lenguaje de conjuntos buscando una prueba de que el conjunto de triples {(𝑎,𝑏,𝑐)∣𝑎=𝑏𝘤} es diofántico. Destaquemos que esta afirmación implica directamente que el conjunto de pares {(𝑎,𝑏)∣∃𝑛∶𝑎=𝑏𝘯} es diofántico (Robinson también probó que el recíproco es cierto, pero la demostración no es de nuestro interés puesto que no trabajaremos demasiado con este segundo conjunto). Contrario a lo que uno podría pensar, es de hecho más sencillo comprobar directamente que el conjunto de triples es diofántico en lugar de probar que lo sea el conjunto de pares y usar la anterior implicación inversa. Vamos por tanto a proceder de tal forma. Alternativamente a la expresión explícita del conjunto de triples, otra forma de entender el conjunto de las potencias de un cierto número 𝑏 dado es a través del conjunto de todos los elementos que conforman la sucesión recurrente 𝛽𝘣(0)=1, 𝛽𝘣(𝑛+1)=𝑏𝛽𝘣(𝑛) Similar a esta sucesión, en la prueba que vamos a realizar trataremos con la sucesión recurrente de segundo orden siguiente: 𝛼𝘣(0)=0, 𝛼𝘣(1)=1, 𝛼𝘣(𝑛+2)=𝑏𝛼𝘣(𝑛+1)−𝛼𝘣(𝑛) 38 ya que para el valor escogido para 𝑣en el desarrollo previo se tiene que 𝑣=𝛼𝘣(𝑚+1)−𝛼𝘣(𝑚−1) =𝑏𝛼𝘣(𝑚)−2𝛼𝘣(𝑚−1) ≥2𝛼𝘣(𝑚) para 𝑏≥4 , puesto que es sencillo comprobar por inducción sobre la definición de 𝛼𝘣 que se cumple que 𝛼𝘣(𝑛)<𝛼𝘣(𝑛+1) ; y por tanto podemos afirmar que, por definición de la función, se tiene que arem(𝛼𝘸(𝑖),𝑣)=arem(−𝛼𝘸(𝑖),𝑣)= 𝛼𝘣(𝑖)para 𝑖entre 1 y 𝑚. Por otro lado, también tenemos por las condiciones impuestas sobre 𝑢 que se tiene 𝑤 ≡2 (mód 𝑢) y por tanto también 𝛼𝘸(𝑛)≡𝛼𝟤(𝑛)=𝑛 (mód 𝑢) , como ya mencionamos al comienzo de la demostración. Así pues, esto nos indica que, aparte del periodo módulo 𝑣 que ya hemos descrito, la sucesión 𝛼𝘸(0),…,𝛼𝘸(𝑛),…también tiene el periodo de 𝑢términos 0,1,…,𝑢−1 en módulo 𝑢. En consecuencia, también la sucesión arem(𝛼𝘸(0),𝑢),…,arem(𝛼𝘸(𝑛),𝑢),… (3.3) tendrá el mismo periodo. Ahora, imponemos sobre 𝑢la nueva condición 𝑢∣𝑚, lo cual nos permite afirmar que la longitud del periodo de la secuencia 3.2 desarrollada previamente es un múltiplo de la longitud de la secuencia anterior, 3.3, y por tanto se sigue que la sucesión, equivalente a la original 3.1, de la cual queríamos eliminar términos adicionales, (arem(𝛼𝘸(0),𝑣),𝑏,arem(𝛼𝘸(0),𝑢)),…,(arem(𝛼𝘸(𝑛),𝑣),𝑏,arem(𝛼𝘸(𝑛),𝑢)),…, es de hecho periódica con un periodo casi simétrico y de longitud 2𝑚 . Por tanto todos estos triples que buscábamos suprimir deben, en caso de haberlos, aparecer entre los primeros 𝑚+1términos de la secuencia. Para estos triples iniciales, está claro que la condición 2·arem(𝛼𝘸(𝑛),𝑣)<𝑢 puede reescribirse como 2𝛼𝘣(𝑛)<𝑢 y por tanto, al cumplirse que 𝑛≤𝛼𝘣(𝑛) como ya hemos mencionado antes, entonces en particular implica que 2𝑛<𝑢. 45 Usando de nuevo las condiciones impuestas sobre 𝑢 , esto nos permite deducir que arem(𝛼𝘸(𝑛),𝑢)=arem(𝑛,𝑢)=𝑛. Luego la condición 2·arem(𝛼𝘸(𝑛),𝑣) < 𝑢 efectivamente elimina todos los triples adicionales de la secuencia. Para tratar de implementar el plan descrito, notamos que se destaca una dificultad que hay que solucionar, esto es, necesitamos ecuaciones diofánticas que definan el par de condiciones 𝑣=𝛼𝘣(𝑚+1)−𝛼𝘣(𝑚−1) 𝑢∣𝑚. En particular, vamos a buscar una forma alternativa de expresar la condición de divisibilidad. Para ello, nos valemos de la propiedad de 𝛼 siguiente que será probada en la sección 3.4: 𝛼𝟤 𝘣(𝑘)∣𝛼𝘣(𝑚)⟹𝛼𝘣(𝑘)∣𝑚. Entonces, tomando 𝑢=𝛼𝘣(𝑘) , podemos reemplazar la condición 𝑢∣𝑚 por la otra condición más fuerte 𝑢𝟤∣𝛼𝘣(𝑚). 3.4 Representación diofántica de las sucesiones recurrentes 𝛼𝑏: demostración En esta sección se va a proporcionar una demostración rigurosa de las ideas presentadas en la sección anterior. Para favorecer la claridad de esta demostración, se presentan previamente algunas propiedades de las sucesiones recurrentes 𝛼𝘣. 3.4.1 Propiedades de 𝛼𝑏 Recordemos que las sucesiones 𝛼𝘣 se definen en base a una recursión de segundo orden tal que 𝛼𝘣(0)=0 𝛼𝘣(1)=1 𝛼𝘣(𝑛+2)=𝑏𝛼𝘣(𝑛+1)−𝛼𝘣(𝑛). Vimos también que esta sucesión es monótona con un crecimiento estricto de modo que 𝛼𝘣(0)<𝛼𝘣(1)<⋯<𝛼𝘣(𝑛−1)<𝛼𝘣(𝑛)<𝛼𝘣(𝑛+1)<⋯ 46 y además se tiene también la siguiente relación con respecto al argumento: 𝑛≤𝛼𝘣(𝑛),∀𝑛∈ℕ La recursión que define 𝛼𝘣 también puede ser expresada en formato matricial usando la matriz 𝐴𝘣(𝑛)=(𝛼𝘣(𝑛+1) −𝛼𝘣(𝑛) 𝛼𝘣(𝑛) −𝛼𝘣(𝑛−1)) donde usando el convenio 𝛼𝘣(−1)=−1 podemos ver que 𝐴𝘣(0)=𝐼 y 𝐴𝘣(𝑛+1)= 𝐴𝘣(𝑛)Ξ𝘣siendo que 𝐼=(1 0 0 1)Ξ𝘣=(𝑏 −1 1 0) En particular, esta relación nos permite establecer que 𝐴𝘣(𝑛)=Ξ𝘯 𝘣. A continuación, recordamos que gracias precisamente a esta expresión matricial, fuimos capaces de establecer la identidad 𝛼𝟤 𝘣(𝑛+1)−𝑏𝛼𝘣(𝑛+1)𝛼𝘣(𝑛)+𝛼𝟤 𝘣(𝑛)=1 De hecho, demostramos que la ecuación 𝑥𝟤−𝑏𝑥𝑦+𝑦𝟤=1 caracteriza la sucesión 𝛼𝘣 en tanto que si se cumple dicha ecuación y 𝑥≠𝑦 , entonces para cierto 𝑚se cumple que 𝑥=𝛼𝘣(𝑚+1)e𝑦=𝛼𝘣(𝑚)o viceversa, según el orden relativo de 𝑥e𝑦. Además, podemos usar la definición de 𝛼𝘣 para reinterpretar la igualdad: 𝛼𝟤 𝘣(𝑛)−𝛼𝘣(𝑛+1)𝛼𝘣(𝑛−1)=1 lo cual nos conduce a otras dos propiedades interesantes. Por un lado, sabemos que 𝛼𝘣(𝑘)∈ℤ,∀𝑘∈ℕ . En particular, los tres factores que intervienen en los sumandos de la igualdad anterior son enteros. Usando la identidad de Bézout, esto nos permite afirmar que 𝛼𝘣(𝑛) es coprimo con 𝛼𝘣(𝑛+1) y con 𝛼𝘣(𝑛−1) . Dicho de otra forma, como esto se cumple para un elemento arbitrario de la sucesión, podemos decir de forma más general que los términos sucesivos de la secuencia 𝛼𝘣 son coprimos dos a dos. Por otra parte, vamos a suponer que 𝛼𝘣(𝑛) es par. Consecuentemente, también debe ser entonces que 𝛼𝟤 𝘣(𝑛) es par. Ahora bien, gracias a la identidad anterior seguimos que 𝛼𝟤 𝘣(𝑛)−1=𝛼𝘣(𝑛+1)𝛼𝘣(𝑛−1), 47 en particular 𝛼𝘣(𝑛+1)𝛼𝘣(𝑛−1) es impar por distanciarse en una sola unidad de un número par. Pero un producto solo es impar si lo son sus dos factores, por tanto 𝛼𝘣(𝑛+1) y 𝛼𝘣(𝑛−1) son ambos impares. Concretamente, como el argumento elegido era arbitrario, hemos probado que en la secuencia 𝛼𝘣 no puede haber dos elementos pares adyacentes. Recordamos también las relaciones de congruencias útiles que cumplen los elementos de la secuencia. Así pues, ya se ha comentado que se cumple 𝑏𝟣≡𝑏𝟤(mód 𝑞)⇒𝛼𝘣𝟣(𝑛)≡𝛼𝘣𝟤(𝑛) (mód 𝑞) En particular, también sabemos que 𝛼𝟤(𝑛)=𝑛 gracias a la propia definición de la recurrencia, luego tendremos por lo anterior que 𝑡≡2 (mód 𝑞)⇒𝛼𝘵(𝑛)≡𝛼𝟤(𝑛)=𝑛 (mód 𝑞). Por otro lado, cuando en el proceso de la demostración tomemos 𝑣= 𝛼𝘣(𝑚+1)−𝛼𝘣(𝑚−1), remarquemos de nuevo que claramente se tiene que 𝛼𝘣(𝑚+1)≡𝛼𝘣(𝑚−1) (mód 𝑣), propiedad que es extensible para otro rango mayor de números pero que no utilizaremos de nuevo más que en su caso inicial. La última propiedad de la sucesión 𝛼𝘣 que vamos a demostrar es la implicación mencionada al final de la sección 3.3. Así pues, consideremos ciertos 𝑏,𝑘y𝑚 satisfaciendo la condición, 𝛼𝟤 𝘣(𝑘)∣𝛼𝘣(𝑚) . Sea también 𝑚=𝑛+𝑘𝑙 (0≤𝑛<𝑘) , recordemos que ambos 𝛼𝘣(𝑘) y 𝛼𝘣(𝑚) son coeficientes de unas ciertas matrices definidas al comienzo de la sección, de modo que se cumple que (𝛼𝘣(𝑚+1) −𝛼𝘣(𝑚) 𝛼𝘣(𝑚) −𝛼𝘣(𝑚−1))=𝐴𝘣(𝑚) =Ξ𝘮 𝘣=Ξ𝘯+𝘬𝘭 𝘣=Ξ𝘯 𝘣(Ξ𝘬 𝘣)𝘭 =𝐴𝘣(𝑛)𝐴𝘭 𝘣(𝑘) =(𝛼𝘣(𝑛+1) −𝛼𝘣(𝑛) 𝛼𝘣(𝑛) −𝛼𝘣(𝑛−1))(𝛼𝘣(𝑘+1) −𝛼𝘣(𝑘) 𝛼𝘣(𝑘) −𝛼𝘣(𝑘−1))𝘭. Pasamos la expresión a módulo 𝛼𝘣(𝑘) , y como sabemos que 𝑛 < 𝑘 ⇒ 𝛼𝘣(𝑛)<𝛼𝘣(𝑘), obtenemos que (𝛼𝘣(𝑚+1) −𝛼𝘣(𝑚) 𝛼𝘣(𝑚) −𝛼𝘣(𝑚−1)) ≡(𝛼𝘣(𝑛+1) −𝛼𝘣(𝑛) 𝛼𝘣(𝑛) −𝛼𝘣(𝑛−1))(𝛼𝘣(𝑘+1) 0 0 −𝛼𝘣(𝑘−1))𝘭(mód 𝛼𝘣(𝑘)), 48 de donde se sigue directamente por la definición del producto entre matrices que 𝛼𝘣(𝑚)≡𝛼𝘣(𝑛)𝛼𝘭 𝘣(𝑘+1) (mód 𝛼𝘣(𝑘)). Ahora bien, ya hemos mencionado que 𝛼𝘣(𝑛) es coprimo con 𝛼𝘣(𝑛+1) y 𝛼𝘣(𝑛−1) , y en particular 𝛼𝘣(𝑘) y 𝛼𝘣(𝑘+1) son coprimos, lo cual junto con la condición 𝛼𝟤 𝘣(𝑘)∣𝛼𝘣(𝑚) que estamos suponiendo y la congruencia anterior nos indica que 𝛼𝘣(𝑛)𝛼𝘭 𝘣(𝑘+1)≡𝛼𝘣(𝑚)≡0 (mód 𝛼𝘣(𝑘)), de modo que 𝛼𝘣(𝑘)∣𝛼𝘣(𝑛)𝛼𝘭 𝘣(𝑘+1) , y al ser coprimo con el segundo factor del producto entonces necesariamente 𝛼𝘣(𝑘)∣𝛼𝘣(𝑛) . Sin embargo, ya hemos señalado al desarrollar la congruencia matricial que se tiene la desigualdad 𝛼𝘣(𝑛)<𝛼𝘣(𝑘) por propiedades de la sucesión 𝛼𝘣 , luego la condición de divisibilidad previa solo es posible si 𝑛=0, por lo que 𝑚=𝑘𝑙. Esto nos permite replicar el desarrollo matricial anterior usando la definición de la matriz 𝐴𝘣y establecer que 𝐴𝘣(𝑚)=𝐴𝘭 𝘣(𝑘)=(𝛼𝘣(𝑘+1) −𝛼𝘣(𝑘) 𝛼𝘣(𝑘) −𝛼𝘣(𝑘−1))𝘭 =(𝑏𝛼𝘣(𝑘)−𝛼𝘣(𝑘−1) −𝛼𝘣(𝑘) 𝛼𝘣(𝑘) −𝛼𝘣(𝑘−1))𝘭 =[(𝑏𝛼𝘣(𝑘) −𝛼𝘣(𝑘) 𝛼𝘣(𝑘) 0 )−(𝛼𝘣(𝑘−1) 0 0 𝛼𝘣(𝑘−1))]𝘭 =[𝛼𝘣(𝑘)Ξ𝘣−𝛼𝘣(𝑘−1)𝐼]𝘭 =𝘭 ∑ 𝘪=𝟢 (−1)𝘭−𝘪 (𝑙𝑖)𝛼𝘪 𝘣(𝑘)𝛼𝘭−𝘪 𝘣(𝑘−1)Ξ𝘪 𝘣. Pasando la ecuación a congruencias en módulo 𝛼𝟤 𝘣(𝑘) , todos los sumandos se anulan salvo los dos primeros gracias al factor 𝛼𝘪 𝘣(𝑘) de la expresión final, de modo que podemos expresar 𝐴𝘣(𝑚)=(𝛼𝘣(𝑚+1) −𝛼𝘣(𝑚) 𝛼𝘣(𝑚) −𝛼𝘣(𝑚−1)) ≡(−1)𝘭𝛼𝘭 𝘣(𝑘−1)𝐼+(−1)𝘭−𝟣𝑙𝛼𝘣(𝑘)𝛼𝘭−𝟣 𝘣(𝑘−1)Ξ𝘣(mód 𝛼𝟤 𝘣(𝑘)). Así, por la forma que tienen las matrices identidad y Ξ𝘣 , aislamos la relación del coeficiente 𝑎𝟤𝟣 y nos queda que 𝛼𝘣(𝑚)≡(−1)𝘭−𝟣𝑙𝛼𝘣(𝑘)𝛼𝘭−𝟣 𝘣(𝑘−1) (mód 𝛼𝟤 𝘣(𝑘)), 49 y como ya tenemos por la hipótesis que estamos asumiendo ( 𝛼𝟤 𝘣(𝑘)∣𝛼𝘣(𝑚) ) que 𝛼𝘣(𝑚)≡0 (mód 𝛼𝟤 𝘣(𝑘)), deducimos que 𝛼𝟤 𝘣(𝑘)∣𝑙𝛼𝘣(𝑘)𝛼𝘭−𝟣 𝘣(𝑘−1) luego 𝛼𝘣(𝑘)∣𝑙𝛼𝘭−𝟣 𝘣(𝑘−1) Usando que 𝛼𝘣(𝑘) y 𝛼𝘣(𝑘−1) son coprimos, llegamos a que 𝛼𝘣(𝑘)∣𝑙 , y como sabemos que 𝑚=𝑘𝑙 , entonces finalmente podemos concluir que 𝛼𝘣(𝑘)∣𝑚 , con lo que tenemos la implicación. Finalizamos la sección de propiedades de 𝛼𝘣 demostrando el teorema chino del resto, que también será usado en la prueba de que estas sucesiones son diofánticas. Teorema 3.3 (Teorema chino del resto) Sean 𝑞𝟣,…,𝑞𝘯 números coprimos dos a dos y 𝑎𝟣,…,𝑎𝘯 tales que 0≤𝑎𝘪<𝑞𝘪 , para (𝑖=1,…,𝑛) . Entonces, existe un único 𝑎tal que 0≤𝑎<𝑞𝟣𝑞𝟤⋯𝑞𝘯y 𝑎𝘪=rem(𝑎,𝑞𝘪), para todo 𝑖=1,…,𝑛 Demostración del teorema 3.3 Consideramos el conjunto de las 𝑞𝟣⋯𝑞𝘯𝑛-tuplas formado por (rem(0,𝑞𝟣),…,rem(0,𝑞𝘯)) ⋮ (rem(𝑞𝟣⋯𝑞𝘯−1,𝑞𝟣),…,rem(𝑞𝟣⋯𝑞𝘯−1,𝑞𝘯)) Todos los elementos definidos del conjunto son diferentes puesto que si se tuviese que rem(𝑎′,𝑞𝘪)=rem(𝑎″,𝑞𝘪) para ciertos 𝑎′,𝑎″∈ {1,…,𝑞𝟣⋯𝑞𝘯−1} y ∀𝑖 ∈ {1,…,𝑛} , entonces se tendría que 𝑞𝘪∣𝑎′−𝑎″ , ∀𝑖∈{1,…,𝑛} . Como estamos suponiendo que 𝑞𝟣,…,𝑞𝘯 son primos entre sí dos a dos, entonces lo anterior implicaría que 𝑞𝟣⋯𝑞𝘯∣𝑎′−𝑎″ pero 𝑎′−𝑎″≤𝑞𝟣⋯𝑞𝘯−1 , de modo que para tener esta propiedad debe ocurrir que 𝑎′−𝑎″=0, es decir 𝑎′=𝑎″. Por otro lado, usando combinatoria podemos deducir que hay exactamente 𝑞𝟣⋯𝑞𝘯𝑛 -tuplas (𝑎𝟣,…,𝑎𝘯) que cumplan que 0≤𝑎𝘪< 𝑞𝘪 50 (∀𝑖=1,…𝑛) , mientras que también apreciamos que cada una de las 𝑛 -tuplas del conjunto que acabamos de definir verifican tal condición por la definición de la función rem. Como acabamos de probar que todas las 𝑛 -tuplas del conjunto anterior son distintas, están entre las 𝑛 -tuplas (𝑎𝟣,…,𝑎𝘯) que mencionábamos por cumplir la propiedad de la hipótesis y también coinciden en número con ellas, entonces cada una de estas últimas se corresponde exactamente con un elemento del conjunto. El resultado se deduce directamente de esta conclusión. 3.4.2 Las sucesiones 𝛼𝑏son diofánticas Estamos ya en condiciones de demostrar que las sucesiones 𝛼𝘣 son diofánticas. Para ello, vamos a mostrar un sistema de ecuaciones diofánticas que será resoluble si y solo si (𝑎,𝑏,𝑐)∈𝐴={(𝑎,𝑏,𝑐)∣𝑏≥4∧𝑎=𝛼𝘣(𝑐)} . Así pues, basándonos en todo el desarrollo hecho hasta ahora, dicho sistema será el siguiente: 𝑏≥4, (1) 𝑢𝟤−𝑏𝑢𝑡+𝑡𝟤=1, (2) 𝑠𝟤−𝑏𝑠𝑟+𝑟𝟤=1, (3) 𝑟<𝑠, (4) 𝑢𝟤∣𝑠, (5) 𝑣=𝑏𝑠−2𝑟, (6) 𝑣∣𝑤−𝑏, (7) 𝑢∣𝑤−2, (8) 𝑤>2, (9) 𝑥𝟤−𝑤𝑥𝑦+𝑦𝟤=1, (10) 2𝑎<𝑢, (11) 𝑎=arem(𝑥,𝑣), (12) 𝑐=arem(𝑥,𝑢). (13) Vamos primeramente a probar que este conjunto de condiciones, al satisfacerse, nos garantizarán que 𝑎=𝛼𝘣(𝑐) . Posteriormente, será demostrado también el recíproco. Ya se comprobó en una sección anterior que para 𝑏≥2 la ecuación 𝑥𝟤−𝑏𝑥𝑦+𝑦𝟤=1 caracteriza la secuencia 𝛼𝘣 en el sentido de que, caso de cumplirse tal ecuación, entonces deben verificarse 𝑥=𝛼𝘣(𝑚+1) e 𝑦=𝛼𝘣(𝑚) 51 o viceversa para algún 𝑚 , determinando el orden relativo de 𝑥 e 𝑦 cual de los dos igualdades se cumple. Así pues, las 4 primeras ecuaciones del sistema nos indican que para unos ciertos 𝑘y𝑚(𝑚positivo) se cumple que 𝑢=𝛼𝘣(𝑘), 𝑠=𝛼𝘣(𝑚), 𝑟=𝛼𝘣(𝑚−1). La quinta ecuación establece, entonces, que 𝛼𝟤 𝘣(𝑘)∣𝛼𝘣(𝑚) , de donde se deduce que 𝑢=𝛼𝘣(𝑘)∣𝑚. Dichas identificaciones también nos permiten, usando la definición de la secuencia 𝛼𝘣con la sexta ecuación, afirmar que 𝑣=𝑏𝑠−2𝑟=𝑏𝛼𝘣(𝑚)−2𝛼𝘣(𝑚−1) =(𝛼𝘣(𝑚+1)+𝛼𝘣(𝑚−1))−2𝛼𝘣(𝑚−1) =𝛼𝘣(𝑚+1)−𝛼𝘣(𝑚−1). Por otra parte, usando el mismo razonamiento anterior podemos también seguir de las ecuaciones novena y décima que para algún 𝑛 se tiene que 𝑥=𝛼𝘸(𝑛). Las ecuaciones séptima y octava representan las condiciones 𝑤≡𝑏 (mód 𝑣) y 𝑤≡2 (mód 𝑢) que impusimos al comienzo del razonamiento explicado en la sección 3.3, de modo que podemos garantizar que 𝑥≡𝛼𝘣(𝑛) (mód 𝑣), 𝑥≡𝑛 (mód 𝑢). Ahora, sea 𝑛=2𝑙𝑚±𝑗 donde 𝑗≤𝑚 . Notemos en primer lugar cómo se tiene la relación 𝐴𝘣(𝑚)=(𝛼𝘣(𝑚+1) −𝛼𝘣(𝑚) 𝛼𝘣(𝑚) −𝛼𝘣(𝑚−1)) ≡−(−𝛼𝘣(𝑚−1) 𝛼𝘣(𝑚) −𝛼𝘣(𝑚) 𝛼𝘣(𝑚+1))(mód 𝑣) =−[𝐴𝘣(𝑚)]−𝟣 gracias a que la elección especial de 𝑣=𝛼𝘣(𝑚+1)−𝛼𝘣(𝑚−1) nos permite establecer que 𝛼𝘣(𝑚+1)≡𝛼𝘣(𝑚−1) (mód 𝑣). Así pues, tenemos que [𝐴𝘣(𝑚)]𝟤=𝐴𝘣(𝑚)𝐴𝘣(𝑚)≡−𝐴𝘣(𝑚)[𝐴𝘣(𝑚)]−𝟣 =−𝐼 (mód 𝑣) y podemos seguir que 𝐴𝘣(𝑛)=Ξ𝘯 𝘣=Ξ𝟤𝘭𝘮±𝘫 𝘣=[[Ξ𝘮 𝘣]𝟤]𝘭Ξ±𝘫 𝘣=[[𝐴𝘣(𝑚)]𝟤]𝘭[𝐴𝘣(𝑗)]±𝟣 ≡(−𝐼)𝘭[𝐴𝘣(𝑗)]±𝟣 =±[𝐴𝘣(𝑗)]±𝟣 (mód 𝑣) 52 siendo posible que se dé cualquiera de las cuatro combinaciones de signos. De esta forma, si pasamos la congruencia en formato matricial a verla en particular para cada componente de las matrices, obtenemos gracias a los coeficientes 𝑎𝟤𝟣 o𝑎𝟣𝟤 la relación 𝑥≡𝛼𝘣(𝑛)≡±𝛼𝘣(𝑗) (mód 𝑣) Como además hemos construido el valor de 𝑛 de modo que se cumpla que 𝑗≤𝑚, entonces podemos seguir rápidamente que 2𝛼𝘣(𝑗)≤2𝛼𝘣(𝑚) ≤(𝑏−2)𝛼𝘣(𝑚) =𝑏𝛼𝘣(𝑚)−2𝛼𝘣(𝑚) <𝑏𝛼𝘣(𝑚)−2𝛼𝘣(𝑚−1) =𝑣 de modo que entonces, usando la duodécima ecuación del sistema, tendremos la igualdad 𝑎=arem(𝑥,𝑣)=arem(𝛼𝘣(𝑛),𝑣)=𝛼𝘣(𝑗) Sabemos también que 𝑛≤𝛼𝘣(𝑛) , luego usando la anterior igualdad junto con la undécima ecuación del sistema podremos afirmar que 2𝑗≤2𝛼𝘣(𝑗)= 2𝑎<𝑢 . Asimismo, como tenemos la condición 𝑢∣𝑚 y sabemos que 𝑛=2𝑙𝑚±𝑗 entonces está claro que 𝑛≡±𝑗 (mód 𝑢) . Junto con estas dos propiedades, usamos también la relación 𝑥≡𝑛 (mód 𝑢) que sabemos de antes y la decimotercera ecuación del sistema, de modo que tendremos que 𝑐=arem(𝑥,𝑢)=arem(𝑛,𝑢)=𝑗. Esto, junto con la igualdad 𝑎=𝛼𝘣(𝑗) que dedujimos antes, nos permite finalmente concluir que 𝑎=𝛼𝘣(𝑐), como queríamos probar. Pasemos ahora al recíproco, es decir, buscamos demostrar que si unos ciertos números 𝑎 , 𝑏 y 𝑐 cumplen que 𝑏≥4 y 𝑎=𝛼𝘣(𝑐) entonces también existen ciertos números 𝑠 , 𝑟 , 𝑢 , 𝑡 , 𝑣 y 𝑤 satisfaciendo las ecuaciones 2 a 13 del sistema presentado anteriormente. Así pues, el proceso a continuación describe la forma en la que dicho valores deben ser escogidos. Para comenzar, tomamos 𝑢 de acuerdo con la igualdad 𝑢=𝛼𝘣(𝑘) , escogiendo 𝑎 y 𝑘 de forma adecuada para que se cumpla la desigualdad 2𝑎<𝑢 (ecuación (11) del sistema) y sea 𝑢 impar. Podemos hacer esto gracias a que sabemos que la sucesión 𝛼𝘣(0),𝛼𝘣(1),… es monótona creciente y gracias a que, como no pueden aparecer dos términos pares sucesivos, si tomamos 53 dos términos consecutivos de la serie entonces al menos uno de ellos es impar. Una vez tenemos tal 𝑢, elegimos 𝑡=𝛼𝘣(𝑘+1)de modo que 1=𝛼𝟤 𝘣(𝑘+1)−𝑏𝛼𝘣(𝑘+1)𝛼𝘣(𝑘)+𝛼𝟤 𝘣(𝑘)=𝑡𝟤−𝑏𝑡𝑢+𝑢𝟤 y por tanto se tiene la ecuación (2) del sistema. A continuación, escogemos 𝑟=𝛼𝘣(𝑚−1) y 𝑠=𝛼𝘣(𝑚) donde 𝑚=𝑢𝑘 . Usando de nuevo la identidad del párrafo anterior vemos que 𝑠𝟤−𝑏𝑠𝑟+𝑟𝟤=1 , y como claramente 𝑚−1<𝑚 entonces 𝑟<𝑠 por monotonía, con lo que se tienen las ecuaciones (3) y (4) del sistema. Por otro lado, dedujimos en el apartado 3.4.1 que para 𝑚=𝑘𝑙 se cumple que 𝛼𝘣(𝑚)≡(−1)𝘭−𝟣𝑙𝛼𝘣(𝑘)𝛼𝘭−𝟣 𝘣(𝑘−1) (mód 𝛼𝟤 𝘣(𝑘)) , gracias a una congruencia que podemos establecer entre las expresiones matriciales de la secuencia 𝛼𝘣 . Así pues, como ahora estamos tomando que 𝑚=𝑢𝑘 donde 𝑢=𝛼𝘣(𝑘) , entonces en la anterior expresión sustituimos 𝑙por 𝑢y nos queda que 𝑠=𝛼𝘣(𝑢𝑘)=𝛼𝘣(𝑚) ≡(−1)𝘶−𝟣𝑢𝛼𝘣(𝑘)𝛼𝘶−𝟣 𝘣(𝑘−1) (mód 𝛼𝟤 𝘣(𝑘)) =(−1)𝘶−𝟣𝑢𝟤𝛼𝘶−𝟣 𝘣(𝑘−1) (mód 𝑢𝟤) ≡0 (mód 𝑢𝟤) debido al factor 𝑢𝟤 de la expresión. Así pues, esto nos indica que 𝑢𝟤∣𝑠 , con lo que se sostiene la ecuación (5). También, puesto que se tiene que 𝑏𝑠−2𝑟=𝑏𝛼𝘣(𝑚)−2𝛼𝘣(𝑚−1) ≥4𝛼𝘣(𝑚)−2𝛼𝘣(𝑚−1) >4𝛼𝘣(𝑚)−2𝛼𝘣(𝑚) =2𝛼𝘣(𝑚), podemos escoger de forma adecuada un cierto 𝑣=𝑏𝑠−2𝑟 satisfaciendo la ecuación (6) y la condición 𝑣>𝛼𝘣(𝑚) requerida por el proceso de demostración. Veamos ahora que 𝑢 y 𝑣 son coprimos. Para ello, supongamos que ∃𝑑∈ℤ∶ 𝑑∣𝑢,𝑣 . Como hemos construido estas variables de forma que 𝑢𝟤∣𝑠 , entonces la condición nos permite afirmar que 𝑑∣𝑠 . A su vez, si 𝑑∣𝑠 y 𝑑∣𝑣=𝑏𝑠−2𝑟 entonces 𝑑∣2𝑟 . Sin embargo, por la elección realizada para 𝑢 , este número es impar, y por tanto al tenerse que 𝑑∣𝑢 entonces 𝑑 no puede tener factores pares en su descomposición, de modo que si 𝑑∣2𝑟 entonces debe ser que 𝑑∣𝑟 . Tenemos por tanto que 𝑑∣𝑟,𝑠⇒𝑑∣𝑠𝟤−𝑏𝑠𝑟+𝑟𝟤=1⇒𝑑∣1⇒𝑑=1 . 54 del par (𝑎,𝑏) , solo tenemos que sumar de nuevo el valor de a, lo cual nos resulta en la fórmula Cantor(𝑎,𝑏)=𝘢+𝘣 ∑ 𝘬=𝟣 𝑘+𝑎 =(𝑎+𝑏)(𝑎+𝑏+1) 2+𝑎 =𝑎𝟤+𝑎𝑏+𝑎+𝑎𝑏+𝑏𝟤+𝑏 2+𝑎 =(𝑎𝟤+2𝑎𝑏+𝑏𝟤)+𝑎+𝑏+2𝑎 2=(𝑎+𝑏)𝟤+3𝑎+𝑏 2. De esta forma, podemos directamente deducir dos representaciones diofánticas de funciones que devuelvan el valor del primer o segundo término que conforman el par numerado en la lista en la posición que sea indicada por el argumento: 𝑎=Elema(𝑐)⟺∃𝑦∶(𝑎+𝑦)𝟤+3𝑎+𝑦=2𝑐, 𝑏=Elemb(𝑐)⟺∃𝑥∶(𝑥+𝑏)𝟤+3𝑥+𝑏=2𝑐. Una vez hemos establecido un método adecuado para trabajar con la numeración de pares, es posible extender inductivamente tales procedimientos a conjuntos formados por tuplas de longitudes arbitrarias, definiendo por ejemplo el proceso de numeración como sigue Cantor𝟣(𝑎𝟣)=𝑎𝟣, Cantor𝘯+𝟣(𝑎𝟣,…,𝑎𝘯+𝟣)=Cantor𝘯(𝑎𝟣,…,𝑎𝘯−𝟣,Cantor(𝑎𝘯,𝑎𝘯+𝟣)), denominando la función Cantor 𝘯(𝑎𝟣,…,𝑎𝘯) como el número de Cantor de la tupla (𝑎𝟣,…,𝑎𝘯) . Asimismo, análogamente a como representamos las funciones Elema yElemb también podemos generalizar su propósito en 𝑛 - tuplas a través de la función diofántica Elem𝘯,𝘮(𝑐) , que devuelve el 𝑚 -ésimo elemento de la 𝑛-tupla con número de Cantor 𝑐: 𝑎=Elem𝘯,𝘮 ⟺ ∃𝑥𝟣,…,𝑥𝘮−𝟣,𝑥𝘮+𝟣,…,𝑥𝘯∶2𝟤𝘯Cantor𝘯(𝑥𝟣,…,𝑥𝘮−𝟣,𝑎,𝑥𝘮+𝟣,…,𝑥𝘯)=2𝟤𝘯𝑐, donde los factores 2𝟤𝘯 se han añadido para garantizar la integridad de los coeficientes de la función Cantor𝘯. 61 4.2 Codificación de Gödel La codificación de Cantor tiene sin embargo un defecto crucial: no conocemos ninguna forma de probar que Elem 𝘯,𝘮(𝑐) es una función diofántica en los argumentos 𝑛 , 𝑚 y 𝑐 . Por tanto necesitamos otros métodos para trabajar con tuplas de longitudes no fijadas a priori. Uno de estos métodos está basado precisamente en el teorema chino del resto 3.3 que introdujimos en el anterior capítulo. Consideremos una 𝑛 -tupla arbitraria, ( 𝑎𝟣,…,𝑎𝘯 ), y sean 𝑏𝟣,…,𝑏𝘯 una serie cualquiera de números coprimos dos a dos y tales que 𝑎𝘪< 𝑏𝘪 , para (𝑖 = 1,…,𝑛) . Así pues, el teorema chino del resto nos garantiza que podemos encontrar un cierto 𝑎 tal que 𝑎𝘪=rem(𝑎,𝑏𝘪)(𝑖=1,…,𝑛) . De esta forma, todos los elementos de la tupla anterior quedan determinados inequívocamente por los números 𝑎,𝑏𝟣,…,𝑏𝘯. A simple vista, no es tan obvio ver cuál ha sido la ganancia obtenida en este proceso, ya que hemos pasado de usar los 𝑛 elementos de la tupla original a los 𝑛+1 anteriores. El beneficio, no obstante, se encuentra en la libertad que se ha conseguido a la hora de tratar con los 𝑏𝘪 , lo cual nos va a permitir determinarlos usando tan solo unos pocos números. Por ejemplo, consideramos las ecuaciones 𝑏𝘪=𝑏𝑖+1 (𝑖=1,…,𝑛) donde 𝑏 es un múltiplo de 𝑛! lo suficientemente grande como para sostener las desigualdades de la hipótesis del teorema chino del resto. Veamos que 𝑏𝘪y𝑏𝘫son coprimos para 𝑖<𝑗. Supongamos para ello que existe un cierto primo 𝑝tal que 𝑝∣𝑏𝑖+1=𝑏𝘪y𝑝∣𝑏𝑗+1=𝑏𝘫 Está claro entonces que gcd(𝑝,𝑏)=1 luego gcd(𝑝,𝑛!)=1 Sin embargo, sabemos que también 𝑝∣(𝑏𝑗+1)−(𝑏𝑖+1)=𝑏(𝑗−𝑖), de modo que necesariamente 𝑝∣𝑗−1. 62 Comolo último implica que 𝑝≤𝑗−𝑖<𝑛 ytambién teníamos que gcd(𝑝,𝑛!)= 1, se sigue que 𝑝=1, es decir, 𝑏𝘪y𝑏𝘫son coprimos. De esta forma, el par ( 𝑎,𝑏 ) contiene información completa sobre cada uno de los elemento de la 𝑛 -tupla inicial. Añadiendo también un tercer elemento que nos indique la longitud de dicha tupla, obtenemos un triple ⟨𝑎,𝑏,𝑐⟩ que llamaremos código de Gödel de la tupla (𝑎𝟣,…,𝑎𝘯)siempre que 𝑐=𝑛 𝑎𝘪=GElem(𝑎,𝑏,𝑖) (𝑖=1,…𝑛) para GElem la función diofántica tal que 𝑒=GElem(𝑎,𝑏,𝑖)⟺𝑒=rem(𝑎,𝑏𝑖+1) Por convenio, ⟨𝑎,𝑏,0⟩ es el código de la tupla vacía, es decir, la tupla de longitud nula sin elementos. También podríamos usar, en lugar del código de Gödel de la tupla, el número Cantor 𝟥(𝑎,𝑏,𝑐) que codifica la misma tupla, obteniendo así una numeración de tuplas de longitud arbitraria usando números naturales. Destacamos, sin embargo, la diferencia entre la numeración de Cantor y la codificación de Gödel: mientras que el número de Cantor de una tupla es único, puede haber indefinidos códigos de Gödel para una sola tupla. Esto se debe a la arbitrariedad en la elección de 𝑏 (y consecuentemente también de 𝑎). 4.2.1 Comentario histórico En los primeros acercamientos a la prueba del décimo problema de Hilbert, la codificación de Gödel jugó un papel importante gracias a que proporcionaba una forma sencilla para dar una representación diofántica de la función GElem, además de tener, en comparación a otros sistema de codificación, propiedades adecuadas para relacionar 𝑛 -tuplas con las respectivas 𝑚 -tuplas resultantes al aplicar a cada una de ellas un cierto polinomio de 𝑛 argumentos. Precisamente el teorema chino del resto es el que permite esta propiedad en particular, lo cual habilitó que Putnam, Davis y Robinson realizasen destacables avances en dirección a la irresolubilidad del problema. Sin embargo, si bien la codificación de Gödel permite una fácil representación para GElem, tiene el efecto contrario con otra serie de funciones, como la concatenación de tuplas, cuya representación se dificulta al usar estos códigos. En versiones más actualizadas de la prueba, se pone en uso la codificación posicional (que se estudiará a continuación en la sección 4.3) que redistribuye esta dificultad de forma más adecuada, como veremos. 63 4.3 Codificación posicional Como acabamos de mencionar, la codificación de Gödel acarrea unos problemas prácticos en relación a las representaciones diofánticas de unas cierta funciones que probarán ser de utilidad más adelante. Así pues, en esta sección nos encargaremos de introducir un sistema de códigos más adecuado para el trato del décimo problema. Dicho código consiste de nuevo en 3 números 𝑎 , 𝑏 y 𝑐 , siendo que 𝑐 volverá a representar la longitud de la tupla que vamos a codificar, ( 𝑎𝟣,…,𝑎𝘯 ). Así pues, 𝑐=𝑛 , mientras que 𝑏 se elegirá arbitrariamente requiriéndose ahora que cumpla la desigualdad 𝑏>𝑎𝘪(𝑖=1,…,𝑛) y𝑎quedará definido por la ecuación 𝑎=𝑎𝘯𝑏𝘯−𝟣 +𝑎𝘯−𝟣𝑏𝘯−𝟤 +⋯+𝑎𝟣𝑏𝟢. De esta forma, podemos interpretar los 𝑎𝟣,…,𝑎𝘯 tan solo como los dígitos de la representación 𝑏 -aria de 𝑎 , de modo que la 𝑛 -tupla ( 𝑎𝟣,…,𝑎𝘯 ) está determinada de forma única por los números 𝑎 , 𝑏 y 𝑐 . Así pues, si las respectivas condiciones sobre cada dígito se cumplen, entonces llamaremos al triple ⟨𝑎,𝑏,𝑐⟩ el código posicional de la tupla ( 𝑎𝟣,…,𝑎𝘯 ). Claramente, ⟨0,𝑏,0⟩ será el código de la tupla vacía. Al igual que pasaba con los códigos de Gödel, también hay infinitos códigos posicionales para cada tupla gracias a la arbitrariedad de elección de 𝑏 (consecuentemente de 𝑎 ); pero contrario a lo que sucedía entonces, hay que tener precaución especial porque no necesariamente cada triple de la forma descrita es código posicional de una tupla. No obstante, esta no es una desventaja tan grande puesto que fácilmente puede solucionarse notando que la propiedad ser un código posicional es diofántica: Code(𝑎,𝑏,𝑐)⟺𝑏≥2∧𝑎<𝑏𝘤. Una vez tenemos todos los elementos destacados, es fácil obtener la tupla a partir de su código posicional. 64 Ejemplo 4.1 Vamos a considerar el código posicional ⟨1091,7,4⟩ . Queremos encontrar la 4-tupla que codifica. Así pues, en primer lugar vamos a remarcar las potencias de 7: 7𝟦=2401, 7𝟥=343, 7𝟤=49. Notamos que efectivamente se tiene Code(1091, 7, 4) porque 7≥2 y 1091<7𝟦. Queremos entonces hallar los coeficientes de la expresión 1091=343𝑎𝟦+49𝑎𝟥+7𝑎𝟤+𝑎𝟣 Así pues, para encontrar el código usamos un razonamiento muy simple: sabemos que 𝑎𝘪𝑏𝘪−𝟣 <𝑏𝘪 , entonces la diferencia del término 𝑎 y el término dominante de la expresión no puede ser mayor que 𝑏𝟥 . Eso nos permite obtener 𝑎𝟦 , y trasponiendo términos repetimos de nuevo el razonamiento para el de grado inmediatamente inferior. Así, sucesivamente, obtenemos cada coeficiente. En el caso que nos ocupa, vemos que 3·343=1029<1091 pero 4·343= 1372>1091 . Por tanto 𝑎𝟦=3 , de modo que sustituyendo y trasponiendo términos ahora nos queda que 62=49𝑎𝟥+7𝑎𝟤+𝑎𝟣⟹𝑎𝟥=1 13=7𝑎𝟤+𝑎𝟣⟹𝑎𝟤=1 𝑎𝟣=6 Por tanto, el código posicional ⟨1091,7,4⟩codifica la 4-tupla (6, 1, 1, 3). En adelante, código se referirá exclusivamente al código posicional de una tupla, puesto que este es el formato con el más frecuentemente se tratará, y de querer referirnos a otro sistema diferente será explicitado en el texto. En cuestión de notación, si tenemos el código ⟨𝑎,𝑏,𝑐⟩ entonces denominaremos a 𝑎la cifra, a 𝑏la base y a 𝑐la longitud del código. Vamos ahora a describir una representación diofántica de la función Elem( 𝑎,𝑏,𝑑 ) que devuelve el 𝑑 -ésimo elemento de una cierta tupla codificada por ⟨𝑎,𝑏,𝑐⟩, de modo que 𝑒=Elem(𝑎,𝑏,𝑑) ⟺∃𝑥,𝑦,𝑧∈ℤ∶[𝑑=𝑧+1∧𝑎=𝑥𝑏𝘥+𝑒𝑏𝘻+𝑦∧𝑒<𝑏∧𝑦<𝑏𝘻]. Nótese que la función Elem es la equivalente para códigos posicionales a la función GElem que fue definida en la sección anterior. Ya fue mencionado 65 entonces que el motivo por el que las versiones más modernas de la prueba del décimo problema hacen uso de la codificación posicional es que, a pesar de que la representación diofántica de Elem es ligeramente más compleja que la representación de GElem, la codificación de Gödel no es apropiada para demostrar que otra serie de funciones son diofánticas. Una de estas funciones es la relación Concat, que recibe como argumentos tres triples de números y decide si el primer triple es código de la concatenación de las tuplas con códigos el segundo y tercer triple, en ese orden y siempre que las bases de los códigos sean la misma. En otras palabras, la relación Concat (𝑎,𝑏,𝑐,𝑎𝟣,𝑏,𝑐𝟣,𝑎𝟤,𝑏,𝑐𝟤) devuelve una respuesta positiva si ⟨𝑎,𝑏,𝑐⟩ es el código de la concatenación ordenada de las tuplas con códigos ⟨𝑎𝟣,𝑏,𝑐𝟣⟩ y ⟨𝑎𝟤,𝑏,𝑐𝟤⟩ . Demostrar que esta función es diofántica es complicado usando códigos de Gödel, pero con la codificación posicional es sencillo ver que puede representarse diofánticamente como Concat(𝑎,𝑏,𝑐,𝑎𝟣,𝑏,𝑐𝟣,𝑎𝟤,𝑏,𝑐𝟤) ⟺Code(𝑎𝟣,𝑏,𝑐𝟣)∧Code(𝑎𝟤,𝑏,𝑐𝟤)∧[𝑎=𝑎𝟤𝑏𝘤𝟣+𝑎𝟣]∧[𝑐=𝑐𝟣+𝑐𝟤]. Las condiciones primera, segunda y cuarta son formalismos obvios, mientras que la tercera se deduce directamente de la definición que hemos dado para la cifra. De esta forma, para una base prefijada, sabemos que la concatenación es una función diofántica. Formalmente, sería más correcto decir que existen un par de funciones diofánticas (las que aparecen en la representación de Concat) que devuelven la cifra y longitud, respectivamente, de la concatenación de dos tuplas. La notación que será usada, sin embargo, para estas funciones, será simplemente ⟨𝑎𝟣,𝑏,𝑐𝟣⟩+⟨𝑎𝟤,𝑏,𝑐𝟤⟩ para el triple que, en base 𝑏 , codifica la concatenación de las tuplas con códigos ⟨𝑎𝟣,𝑏,𝑐𝟣⟩ y ⟨𝑎𝟤,𝑏,𝑐𝟤⟩ , lo cual es mucho más natural a coste de un ligero abuso de notación. Al final de la sección 4.5, se estudiará cómo proceder cuando las bases de las tuplas concatenadas no sean homogéneas. 4.4 Coeficientes binomiales, números primos y función factorial En esta sección, demostraremos que los tres elementos presentados en el título son, de hecho, diofánticos, lo cual es inesperadamente fácil de probar usando la codificación posicional. Por ejemplo, para los coeficientes binomiales, basta notar que, por la fórmula del binomio de Newton, sabemos 66 que (𝑏+1)𝘯=𝘯 ∑ 𝘬=𝟢 (𝑛 𝑘)𝑏𝘯−𝘬1𝘬=𝘯 ∑ 𝘬=𝟢 (𝑛 𝑘)𝑏𝘯−𝘬 =(𝑛 0)𝑏𝟢+(𝑛 1)𝑏𝟣+⋯+(𝑛 𝑛)𝑏𝘯, entonces el triple ⟨(𝑏+1)𝘯,𝑏,𝑛+1⟩codifica la tupla ((𝑛 0),(𝑛 1),…,(𝑛 𝑛)) (suponiendo que 𝑏 es lo suficientemente grande). De esta forma, podemos dar una representación diofántica generalizada de los coeficientes binomiales apoyándonos en las explicadas en la sección anterior, siendo que simplemente estableciendo que 𝑐=(𝑛 𝑚)⟺𝑐=Elem((2𝘯+2)𝘯,2𝘯+1,𝑚+1), al ser 𝑏=2𝘯+1adecuadamente grande, deducimos que (𝘯 𝘮)es diofántico. Seguidamente, a partir de saber que los coeficientes binomiales son diofánticos podemos usar su expresión en términos de factoriales para probar que el factorial es también diofántico. Así pues, sabemos que (𝑛 𝑚)=𝑛! 𝑚!(𝑛−𝑚)!, de modo que trasponiendo términos podemos expresar el factorial en función de binomiales y exponenciales: 𝑚!= 𝑛! (𝘯 𝘮)(𝑛−𝑚)! =𝑛(𝑛−1)⋯(𝑛−𝑚+1) (𝘯 𝘮) =𝑛𝘮 (𝘯 𝘮)(1−1 𝑛)⋯(1−𝑚−1 𝑛), sacando factor común 𝑛de cada uno de los factores del numerador. Ahora bien, para continuar, como el lado izquierdo de la expresión no depende de 𝑛podemos tomar el límite para asegurar que 𝑚!= lím 𝘯→∞ 𝑚!= lím 𝘯→∞ 𝑛𝘮 (𝘯 𝘮)(1−1 𝑛)⋯(1−𝑚−1 𝑛)= lím 𝘯→∞ 𝑛𝘮 (𝘯 𝘮). 67 La operación de límite no pertenece al lenguaje diofántico que se ha estudiado hasta ahora, pero tal y como ya se hizo en la sección 3.5 del capítulo anterior, podemos sustituir dicha operación usando la función div, de modo que para un cierto 𝑛 adecuadamente grande, la anterior expresión implica que 𝑚!=𝑛𝘮div (𝑛 𝑚). Se puede comprobar que para que dicho 𝑛 sea suficientemente grande basta con tomar 𝑛≥(𝑚+1)𝘮+𝟤, de modo que entonces se puede reescribir 𝑚!=(𝑚+1)𝘮(𝘮+𝟤) div ((𝑚+1)𝘮+𝟤 𝑚) y, al ser la función exponencial y los coeficientes binomiales diofánticos, concluimos que también el factorial es diofántico. Una vez tenemos lo anterior, es muy sencillo comprobar que la propiedad ser un número primo puede representarse como Prime(𝑎)⟺𝑎>1∧gcd(𝑎,(𝑎−1)!)=1, con lo que también esta es una propiedad diofántica. En particular, por la definición que estamos trabajando de ser diofántico, esto implica que existe un polinomio tal que el conjunto de todos los posibles valores que toma cuando se permite a sus variables moverse en el rango de los números naturales es, de hecho, el conjunto de todos los números primos. 4.5 Comparación de tuplas Ya se ha mencionado previamente cómo la unicidad del código de una tupla no se tiene en general, puesto que cada tupla puede tener infinitos códigos debido a la arbitrariedad de elección de la base. Diremos entonces que dos códigos son equivalentes si ambos representan a la misma tupla. El objetivo que motiva esta sección es probar que tal equivalencia, la relación ⟨𝑎𝟣,𝑏𝟣,𝑐𝟣⟩ y ⟨𝑎𝟤,𝑏𝟤,𝑐𝟤⟩ son códigos de la misma tupla, notada como Equal (𝑎𝟣,𝑏𝟣,𝑐𝟣,𝑎𝟤,𝑏𝟤,𝑐𝟤) , es diofántica. Lateralmente, también se mostrará cómo de este hecho se deriva de forma casi directa que las funciones NotGreater(𝑎𝟣,𝑏𝟣,𝑎𝟤,𝑏𝟤)⟺∀𝑘∈ℕ∶Elem(𝑎𝟣,𝑏𝟣,𝑘)≤Elem(𝑎𝟤,𝑏𝟤,𝑘) Small(𝑎,𝑏,𝑐,𝑒)⟺Code(𝑎,𝑏,𝑐)∧∀𝑘∈ℕ∶Elem(𝑎,𝑏,𝑘)≤𝑒 68 son diofánticas, así como se concluirá dando una versión generalizada para tuplas de bases diferentes de la función Concat presentada previamente. Comenzamos introduciendo una función auxiliar que necesitamos en la demostración y cuya definición será dada posteriormente. Dicha función será una relación que notaremos como Eq y que será más fuerte que Equal, en el sentido de que Eq(𝑎𝟣,𝑏𝟣,𝑐𝟣,𝑎𝟤,𝑏𝟤,𝑐𝟤)⟹Equal(𝑎𝟣,𝑏𝟣,𝑐𝟣,𝑎𝟤,𝑏𝟤,𝑐𝟤). Se tendrá la implicación inversa tan solo en caso de que 𝑏𝟤 sea un número primo lo suficientemente grande con respecto a los valores de 𝑏𝟣 y 𝑐𝟣 . En cualquier caso, la implicación anterior es suficiente para permitirnos representar la relación Equal en términos de Eq: Equal(𝑎𝟣,𝑏𝟣,𝑐𝟣,𝑎𝟤,𝑏𝟤,𝑐𝟤) ⟺∃𝑥,𝑦,𝑧∈ℕ∶Eq(𝑎𝟣,𝑏𝟣,𝑐𝟣,𝑥,𝑦,𝑧)∧Eq(𝑎𝟤,𝑏𝟤,𝑐𝟤,𝑥,𝑦,𝑧). Así pues, una vez probemos que cierta Eq cumpliendo las condiciones adecuadas es diofántica, directamente deducimos que la relación Equal también lo es. Vamos pues a comenzar considerando dos relaciones análogas a las que definimos al comienzo con base prima. En primer lugar, tenemos la relación PNotGreater(𝑎𝟣,𝑎𝟤,𝑏)⟺Prime(𝑏)∧NotGreater(𝑎𝟣,𝑏,𝑎𝟤,𝑏). Usar un solo número primo como base para ambos códigos es imprescindible porque nos permite utilizar el teorema de Kummer. Teorema 4.2 (Kummer) Si 𝑝 es un número primo, entonces su exponente en la descomposición en factores primos de la expansión canónica del binomial (𝘮+𝘯 𝘮) equivale al número de acarreos usados al sumar los números 𝑚y𝑛en base 𝑝. Demostración del teorema 4.2 Comenzamos recordando que por definición se tiene la expresión (𝑚+𝑛 𝑚)=(𝑚+𝑛)! 𝑚!·𝑛! . Asimismo, vamos a usar la notación 𝜐𝘱(𝑘) para referirnos al exponente del número 𝑝en la descomposición en factores primos de 𝑘. 69 Es fácil ver entonces que se cumple la igualdad 𝜐𝘱((𝑚+𝑛 𝑚))=𝜐𝘱((𝑚+𝑛)!)−𝜐𝘱(𝑛!)−𝜐𝘱(𝑚!). También, como 𝑘!=1·2·⋯·𝑘 entonces sabemos que 𝑝 o alguno de sus múltiplos aparecen en 𝑘! un total de 𝑘div 𝑝 veces, y lo mismo para 𝑝𝟤,𝑝𝟥,… . Se tiene que 𝑝𝘫∣𝑝𝘪,∀𝑗≤𝑖 , de modo que aunque 𝑘div 𝑝𝘪 cuente una sola vez las veces que 𝑝𝘪 aparece en la descomposición de 𝑘! , los sumandos 𝑘div 𝑝,𝑘div 𝑝𝟤,…,𝑘div 𝑝𝘪−𝟣 contienen las 𝑖−1 apariciones restantes de 𝑝𝘪 para corresponder al exponente 𝑖 , y por tanto podemos establecer que 𝜐𝘱(𝑘!)=𝑘div 𝑝+𝑘div 𝑝𝟤+⋯. Por tanto podemos establecer, en base a las dos ecuaciones anteriores, que 𝜐𝘱((𝑚+𝑛 𝑚))=∑ 𝘬≥𝟣((𝑚+𝑛)div 𝑝𝘬−𝑚div 𝑝𝘬−𝑛div 𝑝𝘬). Ahora bien, vamos a expresar el número 𝑚 en base 𝑝 , de modo que sabemos que 𝑚=𝑚𝘕𝑝𝘕+𝑚𝘕−𝟣𝑝𝘕−𝟣 +⋯+𝑚𝘬𝑝𝘬+𝑚𝘬−𝟣𝑝𝘬−𝟣 +⋯+𝑚𝟢𝑝𝟢 =𝑝𝘬(𝑚𝘕𝑝𝘕−𝘬 +⋯+𝑚𝘬)+𝑚𝘬−𝟣𝑝𝘬−𝟣 +⋯+𝑚𝟢𝑝𝟢 ⟹𝑚div 𝑝𝘬=(𝑚𝘕𝑝𝘕−𝘬 +⋯+𝑚𝘬), y análogamente 𝑛div 𝑝𝘬=(𝑛𝘕𝑝𝘕−𝘬 +⋯+𝑛𝘬) . Al sumar ambas expresiones en base 𝑝 y tomar de la misma forma la función div, nos quedará que (𝑚+𝑛)div 𝑝𝘬=(𝑚𝘕+𝑛𝘕+𝑐𝘕)𝑝𝘕−𝘬 +⋯+(𝑚𝘬+𝑛𝘬+𝑐𝘬) donde 𝑐𝘪 son los acarreos de la suma provinientes del término anterior, de forma que 𝑐𝟢=0y para 𝑖≥1 𝑐𝘪={1si 𝑚𝘪−𝟣 +𝑛𝘪−𝟣 +𝑐𝘪−𝟣 ≥𝑝, 0en otro caso. Entonces, se aprecia que al realizar la resta (𝑚+𝑛)div 𝑝𝘬−𝑚div 𝑝𝘬− 𝑛div 𝑝𝘬 en base 𝑝 obtendremos 0 o 1 en función de 𝑐𝘬 , ya que es el único acarreo que persiste al no participar en la diferencia los coeficientes 70 de la máquina, también impondremos que para cada par de un estado no final y un elemento de 𝐴∪{Λ} haya exactamente una sola instrucción con lado izquierdo de la implicación en correspondencia con tal par. Para realizar una computación, se introduce en la cinta de la máquina de Turing una cantidad finita de elementos de 𝐴 a partir de la celda ⋆ y sin dejar ningún hueco, quedando vacías el resto de celdas a la derecha. La cabeza se sitúa en ⋆ y la máquina aquiere el estado inicial 𝑞𝟣 . La máquina procede entonces a realizar la computación paso a paso de acuerdo a su conjunto de instrucciones hasta alcanzar un estado final, quedando el resultado de la computación determinado por el contenido de la cinta y la posición de la cabeza en ese momento y del estado final alcanzado. Es posible que la máquina nunca alcance un estado final, en cuyo caso no se obtendría ningún resultado de esa computación infinita. Nótese que la interpretación de la entrada proporcionada y de la salida obtenida es externa a la máquina de Turing, ya que esta debe considerarse únicamente como un manipulador de símbolos del alfabeto. 5.1 Composición de máquinas de Turing Posteriormente, vamos a establecer una serie de máquinas concretas que, aunque simples, tienen una gran utilidad para nuestro propósito. Sería posible dar una descripción paso a paso de tales máquinas (como hemos definido en la sección anterior), pero este resulta un proceso más engorroso de lo necesario. En su lugar, vamos a describir dos métodos para componer máquinas simples en otra más compleja que tenga una serie de propiedades adecuadas para nuestro fin. Vamos a considerar máquinas sobre un mismo alfabeto {⋆,0,1,2,3,𝜆} . El símbolo 𝜆 se tomará como un representante para las celdas vacías, es decir, para Λ . Es necesario debido a que, por la construcción del sistema de instrucciones que hemos planteado, no podemos «vaciar» una celda, y esto es sin embargo imprescindible para algunas construcciones. Así pues, tendremos que tan solo celdas vacías o con el símbolo 𝜆 pueden estar a la derecha de otra celda con dicho símbolo, y las instrucciones que tengan en su lado izquierdo 𝑞𝘪𝜆 o 𝑞𝘪Λ tendrán lados derechos idénticos, para cualquier estado 𝑞𝘪 . Por otra parte, habrá tan solo dos estados finales 𝑞𝟤 y 𝑞𝟥 , siendo que alcanzar 𝑞𝟤 se interpretará como una respuesta afirmativa y alcanzar 𝑞𝟥 como una negativa. Así pues, dadas dos máquinas 𝑀𝟣 y 𝑀𝟤 con estas propiedades, podremos componerlas en una nueva máquina de Turing 𝑀de dos formas distintas. 77 5.1.1 Composición if - then Las instrucciones de construcción son las siguientes: Si 𝑣 es el número de estados de 𝑀𝟣 , entonces en cada instrucción de esa máquina sustituimos las apariciones de 𝑞𝟤 por 𝑞𝘷+𝟣 . Recordemos que, como es un estado final, 𝑞𝟤 solo aparece en los lados derechos de las instrucciones. En cada instrucción de la máquina 𝑀𝟤 sustituimos los estados no finales 𝑞𝘪por 𝑞𝘷+𝘪. En particular, 𝑞𝟣se cambia por 𝑞𝘷+𝟣. El conjunto de instrucciones de la nueva máquina 𝑀 consiste en la unión de las instrucciones de la máquinas 𝑀𝟣 y 𝑀𝟤 tras realizar los cambios descritos. Se aprecia entonces que la acción de la máquina 𝑀 consiste en una ejecución de la máquina 𝑀𝟣 seguida de una ejecución de 𝑀𝟤 tal y como originalmente se describen estas dos, siempre que 𝑀𝟣 se detenga en el estado afirmativo 𝑞𝟤 . Si alguna de las dos máquinas se detiene en el estado negativo, entonces 𝑀 alcanza una respuesta negativa. En caso contrario, alcanzará la respuesta positiva. Para referirnos a la máquina 𝑀 creada mediante esta composición, usaremos alguna de las siguientes notaciones (en función del contexto): « 𝑀𝟣;𝑀𝟤 », «𝑀𝟣and 𝑀𝟤»o«if 𝑀𝟣then 𝑀𝟤». 5.1.2 Composición while - do - od Las instrucciones de construcción son las siguientes: En todas las instrucciones de 𝑀𝟣 el estado final 𝑞𝟤 se sustituye por 𝑞𝘷+𝟣 , donde 𝑣 es el número de estados de la máquina. Asimismo, el estado final 𝑞𝟥se cambia por 𝑞𝟤. En todas las instrucciones de la máquina 𝑀𝟤 , los estados no finales 𝑞𝘪 se sustituyen por 𝑞𝘷+𝘪 , mientras que el estado final 𝑞𝟤 se sustituye por el estado inicial 𝑞𝟣. El conjunto de instrucciones de la nueva máquina 𝑀 es la unión de las instrucciones de las otras dos máquinas tras la realización de los cambios descritos. 78 La acción de esta máquina es por tanto un bucle: se ejecuta la máquina 𝑀𝟣 ; si la respuesta es negativa, la máquina 𝑀 concluye con respuesta afirmativa; en caso contrario, se ejecuta 𝑀𝟤 ; si esta segunda máquina da una respuesta negativa, entonces la composición tiene respuesta negativa y si 𝑀𝟤 da respuesta positiva, entonces se vuelve a ejecutar la máquina 𝑀𝟣 y se continua repitiendo el proceso de forma indefinida hasta que concluya por una de las dos posibles vías. Usaremos la notación « while 𝑀𝟣do 𝑀𝟤od » para la máquina 𝑀 resultante de esta composición. 5.2 Máquinas para realizar operaciones básicas Aunque por su propia definición es natural considerar que las máquinas de Turing trabajan con cadenas de símbolos, nosotros estamos interesados más bien en trabajar con tuplas de números naturales. Necesitamos entonces un convenio para representar números naturales en la cinta de una máquina. Vamos a usar para ello la notación unaria, de modo que representaremos el número 𝑚 con una serie de 𝑚+1 celdas consecutivas, la primera de ellas por la izquierda conteniendo el símbolo ‘0’ y las restantes conteniendo el símbolo ‘1’. La celda inmediatamente a la derecha de la (𝑚+1) -ésima no tendrá permitido contener de nuevo el mismo símbolo ‘1’, pudiendo diferenciar así dónde termina la representación del número. La representación de una tupla (𝑎𝟣,…,𝑎𝘯) consistirá por tanto de las representaciones de los números 𝑎𝟣,…,𝑎𝘯 colocados uno tras el anterior sin espacios, diferenciándose uno del otro gracias a la primera celda que hemos dicho que queda ocupada por el símbolo ‘0’. La representación de tal tupla comenzará en la segunda celda de la cinta, pues siguiendo el convenio establecido cuando se describió la construcción de máquinas de Turing, la primera celda contendrá siempre el símbolo ⋆ . El resto de celdas estarán vacías o bien tendrán el símbolo ‘ 𝜆 ’, acorde al significado que explicamos que tiene dicho símbolo. Una representación de una tupla sin celdas ocupadas por 𝜆se denominará representación canónica de la tupla. A continuación vamos a mostrar cómo se pueden construir máquinas de Turing que realicen una serie de operaciones básicas sobre tuplas de números naturales que nos serán de utilidad posteriormente. 5.2.1 Máquinas básicas simples La máquina left se traslada una celda hacia la izquierda a menos que la cabeza ya se encuentre sobre la celda con símbolo ⋆ , en cuyo caso la máquina 79 termina sin hacer ningún cambio. Análogamente, tenemos la máquina right que desplaza la cabeza una unidad hacia la derecha a menos que esta esté escaneando una celda vacía. Respectivamente, el conjunto de instrucciones que describen estas máquinas son: 𝑞𝟣⋆⟹⋆S𝑞𝟤, 𝑞𝟣⋆⟹⋆R𝑞𝟤, 𝑞𝟣0⟹0L𝑞𝟤, 𝑞𝟣0⟹0R𝑞𝟤, 𝑞𝟣1⟹1L𝑞𝟤, 𝑞𝟣1⟹1R𝑞𝟤, 𝑞𝟣2⟹2L𝑞𝟤, 𝑞𝟣2⟹2R𝑞𝟤, 𝑞𝟣3⟹3L𝑞𝟤, 𝑞𝟣3⟹3R𝑞𝟤, 𝑞𝟣𝜆⟹𝜆L𝑞𝟤, 𝑞𝟣𝜆⟹𝜆S𝑞𝟤, 𝑞𝟣Λ⟹𝜆L𝑞𝟤. 𝑞𝟣Λ⟹𝜆S𝑞𝟤. A continuación, tenemos la máquina write(0) con las instrucciones 𝑞𝟣⋆⟹⋆S𝑞𝟤, 𝑞𝟣0⟹0S𝑞𝟤, 𝑞𝟣1⟹0S𝑞𝟤, 𝑞𝟣2⟹0S𝑞𝟤, 𝑞𝟣3⟹0S𝑞𝟤, 𝑞𝟣𝜆⟹0S𝑞𝟤, 𝑞𝟣Λ⟹0S𝑞𝟤, que sobrescribe el símbolo ‘0’ en la celda donde se encuentre la cabeza a menos que en esta se encuentre ⋆ , en cuyo caso la máquina termina sin hacer nada. Análogamente, también podemos obtener las máquinas write(1), write(2), write(3) y write( 𝜆 ), que realizan la misma acción para sus respectivos argumentos, tan solo sustituyendo ‘0’ en las partes derechas de las instrucciones descritas arriba por el correspondiente símbolo en cada caso. La máquina read(0) determina la naturaleza de la celda en que se encuentra la cabeza, de modo que tras realizar la acción se detiene devolviendo una respuesta afirmativa si el símbolo ‘0’ es el que ocupa dicha celda; o devolviendo una respuesta negativa en caso contrario. Las instrucciones 80 que determinan la máquina son 𝑞𝟣⋆⟹⋆S𝑞𝟥, 𝑞𝟣0⟹0S𝑞𝟤, 𝑞𝟣1⟹1S𝑞𝟥, 𝑞𝟣2⟹2S𝑞𝟥, 𝑞𝟣3⟹3S𝑞𝟥, 𝑞𝟣𝜆⟹𝜆S𝑞𝟥, 𝑞𝟣Λ⟹𝜆S𝑞𝟥. Similarmente, también obtenemos las máquinas read(1), read(2), read(3) y read( ⋆ ) de forma natural cambiando, en el conjunto de instrucciones anterior, los estados de los lados derechos para que la instrucción que devuelva la respuesta afirmativa vaya acorde con el argumento de la máquina en cada caso. El caso read( 𝜆 ) es ligeramente diferente, pues para esta máquina también se devolverá una respuesta afirmativa si la cabeza se encuentra en una celda vacía (ya que, como establecimos antes, el símbolo ‘ 𝜆 ’ actúa como representante de las celdas vacías): 𝑞𝟣⋆⟹⋆S𝑞𝟥, 𝑞𝟣0⟹0S𝑞𝟥, 𝑞𝟣1⟹1S𝑞𝟥, 𝑞𝟣2⟹2S𝑞𝟥, 𝑞𝟣3⟹3S𝑞𝟥, 𝑞𝟣𝜆⟹𝜆S𝑞𝟤, 𝑞𝟣Λ⟹𝜆S𝑞𝟤. Por último, también será de utilidad considerar las máquinas stop, que provoca que la máquina termine devolviendo una respuesta negativa sin cambiar la posición de la cabeza al pasar directamente del estado 𝑞𝟣 a 𝑞𝟥 ; y, contrariamente, la máquina neverstop que no cambia el estado de la máquina del inicial y por tanto no termina nunca, entrando en un bucle 81 infinito. Sus instrucciones son, respectivamente: 𝑞𝟣⋆⟹⋆S𝑞𝟥, 𝑞𝟣⋆⟹⋆S𝑞𝟣, 𝑞𝟣0⟹0S𝑞𝟥, 𝑞𝟣0⟹0S𝑞𝟣, 𝑞𝟣1⟹1S𝑞𝟥, 𝑞𝟣1⟹1S𝑞𝟣, 𝑞𝟣2⟹2S𝑞𝟥, 𝑞𝟣2⟹2S𝑞𝟣, 𝑞𝟣3⟹3S𝑞𝟥, 𝑞𝟣3⟹3S𝑞𝟣, 𝑞𝟣𝜆⟹𝜆S𝑞𝟥, 𝑞𝟣𝜆⟹𝜆S𝑞𝟣, 𝑞𝟣Λ⟹𝜆S𝑞𝟥. 𝑞𝟣Λ⟹𝜆S𝑞𝟣. 5.2.2 Máquinas básicas compuestas A continuación, vamos a describir algunas nuevas máquinas, esta vez no explícitamente. Usaremos pues las máquinas que acabamos de presentar junto con los métodos de composición expuestos en la anterior sección. Comenzamos con la máquina readnot(0) = while read(0) do stop od la cual tiene una acción contraria a la máquina read(0) que fue descrita antes, es decir, identifica la ausencia del símbolo ‘0’ en la celda en que está posicionada la cabeza. Análogamente se definen las máquinas readnot(1), readnot(2), readnot(3), readnot( 𝜆 ) y readnot( ⋆ ) tan solo cambiando en la fórmula de la composición la primera máquina (read(0)) como corresponda. La máquina star = while readnot(⋆)do left od lleva la cabeza a la primera celda por la izquierda, es decir, a la única en la cinta marcada con el símbolo ‘⋆’. La máquina vacant = star; while readnot(𝜆)do right od primero lleva la cabeza a la primera celda por la izquierda de la cinta y después se mueve hacia la derecha hasta encontrarse una celda que contenga al símbolo ‘ 𝜆 ’ o bien sea una celda vacía. Por tanto la máquina mueve la cabeza a la celda vacía (o representante) que se encuentra más a la izquierda de la cinta. La máquina jump = while readnot(0) do right od 82 mueve la cabeza hacia la derecha hasta encontrar la primera celda que contenga el símbolo ‘0’, de modo que si no hay ninguna de este tipo a la derecha de la cabeza entonces la máquina continua indefinidamente, es decir, nunca para. La secuencia de máquinas find están definidas a través de la relación de recurrencia find(1) = star; jump find(𝑘+ 1) = find(𝑘); right; jump El caso que comienza la recurrencia lleva la cabeza a la casilla ⋆ y a partir de ahí a la primera celda a su derecha marcada con el símbolo ‘0’. El proceso recursivo realiza la acción de la máquina 𝑘 veces, se desplaza una unidad a la derecha (ya que la aplicación de find siempre termina en un ‘0’, en caso de que termine) y vuelve a buscar las primera celda a la derecha con el símbolo ‘0’. Por tanto, lo que hace find( 𝑘 ) es llevar la cabeza hasta la 𝑘 -ésima celda con el símbolo ‘0’ de la cinta. Si estamos tratando con una cinta que representa una tupla, entonces esto se traduce como llevar la cabeza a la celda que comienza la representación del elemento 𝑎𝘬de dicha tupla. La máquina last = vacant; while readnot(0) do left od primero lleva la cabeza hasta la primera celda vacía (o representante) de la cinta y después se mueve a la izquierda hasta localizar una celda con el símbolo ‘0’, es decir, last lleva la cabeza hasta el primer ‘0’ por la derecha de la cinta. Al tratar con 𝑛 -tuplas, esto significa que la máquina desplaza la cabeza hasta el ‘0’ que comienza la representación del elemento 𝑎𝘯 de la tupla. Nótese que la máquina last actúa de la misma forma que lo haría find( 𝑛 ). En particular, si se dan las condiciones adecuadas, esta máquina realizará la acción de una en particular de entre las máquinas que conforman la secuencia infinita de find(𝑘). La máquina new = vacant; write(0) se mueve hasta la primera celda vacía e imprime el símbolo ‘0’ en ella. En el convenio de la representación de tuplas, como a la derecha de la representación del 𝑛 -ésimo elemento tan solo quedan celdas vacías, entonces tenemos que la máquina new en realidad transforma la tupla ( 𝑎𝟣,…,𝑎𝘯 ) en (𝑎𝟣,…,𝑎𝘯,0). La máquina inc = vacant; write(1) 83 se mueve hasta la primera celda vacía e imprime el símbolo ‘1’ en ella, luego por el mismo razonamiento que acabamos de hacer, vemos que inc transforma la tupla ( 𝑎𝟣,…,𝑎𝘯 ) en ( 𝑎𝟣,…,𝑎𝘯+1 ). Complementariamente, la máquina dec = vacant; left; if read(1) then write(𝜆) hace la operación contraria: se mueve hasta la primera celda vacía de la cinta, retrocede un movimiento hacia la izquierda y, en caso de leer el símbolo ‘1’, lo elimina dejando una celda vacía. En el contexto de la representación de tuplas, lo que hace dec es convertir la tupla ( 𝑎𝟣,…,𝑎𝘯+1 ) en ( 𝑎𝟣,…,𝑎𝘯 ). En caso de que el 𝑛 -ésimo elemento de la tupla sea 0, entonces la máquina no altera la cinta, pero read(1) y consecuentemente dec se detienen en un estado de respuesta negativa, indicando así que no se ha producido el decremento. La máquina delete =vacant; while readnot(0)do write(𝜆);left od; write(𝜆) mueve primero la cabeza hasta la primera celda vacía y a partir de ahí se va desplazando hacia la izquierda, vaciando todas las celdas por las que va pasando, hasta que encuentra una celda con el símbolo ‘0’. Cuando lo hace, vacía esta última celda y termina. Al representar tuplas, este proceso se traduce en borrar la representación del último número de una tupla, es decir, delete transforma (𝑎𝟣,…,𝑎𝘯) en (𝑎𝟣,…,𝑎𝘯−𝟣). La máquina mark(2) = while right; read(1) do write(2) od mueve a la cabeza hacia la derecha mientras esté leyendo el símbolo ‘1’ y va cambiando tal símbolo en las celdas por las que pasa por ‘2’. A priori, esta máquina no realiza ningún cambio sobre las tuplas, pero al sustituir una determinada cadena de celdas con el símbolo ‘1’ por celdas con el símbolo ‘2’, nos permite marcar la representación de un miembro particular de la tupla. Típicamente, mark(2) se usará en conjunto con la máquina find, de modo que find( 𝑘 ); mark(2) nos permite seleccionar el elemento 𝑎𝘬 de una tupla. Asimismo, la máquina mark(3) = while right; read(1) do write(3) od realizará un proceso similar. 84 La máquina thereis(2)=star; while readnot(2)do if readnot(𝜆)then right od desplaza la cabeza primero hasta el principio de la cinta y después hacia la derecha mientras no encuentre ninguna celda vacía o que contenga al símbolo ‘2’. Por la forma que tienen las máquinas en la composición, apreciamos como esta máquina determina si el símbolo ‘2’ aparece en algún momento en la cinta, parando en ese caso y devolviendo una respuesta afirmativa (pues acaba en el estado 𝑞𝟤 ). En caso de que ninguna celda contenga a tal símbolo, entonces se sigue desplazando hasta que encuentra una celda vacía, momento en el que la máquina para y devuelve una respuesta negativa (la máquina termina en el estado 𝑞𝟥 ). El convenio establecido que garantiza que no pueden aparecer celdas con el símbolo ‘2’ a la derecha de una celda vacía (o representante) es esencial para el correcto funcionamiento de thereis(2). Completando el funcionamiento de la anterior máquina, therewas(2) = if thereis(2) then write(1) no solo determina la presencia de alguna celda con el símbolo ‘2’, sino que en caso de haberla además la sustituye por una celda con el símbolo ‘1’. Por otro lado, las máquinas thereis(3) y therewas(3) actúan de forma análoga a thereis(2) y therewas(2) respectivamente, pero con el símbolo ‘3’ en lugar de ‘2’. Las máquinas therewas(2) y therewas(3) actúan una única vez, de modo que tan solo reescriben el primer ‘2’ o ‘3’ que encuentran, respectivamente, por ‘1’. En contraposición con ellas, la máquina restore =while thereis(2)do therewas(2)od; while thereis(3)do therewas(3)od nos permite restaurar todos los símbolos ‘1’ en las celdas que previamente hayan podido ser alteradas por las máquinas mark(2) o mark(3). La máquina append(𝑘)=find(𝑘); mark(2); while therewas(2)do inc od 85 marca el 𝑘 -ésimo elemento de una tupla y a continuación posiciona la cabeza en el comienzo de la cinta, que se moverá hacia la derecha hasta que encuentre una celda con el símbolo ‘2’, que sustituye por ‘1’, añade una unidad al último elemento de la tupla y reinicia el proceso llevando de nuevo la cabeza a la celda ⋆ . En otras palabras, en lenguaje de tuplas la máquina append( 𝑘 ) convierte (𝑎𝟣,…,𝑎𝘯) en (𝑎𝟣,…,𝑎𝘯+𝑎𝘬). Similarmente a la máquina anterior, tenemos las máquinas copy(𝑘) = new; append(𝑘) y add(𝑘,𝑙) = copy(𝑘); append(𝑙). La primera añade un elemento 0 en la posición 𝑛+1 -ésima de la tupla y después suma el 𝑘 -ésimo termino a este último elemento, de modo que transforma ( 𝑎𝟣,…,𝑎𝘯 ) en ( 𝑎𝟣,…,𝑎𝘯,𝑎𝘬 ); y la segunda realiza la acción de esta primera máquina recién expuesta y después vuelve a añadir el elemento 𝑎𝘬 al último de la tupla, de modo que transforma ( 𝑎𝟣,…,𝑎𝘯 ) en ( 𝑎𝟣,…,𝑎𝘯,𝑎𝘬+𝑎𝘭 ). Para 𝑘≠𝑙, la máquina mult(𝑘,𝑙)=new; find(𝑘); mark(3); while therewas(3)do append(𝑙)od genera un 0 en la 𝑛+1 -ésima posición de la tupla, marca el 𝑘 -ésimo elemento de la misma y entra en un bucle posicionando la cabeza en la celda ⋆ y moviéndose a la derecha hasta encontrar un ‘3’, que sobrescribe como ‘1’, suma 𝑎𝘬 al último elemento de la tupla y reinicia el bucle. De esta forma, vemos que lo que hace la máquina es sumar 𝑎𝘬 veces 𝑎𝘬 a un elemento 𝑛+1 -ésimo generado al comienzo por la propia máquina, de modo que transforma ( 𝑎𝟣,…,𝑎𝘯 ) en ( 𝑎𝟣,…,𝑎𝘯,𝑎𝘬𝑎𝘭 ). La condición 𝑘≠𝑙 es necesaria porque, si nos fijamos en la composición que define mult( 𝑘 , 𝑙 ), la acción de la máquina append( 𝑘 ) pisaría la de la máquina find( 𝑘 ); mark(3), pues la primera también incluiría la composición find( 𝑘 ); mark(2) en su definición. Así pues, para obtener la tupla (𝑎𝟣,…,𝑎𝘯,𝑎𝟤 𝘬) utilizaríamos la máquina mult(𝑘,𝑘)=copy(𝑘); last; mark(3); while therewas(3)do while therewas(3)do append(𝑘)od od que genera el elemento 𝑎𝘬 en la 𝑛+1 -ésima posición de la tupla, marca con el símbolo ‘3’ las celdas de la representación de este último número, sustituye 86 y que el número de estados de la máquina 𝑀 , digamos 𝑣 , que potencialmente conforman la segunda tupla. De esta forma, el par ( 𝑝,𝑡 ) se llamará código de configuración si 𝑝 y 𝑡 son, en la base 𝛽 , las cifras de las 𝑙 -tuplas ( 0,…,0,𝑖,0,…,0 ) y ( 𝑠𝟣,𝑠𝟤,…,𝑠𝘮,…,𝑠𝘭−𝟣,𝑠𝘓 ) respectivamente. No se requerirá que el código de configuración indique la longitud de las tuplas (en nuestro, 𝑙 ) ya que en la primera tupla hay un único elemento no nulo por construcción mientras que en la segunda los elementos nulos serán interpretados como celdas vacías, sin información relevante para nuestra causa. De esta forma, una configuración quedará determinada de forma única por su código de configuración. Usando esta notación, nuestro primer objetivo será diseñar una ecuación diofántica 𝐷(𝑝,𝑡,𝑥𝟣,…,𝑥𝘮)=0 tal que, si ( 𝑝,𝑡 ) es el código de alguna configuración, entonces la ecuación 𝐷 es resoluble en las incógnitas 𝑥𝟣,…,𝑥𝘮 si y solo si la máquina 𝑀 , empezando en la configuración determinada por 𝑝 y 𝑡 , termina en algún momento. Notamos en esta definición que hemos requerido como condición previa que ( 𝑝,𝑡 ) determine una configuración, y no nos preocuparemos de los casos en los que esto no sucede. 6.2.1 Función de progreso de un paso Comenzaremos simulando los pasos individuales de una máquina de Turing, de modo que vamos a considerar nuestra máquina 𝑀 que se encuentra en la configuración determinada por ( 𝑝,𝑡 ) y, tras realizar la instrucción determinada por sus elementos característicos, pasa a la configuración con código (NextP(𝑝,𝑡),NextT(𝑝,𝑡)). Nuestro objetivo entonces será comprobar que estas dos funciones, NextP y NextT, son diofánticas. Vamos a precisar un poco mejor las definiciones de estas dos funciones. Trabajaremos en adelante suponiendo que ( 𝑝,𝑡 ) es el código de una configuración con un estado no final, de modo que para el caso en el que el estado sí termine la computación de la máquina vamos a definir las funciones como NextP(𝑝,𝑡)=0, NextT(𝑝,𝑡)=𝑡, lo cual es congruente con la terminación de la computación (el estado y la posición de la cadena se ‘eliminan’ mientras que cada celda mantiene los 93 mismos símbolos que ya tenían en el anterior paso). También, entenderemos que NextP y NextT sean diofánticas como que existen funciones diofánticas que equivalen a estas dos cuando sus argumentos ( 𝑝 , 𝑡 ) formen un código de configuración pero que tienen un valor arbitrario o incluso están sin definir cuando no suceda esto, ahorrándonos así la molestia de definir las funciones para situaciones que no se van a considerar en nuestra prueba. Está claro que jugarán un papel clave en la construcción que buscamos las funciones 𝐴 , 𝐷 y 𝑄 que usamos en el capítulo anterior para definir el conjunto de instrucciones de una máquina de Turing. Recordemos que si 𝑖 es el subíndice del estado actual de la máquina y 𝑗 el subíndice del símbolo en la celda donde se posiciona la cabeza, entonces 𝐴(𝑖,𝑗)determina el símbolo que va a escribir la máquina, 𝐷(𝑖,𝑗)determina el movimiento que va a realizar la cabeza, 𝑄(𝑖,𝑗)determina el estado al que pasa la máquina. De esta forma, siguiendo el convenio anterior, comenzamos notando que si 𝑞𝘪 es un estado final entonces tendremos que 𝐴(𝑖,𝑗)=𝑗 , 𝐷(𝑖,𝑗)=𝑆 y 𝑄(𝑖,𝑗)=0 . Que la función NextT (que determina el cambio en la tupla de los símbolos) es diofántica es sencillo de ver. Esto se debe a que cada elemento de la tupla con cifra NextT( 𝑝 , 𝑡 ) está únicamente determinado por los elementos en la misma posición de las tuplas con cifras 𝑝 y 𝑡 . Así pues, podemos simplemente definir A(𝑖,𝑗)={𝐴(𝑖,𝑗) si 0<𝑖≤𝑣,0≤𝑗≤𝑤, 𝑗en cualquier otro caso, recordando que 𝑣es el número de estados de la máquina 𝑀y𝑤el número de símbolos de su alfabeto. Consideramos la extensión a tuplas de la función A, construida con el mecanismo explicado en la sección 4.6. Así pues, la base del código posicional fue fijada y sabemos que es 𝛽 , de modo que por lo explicado en dicha sección, tendremos que la función A[ 𝛽 ] es diofántica, y entonces con la representación generalizada 𝑡′=NextT(𝑝,𝑡)⟺∃𝑙∶𝑡′=A[𝛽](𝑝,𝑡,𝑙) tenemos probado que NextT es diofántica. Que la función NextP sea diofántica es algo menos evidente. Observamos que esto es así porque ahora el 𝑘 -ésimo elemento de la tupla con cifra NextP( 𝑝,𝑡 ) está determinado por los elementos en las posiciones 𝑘−1 -ésima, 𝑘 -ésima y 𝑘+1 -ésima de las tuplas con cifras 𝑝 y 𝑡 , en lugar de por tan solo 94 los dos elementos correspondientes de estas tuplas como sucedía para la función anterior. El sistema para extender funciones a tuplas funciona tan solo elemento a elemento, luego no puede ser aplicado directamente en este caso. Para salvar este problema, vamos a definir los siguientes valores: 𝑝𝘙=𝑝𝛽, 𝑝𝘓=𝑝div 𝛽, 𝑡𝘙=𝑡𝛽, 𝑡𝘓=𝑡div 𝛽. El propósito de estos números es claro: por definición, sabemos (por lo que se vio en el cuarto capítulo) que si una 𝑛 -tupla tiene cifra 𝑎 en base 𝛽 , entonces si dicha tupla es ( 𝑎𝟣,…,𝑎𝘯 ) se tendrá que 𝑎 = 𝑎𝟣+𝑎𝟤𝛽+⋯+ 𝑎𝘯𝛽𝘯−𝟣 . Por tanto, 𝑎𝛽 = 0+𝑎𝟣𝛽+𝑎𝟤𝛽𝟤+⋯+𝑎𝘯𝛽𝘯 y 𝑎 div 𝛽=𝑎𝟤+𝑎𝟥𝛽+⋯+ 𝑎𝘯𝛽𝘯−𝟤 +0𝛽𝘯−𝟣 . Si traducimos esto al lenguaje de tuplas usando la definición de cifra, es fácil deducir que 𝑎𝛽 y 𝑎 div 𝛽 serán las cifras de ( 0,𝑎𝟣,…,𝑎𝘯 ) y ( 𝑎𝟤,…,𝑎𝘯,0 ) respectivamente. De esta forma, como 𝑡 es la cifra de la tupla de la configuración (𝑠𝟣,𝑠𝟤,…,𝑠𝘮,…,𝑠𝘭−𝟣,𝑠𝘓) entonces tenemos que 𝑡𝘙es cifra de (0,𝑠𝟣,𝑠𝟤,…,𝑠𝘮−𝟣,…,𝑠𝘭−𝟣,𝑠𝘭)((𝑙+1)-tupla), 𝑡𝘓es cifra de (𝑠𝟤,𝑠𝟥,…,𝑠𝘮+𝟣,…,𝑠𝘭,0)(𝑙-tupla), donde los elementos intermedios marcados en las tuplas son, en cada caso, los 𝑚 -ésimos términos. De la misma forma, 𝑝 es la cifra de la tupla de la configuración (0,…,0,𝑖,0,…,0), y entonces 𝑝𝘙es cifra de (0,…,0,0,𝑖,…,0)((𝑙+1)-tupla), 𝑝𝘓es cifra de (0,…,𝑖,0,0…,0)(𝑙-tupla), de modo que, acorde a la notación escogida, las operaciones tan solo han desplazado el elemento no nulo de la tupla con cifra 𝑝 una unidad a la derecha y a la izquierda, respectivamente. El hecho de que 𝑡𝘙 y 𝑝𝘙 tengan un elemento más no será relevante, como ya hemos mencionado antes. Con esta precisión hecha, tendremos ahora que cada elemento de la tupla con cifra NextP( 𝑝,𝑡 ) queda determinado por los elementos en la correspondiente posición de las tuplas con cifras 𝑡,𝑡𝘙,𝑡𝘓,𝑝,𝑝𝘙 y 𝑝𝘓 ; y las funciones 𝐷y𝑄. En concreto, vamos a usar estos elementos para definir DQ(𝑖𝘓,𝑖,𝑖𝘙,𝑗𝘓,𝑗,𝑗𝘙)=⎧⎪⎪⎨⎪⎪⎩ 𝑄(𝑖𝘓,𝑗𝘓)si 𝑖𝘓>0,𝑖=𝑖𝘙=0y𝐷(𝑖𝘓,𝑗𝘓)=L, 𝑄(𝑖,𝑗) si 𝑖𝘓=0,𝑖>0,𝑖𝘙=0y𝐷(𝑖,𝑗)=S, 𝑄(𝑖𝘙,𝑗𝘙)si 𝑖𝘓=𝑖=0,𝑖𝘙>0y𝐷(𝑖𝘙,𝑗𝘙)=R, 0en cualquier otro caso. Observamos que, si entendemos la función en su acción sobre la máquina, lo primero que se realiza es el desplazamiento de la cabeza para después 95 comprobar, no solo que la tupla está en el formato adecuado (todos sus elementos son nulos salvo el que determina la posición de la cabeza, que debe ser no nulo puesto que no hay un estado nulo), sino que el desplazamiento realizado es efectivamente correcto. En caso de que ambas cosas se cumplan, se realiza la acción determinada por las instrucciones de la máquina. Asimismo, notamos que la condición «en otro caso» recoge las casos en que el primer término exceda el número de estado o el segundo el número de símbolos, garantizando así la buena definición de DQ. Una vez que tenemos esta función, podemos explicitar la representación diofántica de la función: 𝑝′=NextT(𝑝,𝑡)⟺∃𝑤∶𝑝′=DQ[𝛽](𝑝𝛽,𝑝,𝑝div 𝛽,𝑡𝛽,𝑡,𝑡div 𝛽,𝑤), usando la extensión a tuplas de la función DQ recién definida. 6.2.2 Función de progreso de 𝑘pasos Nuestro siguiente objetivo será generalizar las funciones anteriores a otras que nos permitan simular un número arbitrario de acciones de la máquina y probar que estas generalizaciones son también diofánticas. Para ello, vamos a definir de forma recursiva las funciones de 3 argumentos AfterP y AfterT usando iteraciones de NextP y NextT. Así, tendremos: AfterP(0,𝑝,𝑡)=𝑝; AfterP(𝑘+1,𝑝,𝑡)=NextP(AfterP(𝑘,𝑝,𝑡),AfterT(𝑘,𝑝,𝑡)), AfterT(0,𝑝,𝑡)=𝑡; AfterT(𝑘+1,𝑝,𝑡)=NextT(AfterP(𝑘,𝑝,𝑡),AfterT(𝑘,𝑝,𝑡)). Está claro con esta definición que si la máquina 𝑀 pasa de la configuración (𝑝,𝑡)a(𝑝′,𝑡′) en k pasos, entonces 𝑝′=AfterP(𝑘,𝑝,𝑡)y𝑡′=AfterT(𝑘,𝑝,𝑡). Consideremos las configuraciones intermedias ( (𝑝𝟢,𝑡𝟢),…,(𝑝𝘬,𝑡𝘬) ), de modo que se tiene (𝑝𝟢,𝑡𝟢)=(𝑝,𝑡), (𝑝𝘪+𝟣,𝑡𝘪+𝟣)=(NextP(𝑝𝘪,𝑡𝘪),NextT(𝑝𝘪,𝑡𝘪)), (𝑝𝘬,𝑡𝘬)=(𝑝′,𝑡′). Sea también 𝑙 adecuadamente grande para que se tengan las desigualdades 𝑝,𝑡<𝛽𝘭−𝘬−𝟤 , de modo que en la configuración inicial ( 𝑝,𝑡 ) no puede haber más de 𝑙−𝑘−2 celdas ocupadas por la forma en qué describimos la codificación posicional y las restricciones que impusimos a la cifra de una tupla. Como en 𝑘 pasos la máquina 𝑀 puede escribir sobre un máximo de 𝑘 celdas, deducimos de los anterior que para 𝑖 = 0,…,𝑘 se tendrá 𝑝𝘪,𝑡𝘪< 𝛽𝘭−𝟤 , y en particular 𝑝′,𝑡′<𝛽𝘭−𝟤. 96 Ya fue probado en la sección 4.5 que la concatenación de tuplas es una operación diofántica. Así pues, vamos a construir dos pares ( 𝑝𝘓,𝑡𝘓 )y( 𝑝𝘙,𝑡𝘙 ) formados por las cifras del resultado de concatenar las tuplas de las configuraciones intermedias mencionadas antes, de modo que (𝑝𝘓,𝛽,𝑘𝑙)=(𝑝𝟢,𝛽,𝑙)+⋯+(𝑝𝘬−𝟣,𝛽,𝑙), (𝑡𝘓,𝛽,𝑘𝑙)=(𝑡𝟢,𝛽,𝑙)+⋯+(𝑡𝘬−𝟣,𝛽,𝑙), (𝑝𝘙,𝛽,𝑘𝑙)=(𝑝𝟣,𝛽,𝑙)+⋯+(𝑝𝘬,𝛽,𝑙), (𝑡𝘙,𝛽,𝑘𝑙)=(𝑡𝟣,𝛽,𝑙)+⋯+(𝑡𝘬,𝛽,𝑙) (el símbolo ‘+’ denota la operación de concatenación, y recordemos que 𝑙 lo hemos escogido arbitrariamente grande luego no hay problema con suponer que todas las tuplas son de dicha longitud). Decimos que los pares ( 𝑝𝘓,𝑡𝘓 )y( 𝑝𝘙,𝑡𝘙 ) se denominan superconfiguraciones. Nótese que las superconfiguraciones no codifican configuraciones pues las tuplas de cifras 𝑝𝘓 y 𝑝𝘙 tienen 𝑘 elementos no nulos y las de cifras 𝑝𝘓 y 𝑝𝘙 tienen 𝑘 símbolos que corresponden a celdas marcadas con ‘ ⋆ ’. Estas superconfiguraciones las haremos corresponder entonces con ciertas supermáquinas cuyas cintas estarán divididas en 𝑘 cintas diferenciadas a partir de los símbolos ‘ ⋆ ’, cada una de ellas con una cabeza que funciona de forma independiente y siguiendo las instrucciones originales de la máquina 𝑀. Tal y como las hemos definido, vemos que la superconfiguración ( 𝑝𝘙,𝑡𝘙 ) queda determinada de forma única por ( 𝑝𝘓,𝑡𝘓 ) gracias a las funciones NextP y NextT, puesto que por construcción estas funciones describen un paso de la supermáquina, 𝑝𝘙=NextP(𝑡𝘓,𝑝𝘓), 𝑡𝘙=NextT(𝑡𝘓,𝑝𝘓). Asimismo, vamos a continuar definiendo una nueva superconfiguración (𝑝𝘔,𝑡𝘔) como (𝑝𝘔,𝛽,(𝑘−1)𝑙)=(𝑝𝟣,𝛽,𝑙)+⋯+(𝑝𝘬−𝟣,𝛽,𝑙), (𝑡𝘔,𝛽,(𝑘−1)𝑙)=(𝑡𝟣,𝛽,𝑙)+⋯+(𝑡𝘬−𝟣,𝛽,𝑙), y usando esta notación podemos reescribir las concatenaciones que definían las cifras de las otras superconfiguraciones de forma que (𝑝𝘓,𝛽,𝑘𝑙)=(𝑝,𝛽,𝑙)+(𝑝𝘔,𝛽,(𝑘−1)𝑙), (𝑡𝘓,𝛽,𝑘𝑙)=(𝑡,𝛽,𝑙)+(𝑡𝘔,𝛽,(𝑘−1)𝑙), (𝑝𝘙,𝛽,𝑘𝑙)=(𝑝𝘔,𝛽,(𝑘−1)𝑙)+(𝑝′,𝛽,𝑙), (𝑡𝘙,𝛽,𝑘𝑙)=(𝑡𝘔,𝛽,(𝑘−1)𝑙)+(𝑡′,𝛽,𝑙). 97 Con todo este proceso hemos mostrado que dada una configuración arbitraria ( 𝑝,𝑡 ) y un número positivo 𝑘 , entonces para un cierto 𝑙 lo suficientemente grande existen cifras 𝑝𝘓,𝑡𝘓,𝑝𝘔,𝑡𝘔,𝑝𝘙,𝑡𝘙,𝑝′ y 𝑡′ que satisfacen todas las ecuaciones anteriores. Veamos ahora que estas mismas condiciones pueden ser expresadas en términos de los parámetros 𝑘,𝑙,𝑝y𝑡. En primer lugar, vemos gracias a las concatenaciones anteriores que los primeros 𝑙 elementos de las tuplas con códigos ( 𝑝𝘓,𝛽,𝑘𝑙 )y( 𝑡𝘓,𝛽,𝑘𝑙 ) están únicamente determinados tan solo usando 𝑝 y 𝑡 . Ahora, recordando las representaciones diofánticas que dimos para NextT y NextP, apreciamos que estas funciones fueron definidas de tal forma que los primeros 𝑚 elementos de las tuplas con cifras NextP( 𝑥 , 𝑦 ) y NextP( 𝑥 , 𝑦 ) están únicamente determinados por los primeros 𝑚+1 elementos de las tuplas con cifras 𝑥 e 𝑦 (el «+1» es necesario al hacerse uso en la representación de NextT las tuplas con cifras ·𝘓 , donde el 𝑚 -ésimo elemento es en realidad el ( 𝑚+1 )-ésimo de la tupla original). Así pues, por la relación de 𝑝𝘙 y 𝑡𝘙 con 𝑝𝘓 y 𝑡𝘓 a través de las funciones NextP y NextT que hemos resaltado previamente, como conocemos los primeros 𝑙elementos de las tuplas codificadas por (𝑝𝘓,𝛽,𝑘𝑙) y ( 𝑡𝘓,𝛽,𝑘𝑙 ) entonces también conocemos los primeros 𝑙−1 elementos de las tuplas con códigos ( 𝑝𝘙,𝛽,𝑘𝑙 )y( 𝑡𝘙,𝛽,𝑘𝑙 ). En particular, usando nuevamente la expresión de las concatenaciones anteriores, tendremos también determinados de forma única los primeros 𝑙−1 elementos de las tuplas con códigos (𝑝𝘔,𝛽,(𝑘−1)𝑙)y(𝑡𝘔,𝛽,(𝑘−1)𝑙). Volvemos a las dos primeras concatenaciones con la información de la que ahora disponemos. Como hemos determinado de forma única los primeros 𝑙−1 elementos de las tuplas con cifras 𝑝𝘔 y 𝑡𝘔 , entonces ahora tendremos caracterizados los primeros 2𝑙−1 elementos de las tuplas de códigos ( 𝑝𝘓,𝛽,𝑘𝑙 )y( 𝑡𝘓,𝛽,𝑘𝑙 ). Entonces usando los mismos argumentos con las funciones NextP y NextT podremos determinar los primeros 2𝑙−2 elementos de las tuplas codificadas por ( 𝑝𝘙,𝛽,𝑘𝑙 ) y ( 𝑡𝘙,𝛽,𝑘𝑙 ), y en particular de nuevo tendremos también los 2𝑙−2 primeros de ( 𝑝𝘔,𝛽,(𝑘−1)𝑙 ) y ( 𝑡𝘔,𝛽,(𝑘−1)𝑙 ). Repitiendo varias veces este mismo argumento, acabaremos por determinar la unicidad de todos los elementos de las tuplas que vienen codificadas por ( 𝑝𝘓,𝛽,𝑘𝑙 ), ( 𝑡𝘓,𝛽,𝑘𝑙 ), ( 𝑝𝘔,𝛽,(𝑘−1)𝑙 ) y ( 𝑡𝘔,𝛽,(𝑘−1)𝑙 ), así como también todos los de las tuplas con códigos ( 𝑝𝘙,𝛽,𝑘𝑙 ), ( 𝑡𝘙,𝛽,𝑘𝑙 ), ( 𝑝′,𝛽,𝑙 ) y ( 𝑡′,𝛽,𝑙 ), salvo potencialmente los últimos elementos de ellas en caso de que las tuplas que codifican ( 𝑝′,𝛽,𝑙 )y( 𝑡′,𝛽,𝑙 ) tengan exactamente 𝑙 elementos no nulos. Sin embargo, podemos descartar este caso puesto que las desigualdades 𝑝′,𝑡′<𝛽𝘭−𝟤 que expusimos al comienzo del razonamiento nos garantizan que los últimos elementos de las tuplas con dichas cifras son iguales a 0. De esta forma, hemos logrado demostrar que sean un configuración 98 ( 𝑝,𝑡 ), un número positivo 𝑘 y un cierto 𝑙 tal que 𝑝,𝑡 <𝛽𝘭−𝘬−𝟤 , el sistema de condiciones diofánticas siguiente: 𝑝′,𝑡′<𝛽𝘭−𝟤, 𝑝𝘙=NextP(𝑝𝘓,𝑡𝘓), 𝑡𝘙=NextT(𝑝𝘓,𝑡𝘓), (𝑝𝘓,𝛽,𝑘𝑙)=(𝑝,𝛽,𝑙)+(𝑝𝘔,𝛽,(𝑘−1)𝑙), (𝑡𝘓,𝛽,𝑘𝑙)=(𝑡,𝛽,𝑙)+(𝑡𝘔,𝛽,(𝑘−1)𝑙), (𝑝𝘙,𝛽,𝑘𝑙)=(𝑝𝘔,𝛽,(𝑘−1)𝑙)+(𝑝′,𝛽,𝑙), (𝑡𝘙,𝛽,𝑘𝑙)=(𝑡𝘔,𝛽,(𝑘−1)𝑙)+(𝑡′,𝛽,𝑙) tiene exactamente una solución en las variables 𝑝𝘓,𝑡𝘓,𝑝𝘔,𝑡𝘔,𝑝𝘙,𝑡𝘙,𝑝′𝑡′ para la cual se cumple que 𝑝′=AfterP(𝑘,𝑝,𝑡), 𝑡′=AfterT(𝑘,𝑝,𝑡). Esto implica directamente que las funciones AfterP y AfterT son diofánticas, como queríamos probar. Teniendo ahora disponibles todos estos recursos, estamos al borde de ser capaces de describir a partir de la máquina 𝑀 inicial una ecuación diofántica, con lo cual concluiríamos la equivalencia con la que comenzamos el capítulo. Para ello, vamos a considerar la notación 𝑤𝟣,…,𝑤𝘻 para los subíndices de los estados finales de 𝑀. De esta forma, la condición ∃𝑘,𝑟∶Elem(AfterT(𝑘,𝑝,𝑡),𝛽,𝑟)=𝑤𝟣∨⋯∨Elem(AfterT(𝑘,𝑝,𝑡),𝛽,𝑟)=𝑤𝘻 se cumple si y solo si la máquina 𝑀 , comenzando en una configuración ( 𝑝,𝑡 ), se detiene en un número finito de pasos. Este número de pasos realizados, en particular, es el valor 𝑘 usado para describir la condición. Como tal condición es diofántica por lo que hemos probado hasta ahora, puede ser transformada en una ecuación diofántica 𝐷′(𝑝,𝑡,𝑥𝟣,…,𝑥𝘮)=0. No obstante, esta ecuación no termina de ser suficiente para nuestro propósito. Recordamos que el objetivo de la sección es probar que el conjunto 𝔐 , semidecidible por 𝑀 , es diofántico. Para ello, los parámetros de la ecuación deberían ser de la forma 𝑎𝟣,…,𝑎𝘯 como se requiere en la representación diofántica de un conjunto, en lugar de las cifras de la configuración 𝑝 y 𝑡 , como se tiene en la ecuación 𝐷′ que se ha construido. Para arreglar este problema, no tenemos más que expresar estos dos valores en función de los 𝑎𝘪o como constantes invariables en cada caso. 99 Así pues, se aprecia como para la configuración inicial se tendrá por un lado que 𝑝=1 , ya que esta cifra representa la tupla ( 1,0,…,0 ) que denota que la cabeza se encuentra en la primera celda por la izquierda de la cinta y en el estado inicial 𝑞𝟣. Para 𝑡 , recordamos la función Repeat( (𝑝,𝑞,𝑟) ) =𝘱(𝘲𝘳−𝟣) 𝘲−𝟣 que devuelve la cifra de la tupla ( 𝑝,𝑝,…,𝑝 ) de longitud 𝑟 en la base 𝑞 . Entonces en el momento inicial de la máquina los símbolos sobre la cinta están determinados por el valor 𝑡 de la configuración y, como la cinta contiene la representación canónica de la tupla ( 𝑎𝟣,…,𝑎𝘯 ) en su momento inicial, entonces dichos símbolos deben ser de izquierda a derecha ‘ ⋆ ’, seguido de un ‘0’, a continuación 𝑎𝟣 ‘1’s, un ‘0’, 𝑎𝟤 ‘1’s,..., y así hasta terminar con 𝑎𝘯 ‘1’s. Esto significa que por la definición de cifra, debe cumplirse la igualdad ⟨𝑡,𝛽,𝑎⟩=⟨𝜅,𝛽,1⟩+[⟨𝜇,𝛽,1⟩+⟨Repeat(𝜈,𝛽,𝑎𝟣),𝛽,𝑎𝟣⟩]+⋯ +[⟨𝜇,𝛽,1⟩+⟨Repeat(𝜈,𝛽,𝑎𝘯),𝛽,𝑎𝘯⟩], donde 𝑎=𝑎𝟣+⋯+𝑎𝘯 , el símbolo «+» denota la operación de concatenación de tuplas; y 𝜅,𝜇,𝜈 son respectivamente los subíndices de los símbolos ‘ ⋆ ’, ‘0’ y ‘1’ en el alfabeto ‵𝛼𝟣,…,𝛼′ 𝘸de la máquina. Reuniendo la ecuación 𝐷′ junto con estas dos ecuaciones para 𝑝 y 𝑡 , parámetros de la configuración inicial, podemos desarrollar una nueva ecuación que tenga los parámetros correctos, 𝐷(𝑎𝟣,⋯,𝑎𝘯,𝑥𝟣,…,𝑥𝘮) , y que es una representación diofántica del conjunto 𝔐, como queríamos conseguir. 6.3 Resolución del décimo problema de Hilbert Hemos probado ya en la anterior sección que los conjuntos semidecidibles y los conjuntos diofánticos son equivalentes. Vamos a introducir ahora el concepto de conjuntos decidibles, prácticos para la resolución final del problema décimo. Previamente ya definimos los conjuntos semidecidibles en base a máquinas de Turing tales que si un elemento pertenece al conjunto entonces la máquina termina y devuelve una respuesta afirmativa y si no pertenece entonces la máquina se desarrolla indefinidamente. En realidad, sería más natural haber comenzado definiendo los conjuntos decidibles, pero no hemos tomado este enfoque porque estos no son tan relevantes en el desarrollo de la resolución del problema. Así pues, diremos que un conjunto de 𝑛 -tuplas 𝔐 es Turing-decidible si existe una máquina de Turing 𝑀 tal que, comenzando en el estado inicial 𝑞𝟣 con la cabeza colocada en la celda más a la izquierda de una cinta que contiene la representación canónica de una 100 tupla, la máquina termina en un estado de aceptación si la tupla pertenece al conjunto, y termina en estado de negación en caso contrario. De nuevo, este concepto fue brevemente tratado en la introducción (definición 1.9). Naturalmente, existe una relación entre la semidecibilidad y la decibilidad, y es precisamente esto lo que nos permitirá dar la respuesta al problema. 6.3.1 Semidecibilidad y decibilidad Proposición 6.2 (Semidecidibilidad a partir de decidibilidad) Si un conjunto 𝔐es decidible, entonces también es semidecidible. Demostración de la proposición 6.2 Vamos a comenzar definiendo la máquina not 𝑀=while Mdo stop od que invierte las respuestas que devuelve la máquina cuando termina: si 𝑀 termina en un estado de afirmación, not 𝑀 en un estado de negación; si 𝑀 termina en un estado de negación, not 𝑀 termina en un estado de afirmación; y si 𝑀 no termina entonces ninguna de las dos termina. Esta acción es fácil de deducir tan solo a partir de las definiciones de la composición de tipo while-do-od y la máquina stop. Así pues, sea 𝑀 la máquina que decide el conjunto 𝔐 . Vamos a definir las máquinas 𝑀′=while Mdo stop od; neverstop, 𝑀″= not 𝑀′. Notamos que por sus definiciones, cuando la máquina 𝑀 termina en un estado de aceptación 𝑞𝟤 entonces se realiza la acción de la composición while-do-od y la máquina stop termina 𝑀′ en estado 𝑞𝟥 , mientras que cuando la máquina 𝑀 termina en 𝑞𝟥 entonces se salta directamente a la composición if-then que empieza la acción de neverstop, provocando que la máquina nunca termine. Por tanto, 𝑀′ devuelve una respuesta negativa cuando 𝑀 devuelve una afirmativa, y no termina cuando 𝑀 devuelve una negativa. Ahora bien, sabemos que not 𝑀′ es una máquina que invierte los estados de afirmación y negación cuando 𝑀′ termina, luego la tendremos que 𝑀″ es una máquina que devuelve una respuesta afirmativa cuando 𝑀 devuelve una afirmativa, y no termina 101 cuando 𝑀 devuelve una negativa. De esta forma, tenemos que 𝑀″ es una máquina que semidecide el conjunto 𝔐 , con lo que tenemos la implicación que buscábamos. Asimismo, podemos considerar la composición 𝑀′=while 𝑀do neverstop od cuya acción es fácil de describir: cuando la máquina 𝑀 termina en un estado de afirmación, 𝑀′ no termina; y cuando 𝑀 termina en negación, 𝑀′ termina en afirmación. Por tanto, tenemos que si 𝑀 decide un conjunto entonces 𝑀′ semidecide su complementario. Dicho de otra forma, hemos probado que si un conjunto es Turing-decidible, entonces su complementario es Turing-semidecidible. El último resultado que vamos buscando es ligeramente más complejo de probar. Dicho resultado es el siguiente: Proposición 6.3 (Decidibilidad a partir de semidecidibilidad) Si un conjunto 𝔐 y su complementario son ambos semidecidibles, entonces el conjunto 𝔐es Turing-decidible. Tratar la demostración de este resultado con máquinas consiste en considerar dos máquinas 𝑀𝟣 que semidecide 𝔐 y 𝑀𝟤 que semidecide su complementario, entonces definimos una máquina 𝑀 que alterne las acciones las dos máquinas anteriores y que, por tanto, va a detenerse eventualmente en un estado de afirmación o negación según una tupla pertenezca o no a 𝔐 . Esta máquina, que en su única cinta engloba las acciones de 𝑀𝟣 y 𝑀𝟤 , naturalmente es compleja de definir rigurosamente. Sin embargo, nosotros nos vamos a valer de la equivalencia entre conjuntos semidecibles y conjuntos diofánticos (que hemos establecido anteriormente) para tomar un acercamiento más sencillo a la prueba del resultado. Así pues, comenzamos construyendo un par de ecuaciones diofánticas 𝐷𝟤(𝑎𝟣,…,𝑎𝘯,𝑥𝟣,…,𝑥𝘮)=0, 𝐷𝟥(𝑎𝟣,…,𝑎𝘯,𝑥𝟣,…,𝑥𝘮)=0 que respectivamente describen 𝔐 y su complementario, notando que podemos sin pérdida de generalidad asumir que ambas tienen el mismo número de incógnitas. Estas dos ecuaciones pueden combinarse en una sola de la forma siguiente: (𝐷𝟤 𝟤(𝑎𝟣,…,𝑎𝘯,𝑥𝟣,…,𝑥𝘮)+(1−𝑦𝘮)𝟤) ·(𝐷𝟤 𝟥(𝑎𝟣,…,𝑎𝘯,𝑥𝟣,…,𝑥𝘮)+𝑦𝘮)=0. 102 7El décimo problema en los racionales y otros anillos Una vez que tenemos establecida la indecidibilidad del problema décimo en su planteamiento original, es solo natural preguntar qué sucede cuando intentamos adaptarlo a diferentes anillos de números. En este capítulo nos encargamos de resumir las diferentes respuestas que puede tener el problema en estos casos, dando un enfoque protagonista al cuerpo ℚ de los números racionales, el cual aún sigue en estudio. Planteada explícitamente, la pregunta que nos hacemos es la siguiente. Décimo problema de Hilbert generalizado Sea 𝑅 un anillo. Dada una ecuación polinómica arbitraria en varias variables (las cuales pertenecen a 𝑅 ) ¿existe algún algoritmo universal que determine si tal ecuación tiene o no tiene solución en el anillo? A continuación, daremos un desarrollo breve sobre esta cuestión. No entraremos en profundidad en los conceptos tratados por volverse muy específicos y salirse del interés de este trabajo, pero será ofrecida una vista generalizada sobre la situación actual del estudio del problema. Los contenidos aquí expuestos están basados en los textos [8] y [7] de la bibliografía. Para el lector interesado, puede encontrar una ampliación del tema en las referencias allí indicadas. 7.1 Caso particular 𝑅=ℚ Si el décimo problema de Hilbert hubiese tenido una solución positiva, entonces sería fácil deducir que también para ℚ la solución al problema lo sería. Sin embargo, al haberse establecido la indecibilidad en los enteros, ℤ , se abre la puerta a la discusión sobre qué es lo que sucede para los números 109 racionales. Inicialmente, el estudió se focalizó en la búsqueda de encontrar una forma de representar diofánticamente el conjunto de los números enteros usando tan solo cuantificadores existenciales (lo cual es congruente con el método de trabajo que hemos usado para las representaciones diofánticas en los capítulos anteriores). Dicho de otra forma, el objetivo era encontrar un polinomio 𝐷con coeficientes en ℤtal que 𝑡∈ℤ⟺∃𝑥𝟣,…,𝑥𝘯∈ℚ∶𝐷(𝑡,𝑥𝟣,…,𝑥𝘯)=0. En caso de existir tal polinomio, puede probarse gracias a la indecidibilidad en ℤ que el problema es indecidible en ℚ : supongamos por reducción a lo absurdo que el problema décimo es decidible en ℚ . Vamos a tomar entonces un cierta ecuación sobre ℤ , por ejemplo, 𝑓(𝑦𝟣,…,𝑦𝘮) = 0. A partir de ella, construimos el siguiente sistema de ecuaciones sobre ℚ: 𝑓(𝑦𝟣,…,𝑦𝘮)=0, 𝐷(𝑦𝟣,𝑥𝟣,…,𝑥𝘯)=0, ⋮ 𝐷(𝑦𝘮,𝑥𝟣,…,𝑥𝘯)=0. Este es un sistema de ecuaciones diofánticas, luego sabemos que puede transformarse en una sola ecuación 𝑓′(𝑦𝟣,…,𝑦𝘮,𝑥𝟣,…,𝑥𝘯)=0 . Ahora bien, notamos que salvo la primera, las ecuaciones del sistema garantizan la integridad de las variables de la ecuación original. Por tanto sabemos que la ecuación 𝑓 tendrá solución sobre ℤ si y solo si la ecuación 𝑓′ tiene solución sobre ℚ . Luego si el problema décimo fuese decidible en ℚ , habríamos encontrado una forma de decidirlo en ℤ , pero esto contradice la indecidibilidad del problema en su versión original. Por tanto, no podría tenerse la decidibilidad tampoco en ℚ . En general, esto se cumple para cualquier anillo de característica nula donde ℤ pueda representarse diofántica y existencialmente. Sin embargo, este camino se vio prontamente truncado cuando Barry Mazur formuló una serie de conjeturas sobre la topología de puntos racionales y Teoría de Galois, una de las cuales tiene como implicación directa la imposibilidad de encontrar una representación de ℤ sobre ℚ de este tipo. Poco después, también Jochen Königsmann mostró que una versión fortalecidad de la conjetura de Bombieri-Lang implica que no es posible encontrar una representación diofántica de ℤsobre ℚ. Otra forma alternativa de proceder se centró en tratar de encontrar una función 𝜙∶ℤ⟶ℚ𝘬 de modo que las imágenes de las operaciones de suma 110 y producto en ℤ fuesen diofánticas sobre ℚ𝘬 . De existir una función así, 𝜙 enviaría conjuntos diofánticos en conjuntos diofánticos, de modo que la indecidibilidad del problema décimo en ℤ podría usarse para probar la indecidibilidad en ℚ . Este método ha sido mayoritariamente abordado usando curvas elípticas, pero en el proceso volvemos a encontrar un problema al tratar de describir diofánticamente las operaciones básicas del anillo ℚ con los elementos de ℤ , ya que el producto en los enteros no se comporta como nos gustaría con respecto a los números racionales. Al final, ambos métodos se ven obstaculizados por un teorema de Cornelissen y Zahidi que refleja estos problemas con el operador producto: Teorema 7.1 Si la conjetura de Mazur sobre la topología de puntos racionales es cierta, entonces no hay ningún modelo diofántico de ℤ sobre ℚ. Entendemos modelo diofántico con un conjunto diofántico 𝑆 tal que existe una biyección 𝜙∶ℤ⟶𝑆 de forma que los grafos de la suma y el producto por 𝜙se corresponden con un subconjunto diofántico de 𝑆𝟥. Así pues, viendo que los caminos anteriores no parecían conducir a un resultado satisfactorio, surgen dos rutas diferentes de continuar con el estudio del problema en ℚ : la investigación de los grandes anillos y la reducción del número de cuantificadores universales en las definiciones de primer orden de ℤ sobre ℚ . Nosotros vamos a profundizar en el primero de los métodos. Sea 𝒮 un conjunto de primos de ℚ . Entonces vamos a notar por 𝑂ℚ,𝒮 al subanillo de los racionales definido como {𝑚 𝑛∶𝑚,𝑛∈ℤ,𝑛≠0,𝑛solo es divisible por los primos de 𝒮}. Notamos que si 𝒮 = ∅ entonces, en la definición del conjunto, 𝑛 no es divisible por ningún número primo y por tan necesariamente 𝑛 = 1 ⟹ 𝑂ℚ,∅ =ℤ . Por otra parte, si 𝒮 contiene a todos los primos de ℚ , entonces es fácil ver que 𝑂ℚ,𝒮 =ℚ. Definición 7.2 (Subanillos pequeños y grandes) Diremos que el subanillo 𝑂ℚ,𝒮 es pequeño si 𝒮 es finito, y por el contrario diremos que es grande si 𝒮 es infinito. Los anillos pequeños también son llamados anillos de 𝒮 -enteros, mientras que cuando 𝒮 contiene a todos salvo una cantidad finita de primos de ℚ , entonces decimos que los subanillos asociados se denominan subanillos semilocales de ℚ. 111 Para medir el ‘tamaño’ de los anillos grandes, usamos el concepto de densidad natural de un conjunto de primos. Definición 7.3 (Densidad natural) Sea 𝒜 un conjunto de primos, entonces la densidad natural de 𝒜es igual, en caso de que exista, al límite lím 𝘟⟶∞ #{𝑝∈𝒜,𝑝≤𝑋} #{𝑝≤𝑋} . Sobre anillos pequeños, los trabajos de Julia Robinson sobre la representación de primer orden de los enteros sobre ℚ nos ofrecen toda la información que necesitamos: Teorema 7.4 Para cualquier 𝑝 , el anillo 𝑅𝘱∶={𝑥∈ℚ∶𝑥=𝘮 𝘯;𝑚,𝑛∈ℤ;𝑛> 0;𝑝∤𝑛}puede representarse diofánticamente sobre ℚ. De esto se deduce el siguiente corolario: Corolario 7.5 (El décimo problema en subanillos pequeños de ℚ) 1. ℤ tiene una representación diofántica sobre cualquier anillo pequeño de ℚ. 2. El décimo problema de Hilbert adaptado a cualquier anillo pequeño de ℚes irresoluble. Para los anillos grandes, estamos en una situación más compleja. Sí que se tienen, no obstante, resultados para algunos subanillos particulares. En 2003, Bjorn Poonen probó el primer resultado de indecidibilidad diofántica sobre un anillo grande de ℚ: Teorema 7.6 Existen conjuntos recursivos (decidibles) 𝒮𝟣 y 𝒮𝟤 , ambos con densidad natural nula y cumpliendo 𝒮𝟣∩𝒮𝟤= ∅ , tales que para cualquier conjunto 𝒮de primos con 𝒮𝟣⊆𝒮⊆𝒮𝘊 𝟤se cumple que: ℤtiene un modelo diofántico sobre 𝑂ℚ,𝒮. El décimo problema de Hilbert es indecidible sobre 𝑂ℚ,𝒮. Poonen usó una técina que involucraba de nuevo curvas elípticas, pero de una forma diferente al enfoque clásico que se ha mencionado previamente, 112 ya que él construyó su modelo de enteros por aproximación. Este método fue extendido por otros matemáticos y permitió posteriormente a Eisenträger, Everest y Shlapentokh probar el siguiente resultado que nos proporciona una cubierta de ℚ formada por anillos donde el problema décimo es irresoluble: Teorema 7.7 Para cualquier conjunto finito 𝑟𝟣,…,𝑟𝘬 de números reales positivos computables (números reales que pueden ser aproximados por una secuencia computable de números racionales) tales que 𝑟𝟣+⋯+𝑟𝘬=1 , podemos obtener una partición del conjunto de todos los primos racionales en los conjuntos 𝒮𝟣,…,𝒮𝘬 de modo que la densidad natural de cada 𝒮𝘪 es 𝑟𝘪 y cada anillo 𝑂ℚ,𝒮𝘪 tiene un modelo diofántico de ℤ , de modo que el décimo problema de Hilbert es indecidible para cada 𝑂ℚ,𝒮𝘪. Vamos ahora a abordar el problema de decidibilidad de una forma diferente, más cercana a los estudios que están siendo realizados en la actualidad. Así pues, vamos a convertir esta cuestión de decidibilidad del problema décimo de un anillo recursivo 𝑅 en términos del grado de Turing de un subconjunto de ℤ>𝟢 . Decimos que el grado de Turing es la clase de equivalencia de todos los conjuntos que son mutuamente Turing-reducibles. La relación de Turing-reducidibilidad mutua se denota por ≡𝘛 , siendo que 𝐴≡𝘛𝐵⟺𝐴≤𝘛𝐵∧𝐵≤𝘛𝐴. Sea {𝑝𝘪(𝑥𝟣,…,𝑥𝘯)} una recopilación efectiva de todos los polinomios sobre el anillo 𝑅 , y llamemos HTP( 𝑅 ) al conjunto de los índices de los polinomios de esta familia que tienen alguna raíz en 𝑅 . Está claro que HTP (ℤ)≡𝘛𝐻 para 𝐻 el conjunto de parada que definimos en la sección 6.3, es decir, el conjunto formado por todos los pares (𝑀,𝑥) tales que 𝑀 es una máquina de Turing y 𝑥 una entrada de forma que 𝑀 se detiene sobre 𝑥 . Es más, es fácil ver también que para cualquier anillo 𝑅 que tenga un modelo sobre ℤ se tiene que HTP(𝑅)≡𝘛𝐻. Gracias a resultados de Richard Friedberg y Albert Muchnik, sabemos que existen grados de Turing que contienen conjuntos recursivamente enumerables (semidecidibles) e indecidibles que no son tan complejos como 𝐻 , es decir, tales que 𝐻 no es Turing-equivalente a estos conjuntos. La cuestión que se plantea ahora es, ¿HTP( ℚ ) es uno de estos conjuntos? Si este fuera el caso, entonces tendríamos que no podría existir un algoritmo que resuelva el problema décimo adaptado a ℚ pero tampoco habría un modelo diofántico de ℤ sobre ℚ , lo cual es una situación que hasta ahora no se ha contemplado. Por tanto, si HTP(ℚ)≢𝘛HTP(ℤ), tiene sentido emprender una búsqueda de subanillos grandes tales que estén ‘infinitamente lejos’ de ℚ y que cumplan que HTP(ℚ)≢𝘛HTP(𝑅). 113 En las investigaciones actuales, se ha logrado construir precisamente unas familias de subanillos 𝑅 de ℚ tales que HTP (ℚ)≢𝘛 HTP( 𝑅 ) usando números racionales tales que un conjunto infinito de primos pueden dividir el denominador de los elementos de 𝑅 y de forma que también el complementario de este conjunto (un conjunto de primos que no dividen a los denominadores) es infinito. El conjunto de primos divisores puede ser reordenado para tener la menor densidad natural, equivalente a 0, de modo que en efecto tenemos entre manos un anillo que está en el medio e infinitamente alejado de ambos ℤ y ℚ . Estos anillos son además computables desde HTP( ℚ ), luego si HTP( ℚ ) es decidible, entonces estos conjuntos de primos también serán decidibles y consecuentemente los anillos 𝑅 serán subanillos computables de ℚ. También se ha logrado a partir de este estudio encontrar un análogo debilitado del teorema anterior: Teorema 7.8 Para cualquier entero positivo 𝑘 , se puede obtener una partición del conjunto de todos los números primos en 𝑘 conjuntos 𝒮𝟣,…,𝒮𝘬 de densidad natural nula (la mínima), y construir a través de ellos anillos 𝑅𝟣,…,𝑅𝘬 tales que los primos que pueden dividir los denominadores de los elementos de cada 𝑅𝘪 son precisamente los primos de 𝒮𝘪 (respectivamente) y que además cumplen que HTP(𝑅𝘪)≡𝘛HTP(ℚ). Desgraciadamente, los anteriores anillos no necesariamente son presentables computacionalmente, y tan solo podemos decir que cada 𝒮𝘪 es Turing-reducible a HTP( ℚ ) ( 𝒮𝘪≤𝘛 HTP( ℚ )), de forma que de nuevo si HTP( ℚ ) es decidible entonces estos conjuntos de primos serán decidibles, y los anillos asociados, subanillos computables de ℚ. Combinando todos estos resultados con los obtenidos para anillos grandes con HTP equivalentes al problema de la parada, podemos concluir que si HTP sobre ℤ es distinto al que tenemos sobre ℚ (en particular, si HTP( ℚ ) es decidible), tendremos un entramado de anillos recursivos en ℚ con diferentes niveles de complejidad de sus respectivos HTP’s. A simple vista, esta parece una situación difícil de imaginar, pero no puede ser descartada a falta de una demostración más adecuada que aún no ha podido ser dada. 7.2 Generalización a anillos arbitrarios 𝑅 En esta sección, vamos a repasar los conceptos adecuados que se utilizan en el estudio del problema en anillos más generales (a diferencia de 7.1, donde nos hemos centrado solo en el anillo de los racionales) y concluiremos 114 finalmente mostrando una tabla que resume los resultados conocidos para diferentes anillos. 7.2.1 Fórmulas de primer orden Comenzamos explicando brevemente en qué consisten las fórmulas de primer orden, las cuales guardan una destacable relación con la decidibilidad del problema décimo que será explicada más adelante. Definición 7.9 (Fórmula de primer orden) Una fórmula de primer orden en el lenguaje de los anillos se define como una expresión construida usando los símbolos matemáticos ‘+’, ‘·’, ‘0’, ‘1’, ‘=’ y ‘(·, ·)’; las relaciones lógicas ‘∧’, ‘∨’y‘¬’; los cuantificadores ‘∀’y‘∃’; y las variables 𝑥,𝑦,𝑧, etc. Por ejemplo, una fórmula como ∀𝑦∃𝑧,𝑤∶(𝑥𝑧+3=𝑦𝟤)∨¬(𝑧=𝑥+𝑤) es una fórmula de primer orden. Las variables de las fórmulas se dividen en dos tipos: variables ligadas si aparecen en la fórmula junto a algún cuantificador, o variables libres en caso contrario. En nuestro ejemplo, tan solo la variable 𝑥es libre, mientras que 𝑦,𝑧y𝑤están ligadas. Una fórmula cuyas variables están todas ligadas se denomina una oración de primer orden. Por otro lado, una fórmula con la estructura ∃𝑥𝟣,…,𝑥𝘯∶𝑆 donde 𝑆 es una combinación de ecuaciones involucrando los operadores ‘+’, ‘·’, ‘0’, ‘1’, ‘=’, ‘ ∧ ’y‘ ∨ ’ (es decir, que no tiene cuantificadores ni el operador lógico ‘ ¬ ’) se denomina fórmula existencial positiva. Si además 𝑆 consiste en una única ecuación (de modo que no incluye operadores lógicos en su construcción), entonces en particular se dirá que es una fórmula diofántica. Sea 𝑅 una anillo cualquiera (tan solo vamos a requerir que sea conmutativo y contenga al elemento unidad, 1). Una oración de primer orden obtiene un valor de verdad al interpretarla de la forma natural dejando que las variables ligadas recorran los elementos de 𝑅 . Por otro lado, si 𝜙(𝑥𝟣,…,𝑥𝘯) es una fórmula de primer orden con 𝑥𝟣,…,𝑥𝘯 variables libres, entonces obtenemos de 𝜙(𝑎𝟣,…,𝑎𝘯) un valor de verdad, como la notación sugiere, al sustituir los 𝑎𝘪∈𝑅 por 𝑥𝘪 en la fórmula, de modo que una fórmula 𝜙 con 𝑛 variables libres genera un subconjunto de 𝑅𝘯, { (𝑎𝟣,…,𝑎𝘯)∈𝑅𝘯∶𝜙(𝑎𝟣,…,𝑎𝘯)}. Un subconjunto de 𝑅𝘯 formado de este modo a partir de una fórmula existencial positiva se dice que es existencial positivo sobre 𝑅 . Análogamente, 115 si la fórmula es diofántica entonces se dice que el subconjunto es diofántico sobre 𝑅 . Esta noción es equivalente al concepto de conjunto diofántico que venimos trabajando durante los capítulos anteriores al tratarse sobre ℤ. Nótese que añadir el operador diferencia ‘-’ no cambia las anteriores nociones, ya que la fórmula 𝑥−𝑦 = 𝑧 es equivalente a 𝑥 = 𝑧+𝑦 . Ciertos anillos necesitarán también que proveamos a la definición algunos símbolos adicionales, por ejemplo, los anillos de polinomios 𝑅[𝑡] pueden necesitar que sea añadido el símbolo ‘ 𝑡 ’ a la lista de elementos usables para construir las fórmulas de primer orden. Asimismo, remarquemos que los conjuntos existenciales positivos y diofánticos son cerrados para la unión e intersección finitas. La relación entre ambos tipos de conjuntos aparece a través del siguiente resultado. Proposición 7.10 (Relación entre conjuntos existenciales positivos y diofánticos) Sea 𝑅 un anillo en el cual existen polinomios 𝑓(𝑥,𝑦),𝑔(𝑥,𝑦)∈𝑅[𝑥,𝑦] tales que para 𝑎,𝑏∈𝑅 se cumplen las condiciones 𝑓(𝑎,𝑏)=0⟺𝑎=0∧𝑏=0, 𝑔(𝑎,𝑏)=0⟺𝑎=0∨𝑏=0. Si se disponen de suficientes símbolos en el lenguaje como para poder expresar los coeficientes de 𝑓 y 𝑔 en función de estos, entonces la familia de conjuntos existenciales positivos sobre 𝑅 es equivalente a la familia de conjuntos diofánticos sobre 𝑅. Demostración de la proposición 7.10 Es obvio que los conjuntos diofánticos son, en particular, existenciales positivos, pues por construcción las fórmulas diofánticas se obtienen a partir de las existenciales positivas. La equivalencia en la dirección contraria se obtiene transformando una fórmula existencial positiva en una fórmula diofántica que defina el mismo conjunto usando repetidamente las siguientes sustituciones: Cada ecuación polinómica de la forma 𝑝=𝑞 se transforma en 𝑝−𝑞=0. Las conjunciones de polinomios 𝑝=0∧𝑞=0 se transforman en la ecuación 𝑓(𝑝,𝑞)=0. Las disyunciones de polinomios 𝑝=0∨𝑞=0 se transforman en la ecuación 𝑔(𝑝,𝑞)=0. 116 Ejemplo 7.11 (Equivalencia en dominios de integridad) A partir de la proposición 7.10, se puede probar que en los dominios de integridad cuyo cuerpo de fracciones no es algebraicamente cerrado (los polinomios en el cuerpo de fracciones no necesariamente tienen imágenes en el cuerpo) se pueden construir polinomios 𝑓 y 𝑔 adecuados, de modo que para este tipo de estructuras se tiene la equivalencia entre conjuntos diofánticos y existenciales positivos. Definición 7.12 (Teoría de primer orden) Finalmente, llamamos teoría (existencial positiva) de primer orden de 𝑅 en el lenguaje de los anillos al conjunto de todas las oraciones (existenciales positivas) de primer orden en el lenguaje que son ciertas cuando las variables de la oración recorren los elementos de 𝑅 .La denominación completa de este concepto es usualmente acortada a tan solo teoría. Así pues, la teoría (existencia positiva) se dice que es decidible si existe una máquina de Turing que toma como entrada una oración (existencial positiva) de primer orden y determina si esta pertenece o no a la teoría. Nótese que esta es la noción de decidibilidad usual con la que hemos estado trabajando previamente. De hecho, gracias al resultado previo que establece la equivalencia de conjuntos existenciales positivos y conjuntos diofánticos, podemos afirmar que la respuesta negativa al décimo problema de Hilbert es un resultado equivalente a la indecidibilidad de la teoría existencial positiva de ℤ. Cabe destacar que la decidibilidad de la teoría de primer orden de un anillo es consecuencia de la eliminación efectiva de cuantificadores en algún lenguaje del anillo, que posiblemente puede haber sido ampliado. Con «eliminación de cuantificadores» nos referimos a un proceso tal que para una fórmula de primer orden dada, 𝜙 , que tiene unas ciertas variables ligadas 𝑥𝘪 y otras libres 𝑦𝘫 , buscamos otra fórmula diferente 𝜓 que tan solo usa como argumentos las variables libres 𝑦𝘫 y no tiene ningún cuantificador; y además el conjunto de variables ( 𝑦𝟣,…,𝑦𝘮 ) para las cuales 𝜙 es cierta se corresponde con el conjunto para las cuales 𝜓 es cierta. Decimos además que la eliminación es efectiva si hay una máquina de Turing que tiene a 𝜙 como entrada y devuelve como salida una posible 𝜓 adecuada. De esta forma, si una teoría admite una eliminación efectiva y la veracidad de las fórmulas sin cuantificadores es decidible, entonces la teoría es decidible. Una vez que tenemos la decidibilidad de la teoría, entonces por los resultados que hemos desarrollado antes podemos seguir la decidibilidad del problema décimo adaptado al anillo pertinente. 117 7.2.2 El décimo problema en algunos anillos La formulación del problema décimo para un anillo arbitrario 𝑅 es como sigue: dado un polinomio 𝑓 ∈ℤ[𝑥𝟣,…,𝑥𝘯] , encontrar un algoritmo tal que devuelva una respuesta de tipo sí/no dependiendo de si ∃(𝑎𝟣,…,𝑎𝘯)∈𝑅𝘯∶ 𝑓(𝑎𝟣,…,𝑎𝘯)=0 . En particular, si 𝑆⊆𝑅 entonces podemos definir también un décimo problema de Hilbert sobre 𝑅 con coeficientes en 𝑆 de forma análoga a la que acabamos de presentar, salvo que ahora consideramos dado 𝑓 ∈ 𝑆[𝑥𝟣,…,𝑥𝘯] (en lugar de 𝑓 ∈ ℤ[𝑥𝟣,…,𝑥𝘯] como antes). Estamos asumiendo para esto que hay especificada un sistema de codificación para los elementos de 𝑆. A continuación, vamos a exponer en una tabla una esquematización de los resultados actualmente conocidos concernientes a la decidibilidad del problema décimo en diferentes anillos. En dicha tabla, a parte de los anillos habituales, también vamos a considerar el cuerpo ℚ𝘱 de números 𝑝 -ádicos (resultante de intercambiar en ℚ la norma euclídea por el valor absoluto 𝑝 - ádico, |𝑥|𝘱=𝑝−𝘷𝘱(𝘹) donde 𝑣𝘱(𝑥) es el exponente de 𝑝 en la descomposición de 𝑥 en factores primos); los cuerpos numéricos, que son extensiones finitas 𝐾⊂ ℚ ; los anillos de enteros 𝒪𝘒 definidos como la clausura de ℤ en 𝐾 extensión finita; el cuerpo de funciones globales que son las extensiones finitas de los cuerpos de funciones racionales 𝔽𝘱(𝑡) ; y los cuerpos 𝑝 -ádicos, que son las extensiones finitas de los cuerpos ℚ𝘱 (en todo momento hemos usado 𝑝 para denotar un número primo arbitrario). Recordamos antes también que la decidibilidad de la teoría de primer orden en 𝑅 implica la decidibilidad del problema décimo en el anillo, y por el contrarecíproco también la indecidibilidad del problema implica la indecidibilidad de la teoría. Siguiendo pues el tema con que finalizamos el anterior apartado, vamos a terminar hablando brevemente de la eliminación de cuantificadores en algunos de los anillos que aparecerán en la tabla. Desde el siglo 19, ya era un hecho conocido que ℂ en el lenguaje de anillos tiene una eliminación efectiva de cuantificadores, salvo que no se había terminado de relacionar la utilidad de este hecho con la decidibilidad de la teoría del anillo. De hecho, en general, hay una eliminación de cuantificadores para cualquier cuerpo cerrado 𝐾 . Esto es un resultado equivalente al teorema de Chevalley en geometría algebraica: Teorema 7.13 (Teorema de Chevalley) La imagen de un conjunto constructible a través de una proyección es también constructible. Un subconjunto de 𝐾𝘯 ( 𝐾 un cuerpo algebraicamente cerrado) se dice constructible si es una combinación booleana de conjuntos con la forma { 118