Adenda a "¿La mente humana?"

Con respecto a la entrada ¿La mente humana?, hace unos días recibí un mensaje privado de Hernán Echegoyemberry en el que, y se lo agradezco, me menciona que había allí un error de tipeo que cambiaba completamente el sentido de una frase; error que, merced a esa observación, ya fue corregido.

La frase en cuestión dice: "el teorema de Gödel implica que hay problemas que no son resolubles algorítmicamente". Ahora bien, en referencia a ella, en su mensaje privado Hernán agrega: eso aplica más para el teorema de Turing pero se entiende el punto. Quiero aprovechar este comentario de Hernán para hacer un agregado a la entrada original, un agregado que en aquel momento preferí omitir para no desviarme del tema central.

Es verdad que se le atribuye a Alan Turing (con justicia hay que decir) el descubrimiento de que existen problemas matemáticos que no son resolubles algorítmicamente; concretamente Turing probó que el Halting Problem es irresoluble. Pero no es menos cierto que la existencia de problemas matemáticos que no son resolubles algorítmicamente también se deduce (como dije en la entrada original) del teorema de incompletitud de Gödel. Veamos...

El teorema de Gödel dice que no es posible dar un sistema de axiomas para la Aritmética que sea al mismo tiempo consistente, recursivo y completo. "Consistente" significa que no existe un enunciado P tal que tanto P como su negación sean demostrables. "Recursivo" significa que existe un algoritmo que reconoce si un enunciado es, o no, un axioma. "Completo" es que para todo enunciado P, o bien él, o bien su negación, es demostrable.

Supongamos ahora que propongo como sistema de axiomas a todos los enunciados aritméticos verdaderos. No es difícil probar que este sistema es consistente y completo (ambas características se deducen del hecho de que todos los enunciados verdaderos, y sólo los verdaderos, resultan ser demostrables). Por el teorema de Gödel, entonces, el sistema no puede ser recursivo. En otras palabras, no existe un algoritmo que permita decidir si un enunciado es, o no, un axioma; es decir: no existe un algoritmo que permita decidir si un enunciado aritmético es, o no, verdadero. El problema de determinar la verdad de un enunciado aritmético no es resoluble algorítmicamente.

Ahora bien, si Gödel demostró su teorema en 1931 y el trabajo de Turing es de 1937 ¿por qué se le atribuye a Turing el descubrimiento? Porque en su artículo Gödel propone una definición posible de la idea de algoritmo "aritmético", pero reconoce que no está claro que su definición abarque todos los algoritmos posibles (de hecho, según se vio después, no los abarca). El gran mérito de Turing fue el haber dado una definición (una "modelización matemática", según la idea de la entrada anterior) de la idea de algoritmo lo suficientemente amplia como para abarcar (hasta donde se sabe) a todos los algoritmos posible. Es por eso que, recién después del trabajo de Turing pudo darse por demostrado la existencia de problemas no resolubles algorítmicamente; y fue asimismo después del trabajo de Turing (según Gödel reconoció en una posdata a su artículo) que pudo establecerse el alcance real del teorema de Gödel.

Un último comentario: así como la definición que dio Gödel para la idea de algoritmo resultó ser insuficiente, en el sentido de que hay algoritmos que la definición de Gödel no abarca, del mismo modo nada asegura que no haya algoritmos que queden "fuera" de la definición de Turing, aunque hasta el día de hoy nadie ha sido capaz de dar ni siquiera la insinuación de un ejemplo concreto.

¿La mente humana?

El año pasado Miguel Ángel, administrador del excelente y bien conocido blog Gaussianos, tuvo la gentileza de invitarme a escribir allí una entrada sobre el teorema de Gödel, la que puede leerse haciendo clic aquí. En los comentarios a esa entrada (y también en los comentarios a esta otra) surgió la cuestión de si el teorema de Gödel permite, o no, demostrar que existe una diferencia esencial entre la mente humana y una computadora. En otras palabras ¿la mente humana es "computable", o no?

En esos comentarios sostuve la postura de que el teorema de Gödel no permite demostrar que la mente humana no es computable (a pesar de que lo contrario ha sido afirmado muchas veces por pensadores muy respetables). Algunos de mis interlocutores en aquel intercambio entendieron que yo estaba afirmando que no hay una diferencia esencial entre mente y computadora, cuando en realidad simplemente estaba afirmado que el teorema de Gödel no permite demostrar que esa diferencia existe. (En el mismo sentido, afirmar que el teorema de Gödel no permite demostrar la conjetura de Goldbach no es lo mismo que afirmar que la conjetura de Goldbach sea falsa).

Ahora bien... ¿por qué el teorema de Gödel no permite demostrar que la mente humana no es computable?

El teorema de Gódel es un teorema matemático que habla de entes matemáticos (ciertos conjuntos de enunciados) y que dice que si esos objetos cumplen ciertas hipótesis específicas entonces esos entes verifican ciertas propiedades claramente enunciadas. El punto a destacar aquí es que el teorema de Gödel es un teorema matemático que habla de ciertos objetos matemáticos. Por lo tanto, para que el teorema sea aplicable a una situación cualquiera, ésta debe haber sido, previamente, modelizada matemáticamente.

El teorema de Gódel, por ejemplo, permite demostrar que existen problemas matemáticos bien definidos que no puede ser resueltos algorítmicamente. ¿Por qué? Porque existe una definición matemática del concepto de algoritmo: matemáticamente, un "algoritmo" es una "máquina de Turing". En otras palabras, las máquinas de Turing modelizan matemáticamente el concepto de algoritmo. Si se acepta que este modelo es correcto (es decir, si se acepta que verdaderamente el concepto intuitivo de algoritmo está bien representado por la idea de máquina de Turing) entonces debe aceptarse que el teorema de Gödel implica que hay problemas que no son resolubles algorítmicamente  Si hubiera algoritmos no representables por máquinas de Turing entonces esa conclusión no estaría justificada.

Creo que ahora puede verse hacia dónde voy... Para que el teorema de Gödel pueda decir algo acerca de la mente humana debería existir, previamente, una definición matemática (un modelo matemático) de la mente. Debería haber una definición que nos diga (o nos permita demostrar) qué puede hacer, o qué no puede hacer la menta humana. Todas las supuestas demostraciones de que mente humana no es computable suelen caer en la falacia de atribuirle a la mente, sin ninguna justificación, aquellas propiedades que el razonamiento necesita que verifique. (El razonamiento típico dice: un algoritmo no puede hacer H, pero la mente sí, luego mente y computadora son diferente. Pero.. ¿por qué la mente puede hacer H? Respuesta: porque sí.)

¿Cómo podría definirse matemáticamente la mente? Por ejemplo, podríamos decir que la mente es una máquina de Turing con un oráculo que resuelve el halting problem. Desde luego, si aceptáramos esta definición entonces podríamos deducir inmediatamente que existe una diferencia esencial entre mente y computadora, pero... ¿esa que hemos dado es una definición aceptable de la mente? La respuesta, creo, es "claramente no". Y mientras no haya una definición matemática, aceptable, del concepto de "mente humana" el teorema de Gödel no podrá (legítimamente, al menos) decir nada al respecto.

"Dénme un punto de apoyo y moveré el mundo", dicen que dijo Arquímedes. Parafraseando a Arquímedes, Gödel podría haber dicho; "Dénme una definición matemática de la mente y les diré si es computable o no".

Gödel y Turing (Parte 16 y última)

(A la parte 15)

Las consecuencias del primer teorema de Gödel

Uno de los temas de controversia durante la crisis de los fundamentos giraba en torno a qué razonamientos matemáticos podían considerarse aceptables. Los intuicionistas, en particular, sostenían que las reglas usuales de la lógica sólo son válidas si se aplican a conjuntos finitos y que cuando tratamos con el infinito (que ellos sólo aceptaban en sentido potencial) las reglas de razonamiento debían ser diferentes. En particular los intuicinistas rechazaban para el infinito las demostraciones por el absurdo.

El Programa de Hilbert propuso un criterio objetivo para determinar cuáles razonamientos eran válidos y cuáles no. Para cada teoría matemática debía establecerse un algoritmo que fuera capaz de distinguir entre los razonamiento correctos y los incorrectos. En realidad, ya una idea similar había tenido Leibniz dos siglos antes. Leibniz había imaginado alguna vez la posibilidad de un lenguaje formal para la lógica, lenguaje que estaría constituido de tal modo que razonar equivaliera a calcular, de tal suerte que cuando dos filósofos tuvieran alguna disputa, en lugar de discutir, simplemente calcularían.

