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í:
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:
- Calienta aceite en una sartén.
- Rompe el huevo.
- Vierte el huevo en la sartén.
- Espera hasta que esté hecho.
- Retira la sartén del fuego.
- 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:
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 :-)
