El problema de la parada

Terminaba el post de ayer sobre los bucles infinitos comentando más o menos que una máquina no podría leer un bucle infinito sin quedarse irremediablemente inmersa en él. En los comentarios, Trebol-A nos recordaba un chiste muy bueno sobre el tema con estas palabras:

Pocas veces me he reído tanto como con el chiste aquel del programador muerto en la ducha con un bote de champú en las manos que decía:
– Lavar
– Enjuagar
– Repetir

¿Por qué a los ordenadores se les atragantan tanto los bucles infinitos? ¿No pueden detectarse o evitarse de alguna manera? La respuesta es sencilla: no. Una explicación formal y más precisa tendremos que buscarla en el llamado “problema de la parada“.

Este problema y sus conclusiones tienen implicaciones muy importantes en la gestión de los bucles infinitos que no todo el mundo conoce. Hay que explicar antes de nada que los programadores disponemos de herramientas, conocidas como “depuradores” que nos ayudan a eliminar los errores de nuestras aplicaciones. Podíamos pensar en un depurador que nos alertara de la presencia de bucles infinitos, pero por desgracia, tal herramienta no existirá nunca.

Una de las utilidades del problema de la parada consiste en demostrar que un ordenador no es capaz de reconocer si un programa entra en un bucle infinito. ¿Por qué? Vamos a verlo: imaginemos un ordenador que mostrará un “sí” en pantalla si el programa dado tiene un bucle infinito y un “no” si no lo tiene.

El ordenador comenzaría a ejecutar el programa. Si no tiene un bucle infinito, cuando el programa termine, mostrará un “no”. Supongamos ahora que el programa tarde, por ejemplo, 10 años en realizar sus tareas, sin entrar en un bucle infinito. Al final de los 10 años, el ordenador nos mostrará un bonito “no” en pantalla.

Ahora supongamos que introducimos otro programa, éste con un bucle infinito. El ordenador ejecutará el bucle un número indefinido de veces. Y ahí se quedará para siempre. Jamás podrá salir del bucle, por lo que jamás nos mostrará ese “sí” que nos indicaría precisamente la presencia de un ciclo.

Ahora podemos pensar “bueno, si el ordenador tarda mucho tiempo en mostrarnos el “sí”, significará que el programa entró en un bucle infinito”. Pero ¿cuánto tiempo es “mucho”? ¿Un año? ¿dos? Puede ser que nuestro programa sea complicado y tarde mucho tiempo en ejecutarse… ¿dónde está el límite? Ese el problema precisamente: no podemos predecir si obtendremos respuesta o no, no sabemos si el ordenador parará o no para poder mostrarnos el resultado por pantalla. Dicho de otro modo, si no aparece salida en pantalla, no podremos saber si el programa sigue calculando normalmente o es que ha entrado en un bucle infinito…

Sólo los humanos podemos ver un bucle infinito y no quedarnos el resto de la vida pensando en él. Una muestra más de que los ordenadores son bastante torpes… mucho más que el más estúpido de los humanos. Y eso es ser muy estúpido :-P

Bucles infinitos

No me he cansado de repetir (todavía) que los programas informáticos no son otra cosa que conjuntos de instrucciones que el ordenador “comprende” y ejecuta secuencialmente. Por ejemplo, imaginemos un programa formado por tres instrucciones que se leerán en orden (primero la 1, luego la 2 y por último la 3):

  1. Pide al usuario que escriba su nombre
  2. Escribe en la impresora el nombre del usuario
  3. Fin

Es fácil ver entonces que, a lo largo de la ejecución de un programa, el ordenador irá leyendo y procesando estas órdenes de una en una. Claro que no todo es linealidad pura y dura: muchas veces, al diseñar un programa, nos interesaría repetir algunas instrucciones un determinado número de veces, o ejecutarlas sólo si se dan ciertas condiciones.