Hilbert esperaba que estos razonamientos algorítmicos (o finitistas) fueran suficientemente potentes como para demostrar toda verdad matemática (o al menos todas las verdades de la Teoría Elemental de Números). El Primer Teorema de Gódel dio por tierra con esta esperanza.

Pero la pregunta quedó en pie y sigue en pie desde entonces, aunque ya casi nadie la plantea explícitamente ¿qué es un razonamiento matemático válido? Dijimos clases atrás que toda verdad relativa a la Teoría de Números puede demostrarse a partir de los Axiomas de Peano pero ¿qué significa en este caso la palabra “demostrar”? La respuesta que suele darse a este interrogante es vaga e intuitiva, “todo el mundo sabe” qué es un razonamiento válido. De hecho, el primer Teorema de Gödel prueba que no existe, que nunca podrá existir, un criterio objetivo y finitista para determinar si una demostración es correcta o no.

Ése es el legado de Gödel, no la incertidumbre sobre la consistencia de la Matemática (consistencia de la que nadie duda aunque no pueda darse una demostración finitista de ello), sino la imposibilidad de determinar de modo claro y conciso cuáles razonamientos matemáticos son válidos y cuáles no. La decisión última a este respecto termina siendo en general una cuestión de mayorías, las demostraciones correctas son aquellas que la mayoría de los especialista consideran como tales. Las controversias en torno a la demostración de la conjetura de Kepler son tal vez una consecuencia de este legado.

¿Es posible que en el futuro un nuevo Gödel o un nuevo Hilbert den finalmente con un criterio (no finitista por fuerza) que permita distinguir de modo claro e indubitable cuáles son los razonamientos que pueden considerarse válidos y cuáles no? ¿Podrá suceder entonces que algunas demostraciones hoy consideradas correctas dejen de ser válidas en el futuro? Esto ha sucedido ya en el pasado, en 1806, por ejemplo, Ampère demostró (y la demostración fue publicada en una revista de la época, es decir la demostración era válida en ese tiempo) que toda función continua es derivable, excepto eventualmente en algunos puntos aislados y esto fue tomado como cierto hasta que en 1872 Weierstrass mostró ante la Academia de Ciencias de Berlín un ejemplo de una función continua que no es derivable en ningún punto (Bolzano había encontrado antes otro ejemplo, pero no lo publicó) ¿Podrá suceder esto nuevamente en el futuro? Algunos responderán que no, otros dirán que sí, otros, finalmente, diremos quién sabe.

FIN

(A la parte 15)

Gödel y Turing (Parte 15 y penúltima)

(A la parte 14 - A la parte 16)

La demostración del Primer Teorema de Gödel

Supongamos que hemos dado una axiomatización finitista y consistente de la Teoría de Números, tenemos que demostrar que no puede ser completa, es decir, que existe una afirmación verdadera que no se puede demostrar a partir de los axiomas.

Recordemos que en la parte anterior hablábamos de conjuntos aritméticos. Un conjunto (que siempre supondremos formado por números enteros positivos) es aritmético si la propiedad que lo define puede expresarse en el lenguaje de primer orden de la Teoría de Números, es decir puede expresarse formalmente usando la suma, el producto y los conectivos y cuantificadores lógicos, respetando las restricciones que mencionábamos en la parte anterior.

Por ejemplo, el conjunto de los números pares es aritmético, pues la propiedad “x es par” puede expresarse en el lenguaje de primer orden de la Teoría de Números, ya que “x es par” equivale a “existe algún y tal que x = y + y”. La propiedad “x es primo” también es aritmética, ya que equivale a que “no existen números y, z tales que x = (y + 1)(z + 1)”.

Las expresiones “x es par” o “x es primo” son lo que Bertrand Russell llamaría funciones proposicionales, es decir, afirmaciones genéricas en las que aparece una variable x y en la que cada vez que x es reemplazada por un número concreto se obtiene una afirmación (o un enunciado) que, según el valor elegido, será verdadera o falsa. Si la función proposicional define un conjunto entonces es verdadera exactamente para todos los números que forman parte de ese conjunto.

Indicaremos a las funciones proposicionales como P(x) o Q(x). Así si P(x) es “x es primo” entonces P(2) es verdadera, pues 2 es primo, mientras que P(4) es falsa, pues 4 no es primo.

Supongamos que P(x) es una función proposicional que define un cierto conjunto A. Es bastante claro que la negación de P(x) definirá el complemento de A. Y dado que la negación es una operación lógica perfectamente legítima en un lenguaje de primer orden (y que puede ser usada sin restricciones especiales) entonces podemos deducir que si A es un conjunto aritmético entonces su complemento también lo es. Por ejemplo, así como “existe algún y tal que x = y + y” define al conjunto de los números pares, entonces “no existe algún y tal que x = y + y” define al de los impares.

Por otra parte, decíamos en la parte anterior que todo conjunto recursivamente numerable es aritmético, aunque la demostración de este hecho excede estas notas.

Comencemos ahora la demostración del Teorema de Gödel, en la que usaremos todos los conceptos estudiados en las partes previas.

Sea A un conjunto recursivamente numerable que no es recursivo y sea B su complemento. El conjunto A es, entonces, aritmético y por lo tanto B también es aritmético. Por otra parte, como A es recursivamente numerable pero no es recursivo, entonces B no es ni siquiera recursivamente numerable.

Por lo tanto B es aritmético, pero no es recursivamente numerable.

Ahora bien, como B es aritmético, la propiedad que lo define puede expresarse mediante alguna función proposicional P(x) expresable en el lenguaje de la Teoría de Números. Para cada n, P(n) es una afirmación de la Teoría de Números que es verdadera si n está en B y es falsa en caso contrario.

Por lo tanto B = {n : P(n) es verdadera}.

Recordemos que hemos supuesto que está dada una axiomatización finitista y consistente de la Teoría de Números. A los efectos de lo que sigue, la palabra “demostrable” significará “demostrable a partir de esos axiomas”.

Sea C entonces el conjunto C = {n : P(n) es demostrable}.

Está claro que C está contenido en B, ya que si P(n) es demostrable entonces debe ser verdadera (la consistencia de los axiomas garantiza que no se puede demostrar una falsedad). Veamos que C es recursivamente numerable.

Que la axiomatización sea finitista significa que existe un algoritmo que, dada una sucesión de enunciados, decide si esa sucesión constituye una demostración, o no. Ordenemos lexicográficamente todas las sucesiones posibles de enunciados y programemos nuestra Computadora Permanente de tal modo que las vaya recorriendo una por una y decidiendo si son o no demostraciones. Cuando la sucesión sea una demostración, la computadora debe fijarse si la conclusión de la misma es un enunciado de la forma P(n), para algún n. Si así fuera, debe imprimir el número n, en caso contrario pasa a la siguiente sucesión sin imprimir nada. Es claro que la Computadora Permanente irá así imprimiendo uno por uno los elementos de C. Por lo tanto C es, tal como dijimos, recursivamente numerable.

Recapitulando: C es recursivamente numerable, pero B no lo es, por lo tanto C y B no son el mismo conjunto. Pero C está contenido en B. Luego existe algún m que está en B, pero no está en C. Viendo las definiciones de estos conjuntos, concluimos que existe algún m tal que P(m) es una afirmación verdadera, pero que no es demostrable a partir de los axiomas. De este modo hemos probado el Primer Teorema de Gödel. Q.E.D.

La demostración del Segundo Teorema (la imposibilidad de demostrar de modo finitista la consistencia de la Teoría de Números) excede estas notas.

En la parte 16, y última, hablaremos un poco sobre las consecuencias del Primer Teorema de Gödel.

(A la parte 14 - A la parte 16)

Gödel y Turing (Parte 14)

(A la parte 13 - A la parte 15)

Las hipótesis de los Teoremas de Gödel

El Programa de Hilbert proponía axiomatizar de un modo finitista la Teoría de Números y luego probar, también de modo finitista, que la axiomatización elegida es consistente y completa. Antes de seguir adelante, aclaremos el significado de todas las palabras que acabamos de usar, para ello respondamos algunas preguntas.

1 - ¿Qué es la Teoría de Números?

