Estimados lectores, mundialmente tenemos una dependencia monstruosa hacia todo lo relacionado con la computación electrónica (y también hacia la computación teórica, aunque no lo sepamos con claridad) tanta que es impensable la vida del hombre sin un gadget o una máquina “inteligente” a su lado (o sobre la palma de su mano, sus ojos o muñecas). Siendo tan necesaria esta circuitería en nuestras vidas, alguno de ustedes se ha puesto a pensar o a indagar… ¿de dónde provienen y cómo se crearon estas aleaciones de bits y bytes? ¿Serán solamente una maraña inanimada de cables y protoboards soldadas que funcionan con luz eléctrica? ¿Realmente cuánta es la percepción que una computadora es capaz de tener del mundo? Y quizá la pregunta más importante y clave: ¿es capaz una computadora de resolver cualquier problema en un número finito de pasos o es apta para decirnos si ese problema tiene una solución o no?

Para el padre de la computación, y quiero enfatizar, el verdadero padre de la computación, Alan Turing, el último cuestionamiento del párrafo anterior resultó clave en las investigaciones de toda su vida, pues fue una de las bases con las cuales se construyeron las computadoras que conocemos hoy en día. Y por otra parte la respuesta a esa pregunta, la vivimos a diario, o casi a diario, durante esos angustiosos momentos donde necesitamos urgentemente que nuestro tablet, nuestra laptop o el explorer.exe reaccionen rápido: exactamente cuando se nos quedan bien pasmados y no responden. Con todo esto, acabo de escribirles un poco sobre “El problema de la Parada” pero en las siguientes líneas ahondaré más sobre su origen, explicación y la relevancia en nuestro mundo actual.

El comienzo de todos los modelos computacionales se remonta a la década de los años 30. Aquí suenan nombres de figuras extraordinarias como Alan Turing, Alonzo Church y Kurt Gödel entre otros; y especialmente el nombre de Alan Turing es famoso pues entre varios de sus logros significativos se le debe la victoria de los Aliados en la Segunda Guerra Mundial por haber descrifrado la máquina Enigma de los nazis, pero ese es un tema, muy interesante por cierto, para siguientes posts. El punto inicial de la historia de la computación moderna por así decirlo, radicó en los famosos problemas del milenio propuestos por el matemático David Hilbert allá en el lejano 1900. Hilbert propuso una lista de 23 problemas sin resolver en el Congreso Internacional de Matemáticos de París cuya finalidad era proponer grandes retos a las nuevas generaciones de científicos en el nuevo siglo que comenzaba e impulsar enormemente el desarrollo de las ciencias. Uno de esos problemas fue la columna vertebral para el inicio de la era de la información, el llamado Entscheidungsproblem o problema de decisión. Este consistía en encontrar un algoritmo general que nos ayudara a precisar si una fórmula en el cálculo de primer orden era un teorema; un teorema es una proposición que afirma una verdad que se puede demostrar perfectamente. En palabras mundanas, la cuestión planteada por David Hilbert sobre el asunto de las decisiones era si había un método definido que pudiera aplicarse a cualquier sentencia matemática y que nos dijera si esa sentencia era cierta o no.

Alan Turing describió en su trabajo On computable numbers with an application to the Entscheidungsproblem un artefacto autómata que consistía en una cinta con símbolos definidos y una cabeza lectora que se movía a través de dicha cinta mediante una serie de reglas. Esta máquina de Turing es el equivalente a lo que se conoce como algoritmo, grosso modo una serie de pasos para resolver un problema, y bajo la lógica computacional, una máquina de Turing puede solucionar cualquier cosa que se le presente a una computadora de la actualidad. Y eso es porque lo que Alan Turing describe en su trabajo es la piedra angular de las computadoras presentes; la diferencia radica principalmente en los recursos y espacio de tiempo utilizados, ya que por razones claras una computadora con 8 núcleos procesa más rápido un problema de, por ejemplo, encontrar los primeros 100.000 números de la sucesión Fibonacci que una Máquina de Turing con cintas mecánicas. Lo más importante de todo esto es que una Máquina de Turing sigue siendo la representación fiel de nuestras máquinas actuales.

Volviendo al tema de inicio, Turing con su creación e influenciado de igual forma por el teorema de incompletitud de Gödel, demostró que existían problemas que no se podían resolver y uno de ellos era el Entscheidungsproblem, ya que no había forma de saber mediante ese mecanismo de cintas que establece la máquina de Turing si existía un algoritmo que pudiera decidir si dicha máquina se para en algún momento. Lo que aquí se puntualiza es justamente el Problema de la Parada: no existe una manera automática computable de saber si todos los programas del mundo terminan. Lo cual no quiere decir que no haya prueba para programas concretos, pero recordemos que el Entscheidungsproblem debía satisfacer el universo de “para todo” y Turing con su máquina establecía una tesis que daba una respuesta negativa al problema.

La irresolubilidad del problema la podemos demostrar con una paradoja que se nos enseña a todos los que llevamos alguna vez una materia de teoría computacional, la cual es bastante sencilla de entender y muy didáctica. Supongamos que el problema de la Parada realmente tiene una solución mágica mediante un algoritmo al que llamaremos Se_Acaba(X,Y), que recibe como entrada un programa X y datos de entrada Y y muestra como resultado un Verdadero si el programa acaba o Falso si el programa no acaba. En un pseudocódigo sería más o menos así:

Se_Acaba (X, Y) {# Código mágico que soluciona el problema y al final regresa Verdadero o Falso}

Ahora bien, suponiendo que existe ese algoritmo se puede utilizar obviamente dentro de otros programas y algoritmos; ahora lo probaremos en uno al que llamaremos Paradoja(). Este recibirá ahora como entrada el código de un programa cualquiera, por ejemplo Z, y utilizará el algoritmo Se_Acaba(X,Y) para decidir sobre el mismo si termina o no. Es decir, vamos a aplicar el algoritmo sobre el propio programa Z como dato de entrada. Pero con una añadidura: si Z termina, entonces Paradoja() entra en un ciclo infinito; y si Z entra en un ciclo infinito, es decir, si no termina, entonces Paradoja termina:

Paradoja (Z) {Si Se_Acaba (Z, Z) Mientras regrese Verdadero: Bucle infinito}

Como Z puede ser cualquier programa, entonces perfectamente podríamos aplicar lo siguiente:

Paradoja (Paradoja): Si Se_Acaba (Paradoja, Paradoja) mientras regrese Verdadero: Bucle infinito

En conclusión, si hubiera la posibilidad de que existiera el algoritmo SeAcaba() se tendría como resultado la paradójica conclusión de que hay un programa que acaba siempre y cuando no acabe. Entonces no puede haber nunca un algoritmo parecido a SeAcaba() porque eso resultaría en una contradicción absoluta y, en resumidas cuentas, es imposible resolver el Problema de la Parada con una Máquina de Turing, ergo con una computadora actual.

Al final podemos rematar que todo nuestro poder computacional se alinea a las tesis formuladas por Alan Turing y hasta el momento el poder de resolución de una Alienware MX18 o una Mac Book Pro no pueden rebasar lo establecido por una Máquina de Turing de hace más de 50 años. Así que la próxima vez que les aparezca en sus pantallas ese hermoso cuadro de texto diciéndoles “Microsoft Word no responde, Si reinicia o cierra el programa podría perder información -> Reiniciar el programa -> Cerrar el programa -> Esperar a que el programa responda”, si usted elige la última opción se arriesgará a no poder decidir si su programa responderá o no. Eso no tiene solución.