Todo esto son mecanismos que nos permiten alterar de alguna manera el flujo del programa. Imaginemos que quisieramos pedir e imprimir el nombre de 3 usuarios con el programa anterior. Una forma sería:

  1. Pide al usuario que escriba su nombre
  2. Escribe en la impresora el nombre del usuario
  3. Pide al usuario que escriba su nombre
  4. Escribe en la impresora el nombre del usuario
  5. Pide al usuario que escriba su nombre
  6. Escribe en la impresora el nombre del usuario
  7. Fin

Pero esto no parece muy productivo… tal vez podríamos hacer algo así:

  1. Repite las siguientes instrucciones 3 veces:
    1. Pide al usuario que escriba su nombre
    2. Escribe en la impresora el nombre del usuario
  2. Fin

Esta estructura se conoce como “bucle“, pues supone introducir un ciclo en el orden de ejecución del programa. Un bucle está formado por una condición y un conjunto de instrucciones que se ejecutan mientras se verifica esa condición. En nuestro caso, la condición sería que “el número de iteraciones del bucle sea menor o igual a 3”, pero podemos poner la condición que queramos.

Y también puede ser que la condición que seleccionemos se verifique siempre… con lo cual el ordenador quedará permanentemente ejecutando las instrucciones que compongan el bucle. Por ejemplo, el bucle…

  1. Repite la siguiente instrucción siempre que 1 sea igual a 1
    1. No hagas nada

… dejará al ordenador en un ciclo continuo de no hacer nada. Tampoco será un problema serio, pues el bucle sólo afectará al programa que lo contenga, y en principio el Sistema Operativo no se desestabilizará. Este tipo de bucles son conocidos en informática como bucles infinitos, y pueden causar fallos bastante graves…

Tal vez piense que evitarlos debe de ser trivial, pero rara vez se sabe de antemano cuántas veces se ejecutará un bucle, y puede ser que suceda algo que no hayamos previsto en el diseño que desencadene una secuencia sin fin… tiene su cosa, no crea…

Bien, ahora imagine un programa con esta pinta:

  1. Ejecuta la instrucción número 1

¿Qué hará el ordenador? Leerá la instrucción 1. ¿Qué dice? Que ejecute la instrucción 1. Vale, voy a leerla. ¿Qué dice? Que ejecute la instrucción 1… y así hasta el infinito (o hasta que el Sistema Operativo arrebate el procesador al programa)

Por cierto, que tiene usted mucha suerte: si fuera un ordenador jamás habría llegado a leer esto, sino que se habría quedado eternamente leyendo el bucle anterior… ¿Por qué? Bien, se trata de algo que veremos en la próxima entrada :-P

Gracias por su cooperación

Es la frase que salía de boca de mi ídolo de la infancia, RoboCop, cuando arrestaba a un delincuente, ya fuera con cooperación o sin ella… La primera entrega de lo que luego fue una olvidable saga me encanta por varios motivos. En particular, creo que da una esperanzadora aplicación a la robótica, y presenta un drama humano muy interesante, con muchas connotaciones filosóficas. Supongo que cuando era pequeño todas estas consideraciones no me importaban en absoluto… pero se trata de un personaje que me divertía y me emocionaba a partes iguales…

gracias.jpg

Hoy tengo que decirles a mis lectores “gracias por su cooperación”. El post anterior retándoles a realizar un diagnóstico sobre un problema intrigante ha desbordado mis espectativas por la respuesta masiva y el enorme nivel de conocimientos que se aprecia en los comentarios. Ya puedo revelar que mi diagnóstico básico es el de un fallo en la controladora del USB, y la reparación requerida, sustituir la placa base.

No obstante, muchos lectores aportaron ideas muy interesantes sobre el problema, así que en cuanto tenga un poco de tiempo libre, revisaré el equipo a fondo para completar mi hipótesis sobre el tema. Y les mantendré informados.

Por cierto, que RoboCop tenía grabadas en su circuitería cuatro directrices, que eran:

  1. Servir a la confianza pública
  2. Proteger al inocente
  3. Defender la ley
  4. Clasificada

