La Singularidad Desnuda

Un universo impredecible de pensamientos y cavilaciones sobre ciencia, tecnología y otros conundros

Turing en una cáscara de nuez: No computabilidad

Posted by Carlos en abril 20, 2007

Cuando empezamos a hacer el recorrido por los resultados de Gödel ya teníamos en perspectiva cómo eventualmente llegaríamos a enlazarlos con la noción de no-computabilidad. De hecho, esta noción emana de manera natural de los teoremas de incompletitud, y viceversa: partiendo de la noción de no-computabilidad llegamos a la conclusión de que la consistencia y la completitud de un sistema formal lo suficientemente complejo son características incompatibles entre sí. Vamos a ver por qué sucede esto, y para ello es necesario partir de una definición de computabilidad que nos permita entender qué quiere decir no-computable.

Intuitivamente y sin entrar en muchos detalles, la noción de computabilidad en relación a un cierto problema hace referencia a la posibilidad de disponer de un algoritmo para resolverlo, esto es, que exista un procedimiento mecánico, con descripción finita y no ambigua, y que resuelva dicho problema en tiempo finito. Esto enlaza claramente con el programa formalista de Hilbert, en el que se pretendía tener un procedimiento de este tipo para demostrar/refutar cualquier afirmación matemática expresada en ese hipotético sistema formal definitivo que se anhelaba. En este contexto, el que Gödel hubiera demostrado en su denominado Teorema de Completitud que toda afirmación universalmente válida en la lógica de primer orden es demostrable, conducía a la cuestión obvia de encontrar esa demostración (o determinar su inexistencia) para una cierta expresión lógica. Si nos fijamos un poco, es fácil ver que esta cuestión en el fondo se reduce a determinar si existe una demostración o no, ya que una vez se ha determinado que existe, basta generar sistemáticamente todas las demostraciones (por ejemplo, ordenadas crecientemente por su número de Gödel) hasta dar con la demostración que nos interesa. La determinación de la existencia de una demostración para una fórmula arbitraria de la lógica de primer orden es lo que se conoce como problema de la decisión (Entscheidungsproblem en alemán).

¿Existe algún procedimiento mecánico (un algoritmo) para resolver el problema de la decisión? La respuesta es “no”. Para ver por qué partamos de algún tipo de formalismo para expresar algoritmos, por ejemplo una máquina de Turing (MT). Los detalles del formalismo son realmente poco importantes aquí, pero sí es interesante el hecho de que una MT captura bien la idea intuitiva de procedimiento secuencial, en el que se van realizando acciones paso a paso, y se van tomando decisiones sobre qué acciones realizar. En el marco de un procedimiento de este tipo es natural preguntarse sobre si acaba eventualmente o no. Para formalizar un poco esta idea, consideremos en primer lugar que una MT es una descripción finita de un procedimiento, por lo que podemos codificar dicha descripción como un número natural, de manera similar al proceso de gödelización. Así, Mn es la MT cuya codificación es el número n. Del mismo modo, si el procedimiento admite unos datos de entrada, éstos serán también finitos y representables mediante otro número natural. Diremos entonces que Mn(m) -donde m,n son números naturales- es el resultado de aplicar Mn a los datos de entrada representados por m. En caso de que Mn(m) no se detuviera, diremos que Mn(m)=■.

Vamos a plantearnos ahora la cuestión de si una MT particular se para con unos ciertos datos de entrada o no. Supongamos que se trata de una cuestión computable, esto es, que existe una MT H que tomando como entradas m y n determina si Mn(m) se para o no. Por ejemplo,