En el contexto en que estamos, podemos decir que la Teoría de Números es el estudio de las propiedades de los números naturales que son expresables en términos de la suma y el producto. Esta teoría habla de números primos, números compuestos, números perfectos, propiedades de la divisibilidad, etc. La Conjetura de Goldbach, el Último Teorema de Fermat y la Conjetura de los Primos Gemelos son expresables en el contexto de la Teoría de Números.

2 - ¿Qué significa axiomatizar una teoría?

En el siglo III a.C., en su libro Elementos, Euclides axiomatizó la Geometría, o al menos una buena parte de los conocimientos geométricos de su tiempo. Para ello eligió cinco enunciados, que estableció como postulados o axiomas, y en base a los cuales resultaba posible deducir a modo de teoremas todos los demás enunciados verdaderos de la teoría.

En realidad, Euclides estableció otros axiomas además de los famosos cinco postulados, a estos otros axiomas los que llamó nociones comunes. Se trataba de reglas generales del pensamiento, reglas válidas en cualquier contexto y no solamente en la Geometría. Una de ellas, por ejemplo, enuncia que dos cosas iguales a una tercera son iguales entre sí.

Del mismo modo, cuando Hilbert habla de una axiomatización de la Teoría de Números n sólo pide elegir algunos de los enunciados de la teoría como axiomas, sino que también pide incluir también nociones comunes, que modernamente son llamadas enunciados universalmente válidos, enunciados válidos en cualquier contexto. Pero además de los axiomas debían indicarse “reglas de inferencia”. Es decir, las reglas que indican qué conclusiones es lícito extraer de determinadas premisas. Es posible, de hecho, utilizar una única regla de inferencia, la llamada regla del Modus Ponens, que dice que tomando como premisas la afirmación “Si P entonces Q” y la afirmación P entonces es válido deducir Q.

3 - ¿Qué significa que una axiomatización sea finitista?

Una vez que se ha establecida una axiomatización para una teoría podemos definir qué es una demostración.

Definición: Una demostración es una sucesión de afirmaciones tal que cada una de ellas es, o bien un axioma, o bien se deduce de afirmaciones anteriores por aplicación de las reglas de inferencia.

Esta definición responde a la idea intuitiva de lo que es una demostración, una concatenación de enunciados en los que cada uno de ellos es, o bien un axioma, o bien una consecuencia de hechos enunciados anteriormente en la demostración.

Decimos entonces que una axiomatización es finitista si existe un algoritmo que, dada una sucesión finita de enunciados, nos permite decidir si esa sucesión es una demostración o no. En otras palabras, pensando en el universo de las sucesiones finitas de enunciados, una axiomatización es finitista si el conjunto de todas las demostraciones es recursivo.

4 - ¿Es a priori concebible que una axiomatización sea finitista?

Si una axiomatización fuese finitista existiría entonces una Máquina de Turing tal que si escribimos en su cinta una sucesión de enunciados de la teoría así axiomatizada, la máquina nos dará como salida un # si la sucesión constituye una demostración y un ## en caso contrario. En otras palabras, esta máquina permitiría disipar cualquier conflicto que pudiera surgir en torno a la validez de un razonamiento referido a la teoría. Pero ¿no le estamos pediendo demasiado a una simple máquina de Turing?

Para comenzar, ¿cómo escribimos en la cinta la sucesión de enunciados? Para ello debemos establecer un lenguaje formal preciso que servirá para escribir todos los enunciados de la teoría. Deberá indicarse claramente qué símbolos se pueden usar y con qué reglas sintácticas se construirán los enunciados. Habrá símbolos para variables, para constantes, para operaciones, habrá también conectivos lógicos, paréntesis, etc. Será conveniente agregar un símbolo especial que marque la separación entre los distintos enunciados de una sucesión.

Una vez establecidos los símbolos, estos serán codificados de tal modo que una máquina de Turing pueda aceptarlos. El primer símbolo será codificado como #, el segundo como ##, etc.

Dada un enunciado sea parte de una sucesión, la máquina deberá ser capaz de determinar si se trata de un axioma o si el enunciado se deduce de enunciados anteriores por aplicación de las reglas de inferencia.

Supongamos que, como de hecho es posible hacer, tomamos al Modus Ponens como única regla de inferencia. Es claro que dada una sucesión de enunciados (codificados como antes dijimos), es posible determinar algorítmicamente si uno de ellos se deduce de los anteriores por aplicación de esta regla. Un enunciado Q (pensado meramente como una sucesión de símbolos de una cinta de una máquina de Turing), que forma parte de una sucesión, se obtiene por aplicación de la regla del Modus Ponens si antes, en la misma sucesión, aparecen un enunciado P y el enunciado “P -> Q”. Es claro que la verificación de esta condición puede hacerse algorítmicamente.

Por lo tanto, para que una axiomatización sea finitista sólo es necesario que exista un algoritmo que reconozca si un enunciado dado es o no un axioma. En particular, el conjunto de los axiomas que elijamos para la teoría debe ser recursivo. Esta condición se cumplirá casi inevitablemente ya que, como dijimos alguna vez, casi cualquier conjunto que imaginemos será, de hecho, recursivo.

¿Qué sucede con las nociones comunes (o enunciados universalmente válidos)? En 1929, en la que fue su tesis doctoral, Kurt Gödel demostró que es posible axiomatizar las nociones comunes. Es decir, existe un conjunto recursivo de enunciados universalmente válidos tal que cualquier otro enunciado de ese tipo puede deducirse de ellos por aplicaciones sucesivas del Modus Ponens. Sin embargo, para que esto sea posible, el lenguaje formal en el que se escriben los enunciados debe respetar dos restricciones, que son las siguientes:

a) Los cuantificadores, es decir los símbolos “para todo” y “existe”, sólo pueden aplicarse a variables que representen individuos de la teoría. Así por ejemplo, si se trata de la Teoría de Números, los cuantificadores sólo pueden aplicarse a variables que representen números. En particular, los cuantificadores no pueden referirse a enunciados ni a conjuntos de individuos.

b) Las operaciones, tanto lógicas como aritméticas o de cualquier otro tipo, sólo pueden aparecer aplicadas una cantidad finita y determinada de veces. Por ejemplo, es lícito decir y = x + x + ... + x + x (2.400 veces la x), pero no es lícito y = x + x + ... + x + x (n veces la x), donde n es número no determinado.

Los lenguajes que se ajustan a estas restricciones se llaman lenguajes de primer orden. Las teorías axiomáticas cuyos lenguajes son de primer orden se denominan, por supuesto, teorías de primer orden. Puesto que en estas teorías las nociones comunes son axiomatizables, entonces en toda teoría de primer orden es posible dar una axiomatización finitista ¿pero será una axiomatización completa? Dejemos esta cuestión para la próxima respuesta.

Puesto que sólo las teorías de primer orden pueden llegar a ser finitistas y dado que los Teoremas de Gödel se refieren a teorías finitistas, los Teoremas de Gödel sólo se aplican a teorías de primer orden. La axiomatización de Peano, que vimos algunas partes atrás, no es de primer orden y por ende, no es finitista. No es de primer orden porque incluye un axioma que no respeta las restricciones anteriores:

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.

5 - ¿Qué significa que una axiomatización sea completa?

Una axiomatización para una teoría es completa si todo enunciado verdadero de la teoría es demostrable a partir de los axiomas. Uno podría preguntarse qué significa que un enunciado sea verdadero, para evitar esta cuestión suele decirse simplemente que una axiomatización es completa si para todo enunciado P, o bien P, o bien su negación es demostrable a partir de los axiomas.

6 - ¿Qué significa que una axiomatización sea consistente?

Una axiomatización es consistente si no es posible deducir de los axiomas ninguna falsedad. Otra forma de decirlo, es que no existe ningún enunciado P tal que tanto P como su negación sean ambos demostrables.

7 - ¿Qué dice el Primer Teorema de Gödel?

Consideremos la Teoría de Números, más exactamente la parte de la Teoría de Números que es expresable mediante un lenguaje de primer orden, a la que llamaremos Teoría Elemental de Números.

El Primer Teorema de Gödel dice que es imposible dar una axiomatización finitista de la Teoría Elemental de Números que sea al mismo tiempo consistente y completa.

El Segundo Teorema de Gödel dice que es imposible dar una demostración finitista de la consistencia de la Teoría Elemental de Números. (1)

Puesto que el Programa de Hilbert proponía dar una axiomatización finitista de la Teoría Elemental de Números y luego demostrar su consistencia y completitud de modo finitista, los Teoremas de Gödel demostraron, en definitiva, que el Programa de Hilbert era irrealizable.

8 - ¿Qué significa que una teoría contenga a la Teoría de Números?

Tomemos una teoría que hable de los números naturales. Un conjunto de números es definible en esa teoría si la propiedad que define al conjunto es expresable en el lenguje de la teoría. Por ejemplo, el conjunto de los números pares es definible en la Teoría Elemental de Números, ya que la propiedad “x es par” equivale a decir “existe algún y tal que x = y + y”, y esta última propiedad está expresada en el lenguaje de la Teoría Elemental de Números.

Decimos que un conjunto es aritmético si es definible en la Teoría Elemental de Números. Tal como dijimos alguna vez para los conjuntos recursivos, es casi seguro que cualquier conjunto numérico que los lectores puedan imaginar será aritmético. Existen, sin embargo, conjuntos que no lo son, aunque no daremos aquí ningún ejemplo.

Será de vital importancia para nosotros la siguiente propiedad:

Teorema: Todo conjunto recursivamente numerable es aritmético. (Aunque no vale la recíproca.)

Respondamos ahora la pregunta planteada: una teoría contiene a la Teoría Elemental de Números si permite definir todos los conjuntos aritméticos. A los efectos de los Teoremas de Gödel es suficiente en realidad que permita definir todos los conjuntos recursivamente numerables. El Primer Teorema de Gödel puede enunciarse diciendo que es imposible dar una axiomatización finitista, consistente y completa de cualquier teoría de primer orden que contenga a la Teoría Elemental de Números.

En la próxima parte veremos finalmente la demostración del Primer Teorema de Gödel.

Notas:

(1) Para dar una demostración finitista de la consistencia de la teoría de números habría que formular una teoría que se refiera a los enunciados de la Teoría de Números en la que sea posible expresar la consistencia de esta teoría. Habría que axiomatizar de modo finitista esta teoría y luego demostrar la consistencia de la Teoría de Números.

(A la parte 13 - A la parte 15)

Gödel y Turing (Parte 13)

(A la parte 12 - A la parte 14)

El Programa de Hilbert

Según veíamos en la parte anterior, a principios del siglo XX se descubrió que la Teoría de Conjuntos de Cantor era inconsistente. Esto significó una crisis, pues en ese momento la Teoría de Conjuntos se había transformado en la columna vertebral del Cálculo. De hecho, la Teoría de Conjuntos iba en camino de transformarse en el fundamento mismo de toda la Matemática, pues Georg Cantor, Richard Dedekind y Gottlob Frege (1), trabajando independientemente, habían logrado definir a partir de la noción de conjunto el concepto mismo de número.

Esta crisis de los fundamentos generó inicialmente dos reacciones, dos intentos casi diametralmente opuestos de recuperar la solidez de las bases de la Matemática. Una de estas reacciones fue el Programa Logicista, propuesto por Bertrand Russell hacia 1905 y cuya obra fundamental es Principia Mathematica. La otra propuesta fue el Intuicionismo o Cosntructivismo, contemporáneo del Logicismo y cuyo principal ideólogo fue L.E.J. Brouwer.

El Logicismo proponía fundamentar la Matemática en la Lógica y la Teoría de Conjuntos, aunque, para evitar las paradojas, Russell proponía hacer previamente una reestructuración en el lenguaje. Russell sostenía que todas las paradojas, no sólo las de la Teoría de Conjuntos sino en general todas las paradojas lógicas conocidas, provienen de un uso indebido de la autorreferencia, de la existencia de círculos viciosos en los que, metafóricamente, se crean serpientes que se comen a sí mismas desde su propia cola. Así por ejemplo, la “paradoja de Russell”, que vimos en la parte anterior, proviene de considerar conjuntos que son elementos de sí mismos.

Para evitar estas autorreferencias indebidas, Russell propuso establecer en el lenguaje una jerarquía estricta e inviolable, a la que llamó Teoría de los Tipos. En el nivel inferior de esta jerarquía estarían los individuos (por ejemplo, las letras). En el nivel inmediato superior estarían las oraciones de tipo-1, que son las oraciones que se refieren a los individuos. Por ejemplo “La letra a es una consonante” es una oración de tipo-1.

En el nivel inmediato superior están las oraciones de tipo-2, que se refieren a las oraciones de tipo-1. Así por ejemplo, “Es falso que la letra a es una consonante” es de tipo-2.

Luego están las oraciones de tipo-3, que son las que hablan de las oraciones de tipo-2, y así sucesivamente. De este modo toda oración, para ser válida, debería ocupar un lugar en esta jerarquía, en algún tipo-n. Cualquier oración que no se ajustara a esta restricción sería considerada un sin-sentido.

“Esta frase es falsa”, que se refiere a sí misma, es un ejemplo de sin-sentido, es decir, es una concatenación de palabras que parece decir algo, pero que en realidad carece de significado. Las propiedades que definen a los conjuntos, por supuesto, deberán también adaptarse a esta jerarquía de tipos. De tal modo que “El conjunto de todos los conjuntos” es un sin-sentido que, por ende, no define ningún ente matemático.

Esta jerarquía, en efecto, evita todas las paradojas (al menos todas las paradojas conocidas hasta la actualidad). El problema es que cuando tratamos de fundamentar toda la Matemática ateniéndonos a estas restricciones de lenguaje, la situación se vuelve insostenible. Por ejemplo, supongamos que quisiéramos establecer a modo de axioma que “Toda afirmación es verdadera o falsa”. Pues bien, no podríamos hacerlo. En efecto, “Toda afirmación es verdadera o falsa” habla de todas las afirmaciones, en particular habla de sí misma, y por lo tanto es autorreferente y un sin-sentido.

Ante este problema, Bertrand Ruseell introduce el llamado Axioma de Reductibilidad, que dice que toda oración de tipo-n es equivalente a alguna oración de tipo-1. De este modo podemos decir con toda corrección que “Toda afirmación de tipo-1 es verdadera o falsa” y como cualquier otra afirmación es equivalente a una de tipo-1 estaremos diciendo en definitiva que toda afirmación es verdadera o falsa.

Pero si bien se mira el Axioma de Reductibilidad tira por la borda toda la filosofía de la jerarquía del lenguaje. Hemos creado entonces una rígida jerarquía del lenguaje, para decir inmediatamente después que toda la jerarquía se reduce al tipo-1.

El mismo Russell se vio obligado a admitir que este axioma no era para nada evidente y que se vio obligado a introducirlo meramente porque le resultaba indispensable para completar ciertas definiciones o demostraciones que no habría sabido hacer de otro modo. Pero la introducción de un axioma controvertido con la única justificación de que resulta práctico no es una buena idea si es que estamos construyendo una fundamentación indubitable para la Matemática. Por eso mismo las controversias en torno al Axioma de Reductibilidad acabaron por herir de muerte la idea de Russell y, finalmente, hacia 1920 el Logicismo había perdido toda acabado por perder toda influencia.

La segunda propuesta, contemporánea del Logicismo, fue el Intuicionismo o Constructivismo, cuyo principal impulsor fue L.E.J. Brouwer. Los intuicionistas sostenían que las inconsistencias de la Teoría de Conjuntos se debían simplemente al uso del infinito actual, concepto que los intuicionistas consideraban inconsistente en sí mismo. Más allá de este rechazo al uso del infinito actual, el concepto central de la filosofía intuicionista es el concepto de algoritmo.

Para los intuicionistas los números naturales están dados a priori, por una intuición inherente al pensamiento humano. Cualquier otro objeto matemático sólo existe si es posible mostrar un algoritmo que lo construya a partir de los números naturales. Así por ejemplo, la raíz cuadrada de 2 no existe como número “actual” o “acabado”, pero sí existen (porque se pueden calcular algorítmicamente) números racionales que se acercan tanto como uno quiera a un número positivo que elevado al cuadrado sea igual a 2.