La cuarta directiva, de la que en principio Robocop no era consciente, le impedía detener a cualquier miembro de la OCP (la organización que en la película controla la policía de Detroit), y quedaba paralizado si lo intentaba. Eso de las directivas está relacionado con las tres leyes de la robótica enunciadas por Asimov, que son:

  1. Un robot no puede hacer daño a un ser humano o, por inacción, permitir que un ser humano sufra daño.
  2. Un robot debe obedecer las órdenes dadas por los seres humanos, excepto si estas órdenes entrasen en conflicto con la Primera Ley.
  3. Un robot debe proteger su propia existencia en la medida en que esta protección no entre en conflicto con la Primera o la Segunda Ley.

Hay que decir que esto es ciencia ficción y hay que tomárselo como lo que es. Isaac Asimov escribió historias fantásticas sobre robots que sienten y que razonan, pero lo cierto es que estos procesos nos quedan aun demasiado lejos: Estudiemos primero si las redes neuronales nos pueden ayudar a romper el límite computacional. Apuesto a que sí. Una vez hayamos conseguido esto, veamos dónde está el nuevo límite. Comprendamos entonces el funcionamiento de la mente y diseñemos un modelo de la misma.

Creo que moriré sin haber visto a un RoboCop de verdad…

El test de Turing

Allá por el 1950, Alan Turing propuso una prueba, con el objetivo de proporcionar una definición práctica de inteligencia… No es ninguna broma: puede ser que un día nos encontremos ante la situación de tener que decidir si algo es inteligente o no… Nuestro científico computacional favorito sugirió una especie de examen: los sistemas que lo superasen podrían considerarse inteligentes.

Para hacer esta prueba, Turing propuso que un humano interactuase con el sistema (un ordenador, por ejemplo). Si la persona no fuera capaz de saber si está interactuando con un humano o una máquina, entonces el computador a prueba podría considerarse inteligente. El examen consistiría en una serie de preguntas y respuestas.

Desgraciadamente, un computador que supere esta prueba es muy complicado de construir, aunque no imposible. Se supone que un equipo, para pasar este test, necesitaría:

  • Comprender el lenguaje natural y comunicarse satisfactoriamente.
  • Saber cómo guardar sus conocimientos y lo que siente
  • Ser capaz de razonar, utilizando la información que tiene guardada para responder a preguntas o extraer conclusiones
  • Poseer aprendizaje automático, para adaptarse a nuevos contextos

El lector puede pensar “qué tontería, yo sé distinguir perfectamente un ordenador de una persona”… y de hecho es así, de modo que Turing evitó incluir la interacción física en su prueba. A fin de cuentas, no hace falta simular a una persona para poder medir la inteligencia. Hay otra prueba, llamada la Prueba Global de Turing que incluye estos aspectos: el computador debe, además, ser capaz de ver y de manipular objetos. Pero esa es otra historia…

Sin embargo, a muchos nos parece muy discutible que un ordenador pueda ser considerado inteligente por superar esta prueba… Anoche estuve entreteniéndome con un programa llamado Doctor Abuse, que permite mantener conversaciones con él. Incluso podemos descargar el sintetizador para escucharle. Por ejemplo, este es un fragmento de la conversación que mantuve con él:

Abuse > Conozco a algunas personas que se llaman Pau.
Yo > ¿Ah si? Yo no conozco a nadie llamado Abuse
Abuse > Pues quizá deberías de conocerlo.
Yo > Bueno, en realidad ya conozco a alguien ;)
Abuse > Je, je, je :-].
Yo> Bien, me gustaría comentarte un problemilla
Abuse > ¿Pero qué supondría para ti si lo consiguieras?
Yo> Quizá podrías ayudarme
Abuse > ¿De qué forma?
Yo> Dándome consejos, ¿no?
Abuse > ¿Qué tipo de consejos?
Yo> No sé… yo te cuento mi problema y tú me dices cómo podría solucionarlo…
Abuse > Dame más datos acerca de ese asunto.
Yo> Bien. Verás, se trata de un problema que tengo con los ordenadores
Abuse > Ya veo, estamos hablando de un problema que tienes con los ordenadores.

