Aquiles: Qué curioso lo similar de esta pregunta a la conjetura de Goldbach (que sustituye "diferencia" por "suma")
Tortuga: Ciertamente. Pero existe una diferencia impresionante. (...) su búsqueda de una representación de un billón como la suma de dos primos tiene la garantía de finalizar.
Aquiles: ¡Ahhh! Ya veo, si elijo representar un billón como la diferencia de dos primos no tendré ningún límite para el tamaño de los primos involucrados, podrían ser tan grandes que me tomaría un billón de años encontrarlos.
D.R. Hofstadter: Gödel, Escher, Bach, un eterno y grácil bucle.
En este artículo daremos una breve introducción a la teoría de la computabilidad, con implicaciones para el conocimiento, la mente, la inteligencia artificial y el Universo (casi nada ;-) .
Comprobación de afirmaciones sobre números
Tal como expone la conversación entre Aquiles y la Tortuga, hay afirmaciones de la teoría de números que pueden comprobarse en un número máximo de pasos previamente conocido, mientras que en otras afirmaciones no podemos asegurar cuantos pasos son necesarios. Para saber si un número natural N es igual a la suma de dos primos, basta con ir probando todas la combinaciones de dos primos menores que el propio número N. Por ejemplo, para N = 24 efectuaremos las sumas crecientes 1+1=2, 1+3=4, 2+3=5, 1+5=6, ..., 11+11=22, 11+13=24. Este proceso tenía que acabar como mucho sumando N-1=23 con 1.
En cambio si buscamos diferencias de números primos no hay un número límite, ya que siempre podemos escoger primos arbitrariamente grandes, como por ejemplo 991-967=24. Este hecho aparentemente inocente tiene profundas implicaciones, como veremos. Para ello, introducimos los conceptos de sistemas formales y recursión.
Tal como expone la conversación entre Aquiles y la Tortuga, hay afirmaciones de la teoría de números que pueden comprobarse en un número máximo de pasos previamente conocido, mientras que en otras afirmaciones no podemos asegurar cuantos pasos son necesarios. Para saber si un número natural N es igual a la suma de dos primos, basta con ir probando todas la combinaciones de dos primos menores que el propio número N. Por ejemplo, para N = 24 efectuaremos las sumas crecientes 1+1=2, 1+3=4, 2+3=5, 1+5=6, ..., 11+11=22, 11+13=24. Este proceso tenía que acabar como mucho sumando N-1=23 con 1.
En cambio si buscamos diferencias de números primos no hay un número límite, ya que siempre podemos escoger primos arbitrariamente grandes, como por ejemplo 991-967=24. Este hecho aparentemente inocente tiene profundas implicaciones, como veremos. Para ello, introducimos los conceptos de sistemas formales y recursión.
Sistemas formales y proposiciones recursivas
Un sistema formal es un conjunto de símbolos (el alfabeto del sistema, también llamados axiomas), reglas para combinar los símbolos para formar secuencias de símbolos (también llamadas cadenas o teoremas) y las reglas de la lógica de proposiciones, para poder afirmar o negar proposiciones.
Por ejemplo, sea el siguiente sistema formal:
UUU (por la regla I), ∀xUUUy xMy (la regla II).
En todo sistema formal hay verdades (teoremas y axiomas) y falsedades (ninguna de las anteriores):
Una proposición es recursiva si podemos diseñar un algoritmo que sea capaz de comprobar si la proposición es cierta. Si además el algoritmo necesita una secuencia de pasos de finalización predecible, entonces la proposición es recursiva primitiva. Así, en el sistema de la aritmética, la afirmación "el número N cumple la conjetura de Goldbach", equivalente a decir "es igual a la suma de dos primos", es una verdad recursiva primitiva, ya que podemos comprobarlo realizando operaciones aritméticas en un número finito que será menor o igual que un límite dado. En cambio la proposición "N es una diferencia de dos primos" no es recursiva primitiva, pues no sabemos el número máximo de pasos a seguir. Cuando todas las proposiciones que podamos hacer sobre un sistema son recursivas, el propio sistema formal será recursivo.
Por ejemplo, sea el siguiente sistema formal:
- Alfabeto: "M","U"
- Cadenas válidas: secuencias de las letras del alfabeto que siguen las reglas.
- Regla I: a una cadena terminada en U se le puede agregar otra U
- Regla II: a una cadena que contenga la secuencia UUU se le puede sustituir la secuencia por M
- Variables: x, y, z que representan cadenas cualesquiera
- Operaciones lógicas: AND, OR, NOT , (implicación), ∀ (para todo)
UUU (por la regla I), ∀xUUUy xMy (la regla II).En todo sistema formal hay verdades (teoremas y axiomas) y falsedades (ninguna de las anteriores):
- UU es un teorema: es cierto
- M es un axioma: es cierto
- MU M es falso: no hay ninguna regla que lo permita
Una proposición es recursiva si podemos diseñar un algoritmo que sea capaz de comprobar si la proposición es cierta. Si además el algoritmo necesita una secuencia de pasos de finalización predecible, entonces la proposición es recursiva primitiva. Así, en el sistema de la aritmética, la afirmación "el número N cumple la conjetura de Goldbach", equivalente a decir "es igual a la suma de dos primos", es una verdad recursiva primitiva, ya que podemos comprobarlo realizando operaciones aritméticas en un número finito que será menor o igual que un límite dado. En cambio la proposición "N es una diferencia de dos primos" no es recursiva primitiva, pues no sabemos el número máximo de pasos a seguir. Cuando todas las proposiciones que podamos hacer sobre un sistema son recursivas, el propio sistema formal será recursivo.
Expresabilidad y representabilidad
En un sistema formal la expresabilidad significa que cualquier predicado que enunciemos sobre el sistema podrá expresarse en el lenguaje propio del sistema.
Resulta ser que todo sistema recursivo es expresable.
Resulta ser que todo sistema recursivo es expresable.
Entonces cualquier afirmación cierta o falsa respecto al sistema, como por ejemplo "no existe ningún teorema (cadena bien formada) que termine en MU", la podremos expresar con los símbolos del sistema: "NOT xMU". Tenemos que este sistema posee la propiedad de la expresabilidad.
La representabilidad de una proposición significa que siempre que la proposición es cierta entonces tenemos un teorema del sistema, y cuando es falsa tenemos un no teorema. Por ejemplo "existen cadenas que terminan en MU" produce las cadenas MU, UMU, MUMU, ... ¿Son todas teoremas? Sí lo son. (compruébelo el lector). En el caso de que cualquier cadena terminada en MU sea un teorema, diremos que la proposición es representable. Si todas las proposiciones posibles son representables, el sistema formal será representable.
La propiedad de la representabilidad es más difícil de poseer que la expresabilidad. No insistiremos en ello, ya que nos apartaría de la línia que nos hemos trazado.
Verdades y falsedades no computables
Se cree que la propiedad de un sistema de ser recursivo implica que es computable (tesis Church-Turing), o sea que para saber si una proposición es cierta o falsa podemos programar un computador que nos responda la pregunta; el tiempo que empleará dependerá de si la proposición es recursiva primitiva o no.
¿Qué afirmaciones no serán recursivas y por tanto no computables? En general cualquier sistema suficientemente complejo para poder referenciarse a sí mismo será no recursivo. Por ejemplo, decidir si un algoritmo que busca dos números primos cuya diferencia sea igual a un billón se detendrá en un número finito de pasos no es un problema computable; o sea, no existe ningún algoritmo que decida si el algoritmo de las diferencias de primos se detendrá. Entonces la verdad o falsedad de la afirmación "el algoritmo que busca dos números primos cuya diferencia sea igual a un billón se detendrá" no es computable. Observemos que "no computable" significa que no sabemos si el programa de ordenador encontrará la solución en tiempo determinado, que es indecidible computacionalmente.
Ahora bien, parece evidente que toda afirmación ha de ser falsa o verdadera, aunque ello sea indecidible computacionalmente. ¿O quizá no está tan claro?. Veamos algunas opiniones al respecto.
Computabilidad de la mente. Tesis de la inteligencia artificial (IA)
Viene a decir: "Lo que es computable por los seres humanos es computable a través de máquinas". O sea que todo proceso mental de decisión ha de poder representarse por un algoritmo que se pueda ejecutar en un ordenador. Si es el caso, entonces como hay afirmaciones indecidibles computacionalmente, tales afirmaciones también seran indecidibles para la mente humana. Siguiendo esta línea de razonamiento, si una afirmación es indecidible, ¿podemos sostener que ha de ser cierta o falsa? ¿O bien su certeza es simplemente indefinida, ni cierta ni falsa?
Nuestra intuición nos indica lo contrario, que toda afirmación ha de estar definida, otra cosa es el conocimiento que tengamos sobre ella. Siguiendo nuestra intuición diríamos que hay un conocimiento computable y también un conocimiento no computable. La cuestión ahora es: ¿la mente tiene acceso al conocimiento no computable?. Según los defensores de la IA la respuesta es negativa.
Por otro lado existe la teoría de la hipercomputación que afirma la posibilidad de programar máquinas para resolver problemas no recursivos; si fuera cierto todos los enunciados serían decidibles computacionalmente, e incluso podríamos tener IA superior a la inteligencia humana.
Autoconciencia y computabilidad
La autoconciencia es una forma de auto-referencia, y en principio, aplicando lo visto hasta ahora, podemos pensar que es poseída por sistemas no computables. No obstante, los seguidores de la tesis de la IA en su versión fuerte enuncian que también la conciencia ha de ser computable. Claro, siempre podemos separar la conciencia de la autoconciencia, y decir que la primera es computable y la segunda no; por ejemplo, un gato es consciente pero no es autoconsciente, así que debería ser posible emular con un ordenador la mente de un gato, algo que todavía está fuera de nuestras posibilidades. (Nota: IBM anunció que había construido un superordenador con 147.000 CPU's que tenía la potencia de cálculo del cerebro de un gato, pero hay cierta controversia con ello, y además sólo han construido el "hardware", falta el "software", esto es, la mente).
La representabilidad de una proposición significa que siempre que la proposición es cierta entonces tenemos un teorema del sistema, y cuando es falsa tenemos un no teorema. Por ejemplo "existen cadenas que terminan en MU" produce las cadenas MU, UMU, MUMU, ... ¿Son todas teoremas? Sí lo son. (compruébelo el lector). En el caso de que cualquier cadena terminada en MU sea un teorema, diremos que la proposición es representable. Si todas las proposiciones posibles son representables, el sistema formal será representable.
La propiedad de la representabilidad es más difícil de poseer que la expresabilidad. No insistiremos en ello, ya que nos apartaría de la línia que nos hemos trazado.
Verdades y falsedades no computables
Se cree que la propiedad de un sistema de ser recursivo implica que es computable (tesis Church-Turing), o sea que para saber si una proposición es cierta o falsa podemos programar un computador que nos responda la pregunta; el tiempo que empleará dependerá de si la proposición es recursiva primitiva o no.
¿Qué afirmaciones no serán recursivas y por tanto no computables? En general cualquier sistema suficientemente complejo para poder referenciarse a sí mismo será no recursivo. Por ejemplo, decidir si un algoritmo que busca dos números primos cuya diferencia sea igual a un billón se detendrá en un número finito de pasos no es un problema computable; o sea, no existe ningún algoritmo que decida si el algoritmo de las diferencias de primos se detendrá. Entonces la verdad o falsedad de la afirmación "el algoritmo que busca dos números primos cuya diferencia sea igual a un billón se detendrá" no es computable. Observemos que "no computable" significa que no sabemos si el programa de ordenador encontrará la solución en tiempo determinado, que es indecidible computacionalmente.
Ahora bien, parece evidente que toda afirmación ha de ser falsa o verdadera, aunque ello sea indecidible computacionalmente. ¿O quizá no está tan claro?. Veamos algunas opiniones al respecto.
Computabilidad de la mente. Tesis de la inteligencia artificial (IA)
Viene a decir: "Lo que es computable por los seres humanos es computable a través de máquinas". O sea que todo proceso mental de decisión ha de poder representarse por un algoritmo que se pueda ejecutar en un ordenador. Si es el caso, entonces como hay afirmaciones indecidibles computacionalmente, tales afirmaciones también seran indecidibles para la mente humana. Siguiendo esta línea de razonamiento, si una afirmación es indecidible, ¿podemos sostener que ha de ser cierta o falsa? ¿O bien su certeza es simplemente indefinida, ni cierta ni falsa?
Nuestra intuición nos indica lo contrario, que toda afirmación ha de estar definida, otra cosa es el conocimiento que tengamos sobre ella. Siguiendo nuestra intuición diríamos que hay un conocimiento computable y también un conocimiento no computable. La cuestión ahora es: ¿la mente tiene acceso al conocimiento no computable?. Según los defensores de la IA la respuesta es negativa.
Por otro lado existe la teoría de la hipercomputación que afirma la posibilidad de programar máquinas para resolver problemas no recursivos; si fuera cierto todos los enunciados serían decidibles computacionalmente, e incluso podríamos tener IA superior a la inteligencia humana.
Autoconciencia y computabilidad
La autoconciencia es una forma de auto-referencia, y en principio, aplicando lo visto hasta ahora, podemos pensar que es poseída por sistemas no computables. No obstante, los seguidores de la tesis de la IA en su versión fuerte enuncian que también la conciencia ha de ser computable. Claro, siempre podemos separar la conciencia de la autoconciencia, y decir que la primera es computable y la segunda no; por ejemplo, un gato es consciente pero no es autoconsciente, así que debería ser posible emular con un ordenador la mente de un gato, algo que todavía está fuera de nuestras posibilidades. (Nota: IBM anunció que había construido un superordenador con 147.000 CPU's que tenía la potencia de cálculo del cerebro de un gato, pero hay cierta controversia con ello, y además sólo han construido el "hardware", falta el "software", esto es, la mente).
Computabilidad del Universo
Hay teorías que afirman que el Universo en su conjunto se comporta como un inmenso ordenador, que procesa información y la transforma.
En esta línea una de las variantes afirma que el Universo sólo procesa información recursiva (computable), y precisamente por ello la información no recursiva es no computable, ya que el Universo no puede contener un ordenador más potente que él mismo (!). Equivalentemente, se afirma que el Universo se comporta como una máquina de Turing. Si están en lo cierto, todo proceso físico podrá simularse en un computador, y la Física computacional eventualmente podrá simular todo el Universo.
Otra corriente de opinión sostiene que existen procesos no computables, y que no podemos ignorarlos, y por tanto el Universo se comporta como un hipercomputador cuántico. Entonces, en un futuro podría ser posible construir hipercomputadores que resolvieran todos los problemas, tanto computables como no computables.
Por último hay quienes opinan que el Universo no es computable ni lo será nunca, y que la hipercomputación es irrealizable en la práctica.
Conclusiones
De un asunto aparentemente muy específico, como es la computabilidad de afirmaciones numéricas sencillas, vemos que se extienden ramificaciones que llegan a la teoría del conocimiento (cómo saber que es cierto y que es falso), la mente y la conciencia e incluso a todo el Universo, planteándonos cuestiones muy importantes que quedan abiertas.
Bibliografía
- D.R. Hofstadter: Gödel, Escher, Bach, un eterno y grácil bucle.
Interesante discusión sobre los sistemas formales :) el próximo semestre llevaré lógica y teoría de conjuntos estoy emocionado por ello hay quienes dicen que es bastante complicado pero a mi me interesa (aunque bien es cierto que no he leído mucho sobre ello sólo he ojeado un poco el libro de Carlos Ivorra y me pareció algo complicado)
ResponderEliminarPor este tipo de artículos es que el blog es magnífico, me gustaría que escribieras más sobre la conciencia es fascinante el tema.
Me pareció inquietate la idea de que el universo se comporta cómo un ordenador jamás había escuchado nada parecido y es una idea para realmente ponerse a pensar buscaré sobre ello.
Se me olvidó comentar sobre IBM y la nota en donde afirman haber emulado el comportamiento de un gato , yo tenía entendido que muchas de las pruebas que se realizaron fueron exitosas también hay una nota sobre como una supercomputadora (no se si sea la misma) ganó a un humano en un juego que se requiere cierta empatía y sentido del humor llamado Jeopardy!
ResponderEliminaraquí el link http://eliax.com/index.cfm?post_id=8505
¿Qué opinas de ello?
yo en lo particular no soy un seguidor de la IA fuerte pero me desconcierta el asiduo y constante progreso que tienen sus seguidores
Tienes unos artículos profundos y estupendos,Sigue así
Saludos
Respecto a IBM, he visto algunas notas que ponen en duda la simulación, por ejemplo: http://www.diosesimaginario.com/index.php/2009/computadora-cerebro-de-gato-de-ibm-desacreditada/
ResponderEliminarhttp://www.neoteo.com/el-cerebro-de-gato-de-ibm-un-engano
Creo que los superordenadores que juegan mejor que los humanos son una realidad; es más, a nivel puramente intelectual creo que las máquinas acabaran superándonos, en eso coincido con la tesis de la IA: todo lo computable puede ser programado en un ordenador. Pero tal como expuse en el artículo, no todo es computable, seguramente la autoconciencia no lo sea. Entonces ese sería el límite para la IA, la cual nunca podría crear seres autoconscientes, y por tanto libres, sólo podría crear seres programados, predecibles, sin libertad. Esta sería mi tesis, pero actualmente sólo es una opinión, me falta maś información para desarrollarla.
Gracias por tus comentarios.
Saludos
Se me ocurre una argumentación sencilla, con un contenido empírico:
ResponderEliminar(i) Todo lo que es computable a través de máquinas pertenece a un sistema formal coherente (y si una fórmula no puede obtenerse a partir de las reglas del sistema, la misma no pertenece a él; en el ejemplo del post, CELARENT no es una fórmula válida del sistema).
(ii) Existen procesos mentales en sí incoherentes (razonamientos falaces, fenómenos psíquicos azarosos, actos libres, etc.)
Por lo tanto:
(iii) No todo proceso mental es computable a traves de máquinas.
Sé que el hecho empírico aludido en (ii) es a veces negado por algunos filósofos, pero también es cierto que prescindiendo de toda refrencia a hechos, y basando la argumentación en métodos deductivos, esa pretención genera una petitio principii pues se cree que la mente humana equivale a lo afirmable según dichos métodos, de modo que se excluye por principio todo posible contrejemplo de lo que se quiere demostrar por no ser conforme al sistema en cuestión (y no por no ser hecho.
Por otra parte llama la atención la similitud de la tesis del universo computacional y el deísmo de la filosofía en la modernidad.
Un saludo.
Gracias por tus comentario.
ResponderEliminarEn principio podemos programar algoritmos que no sean determinísticos, de forma que su resultado sea aleatorio, a veces correcto y a veces incorrecto, caótico, etc. Entonces creo que podemos simular los procesos mentales "ilógicos", haciendo que la máquina caiga en errores de vez en cuando.
Respecto al deísmo coincido contigo, en efecto, es sugerente la idea de identificar, hasta cierto punto, una posible deidad con el "programa" que hace funcionar el universo. E incluso con una mente universal no computable.
Saludos.
¿Algoritmos no determinísticos? ¿Cómo se programa un error? ¿Es un verdadero resultado fortuito basado en un procedimiento mecánico o apela a algún fenómeno externo (obtenido por ejemplo del medio físico, donde sin duda la no se trataría de un procedimiento mecánico formal)? Es decir, es obvio que puede simularse un error, pero mediante un programa determinístico, y también es obvio que puede obtenerse un dato del medio, aunque ahí se sale del sistema; pero no sabía que un programa podía errar. Sería muy interesante un post al respecto, no?
ResponderEliminarSaludos
En Investigación Operativa hay una clase de problemas denominados estocásticos en los cuales algunos parámetros son deterministas y otros son aleatorios, que se tratan con los algoritmos de optimización estocástica; es un campo activo de investigación en el que trabaja un colega y que conozco un poco.
ResponderEliminarPor otro lado tal como dices está claro que puede incorporarse a un programa un error aleatório, y efectivamente aquí nos encontramos con el problema de la aleatoriedad: ¿cómo generar algo realmente aleatorio? Tienes razón en proponerlo como tema, pues da bastante de sí. Lo intentaremos ;-)
Saludos.