Otro ejemplo del papel de la noción de algoritmo desempeña en el pensamiento intuicionista es éste: para los intuicionistas una propiedad, digamos una propiedad referida a los números naturales, sólo puede considerarse bien definida si existe un algoritmo que, dado un número, nos permita verificar si el número cumple o no la propiedad en cuestión. Usando la terminología que desarrollamos en las partes anteriores, para los intuicionistas las únicas funciones que existen son las funciones recursivas y los únicos conjuntos que existen son los conjuntos recursivos.

El llamado Programa Intuicionista se proponía reconstruir toda la Matemática respetando esta filosofía. Desde luego, esta reconstrucción dejaría fuera de la Matemática a la teoría de Cantor, así como gran parte del Análisis.

Hacia 1920, con la caída del Logicismo, el Intuicionismo comenzaba a transformarse en la filosofía dominante de la Matemática y esto ponía, por decirlo dramáticamente, en riesgo de muerte a la teoría de Cantor.

David Hilbert, uno de los más grandes matemáticos de fines del siglo XIX y principios del XX, había sido desde siempre un gran defensor de las ideas de Cantor y, ante el avance del intuicionismo, decide proponer una filosofía alternativa: el Formalismo.

La idea de Hilbert, que además de ser un gran matemático era un muy hábil político, fue crear un concepto que sedujera a los intuicionistas, es decir que fuera completamente compatible con su forma de ver la Matemática, pero que a la vez permitiera conservar la intacta teoría de Cantor. La idea de Hilbert consistió esencialmente en respetar la exigencia algorítmica que impregnaba el pensamiento intuicionista, pero llevándola a los razonamientos matemáticos en lugar de aplicarla a los objetos matemáticos en sí.

La idea central del Formalismo es la siguiente: toda teoría matemática debe ser axiomática (es decir, debe estar basada en axiomas de los cuales se deducen todos los teoremas), pero la axiomatización debe ser realizada de tal modo que exista un algoritmo que, dada una sucesión de enunciados, nos indique si esa sucesión constituye o no una demostración. Es decir, la exigencia de recursividad ya no se refiere a las propiedades de los objetos matemáticos, sino a las propiedad (referida a sucesiones de afirmaciones) de “ser una demostración”. Una teoría axiomática para la cual exista un algoritmo así es llamada una teoría finitista. Podemos hablar del infinito actual, dice Hilbert, siempre y cuando al hablar de él hagamos razonamientos finitistas.

En concreto, la propuesta de Hilbert era axiomatizar de modo finitista la Teoría de Números y luego demostrar, también de modo finitista, que esa axiomatización es completa y consistente. Donde completa significa que toda verdad pueda deducirse de los axiomas y consistente significa que ninguna falsedad puede ser demostrada. Una vez así axiomatizada la Teoría de Números se tendría un fundamento sólido para el resto de la Matemática (digamos, dadme un punto de apoyo bien fundamentado y fundamentaré a partir de él toda la Matemática).

Tras una década de luchas y polémicas, en septiembre de 1930 los intuicionistas aceptaron finalmente el Programa de Hilbert. Si el programa podía completarse, los intuicionistas aceptarían incluso el infinito actual. Pero fue justo en septiembre de 1930 (2) cuando Gödel expuso públicamente por primera vez sus teoremas de incompletitud.

El primer teorema dice que es imposible dar una axiomatización finitista de la Teoría de Números que sea a la vez completa y consistente. El segundo teorema dice que es imposible demostrar de modo finitista la consistencia de la Teoría de Números. En otras palabras, justo en el mismo momento en que parecía que el programa de Hilbert había triunfado, los teoremas de Gödel demostraron que el ese programa era irrealizable.

En la próxima parte comenzaremos a estudiar la demostración del primer teorema de Gödel.

Notas:

(1) Hay que aclarar que el concepto que tenían Frege y Dedekind de la noción de conjunto difería en algunos puntos esenciales de la noción que tenía Cantor.

(2) Kurt Gódel expuso por primera vez su teorema en septiembre de 1930, en un congreso sobre fundamentos de la Matemática. El artículo que contiene los teoremas se publicó algunos meses después, en 1931.

(A la parte 12 - A la parte 14)

Gödel y Turing (Parte 12)

(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)

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)

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)

Gödel y Turing (Parte 9)

(A la parte 8 - A la parte 10)

Conjuntos recursivos y recursivamente numerables

Tomemos un conjunto finito de símbolos, que pueden ser letras, números, garabatos o símbolos de cualquier otra naturaleza. Estos símbolos formarán nuestro alfabeto. Digamos, para poner un ejemplo, que el alfabeto esté formado por tres símbolos: a, b, c.

Una vez fijado el alfabeto, podemos usarlo para construir palabras. Una palabra es simplemente una sucesión finita de símbolos (1). Por ejemplo, aaabc, aaa o bbbcc. Si los símbolos fueran cifras, las palabras serían simplemente números. Como veremos a continuación, en realidad siempre podemos suponer que las palabras son números. En efecto, si el alfabeto es, como antes, a, b, c, entonces el conjunto de todas las palabras posibles comienza (ordenado lexicográficamente) así: a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, etc., sucesión de palabras que podemos rotular o numerar como 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, etc.

De este modo, en lugar de aa podemos decir 4 y en lugar de c, 3 y, por ejemplo, la frase “c no es parte de aa” se transformará en “3 no es parte de 4” (frase que en sí misma parece carecer de sentido, pero que es de una claridad meridiana si sabemos qué significado le estamos dando a “3” y “4”).

De ahora en adelante, entonces, hablaremos únicamente de conjuntos numéricos, aunque el lector no deberá perder nunca de vista que estaremos hablando en realidad de palabras sobre un alfabeto cualquiera. Sea N, entonces, el conjunto de todos los enteros positivos y sea A un subconjunto de N. Vamos a definir a continuación qué significa que A sea recursivo o recursivamente numerable.

Definición: A es recursivo si existe un algoritmo que, dado un entero n, nos permite decidir si n pertenece o no pertenece a A.

En otras palabras, A es recursivo si existe una máquina de Turing que acepta como entrada válida a cualquier número n y que da como salida “1” si n pertenece a A y “2” en caso contrario.

Por ejemplo, el conjunto de todos los números primos es recursivo. En efecto, existe un algoritmo que, dado un número cualquiera, determina si el número es primo o no. Una opción es dividir a n por todos los números entre 2 y n-1 y ver si en algún caso el resto es 0 (2). Es cierto que para ciertos valores de n este algoritmo tardará siglos en darnos una respuesta, pero no es eso lo que nos preocupa aquí. Sólo nos interesa que el algoritmo dé siempre una respuesta correcta y que lo haga al cabo de una cantidad finita de tiempo. A los efectos de nuestra definición, si esa cantidad de tiempo resulta ser un millón de años, no habrá ningún problema.

En realidad, todos los conjuntos que el lector pueda imaginar serán, casi con certeza, conjuntos recursivos. El conjunto los números cuadrados, de los números perfectos, de los primos de Fermat, etc. son todos recursivos.

Una pregunta natural es entonces ¿existen conjuntos que no sean recursivos? Pues bien, sí existen y, de hecho, ya vimos un ejemplo. En la Parte 8 vimos que si numeramos todas las máquinas de Turing como T1, T2, T3,... entonces no existe ningún algoritmo que, dado un número n, determine si n es o no es una entrada válida para la máquina Tn. En otras palabras, el conjunto de todos los n que son entradas válidas para Tn es un conjunto no recursivo.

Parientes cercanos de los conjuntos recursivos, son los conjuntos recursivamente numerables.

Definición: La definición formal dice que un conjunto A es recursivamente numerable si existe una función recursiva F tal que A está formado por los números F(1), F(2), F(3),.... (3)

Una manera menos formal, pero tal vez más clara de explicarlo, es ésta: imaginemos que tenemos una computadora que, una vez que la encendamos, permanecerá en funcionamiento por los siglos de los siglos, llamémosla, para referirnos cómodamente a ella, la Computadora Permanente. Esta computadora, de tanto en tanto, imprimirá un número.

Un conjunto A es recursivamente numerable si es posible programar a la Computadora Permanente de tal modo que se cumplan las siguientes dos condiciones:

1) Todo número que la computadora imprima debe pertenecer a A (es decir, nunca imprimirá un número que no esté en A).
2) Todo número que pertenece a A, tarde o temprano, deberá ser impreso al menos una vez.

La relación entre esta definición informal y la definición formal de más arriba será clara si convenimos en llamar F(1) al primer número que la computadora imprima, F(2) al segundo y así sucesivamente.

Todo conjunto recursivo es también recursivamente numerable. En efecto, supongamos que A es recursivo, existe entonces un algoritmo que, dado un número n, determina si n pertenece o no a A. El siguiente es el programa que podríamos cargar en la Computadora Permanente:

Paso 1: Defina n = 1.
Paso 2: Determine si n pertenece o no al conjunto A (usando el algoritmo correspondiente). Si pertenece, imprima n. Si no pertenece, no haga nada.
Paso 3: Sume 1 al valor de n y vuelva al Paso 2.

¿Existirá algún conjunto que sea recursivamente numerable, pero no recursivo? Antes de responder a esta pregunta, comprendamos claramente qué significaría esto. Supongamos que A fuese recursivamente numerable, pero no recursivo, por una parte esto significa que podemos programar a la Computadora Permanente para que vaya imprimiendo los elementos de A, pero que no tenemos ninguna forma de saber de antemano si un número dado será impreso o no alguna vez.

Podemos imaginar la siguiente historia. Programamos la Computadora Permanente y la echamos a andar. Por unas horas no sucede nada. Un día y medio después la Computadora imprime se rápida situación los números 2, 345 y 222. Pasan unos días e imprime el 13. Al cabo de quince años ha impreso los números 2, 345, 222, 13, 77, 1.300.000, 4 y 80. ¿Imprimirá alguna vez el 1? No hay forma de saberlo de antemano. Sólo podemos esperar. Si resulta que el 1 pertenece a A, algún día lo sabremos, aunque tal vez tengamos que esperar miles de años para ello. Pero si resulta que el 1 no está en A, nunca lo sabremos. Es decir, si al cabo de un millón de años el 1 no ha sido impreso, no hay forma de saber si será impreso al día siguiente o si nunca los será.

Vimos antes que el conjunto de todos los n que son entradas válidas para la máquina Tn no es un conjunto recursivo, veamos ahora que sí es recursivamente numerable.

Para verlo imaginemos que en la Computadora Permanente vamos cargando sucesivamente varios programas que trabajan en paralelo. Primero le cargamos el programa de la máquina T1 con 1 como entrada. Mientras la máquina trabaja, introducimos el programa de la máquina T2 con la entrada 2. Luego programamos T3 con la entrada 3, y así sucesivamente. Programamos además la siguiente instrucción: “si en algún momento la máquina Tn se detiene y da una entrada válida, imprima n.” (4)

De este modo, la Computadora Permanente irá imprimiendo todos los n que son entradas válidas para Tn y ningún otro número. Es decir, hemos visto así que el conjunto de todos los n que son entradas válidas para la máquina Tn (que no es recursivo) es recursivamente numerable.

Estamos aquí en el corazón mismo de nuestro tema, de cara al mismísimo Teorema de Gödel. Tomemos alguna conjetura matemática aún no resuelta, por ejemplo la Conjetura de Goldbach. (5) Notemos que si la conjetura fuese finalmente demostrada, se habrá demostrado un teorema, pero si la conjetura es refutada, de todos modos se habrá demostrado un teorema (el teorema diría “la conjetura es falsa”).

Sin entrar todavía en detalles, y permitiéndonos un dejo de imprecisión, podemos decir que el Teorema de Gödel afirma que el conjunto de todos los teoremas matemáticos es recursivamente numerable, pero no recursivo. El papel de la Computadora Permanente sería jugado en este caso por la comunidad matemática, que va imprimiendo sucesivamente todos los teoremas en forma de papers.

Que el conjunto no sea recursivo significa que hay afirmaciones de las que nunca se sabrá si son o no teoremas. Podría suceder que ni la afirmación “La Conjetura de Goldbach es cierta”, ni “La Conjetura de Goldbach es falsa” lleguen a ser nunca impresas. En ese caso diríamos que la Conjetura de Goldbach es una “proposición indecidible”. El Teorema de Gödel asegura que tales proposiciones indecidibles existen, pero a priori no hay de modo de saber cuáles son.

Notas:

(1) Técnicamente suele hablarse también de la palabra vacía, que es aquella que carece de símbolos. Nosotros, sin embargo, no necesitaremos incluirla en nuestras consideraciones. Por cierto, el término palabra se usa aquí en un sentido puramente técnico, una palabra no tiene por qué tener significado.

(2) Es obvio que no es éste el mejor algoritmo para determinar si un número es primo o no. He elegido a propósito el menos eficiente de todos los algoritmos para mostrar que no se trata aquí de una cuestión de eficiencia. No me interesa hallar el mejor algoritmo, me interesa saber solamente si existe alguno.

(3) Véanse las partes anteriores del artículo, esencialmente F es recursiva si existe un algoritmo que permite calcularla.

(4) En lugar de ir programando en paralelo las máquinas T1, T2, T3,... podemos reducir todo el proceso a un solo programa. Éste indicaría ejecutar la primera instrucción de T1 con la entrada 1. Luego las dos primeras instrucciones de T1 y T2 con las entradas 1 y 2 respectivamente. Luego las tres primeras instrucciones de T1, T2 y T3 con las entradas 1, 2 y 3 respectivamente. Y así sucesivamente. Cada vez que una máquina se detiene y da una salida válida, su número es impreso.

(5) La Conjetura de Goldbach afirma que todo número par mayor que 2 es suma de dos números primos. Hasta el día de hoy no se sabe si es cierta o falsa. Véase aquí más información.

(A la parte 8 - A la parte 10)

Gödel y Turing (Parte 8)

(A la parte 7 - A la parte 9)

Una función no recursiva

Vimos en la parte anterior que existe una forma de numerar todas las máquinas de Turing (T1, T2, T3,...) de manera tal que sea posible construir una máquina de Turing U (llamada máquina universal) que al recibir como entrada el par (n,m) imita el comportamiento que tendría la máquina Tn al recibir como entrada al número m. Más precisamente, si ante la entrada m la máquina Tn se detiene después de una cantidad finita de pasos, lo mismo sucederá con U al recibir el par (n,m) y en ambos casos la salida será la misma. Si con la entrada m la máquina Tn entra en un estado de cómputo infinito, lo mismo sucederá con U al recibir el par (n,m).

Recordemos ahora que cada máquina de Turing (llamémosla Z) define una función F cuyo dominio es el conjunto de todas las entradas válidas de Z, es decir el conjunto de todos los enteros positivos n que, ingresados en Z, hacen que la máquina se detenga después de una cantidad finita de pasos y que dé como salida algún número m. El valor de F(n) se define, precisamente, como ese número m.

Recordemos finalmente que una función F es recursiva parcial si y sólo si existe una máquina de Turing Z tal que F es la función definida por ella. Es decir, una función es recursiva parcial si existe un algoritmo que permite calcular F(n) para cada n de su dominio y que se “cuelga” si intenta calcular el valor de F(n) para algún n que no pertenezca al dominio. Si este dominio está formado por todos los números enteros positivos entonces la función se denomina recursiva.

Vamos a definir ahora una función G, cuyo dominio será el de todos los números enteros positivos y que, como veremos, no es recursiva.

Instrucciones para calcular G(n):

Entrada: n.
Paso 1: Determine si n es una entrada válida para Tn.
Paso 2: Si en el paso 1 la respuesta es sí, calcule la salida de U(n,n),, si es el número m, defina G(n) = m + 1.
Paso 3: Si en el paso 1 la respuesta es no, defina G(n) = 1.
Salida: G(n).

Demostremos que la función G no es recursiva. Supongamos que sí lo fuera, entonces existiría un número n tal que Tn calcula G. Como el dominio de G es el conjunto de todos los enteros positivos entonces n es una entrada válida para Tn, llamemos m a la salida. Este m es la salida de U(n,n), luego G(n) = m + 1. Luego, la salida de Tn no coincide con el valor de G(n), lo cual contradice que Tn calcule G.

No existe entonces ningún algoritmo que permita calcular la función G. Pero el conjunto de instrucciones que definen G(n) ¿no es acaso un algoritmo que calcula el valor de G(n)? ¿Cómo podemos salir de esta aparente contradicción?

La respuesta es que un conjunto de instrucciones no es necesariamente un algoritmo. Para que realmente lo sea, debemos estar seguros de que cada uno de sus pasos puede ejecutarse mecánicamente. La única conclusión que nos permite evitar la paradoja es que el conjunto de instrucciones que define a G no es realmente un algoritmo.