Fascinante, ¿no? Al principio cuesta que nos responda de forma coherente, pero no es más que aprender a tratar con él… Sin embargo, si somos un poco exigentes, en seguida aparecerán respuestas ilógicas o irrelevantes… hay muchas formas de confundir al Doctor Abuse: utilizando dobles sentidos, ironías, sobreentendidos… Así que no podemos decir que éste programa supere el Test de Turing.

Sin embargo (y aqui viene lo más curioso a mi parecer) es que los investigadores de inteligencia artificial apenas se han esforzado en superar esta prueba… y yo estoy de acuerdo con su postura: es más importante entender en qué se basa la inteligencia que duplicar un ser inteligente… Peter Norvig, en su libro Inteligencia Artificial: un enfoque moderno (lectura que recomiendo) lo explica tan bien que me voy a permitir citar:

La búsqueda de un ingenio que “volara artificialmente” tuvo éxito cuando los hermanos Wright, entre otros, dejaron de imitar a los pájaros y comprendieron los principios de la aerodinámica. Los textos de ingeniería aeronaútica no definen el objetivo de su campo como la construcción de “máquinas que vuelen como palomas de forma que puedan incluso confundir a otras palomas”

Fantástico :-)

El límite computacional y los huevos fritos

Un comunicante anónimo nos dejaba en este post el siguiente comentario:

¿Puede alguien dar más detalles sobre el límite computacional este? Jo, esto ha sido como hace años cuando un profe nos dejó tirados con el teorema de Godel y los límites del conocimiento humano pero no nos quiso dar detalles para no complicarnos la vida … :)

Y como lo prometido es deuda, vamos a profundizar un poco en el tema, ya que en el anterior post sobre el límite computacional sólo hablamos, en realidad, sobre la Máquina de Turing.

Imaginemos una lista donde pudiéramos incluir todos los problemas del Universo (sí, se que no parece fácil). Ahora recordemos que los computadores son máquinas que resuelven problemas. Esto último puede resultar extraño, pero los ordenadores no se inventaron para jugar al buscaminas, sino como grandes máquinas calculadoras… ¡qué cosas!

Sabiendo todo ésto, podemos preguntarnos: ¿qué problemas de nuestra lista podremos resolver con un ordenador? De hecho, es una pregunta muy buena: si puedo saber a priori que no puedo resolver computacionalmente un problema, me evitaré el esfuerzo de intentarlo (salvo si me gusta trabajar en vano). A los programas que pueden resolverse computacionalmente los vamos a llamar, en adelante, problemas computables.

Bien, si separara en otra lista los programas computables de los que no lo son, lo primero que veríamos es que el conjunto de los computables es mucho menor que el otro. Si lo representáramos como un huevo frito sería una cosa así:

lc01.jpg

El límite entre la yema y la clara es precisamente el famoso límite computacional… (estoy impresionado por lo geeky de mi propia exposición…) Ahora bien, en la informática, ¿dónde se encuentra exactamente ese límite? Esto quizá sea más complicado, así que vamos a dar algunas ideas.

Un algoritmo es una secuencia de instrucciones que un ordenador comprende. O sea, del estilo de “abre el menú de inicio”, “conéctame con Internet”… cosas del estilo, nunca le decimos al ordenador “¿qué piensas sobre mi peinado esta mañana?”, sólo le mandamos que haga cosas (¡qué vida más dura!). Para poner un ejemplo, éste el algoritmo para freír un huevo:

  1. Calienta aceite en una sartén.
  2. Rompe el huevo.
  3. Vierte el huevo en la sartén.
  4. Espera hasta que esté hecho.
  5. Retira la sartén del fuego.
  6. Extrae el huevo de la sartén.