H(m,n) = \left\{ \begin{array}{ll} 1 & M_n(m)  \mbox{ se para}\\ 0 & \mbox{en otro caso}  \end{array} \right.

Es fácil demostrar que esta MT no existe haciendo uso del corte diagonal. Para ello, definamos F(n) = 1 + H(n,n) · Mn(n), es decir,

F(n) = \left\{ \begin{array}{ll} 1 & M_n(n)  \mbox{ no se para}\\ 1+M_n(n) & \mbox{en otro caso}  \end{array} \right.

Si H existe, no hay dificultad en definir una MT como F, cuya codificación será un cierto valor r (es decir, Mr=F). Ahora, ¿se detiene F(r)?

  • Si la respuesta es afirmativa, entonces H(r,r) = 1, con lo que F(r) = 1+F(r), lo que es una contradicción.
  • Si la respuesta es negativa, entonces H(r,r) = 0, con lo que F(r) = 1, lo que no tiene sentido, ya que F(r)=■.

Llegamos a una contradicción en ambos casos, por lo que la suposición de partida -que existe H– es falsa. La única posibilidad que tendríamos de escapar de la contradicción es pensar que H es sólo un resolutor parcial de parada (PHS, por sus siglas en inglés), es decir, que puede determinar correctamente si algunos procedimientos se paran o no, pero a veces el propio H no llega a pararse. En otras palabras, H daría una respuesta correcta, o no daría respuesta. En ese caso, no hay inconveniente en suponer que F(r) no se para (i.e., H(r,r) = ■, F(r) = ■). El problema es que no tenemos forma de determinar en general si H es un PHS fiable. Si lo pudiéramos determinar, esto es, si existiera un procedimiento R tal que

R(n) = \left\{ \begin{array}{ll} 1 & M_n \mbox{ es un PHS}\\ 0 & \mbox{en otro caso}  \end{array} \right.

entonces podríamos definir un procedimiento XN

X_N(n) = \left\{ \begin{array}{ll} 1 & n=N \\ \blacksquare & \mbox{en otro caso}  \end{array} \right.

donde N es una cierta constante. La codificación de XN sería w, o más precisamente w(N), dependiendo del valor de N. Definamos ahora un procedimiento Q(n)=R(w(n)). Este procedimiento devolverá 1 si, y sólo si, Xn está en lo cierto al decir que Mn se para (asumimos sin pérdida de generalidad procedimientos sin datos de entrada), es decir, tendríamos un resolutor completo de parada. Como esto es imposible, no podemos disponer por lo tanto de un reconocedor de resolutores parciales de parada.

Hemos encontrado un problema al que no podemos dar respuesta computacionalmente. Las implicaciones de este hecho son enormes. Podemos por ejemplo desandar un poco el camino, y ver que la cuestión de la detención de una cierta MT es expresable mediante una fórmula lógica de primer orden. El que se trate de un problema no computable implica que dicha fórmula es indemostrable e irrefutable, lo que nos lleva a dar una respuesta negativa al problema de la decisión, y enlazar con el primer Teorema de Incompletitud de Gödel. Con todo y con ello, lo más interesante es la cantidad de problemas aparentemente simples que por mor de la no-computabilidad del problema de la parada resultan ser no-computables también. Otro día veremos algunos de ellos.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Anuncios

7 comentarios to “Turing en una cáscara de nuez: No computabilidad”

  1. David said

    Hola Carlos, personalmente encuentro fascinante todos estos temas que has estado planteando ( computabilidad, decidibilidad, completitud, …). Para mí como estudiante de Informática, éstos conceptos representaron casi una bofetada en la cara, la forma de darme cuenta de lo potente, y a la vez, de lo impotente, que puede llegar a ser la computación. En cierta manera ésto enlaza con lo que te comente en una entrada anterior, sobre la belleza casi artística que tienen ciertos razonamientos, por lo reveladores y trascendentes que son.

    Por otra parte, me encanta ver que el tema éste seguirá dando guerra en el blog. Sigue así !!

  2. janzo said

    Opino como David.
    Además estos artículos me están sirviendo como “vista de pájaro” sobre la computabilidad para acercarme a su estudio desde una visión más amplia.
    Este tema es fascinante y hay escaso material (o al menos yo no encuentro) de calidad en nuestra lengua.

  3. Pérez Poch said

    Buenas tarde,

    He topado con esta web divagando por la red. Sólo he leído los artículos sobre Gödel y Turing y me parecen muy encomiables. Me permito aportar un par de referencias por si fueran de interés para ampliar.

    Un guión didáctico en castellano, a mi juicio muy bueno para un nivel elemental, sobre los teoremas de Gödel y Turing se puede encontrar aquí:
    http://eltopologico.blogspot.com/2005/12/gdel-y-turing-parte-1.html

    A los artículos de esta web les encuentro la ventaja de introducir más conceptos técnicos que los del Topo Lógico, con lo que pueden servir para una segunda batida, una vez se ha pasado por la exposición más elemental.

    La introducción que para mí fue útil en su día no está en internet, pero me apetece citarla aquí porque es un libro que me resulta entrañable: “Introducción a la teoría matemática de las computadoras y de la programación”, del matemático por entonces soviético B.A.TRajtenbrot, que se publicó en las colecciones de divulgación de siglo XXI. Trajtenbrot demostró -en otro sitio- que no hay procedimiento de decisión para todas las clases finitas.

    Una introducción reciente facil de encontrar en castellano, es, claro, “Los lógicos”, de Jesús Mosterín -Espasa- que ya se ha citado en otros comentarios.

    Lamento decir que mi relación con estos temas viene de la filosofía -ni siquiera de la llamada ‘lógica’-, lo que me sitúa en el pelotón de los torpes respecto al resto de las personas que están contribuyendo. Aún así, me permito recomendar, a los que leen inglés, la lectura de la web del biografo de Alan Turing Andrew Hodges:
    http://www.turing.org.uk/turing/

    Creo que Hodges aporta la visión más matizada sobre las consecuencias filosóficas de estos teoremas, que suelen ser zanjadas por los especialistas en inteligencia artificial y cientificos cognitivos varios en dos patadas mal dadas. Hodges ha sido colaborador de Penrose -en física- y sus reflexiones sobre los teoremas van en la línea de las de éste, pero con más extensión.

    Por cierto, la biografía de Turing que ha escrito Hodges está editada en castellano, en una edítorial colombiana de la que no encuentro ahora la referencia.

    Finalmente, a quienes estén interesados por rumiar sobre la transcendencia filosófica de los teoremas de Gódel, les aconsejo tener en cuenta su relevancia no sólo respecto al programa de Hilbert, sino también respecto a los enfoques constructivistas en matemática; pienso que es respecto a estos, como empiristas y psicologistas sofistícados, reductores de la matemática a construcción mental, de los que más se distanció Gödel -filosóficamente-. Algo que se puede percibir en sus comparaciones sobre la consistencia de la lógica intuicionista y la lógica clásica -que se pueden zanjar en ‘para este viaje no necesitamos esas alforjas de autorrestricción teórica’-, pero también en otros trabajos…

  4. Pérez Poch said

    La editora en castellano de la biografía de Turing por Hodges es Norma (Bogotá), y la editó en 1998.

  5. Carlos said

    @David y @Janzo: El tema es ciertamente fascinante como comentáis, y todavía nos queda mucha tela que cortar, así que como dicen los ingleses, stay tuned 😉 .

    @Pérez Poch: Gracias por las referencias. La vida de Turing fue de veras convulsa. Parece el sino de los grandes matemáticos del sigo XX.

  6. […] por Carlos on 7/05/07 En el último artículo sobre Turing vimos como hay ciertos problemas cuya resolución no es abordable mediante un proceso […]

  7. […] por Carlos on 15/05/07 Siguiendo la serie sobre computabilidad, hoy nos vamos a fijar en una función muy interesante, y que nos va a servir de […]

Sorry, the comment form is closed at this time.

 
A %d blogueros les gusta esto: