(A la parte 11 - A la parte 13)
Infinito potencial e infinito actual
En esta parte y en la siguiente vamos a estudiar el contexto histórico en el que Gödel desarrolló sus teoremas, paso indispensable para comprender cabalmente el enunciado de esos teoremas. La historia, curiosamente, comienza en el infinito.
¿Qué queremos decir cuando, en geometría, afirmamos que una recta es infinita? Hoy en día esta afirmación suele entenderse en el sentido de que la recta se prolonga indefinidamente en ambas direcciones y que tiene por lo tanto una longitud efectivamente infinita.
Sin embargo, no siempre los matemáticos interpretaron de esta manera la idea de infinitud. Hacia el siglo III a.C. Euclides de Alejandría reunió gran parte del saber geométrico de su época en una única obra, que llamó Elementos. Euclides estructuró estos conocimientos geométricos en un sistema axiomático, basado en unos pocos axiomas de los que todos los demás resultados se deducían como teoremas. Siguiendo una idea de Aristóteles, los axiomas de Euclides estaban divididos en dos grupos: las Nociones Comunes y los Postulados.
Las Nociones Comunes (cuya cantidad exacta varía según las ediciones de Elementos) son principios generales del razonamiento, válidos en cualquier contexto, como por ejemplo que “dos cosas iguales a una tercera son iguales entre sí”. Los Postulados, en cambio, son axiomas propios de la Geometría. Su número también varía con las ediciones, pero la tradición más difundida asegura que son cinco y el segundo de ellos afirma que “una recta puede prolongarse por cualquiera de sus extremos”.
Ahora bien ¿cómo puede prolongarse una recta si ya es de por sí infinita? Es que para Euclides una recta no es una línea infinita (en el sentido en que hoy en día se entiende esta palabra), sino que es un segmento de longitud finita que puede ser prolongado tanto como se quiera. Vemos aquí claramente las dos concepciones posibles del infinito: la llamada “concepción potencial” y la “concepción actual”.
En la concepción potencial, el infinito siempre existe en potencia, nunca en acto. Este punto de vista sostiene que podemos acercarnos al infinito tanto como queramos, pero que nunca podremos alcanzarlo realmente. Ésta es, precisamente, la concepción que Euclides revela en su segundo postulado: una recta es un segmento de longitud siempre finita que puede prolongarse tanto como se requiera. Dentro de la misma idea, cuando Euclides, también en Elementos enuncia que existen infinitos primos, lo dice así: se puede superar cualquier cantidad dada de números primos. La noción de límite en el Análisis muestra otro ejemplo de concepción potencial del infinito.
Por el contrario, en la concepción actual del infinito (“actual” en el sentido de “en acto”, no en el sentido de “moderno”) la infinitud es, de hecho, alcanzable. Desde este punto de vista, cuando decimos que una recta es infinita queremos decir que su longitud es realmente infinita, y que la línea se extiende indefinidamente en ambas direcciones (y, por ende, no puede ser prolongada). Por otra parte, cuando decimos que hay infinitos números primos es que hay infinitos.
A lo largo de casi toda la historia de la Matemática, desde la Antigüedad Clásica y hasta más o menos el año 1872, la única concepción del infinito considerada como válida era la del infinito potencial. A modo de ejemplo, en 1831 Carl F. Gauss había escrito: “Protesto contra el uso de una cantidad infinita como si fuera una entidad real, esto nunca se permite en las matemáticas. El infinito es sólo una manera de hablar, en la cual propiamente se habla de los límites a los que ciertas razones pueden acercarse tanto como se desee.” El infinito actual era unánimemente rechazado.
En 1872, sin embargo, en el marco de una investigación sobre series de Fourier, el matemático ruso Georg Cantor (1) fue llevado a introducir la idea de infinito actual (2). Desde ese año y hasta 1897 Cantor publicó una serie de artículos en los que investigó y en los que, además, introdujo por primera vez en la historia la noción de conjunto. Cantor define la noción de conjunto de la siguiente manera: “Por conjunto entendemos cualquier reunión en un todo M de objetos bien definidos e individualizados de nuestra intuición o nuestro pensamiento. Estos objetos serán llamados los elementos de M”.
Tal como era de esperar, la teoría de Cantor generó grandes controversias, especialmente en los círculos científicos más conservadores de la Alemania de esa época y muy especialmente de parte del muy influyente y muy conservador Leopold Kronecker (3). Sin embrago, a pesar de esta oposición, lentamente la teoría de conjuntos cantoriana fue ganando adeptos y, hacia fines del siglo XIX, se había transformado en una herramienta central de la Matemática. (4) Por ejemplo, muchas ramas del Análisis Matemático creadas a fines del siglo XIX y principios del XX se apoyaban fuertemente en la noción de conjunto. Por otra parte, cada uno de ellos independientemente de los otros, el propio Cantor, Richard Dedekind y Gottlob Frege se propusieron el objetivo de fundamentar toda la Matemática en la teoría de conjuntos. En los tres casos, los números enteros positivos eran definidos como las cantidades de elementos (o cardinales) de los conjuntos finitos y las operaciones numéricas eran entonces definidas a partir de las operaciones conjuntistas.
Podemos decir que a principios del siglo XX la teoría de conjuntos Cantor se había transformado en la columna vertebral de todos los nuevos desarrollos en Matemática. La crisis, la llamada Crisis de los Fundamentos, se precipita cuando se descubre que la teoría de Cantor es inconsistente.
En 1902 Bertrand Russell descubre la llamada “Paradoja de Russell”, que demuestra que la noción misma de conjunto, tal como la define Cantor es contradictoria. Veamos la explicación de la paradoja. Todo conjunto no vacío tiene elementos. Pensemos, por ejemplo, en un conjunto formado por tres caballos, sus elementos son esos tres caballos. Pero el conjunto en sí mismo no es caballo, por lo que el conjunto no es elemento de sí mismo. Otro ejemplo, el conjunto {1,2} tiene como elementos al número 1 y al número 2, pero ni el número 1 ni el 2 es {1,2}, luego {1,2} no es elemento de sí mismo.
¿Hay conjuntos que sean elementos de sí mismos? Sí los hay. Por ejemplo, el conjunto formado por todos los conjuntos es también un conjunto y, por lo tanto, es elemento de sí mismo. El conjunto de todas las ideas abstractas es también una idea abstracta, por lo tanto es también elemento de sí mismo.
Ahora bien dado que, según Cantor, podemos reunir en un conjunto objetos cualesquiera de nuestra intuición o nuestro pensamiento, podemos entonces definir el conjunto R cuyos elementos son todos los conjuntos que no son elementos de sí mismos.
R = {A : A no es elemento de sí mismo}
¿Es R elemento de sí mismo?
Si R fuera elemento de sí mismo, entonces no cumpliría la condición que define a R y, por lo tanto, R sería elemento de R. Es decir, si R fuera elemento de sí mismo entonces no sería elemento de sí mismo. Esto es una contradicción.
Deducimos del párrafo anterior que R no puede ser elemento de sí mismo. Pero si R no fuese elemento de sí mismo, entonces cumpliría con la condición que define a R y en consecuencia sería elemento de R. Entonces, si R fuese elemento de sí mismo deduciríamos que no lo es. Otra contradicción. (5)
La contradicción es inevitable, por lo tanto es la Teoría de Conjuntos la que es en sí misma contradictoria. Este descubrimiento precipitó una gran crisis en la Matemática, tanto más porque, como dijimos antes, la Teoría de Conjuntos se había transformado en uno de sus pilares centrales. (6) ¿Qué sucedió entonces? Eso es lo que veremos en la próxima parte.
Notas:
(1) Georg Cantor nació en San Petersburgo, Rusia, en 1845, aunque estudió y vivió casi toda su vida en Alemania. Cantor murió en Halle, Alemania, en 1918.
(2) La idea del infinito actual era contraria a toda la educación que había recibido Cantor como matemático y no le resultó fácil aceptar esa noción como válida. Cantor escribió en 1883: “La idea de considerar lo infinitamente grande no sólo en la forma de una magnitud que se incrementa ilimitadamente [...] sino también de fijarlo matemáticamente por medio de números en la forma definida del infinito absoluto me fue impuesta lógicamente, casi contra mi voluntad puesto que es contraria a las tradiciones que yo había llegado a venerar en el curso de muchos años de esfuerzos e investigaciones científicas.”
(3) Kronecker llevó su antagonismo mucho más allá del terreno puramente intelectual, presionando a las revistas alemanas para que no publicaran artículos de Cantor y a las principales universidades para que no lo admitieran en su plantel docente.
(4) Se atribuye al físico Max Planck la idea de que si una noción científica controvertida logra a la postre imponerse, este éxito no se debe a que quienes se oponían a la idea llegan finalmente se convencerse de ella, sino a que los que se oponían eventualmente mueren y nace una nueva generación de científicos para quienes esa idea no es revolucionaria pues “siempre estuvo allí”. Ciertamente éste es el caso de la teoría de Cantor. Leopold Kronecker, su gran enemigo, falleció en 1891, mientras que David Hilbert, quien fuera su gran defensor, nació en 1862 y tenía 10 años de edad cuando Cantor publicó sus primeros artículos sobre el infinito.
(5) Posteriormente, Bertrand Russell dio una versión popularizada de esta paradoja. Pensemos, dijo Russell, en un pueblo en que hay un solo barbero, que afeita a todos los hombres que no afeitan a sí mismos. Ahora bien, el barbero, que es también un hombre ¿debe afeitarse a sí mismo? Como en el caso del conjunto R, se llega a conclusión de que se afeitará a sí mismo si y sólo si no se afeitará a sí mismo.
(6) La Teoría de Conjuntos de Cantor es hoy en día conocida como Teoría Ingenua o Teoría Intuitiva de Conjuntos. Hasta donde se sabe, en esta teoría sólo aparecen contradicciones cuando se trabaja con conjuntos “muy grandes” como el conjunto de todos los conjuntos. La actual teoría de conjuntos (la teoría “oficial”) es la Teoría Axiomática de Zermelo-Fraenkel. En esta teoría se hace una distinción entre “conjuntos” y “clases propias”. A cada propiedad le corresponde una “clase”, algunas clases pueden elementos de clases más grandes, a esas clases se las llama “conjuntos”. Otras clases no pueden ser elementos de ninguna otra clase y se las llama “clases propias”. Ningún conjunto es elemento de sí mismo. Estas distinciones de lenguaje evitan la paradoja de Russell. La clase de todos los conjuntos que no son elementos de sí mismo coincide con la clase de todos los conjuntos y, como es una clase propia, no es elemento de sí misma (ni de ninguna otra clase) sin que haya en ello ninguna contradicción.
(A la parte 11 - A la parte 13)
31.10.06
17.10.06
Gödel y Turing (Parte 11)
(A la parte 10 - A la parte 12)
¿Qué es lo que no dice el Teorema de Gödel?
Suele decirse en los textos de divulgación que el Teorema de Gödel (1) asegura que todo sistema axiomático que sea suficientemente amplio como para contener a la Aritmética (2) tiene necesariamente enunciados indecidibles, es decir, enunciados que no pueden ser demostrados ni refutados a partir de los axiomas (3).
Pues bien, debo decirles que esto que los textos de divulgación dicen casi unánimemente y que, a causa de ello, ha siso repetido tantas veces por aquí y por allí, no es verdad. El Teorema de Gödel no afirma lo que dijimos más arriba. Más aún, no solamente el Teorema de Gödel no afirma eso, sino que, además, lo que dijimos en el párrafo anterior es, de hecho, falso. Es decir, no es cierto que todo sistema axiomático lo suficientemente amplio como para contener a la Aritmética, deba tener necesariamente enunciados indecidibles.
Tomemos por ejemplo el siguiente sistema de axiomas para la suma y producto de números enteros positivos (4) y que, de hecho, contiene a la Aritmética, en el sentido de que permite demostrar todas las propiedades básicas de la suma y el producto.
En estos axiomas se mencionan como elementos primitivos (5) al conjunto N de todos los enteros positivos, al número 1, a la función Sig(x) (que a cada número x le hace corresponder su siguiente en la secuencia de los números naturales) y a las operaciones de suma y producto:
Ax.1: Si x = y entonces Sig(x) = Sig(y).
Ax.2: Si Sig(x) = Sig(y) entonces x = y.
Ax.3: Para ningún x sucede que 1 = Sig(x).
Ax.4: Para todo x vale que x + 1 = Sig(x).
Ax.5: Para todo x e y vale que x + Sig(y) = Sig(x + y).
Ax.6: Para todo x vale que x.1 = x.
Ax.7: Para todo x e y vale que x.Sig(y) = x.y + Sig(y).
Ax.8: Si A es un conjunto tal que 1 es elemento de A y tal que para todo x vale que si x es elemento de A entonces Sig(x) también lo es, entonces A = N.
Pues bien, puede demostrarse (6) que todo afirmación aritmética puede, o bien probarse, o bien refutarse a partir de estos axiomas. No hay en este sistema axiomático afirmaciones indecidibles. Este ejemplo muestra que aquello que, según los textos de divulgación afirma el Teorema de Gödel, es falso.
¿Qué dice entonces realmente el Teorema de Gödel? Recordemos que en la primera parte (hace ya mucho tiempo) dijimos que el Teorema de Gödel afirma que en cualquier sistema axiomático que contenga a la Aritmética y que respete ciertas restricciones formales (que en aquél momento no especifiqué) existen necesariamente enunciados indecidibles. Es evidente entonces que los axiomas indicado más arriba no respetan esas restricciones formales ¿Cuáles son entonces esas restricciones y cuál es su interés? Eso es precisamente lo que empezaremos a estudiar en la próxima entrada.
Notas:
(1) Con más precisión el Primer Teorema de Incompletitud de Gödel.
(2) La Aritmética, o Teoría Elemental de Números, es la teoría que habla de las propiedades de la suma y el producto de números enteros. A los efectos que nos interesa es suficiente hablar solamente de enteros positivos.
(3) Un enunciado P es indecidible si no es posible demostrar P a partir de los axiomas del sistema, pero tampoco es posible demostrar la negación de P.
(4) Estos axiomas son una ligera variante de los Axiomas de Peano, propuestos por el matemático italiano Giusepe Peano a fines del siglo XIX.
(5) Todo sistema axiomático tiene símbolos primitivos o no definidos. A estos símbolos se les puede asignar cualquier significado, siempre que sea coherente con lo enunciado en los axiomas.
(6) Véase G.S.Boolos & R.C.Jefrrey, Computability and Logic, Cambridge University
Press, 1980. En particular, si la Conjetura de Goldbach fuese verdadera, existiría uan demostración de ella a partir de estos axiomas, esto refuta buena parte del argumento de la novela El Tío Petros y la Conjetura de Goldbach.
Addenda:
Dentro del contexto de los Axiomas de Peano definamos 2 = Sig(1), 3 = Sig(2) y 4 = Sig(3). Ésta es una demostración de que 2 + 2 = 4:
2 + 2 = 2 + Sig(1) = Sig(2 + 1) = Sig(Sig(2)) = Sig(3) = 4
(A la parte 10 - A la parte 12)
¿Qué es lo que no dice el Teorema de Gödel?
Suele decirse en los textos de divulgación que el Teorema de Gödel (1) asegura que todo sistema axiomático que sea suficientemente amplio como para contener a la Aritmética (2) tiene necesariamente enunciados indecidibles, es decir, enunciados que no pueden ser demostrados ni refutados a partir de los axiomas (3).
Pues bien, debo decirles que esto que los textos de divulgación dicen casi unánimemente y que, a causa de ello, ha siso repetido tantas veces por aquí y por allí, no es verdad. El Teorema de Gödel no afirma lo que dijimos más arriba. Más aún, no solamente el Teorema de Gödel no afirma eso, sino que, además, lo que dijimos en el párrafo anterior es, de hecho, falso. Es decir, no es cierto que todo sistema axiomático lo suficientemente amplio como para contener a la Aritmética, deba tener necesariamente enunciados indecidibles.
Tomemos por ejemplo el siguiente sistema de axiomas para la suma y producto de números enteros positivos (4) y que, de hecho, contiene a la Aritmética, en el sentido de que permite demostrar todas las propiedades básicas de la suma y el producto.
En estos axiomas se mencionan como elementos primitivos (5) al conjunto N de todos los enteros positivos, al número 1, a la función Sig(x) (que a cada número x le hace corresponder su siguiente en la secuencia de los números naturales) y a las operaciones de suma y producto:
Ax.1: Si x = y entonces Sig(x) = Sig(y).
Ax.2: Si Sig(x) = Sig(y) entonces x = y.
Ax.3: Para ningún x sucede que 1 = Sig(x).
Ax.4: Para todo x vale que x + 1 = Sig(x).
Ax.5: Para todo x e y vale que x + Sig(y) = Sig(x + y).
Ax.6: Para todo x vale que x.1 = x.
Ax.7: Para todo x e y vale que x.Sig(y) = x.y + Sig(y).
Ax.8: Si A es un conjunto tal que 1 es elemento de A y tal que para todo x vale que si x es elemento de A entonces Sig(x) también lo es, entonces A = N.
Pues bien, puede demostrarse (6) que todo afirmación aritmética puede, o bien probarse, o bien refutarse a partir de estos axiomas. No hay en este sistema axiomático afirmaciones indecidibles. Este ejemplo muestra que aquello que, según los textos de divulgación afirma el Teorema de Gödel, es falso.
¿Qué dice entonces realmente el Teorema de Gödel? Recordemos que en la primera parte (hace ya mucho tiempo) dijimos que el Teorema de Gödel afirma que en cualquier sistema axiomático que contenga a la Aritmética y que respete ciertas restricciones formales (que en aquél momento no especifiqué) existen necesariamente enunciados indecidibles. Es evidente entonces que los axiomas indicado más arriba no respetan esas restricciones formales ¿Cuáles son entonces esas restricciones y cuál es su interés? Eso es precisamente lo que empezaremos a estudiar en la próxima entrada.
Notas:
(1) Con más precisión el Primer Teorema de Incompletitud de Gödel.
(2) La Aritmética, o Teoría Elemental de Números, es la teoría que habla de las propiedades de la suma y el producto de números enteros. A los efectos que nos interesa es suficiente hablar solamente de enteros positivos.
(3) Un enunciado P es indecidible si no es posible demostrar P a partir de los axiomas del sistema, pero tampoco es posible demostrar la negación de P.
(4) Estos axiomas son una ligera variante de los Axiomas de Peano, propuestos por el matemático italiano Giusepe Peano a fines del siglo XIX.
(5) Todo sistema axiomático tiene símbolos primitivos o no definidos. A estos símbolos se les puede asignar cualquier significado, siempre que sea coherente con lo enunciado en los axiomas.
(6) Véase G.S.Boolos & R.C.Jefrrey, Computability and Logic, Cambridge University
Press, 1980. En particular, si la Conjetura de Goldbach fuese verdadera, existiría uan demostración de ella a partir de estos axiomas, esto refuta buena parte del argumento de la novela El Tío Petros y la Conjetura de Goldbach.
Addenda:
Dentro del contexto de los Axiomas de Peano definamos 2 = Sig(1), 3 = Sig(2) y 4 = Sig(3). Ésta es una demostración de que 2 + 2 = 4:
2 + 2 = 2 + Sig(1) = Sig(2 + 1) = Sig(Sig(2)) = Sig(3) = 4
(A la parte 10 - A la parte 12)
12.10.06
Gödel y Turing (Parte 10)
(A la parte 9 - A la parte 11)
Más sobre conjuntos recursivamente numerables
Veremos esta vez algunas cuestiones técnicas que nos serán de utilidad un poco más adelante.
Hablábamos en la parte anterior sobre conjuntos recursivos y conjuntos recursivamente numerables. Recordemos que un conjunto A es recursivo si existe un algoritmo que, dado un número n, nos permite determinar (en una cantidad finita de tiempo) si n pertenece o no pertenece al conjunto A (el tiempo que demore el algoritmo en dar una respuesta puede ser extremadamente largo, eso no importa siempre que sea finito).
Definición: Diremos que un algoritmo decide al conjunto A si admite como entrada válida a cualquier número n y da como salida un “sí” en caso de que n pertenezca a A y un “no” en caso contrario. (Si lo quisiéramos expresar en términos de máquinas de Turing, podríamos decir que la salida es # si n pertenece a A y ## en caso contrario.)
Es claro que A es recursivo si y sólo si existe un algoritmo que lo decide.
Un conjunto A, por otra parte, es recursivamente numerable si es posible programar a la Computadora Permanente (una computadora teórica que permanece encendida por tiempo indefinido imprimiendo números de tanto en tanto) de tal modo que todo número que la computadora imprime pertenece al conjunto A y tal que, además, pueda asegurarse todo elemento de A será impreso al menos una vez, aunque para que ello debamos esperar millones de años. (Para más detalles y ejemplos, véase la parte anterior.)
Vimos también que todo conjunto recursivo es recursivamente numerable, pero que existen conjuntos que son recursivamente numerables pero no recursivos. Específicamente vimos que si se numeran algorítmicamente todas las máquinas de Turing como T1, T2, T3,... entonces el conjunto de todos los n que son entradas válidas para Tn es recursivamente numerable, pero no recursivo.
Nuestra intención en esta parte es mostrar que existen conjuntos que no son ni siquiera recursivamente numerables.
Si A es un conjunto (siempre pensaremos en conjuntos formados por números enteros positivos), se llama complemento de A al conjunto formado por todos los números que no pertenecen a A. Por ejemplo, el complemento del conjunto de todos los números pares es el conjunto de los números impares; el complemento del conjunto de los números terminados en 5 es el conjunto de los números terminados en cualquiera de las otras nueve cifras, etc.
Un hecho obvio, pero fundamental, es que cualquiera sea el conjunto A todo número n pertenece, o bien a A, o bien a su complemento, y nunca a los dos a la vez.
Propiedad: Si A es un conjunto recursivo entonces su complemento también es recursivo.
En efecto, si A es recursivo entonces existe un algoritmo que lo decide. Tomemos el mismo algoritmo, pero agreguemos una instrucción que transforme el “sí” en “no” y viceversa, obtendremos así un algoritmo que decide el complemento de A.
Propiedad: Si A y su complemento son ambos recursivamente numerables entonces A es recursivo.
En efecto, si A y su complemento son ambos recursivamente numerables entonces existen dos Computadoras Permanentes, una que imprime los elementos de A y otra que imprime los de su complemento. Ahora bien, y esto es esencial, dado cualquier número n, éste número, al cabo de una cantidad finita de tiempo, será impreso por una y sólo una de las dos computadoras. El algoritmo para decidir A es entonces el siguiente: cuando le den un número n, ponga a andar las dos Computadoras Permanentes a la vez, la de A y la de su complemento, y espere a que n sea impreso por alguna de las dos (tarde o temprano esto sucederá). Si lo imprime la Computadora de A la salida es “sí”, si lo imprime la otra computadora la respuesta es “no”. (El argumento precedente falla si se tiene solamente una de las Computadoras Permanentes, pues no se tendría la garantía de obtener una respuesta al cabo de una cantidad finita de tiempo.)
Propiedad: Si A es recursivamente numerable, pero no recursivo entonces el complemento de A no es ni siquiera recursivamente numerable.
Esto es una consecuencia de la propiedad anterior. Si el complemento de A fuese también recursivamente numerable, entonces A sería recursivo.
Dijimos antes que el conjunto de todos los números n que cumplen la propiedad “n es entrada válida para la máquina Tn” es recursivamente numerable, pero no recursivo. En razonamiento precedente nos dice que el conjunto de todos los n que cumplen que “n no es entrada válida para Tn” no es ni siquiera recursivamente numerable. Si intentamos programar la Computadora Permanente para que imprima estos valores de n entonces fallará, es decir, o bien imprimirá números que no pertenecen al conjunto, o bien nunca imprimirá algunos de los números que sí están, no importa cuánto tiempo esperemos.
Llegados a este punto ya estamos en condiciones de enunciar e incluso demostrar el Primer Teorema de Incompletitud de Gödel. Sin embargo, para entenderlo cabalmente resulta conveniente conocer el contexto histórico en el que Kurt Gödel llevó adelante su idea. En la parte 12 acometeremos la tarea de comprender ese contexto histórico. En la parte 11 haremos una aclaración importante.
(A la parte 9 - A la parte 11)
Más sobre conjuntos recursivamente numerables
Veremos esta vez algunas cuestiones técnicas que nos serán de utilidad un poco más adelante.
Hablábamos en la parte anterior sobre conjuntos recursivos y conjuntos recursivamente numerables. Recordemos que un conjunto A es recursivo si existe un algoritmo que, dado un número n, nos permite determinar (en una cantidad finita de tiempo) si n pertenece o no pertenece al conjunto A (el tiempo que demore el algoritmo en dar una respuesta puede ser extremadamente largo, eso no importa siempre que sea finito).
Definición: Diremos que un algoritmo decide al conjunto A si admite como entrada válida a cualquier número n y da como salida un “sí” en caso de que n pertenezca a A y un “no” en caso contrario. (Si lo quisiéramos expresar en términos de máquinas de Turing, podríamos decir que la salida es # si n pertenece a A y ## en caso contrario.)
Es claro que A es recursivo si y sólo si existe un algoritmo que lo decide.
Un conjunto A, por otra parte, es recursivamente numerable si es posible programar a la Computadora Permanente (una computadora teórica que permanece encendida por tiempo indefinido imprimiendo números de tanto en tanto) de tal modo que todo número que la computadora imprime pertenece al conjunto A y tal que, además, pueda asegurarse todo elemento de A será impreso al menos una vez, aunque para que ello debamos esperar millones de años. (Para más detalles y ejemplos, véase la parte anterior.)
Vimos también que todo conjunto recursivo es recursivamente numerable, pero que existen conjuntos que son recursivamente numerables pero no recursivos. Específicamente vimos que si se numeran algorítmicamente todas las máquinas de Turing como T1, T2, T3,... entonces el conjunto de todos los n que son entradas válidas para Tn es recursivamente numerable, pero no recursivo.
Nuestra intención en esta parte es mostrar que existen conjuntos que no son ni siquiera recursivamente numerables.
Si A es un conjunto (siempre pensaremos en conjuntos formados por números enteros positivos), se llama complemento de A al conjunto formado por todos los números que no pertenecen a A. Por ejemplo, el complemento del conjunto de todos los números pares es el conjunto de los números impares; el complemento del conjunto de los números terminados en 5 es el conjunto de los números terminados en cualquiera de las otras nueve cifras, etc.
Un hecho obvio, pero fundamental, es que cualquiera sea el conjunto A todo número n pertenece, o bien a A, o bien a su complemento, y nunca a los dos a la vez.
Propiedad: Si A es un conjunto recursivo entonces su complemento también es recursivo.
En efecto, si A es recursivo entonces existe un algoritmo que lo decide. Tomemos el mismo algoritmo, pero agreguemos una instrucción que transforme el “sí” en “no” y viceversa, obtendremos así un algoritmo que decide el complemento de A.
Propiedad: Si A y su complemento son ambos recursivamente numerables entonces A es recursivo.
En efecto, si A y su complemento son ambos recursivamente numerables entonces existen dos Computadoras Permanentes, una que imprime los elementos de A y otra que imprime los de su complemento. Ahora bien, y esto es esencial, dado cualquier número n, éste número, al cabo de una cantidad finita de tiempo, será impreso por una y sólo una de las dos computadoras. El algoritmo para decidir A es entonces el siguiente: cuando le den un número n, ponga a andar las dos Computadoras Permanentes a la vez, la de A y la de su complemento, y espere a que n sea impreso por alguna de las dos (tarde o temprano esto sucederá). Si lo imprime la Computadora de A la salida es “sí”, si lo imprime la otra computadora la respuesta es “no”. (El argumento precedente falla si se tiene solamente una de las Computadoras Permanentes, pues no se tendría la garantía de obtener una respuesta al cabo de una cantidad finita de tiempo.)
Propiedad: Si A es recursivamente numerable, pero no recursivo entonces el complemento de A no es ni siquiera recursivamente numerable.
Esto es una consecuencia de la propiedad anterior. Si el complemento de A fuese también recursivamente numerable, entonces A sería recursivo.
Dijimos antes que el conjunto de todos los números n que cumplen la propiedad “n es entrada válida para la máquina Tn” es recursivamente numerable, pero no recursivo. En razonamiento precedente nos dice que el conjunto de todos los n que cumplen que “n no es entrada válida para Tn” no es ni siquiera recursivamente numerable. Si intentamos programar la Computadora Permanente para que imprima estos valores de n entonces fallará, es decir, o bien imprimirá números que no pertenecen al conjunto, o bien nunca imprimirá algunos de los números que sí están, no importa cuánto tiempo esperemos.
Llegados a este punto ya estamos en condiciones de enunciar e incluso demostrar el Primer Teorema de Incompletitud de Gödel. Sin embargo, para entenderlo cabalmente resulta conveniente conocer el contexto histórico en el que Kurt Gödel llevó adelante su idea. En la parte 12 acometeremos la tarea de comprender ese contexto histórico. En la parte 11 haremos una aclaración importante.
(A la parte 9 - A la parte 11)
Suscribirse a:
Entradas (Atom)