Los ordenadores son muy buenos para hacer este tipo de acciones, pero desgraciadamente son las únicas que pueden hacer: los problemas que un ordenador puede resolver (los computables, o la yema del huevo) son los que tienen un algoritmo. Con “problemas que tienen un algoritmo” quiero hacer referencia a los problemas resolubles mediante la aplicación de un número finito de pasos sencillos.

Y si lo piensa se dará cuenta: nunca le dirá a su ordenador “haz eso, ya sabes, lo del otro día” o “¿qué opinas sobre Kant?”. Y si se lo dice, jamás podrá obedecerle: son dos ejemplos del inmenso mundo de problemas que no tienen algoritmo; esto es, que no pueden resolverse en un número finito de pasos concretos. No obstante, sumar dos números puede hacerse en un número muy pequeño de pasos, de la misma forma que buscar una palabra en un texto… Para ilustrar esto último, he revisado la imagen del huevo:

lc02.jpg

Ni más ni menos. Y (casualidades de la vida), todos los programas argorítmicos tienen una máquina de Turing que los resuelve. Y viceversa: todas las Máquinas de Turing expresan soluciones algorítmicas. Como apunte extra, diré que ésto se conoce como la Tesis de Church-Turing

Espero haber esclarecido el tema del límite computacional que tanto intriga a nuestros lectores… la verdad es que uno no se cansa nunca de revisar estas cosas, y siempre está bien recordar que, en contra de lo que nos venden, los ordenadores no valen para todo… Ah, y si se lo están preguntando, sí: un ordenador podría freír un huevo :-)

Deprímase: El límite computacional

Vamos a imaginar una extraña máquina… una máquina que consta de simplemente de una cinta de papel y un cabezal que sea capaz de hacer estas tres acciones:

  • Moverse una posición a la derecha o a la izquierda
  • Leer un caracter
  • Escribir un caracter

Parece sencillo, ¿no? Esta máquina se conoce como Máquina de Turing, en honor a su creador, Alan Turing. Y es bastante sencillo construir una. Hay quien ha optado por el Lego, aunque también podemos simular una con papel y lápiz…

Ahora agárrese a la silla: esa máquina inocente puede hacer exactamente lo mismo que su potente ordenador. Dicho de otro modo más impactante: no podrá hacer nada con su ordenador que yo no pueda hacer con mi máquina de Turing.

Piense en algo que pueda hacer con su equipo, lo más complicado… puedo jurarle que la máquina de Turing puede hacerlo. Probablemente más despacio, pero lo hará… ¿Se lo imagina? Esto no es vudú ni magia negra, sino que se debe al hecho (dramático) de que un ordenador no es más que una máquina de Turing.

mt.jpg

Si queremos una explicación más detallada, tenemos que entender que los ordenadores no son más que unos dispositivos que computan, esto es, que calculan cosas a partir de otras cosas. Dibujar algo en una pantalla no es una tarea complicada para un ordenador, en absoluto… sus problemas vienen cuando se trata de realizar operaciones o decidir sobre problemas… de hecho, si pudieramos meter en una bolsa todos los problemas del universo, veríamos que los ordenadores sólo son capaces de resolver unos pocos… Otro día comentaré algunos problemas que los computadores convencionales jamás podrán solucionar…

El panorama es un poco deprimente… mi potente equipo no puede hacer nada que no pueda hacer la máquina de Lego que comentaba antes… esto, en teoría de computación se conoce como el “límite computacional”, que delimita esa pequeña porción de problemas en los que los ordenadores se sienten cómodos… Este límite no ha cambiado, ni cambiará… los ordenadores son capaces de resolver problemas que antes no podían resolverse en un tiempo razonable, pero no hacen nada ahora que no pudieran hacer antes.

Alan Turing postuló que el poder de su máquina llegaba hasta el mismo límite computacional. Y parece que no se equivocó…