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

  1. Guau. Muuuuy interesante.
    Aunque sin duda, lo que más me ha impresionado ha sido el dibujillo del huevo ;)
    Me parece a mí que no fríes muchos huevos, se te ha pasado hablar de echarle aceite por encima con la espumadera :P

  2. Depende, si los fríes con muy poco aceite (a mí me gusta así, aparte de ser más sano) el mismo calor hace que la yema se cocine.
    Si por el contrario hay más aceite, entonces sí que hay que echar aceite por encima :P
    Interesante disertación :)

  3. Ya veo, así que el límite computacional viene a ser que los computadores actuales solo pueden resolver problemas que se puedan resolver con algoritmos.

    Pero lo que no me queda claro por lo que leí en el link a la wikipedia lo que no se ha demostrado es que haya problemas que no se puedan resolver con un algoritmo (o se os ocurre alguno), así que me guardaré mucho de vacilarle a un ordenador basandome en el límite computacional.

    De hecho aunque fuera una ley en lugar de una tesis también me guardaría mucho de vacilarle a un ente que con una simple pantalla azul puede hacerme perder meses de trabajo. Además, seguro que me ponen el ‘word verification’ más chungo para que no me ponga chulo; [ACTUALIZADO] -> o me putea al hacer comentarios en blogs ajenos.

    Otro tema es si las personas sí que somos capaces de resolver problemas sin algoritmos.

    Especialmente si no somos capaces ni de ponernos de acuerdo en el algoritmo de freir un huevo. Suerte que a mí no me gustan especialmente (aunque apreciaré los comentarios que querais hacer sobre las tortillas de patatas).

  4. El hecho de que la Tesis de Church-Turing no esté demostrada se debe a que es muy complicado formalizar términos como «algoritmo», desde mi óptica no hay motivos para pensar que es falsa.
    Hay muchos problemas que los humanos podemos resolver mediante intuición para los que no hay un algoritmo: ¿cuál es el algoritmo para formarse una opinión sobre algo? Hay un ejemplo computacional: un ordenador nunca podrá saber si un programa va a terminar o bien va a quedarse permanentemente calculando (bucle infinito). Esto se conoce como el «problema de parada».
    Como he dicho, de todos los problemas, los que pueden resolverse algorítmicamente son una pequeña fracción de todo el conjunto de problemas.
    Y en relación con lo que dices, las personas sí que somos capaces de resolver problemas sin algoritmos: de hecho lo hacemos contínuamente… expresarte en el comentario era un problema al que te enfrentaras, y seguramente no has seguido una secuencia formalizada de pasos: lo has escrito y punto. Pídele a tu ordenador que lo haga, seguro que no puede :)
    El límite computacional es un concepto lo bastante sólido para que puedas vacilar a tu ordenador… otra cosa es que él pueda vengarse, como bien dices, haciéndote perder el trabajo de meses :)
    ¡Gracias por el comentario!

  5. Yo creo que los humanos siempre estaremos por encima de los ordenadores porque, aunque un ordenador pueda vengarse con una pantalla azul haciéndote perder tu trabajo, tu siempre puedes pegarle una patada, y eso si que no te lo puede devolver, jijiji.

  6. :) es una buena apreciación.
    De todas formas las pantallas azules no son algo inherente a la computación, sino que pertenecen a un Sistema Operativo concreto. A los demás esas cosas no les pasan, cosas de la vida…

  7. Buenas. Llego tarde al comentario, pero no me he podido resistir.

    El limite computacional… mas que eso, me gustaria pensar que el limite no esta ahi, sino en la capacidad humana de crear algoritmos para solucionar ese tipo de problemas.

    Problemas como el tratamiento de la imagen, se creian ireesolubles hace unos años, y ahora nos encontramos cosas cada vez mas interesantes. Si, los ordenadores han avanzado, pero tambien ha avanzado la manera de enfrentarse a los problemas por parte de los programadores…

    Ese limite computacional, me parece mas difuso que en la analogia (fantastica, por cierto) del huevo frito. Es responsabilidad nuestra encontrar formas de traspasar los problemas de la clara, a la yema.

    Un saludo.

  8. hola soy Denisse: me encanto tu forma de aclarar lo que es un algoritmo porque me hizo acordarme cuando me lo enzeñaron en el colegio gracias

Los comentarios están desactivados.