¿Es posible ejecutar mecánicamente el Paso 2 o el Paso 3? Evidentemente sí. Por lo tanto, el “culpable” sólo puede ser el Paso 1, es este paso el que no puede ejecutarse mecánicamente, el que no puede reducirse a una serie de pasos elementales.

Por lo tanto, no existe ningún algoritmo que, dado un número n, nos permita determinar si n pertenece es o no una entrada válida para Tn. Una ligera modificación del argumento nos permite demostrar que no existe un algoritmo que, dado n, permita decidir si al recibir esta entrada la máquina Tn se detendrá o no se detendrá al cabo de una cantidad finita de tiempo. A este último problema se lo denomina tradicionalmente “el problema de la parada” (en inglés, the halting problem.) El problema de la parada, entonces, no es resoluble algorítmicamente.

El Entscheidungsproblem es el problema (planteado por David Hilbert) que pide decidir si, dada una cierta rama de la Matemática, será posible hallar un algoritmo que resuelva todos los problemas que puedan plantearse en ella. El razonamiento anterior nos muestra que la respuesta al Entscheidungsproblem es negativa. En efecto, en la teoría de algoritmos el problema de la parada no es resoluble algorítmicamente. Por lo tanto no es posible resolver mecánicamente todos los problemas de esa rama del conocimiento.

Es importante destacar que la imposibilidad se refiere a la existencia de un método general que permita decidir, para cualquier n, si la entrada #n es válida para la n-ésima máquina T (el mismo método para todos los valores de n). Sí es posible, en cambio, resolver la cuestión para valores específicos de n, usando en cada caso mecanismos diferentes.

Nota: Se insinúa aquí un argumento a favor de la idea de que la mente humana es esencialmente superior a una computadora. Este argumento diría así: hay cuestiones que una computadora no puede resolver, pero sí la mente humana. El argumento, hay que decirlo, es falaz y la falacia está muy claramente explicada en el artículo que se puede descargar haciendo click aquí. Hasta donde sabemos, el "juego" entre cerebro y computadora sigue todavía empatado.

(A la parte 7 - A la parte 9)

Gödel y Turing (Parte 7)

(A la parte 6 - A la parte 8)

La máquina universal de Turing

Cada máquina de Turing queda caracterizada por el programa que rige su comportamiento. Es decir, dos máquinas de Turing son iguales si y solo si son iguales (símbolo a símbolo) sus respectivos programas. Utilizaremos esta definición para mostrar una manera de enumerar una por una todas las máquinas de Turing existentes.

Convengamos en adoptar el siguiente código, que transforma en números enteros a los símbolos que hemos usado para describir a las máquinas T:

1 = símbolo 0 (o casilla vacía)
2 = símbolo #
3 = letra D
4 = letra I
5 = letra S
6 = estado final de la máquina (q0), que indica el final del cálculo.
7 = estado inicial de la máquina (q1), en el que se encuentra al comenzar.
8 = estado 2 de la máquina (q2).
9 = estado 3 de la máquina (q3).
10 = estado 4 de la máquina (q4).
Etc.

Con esta convención, todo programa de una máquina de Turing puede transformarse en una sucesión finita de enteros positivos. Por ejemplo, el programa siguiente:

# + q1 -> 0Dq2
0 + q1 -> 0Iq1
# + q2 -> #Sq0
0 + q2 -> 0Dq2

se transforma en 1-3-8-1-4-7-2-5-6-1-3-8, que es simplemente la traducción de 0-D-q2-0-I-q1-#-S-q0-0-D-q2 (nótese que en esta traducción omitimos la columna de la izquierda).

Toda sucesión que sea la traducción del programa de una máquina T tendrá necesariamente las siguientes características:

a) Estará formada por una cantidad par de ternas de números naturales. Más precisamente, si la máquina tiene n estados, la sucesión tendrá 2n ternas.

b) El primer número de cada terna será 1 o 2.

c) El segundo número de cada terna será 3, 4 o 5.

d) Si la máquina tiene n estados, el tercer número de cada terna será mayor o igual que 6 y menor o igual que n + 6.

Recíprocamente, toda sucesión que cumpla las condiciones anteriores será la traducción de una máquina de Turing de n estados.

La traducción que hemos descripto nos da un método para enumerar una por una todas las máquinas T existentes. En primer lugar enumeramos las sucesiones correspondientes a todas las máquinas de un solo estado, ordenadas lexicográficamente (1). La lista de todas las máquinas de un estado comenzaría así:

1-3-6-1-3-6
1-3-6-1-3-7
1-3-6-1-4-6

Un simple razonamiento combinatorio nos permite deducir que existe un total de 144 máquinas de Turing de un estado.

A continuación de las máquinas de un estado enumeramos las máquinas de dos estados, luego las de tres estados y así sucesivamente. Si procedemos de esta manera, tarde o temprano, toda máquina T aparecerá en nuestra lista una y sólo una vez. Llamaremos T1 a la primera de las máquinas de la enumeración, T2 a la siguiente, etc.

Es claro que es posible escribir un algoritmo que, dados los números n y m, escriba la sucesión finita que describe a la máquina Tn y que además ejecute el cálculo que haría Tn si recibiera como entrada el número m. Este algoritmo, de acuerdo a la tesis de Turing, puede a su vez representarse mediante una máquina T.

Deducimos entonces que existe una máquina de Turing U (llamada máquina universal de Turing) que recibe como entrada dos números (n,m) y que imita el cálculo que haría Tn al recibir como entrada el número m. Esta máquina será esencial en la construcción de una función no recursiva.

Nota:

(1) En el orden lexicográfico u orden del diccionario las sucesiones se ordenan según la primera cifra, a igualdad de la primera cifra se ordenan según la segunda, a igualdad de las dos primeras se ordenan según la tercera y así sucesivamente. Por ejemplo 1-2-6 viene antes que 1-2-9, pero después de 1-1-7.

(A la parte 6 - A la parte 8)

Gödel y Turing (Parte 6)

(A la parte 5 - A la parte 7)

Funciones recursivas parciales

Toda máquina de Turing Z define de manera natural una función F cuyo dominio (1) está formado por todos los enteros positivos n tales que #n es una entrada válida para Z, es decir, todos los números que, cargados en Z dan (después de una cantidad finita de tiempo) una salida que representa un entero positivo. El número F(n) se define entonces del siguiente modo: F(n) = m si y sólo si #m es la salida que corresponde a la entrada #n.

Definición: Diremos que una función G es recursiva parcial si existe una máquina de Turing Z tal que la función F por ella definida coincide exactamente con la función G (es decir, si F y G tienen el mismo dominio y además para cada número n de ese dominio vale que F(n) = G(n)). Cuando el dominio de G está formado por todos los enteros positivos, decimos simplemente que la función es recursiva.

Expresado en términos más simples, una función G es recursiva parcial si existe un algoritmo (o un programa de computadora) que permite calcular G(n) para cualquier número n de su dominio y que, cuando intenta calcular G(n) para un n que no pertenezca al dominio, o bien entra en un ciclo de cómputo infinito o bien da una respuesta ininteligible.

Como ya hemos visto en la Parte 4, la función G(n) = n – 1 (cuyo dominio está formado por los enteros mayores que 1) es recursiva parcial. Para dar otro ejemplo, veamos que la función H(n) = log n, cuyo dominio es el conjunto de las potencias de 10, es también recursiva parcial. Gracias a la Tesis de Turing no será necesario mostrar explícitamente una máquina T que calcule H(n), alcanzará con mostrar cualquier algoritmo que haga ese cálculo, la Tesis nos garantiza que dicho algoritmo podrá traducirse a una máquina T. En este caso un algoritmo puede describirse de la siguiente manera:

1) Entrada: n.
2) Defina k = 1.
3) Calcule 10 elevado a la k y compárelo con n, si son iguales deténgase, en caso contrario vaya al paso siguiente.
4) Sume 1 al valor de k y vuelva al paso 3).
5) Salida: k.

En realidad toda función que esté descripta mediante una o varias fórmulas basadas en las operaciones usuales (suma, resta, producto, cociente, radicación, etc.) será una función recursiva parcial. Casi cualquier función que Ud., lector, pueda llegar imaginar será, casi con certeza, una función recursiva parcial.

Surge entonces la pregunta siguiente: ¿existen funciones que no sean recursivas parciales? Es decir, ¿existen funciones tales que no haya algoritmos capaces de calcularlas? Curiosamente la respuesta es afirmativa.

Una manera indirecta de demostrar la existencia de infinitas funciones no recursivas parciales es la siguiente. Puede probarse con no demasiada dificultad que el conjunto de todas las máquinas de Turing es numerable, mientras que el conjunto de todas las funciones del conjunto de los números naturales en sí mismo es no numerable. Por lo tanto deben existir necesariamente funciones no calculables por máquina de Turing alguna. Es decir, existen funciones que no pueden ser calculadas algorítmicamente (no pueden ser “comprendidas” por un programa de computadora).

En la parte 7 iniciaremos el proceso que nos permitirá mostrar explícitamente un ejemplo concreto de función no recursiva.

Nota:

(1) A los efectos de estas notas, el dominio de F es el conjunto de todos los enteros positivos n para los cuales F(n) puede calcularse y da como resultado un entero positivo. Por ejemplo, para F(n) = n/2 el dominio está formado por todos los números pares.

(A la parte 5 - A la parte 7)

Gödel y Turing (Parte 5)

(A la parte 4 - A la parte 6)

Más sobre la tesis de Turing

“El trabajo de Turing en la construcción de tablas de comportamiento parece inmerso en la cuestión de la programación de computadoras, tanto más cuanto Turing utilizó una notación abreviada equivalente a la definición de subrutinas. Aunque no puede decirse que la idea de la programación tenga su origen en el trabajo de Turing, la verdad es que en éste la idea es formalizada de tal modo que es difícil creer que las computadoras todavía no existieran. Sin embargo, un asunto tiene que enfatizarse: en su trabajo Turing no estaba considerando las máquinas de computación (que llegarían sólo diez años más tarde), lo que Turing hacia era modelar la acción de la mente humana.”
(HODGES, Andrew – Turing – Editorial Norma, Bogotá, 1998. )

Un algoritmo es, informalmente hablando, un procedimiento mecánico (o una receta) para resolver un problema determinado. Específicamente serán de nuestro interés los problemas matemáticos que involucran números enteros positivos.

Normalmente un algoritmo se expresa como una serie de instrucciones que deben seguirse paso a paso al pie de la letra (de la misma manera en que una computadora ejecuta los pasos de un programa). Supongamos, por ejemplo, que nuestro problema consiste en calcular la parte entera de la raíz cuadrada de un número dado. Como primer intento podríamos plantear sencillamente el “algoritmo” siguiente:

Propuesta I:

Entrada: n.
Paso 1: Calcule la parte entera de la raíz cuadrada de n y llámela k.
Salida: k.

Sin embargo, como es fácil imaginar, las instrucciones que acabamos de escribir no constituyen genuinamente un algoritmo. La instrucción principal dice sencillamente “resuelva el problema”, sin indicarnos realmente el modo de hacerlo.

Para que un conjunto de instrucciones constituya verdaderamente un algoritmo deberíamos estar seguros de que cada uno de sus pasos puede ser ejecutado mecánicamente, mientras que en la Propuesta I no tenemos ninguna garantía de que el Paso 1 cumpla esa condición. El siguiente conjunto de instrucciones nos da una respuesta mejor para nuestro problema:

Propuesta II:

Entrada: n.
Paso 1: Asigne a la variable k el valor 1.
Paso 2: Eleve k al cuadrado.
Paso 3: Si el cuadrado de k es menor o igual que n, sume 1 al valor de k y vaya al paso 2.
Paso 4: Si el cuadrado de k es mayor que n, vaya al paso 5.
Paso 5: Reste 1 al valor de k.
Salida: k.

Por ejemplo, si n = 22, las instrucciones nos llevan a calcular los cuadrados de 1, 2, 3,... Estos cálculos llegarán hasta el cuadrado de 5, que es el primer número que es excede a 22. La salida es k = 4, la respuesta correcta del problema.

La Propuesta II es un refinamiento de la Propuesta I, pues está construida subdividiendo cada instrucción de ésta en pasos más sencillos. Pero ¿es cierto que cada paso del segundo algoritmo puede realizarse mecánicamente? Analicemos: cada instrucción de la Propuesta II nos pide, o bien elevar un número al cuadrado, o bien sumarle o restarle una unidad, o bien comparar dos números enteros. Nuestra familiaridad con calculadoras y computadoras nos indica que, en efecto, todas estas operaciones pueden efectuarse mecánicamente.

Pero, si no contásemos con esa familiaridad ¿cómo podríamos tener la absoluta certeza de que existe un procedimiento mecánico para, por ejemplo, elevar un número al cuadrado? El modo de lograr esta certeza sería refinar una y otra vez la Propuesta II hasta lograr un conjunto de instrucciones tan sencillas que no quepa ninguna duda de que pueden ser ejecutadas mecánicamente. La idea central de la Tesis de Turing es que el último refinamiento de cualquier algoritmo será, a la larga, una máquina de Turing (o máquina T, para abreviar).

En el artículo donde presenta por primera vez su tesis (1), Turing ofrece el siguiente argumento como justificación de la misma (2):

Turing analiza los pasos que sigue una persona al realizar un cálculo matemático. Dice que en esa tarea, los humanos revisamos cifra por cifra los números involucrados en el cálculo y que en cada paso elemental (o irreducible) del mismo escribimos o borramos un símbolo. Finalmente argumenta que nuestro modo de proceder está siempre regido por nuestro “estado mental” en cada instante (análogo al “estado interno” de una máquina T). Por lo tanto, dice Turing, los pasos elementales de cualquier cómputo son equivalentes a los que realiza una máquina T.

Es interesante observar que en su razonamiento Turing analiza los pasos que sigue una persona (no un artefacto) al realizar un cálculo. Por lo tanto, al definir su máquina, Turing estaba intentando dar un modelo matemático del funcionamiento del cerebro humano. En otras palabras, al momento de escribir su artículo, Turing consideraba que el cerebro humano funciona esencialmente igual que computadora. La complejidad del cerebro es, desde luego, mucho mayor que el de cualquier computadora actual, pero la diferencia entre ambos residiría sólo en una cuestión de complejidad, no en una cuestión de naturaleza esencial.

En escritos posteriores Turing modificó esta primera convicción y pasó a creer que el cerebro humano tiene en realidad capacidades que son imposibles de alcanzar por una computadora, ni siquiera en teoría (3). Concretamente, en esta segunda etapa de su pensamiento, Turing creía que los presentimientos o la intuición marcaban una diferencia real entre mente humana y la computadora mecánica.

¿Es el cerebro humano una computadora (extraordinariamente compleja, pero computadora al fin) o, por el contrario, existe una diferencia esencial entre “computadora” y “cerebro”? No existe por el momento (y tal vez nunca exista) un acuerdo unánime acerca del cuál es la respuesta a esta pregunta. En la actualidad, sólo por citar algunos ejemplos, el físico-matemático Roger Penrose es defensor de la convicción según la cual el cerebro es esencialmente superior a una computadora y que no pueden equipararse, ni siquiera en teoría. Por el contrario, el filósofo Daniel Dennett y el matemático Douglas Hofstadter sostienen la idea opuesta, es decir, que el cerebro es fundamentalmente una computadora muy compleja y que es posible, al menos en teoría, que en el futuro lejano las computadoras artificiales lleguen a equipararse al cerebro humano en sus capacidades. El autor de estas notas debe decir que simpatiza con esta última postura. [...]

Notas:

(1) On computable numbers with an aplication to the Entscheidungsproblem, publicado en el Proceedings of London Mathematical Society, vol. 42 (1937), pp. 230 – 265.

(2) Decíamos en la nota anterior que la Tesis de Turing no puede ser demostrada matemáticamente. Por lo tanto, cualquier argumento que intente justificarla debe ser necesariamente de carácter extra-matemático.

(3) La pregunta de si las máquinas pueden pensar preocupó a Turing durante décadas. En 1950, por ejemplo, presentó la idea de un test (hoy conocido como Test de Turing) que permitiría en teoría determinar si una computadora piensa o no. La idea del test es que si ante preguntas de carácter general una computadora puede dar respuestas que no se distingan de las que daría una persona, entonces puede decirse que la máquina efectivamente piensa. Desde su misma formulación el test ha sido motivo de mucha controversia.

(A la parte 4 - A la parte 6)