Facultad de Ciencias Exactas y Naturales-UBA   AÑO 15 - NÚMERO 540   JUEVES, 27 DE OCTUBRE DE 2005

De puzzles, soluciones y cuelgues de computadora

«Si te doy un puzzle, ¿sabés si tiene solución?», fue el planteo que lanzó Verónica Becher durante la Semana de la Computación que tuvo lugar días atrás en esta Facultad ante un salón colmado de estudiantes secundarios. Para quien gusta de estos juegos puede parecerle un interrogante que resolverá si logra terminar exitosamente la partida. Pero para el padre de la computación, Alan Turing (1912-1954), resultó una cuestión clave en su trayectoria, y -es más- hoy todos somos testigos de las respuestas, cada vez que se «cuelga» la computadora.

Por Cecilia Draghi (*)

Verónica Becher.

  A poco de iniciar la charla, Becher, directora del grupo de investigación en Lógica y Computabilidad del Departamento de Computación de esta Casa de estudios, señaló: «No hay ningún método sistemático para testear puzzles. Si esto quisiera decir que a nadie se le ocurrió, no sería muy profundo. Lo que demostró Turing es que este método nunca será encontrado», subrayó.

  Tomemos un ejemplo concreto. Supongamos que uno recibe como regalo el puzzle del 15 (el jueguito ideado por Sam Loyd en 1878). Se trata de una tablilla de cuatro filas verticales y otras cuatro horizontales con 15 fichas móviles numeradas del 1 al 15. Queda un casillero libre. Dada una configuración inicial, el problema es llevarla a una configuración final deseada, por ejemplo, la que tiene las fichas ordenadas en el tablerito de manera numéricamente creciente. Hay una sola regla en este juego: si una ficha está arriba, abajo, a la izquierda o a la derecha del casillero libre, se la puede desplazar para ocuparlo.

  Que quede claro que el acertijo tiene solución si existe una sucesión de movidas que transforman el tablerito en el deseado.

  Una observación crucial es que la regla del juego permite hacer un movimiento, y aplicando la regla otra vez, se puede deshacer. De esto surge una propiedad fundamental de este rompecabezas, y es que será posible ordenar el tablero solamente si es posible también llevar el tablero ordenado a su desorden original. Sobre la base de esta observación y de otras de esta naturaleza Turing consigue este veredicto: el acertijo tiene solución solamente en el caso de se pueda ir de la configuración inicial a la final repitiendo el acto de intercambiar dos fichas, una cantidad de par de veces. «Observemos que un número impar de intercambios no dejaría nunca los objetos en su posición original», destaca.

  Otra forma de analizar el acertijo del 15 es la «exploración exhaustiva»: probando una y otra vez, hasta agotar todas las posibilidades y comprobar así la factibilidad de alcanzar el resultado buscado. Hay solamente una cantidad finita de posibles formas de disponer las fichas en las 16 casilleros del tablero, esta cantidad es 2.092.278.988.000. Y hay solamente una cantidad finita de movimientos en cada tablero, pueden ser dos, tres o cuatro, según el blanco esté en una esquina, en un borde o fuera del borde. Entonces se puede hacer una lista de todas las posibles configuraciones y trabajar sobre cada posible movida. Luego se puede dividir las configuraciones en clases para saber cuáles son alcanzables desde una configuración dada. Se concluye que será posible pasar de una configuración inicial a una final siempre y cuando ambas estén en la misma clase. Si no, será imposible.

  «Desde un punto de vista práctico, este argumento de ‘exploración exhaustiva’ resulta un tanto insultante como contestación a la pregunta de si un puzzle tiene solución, ya que no es practicable para ninguna persona revisar sistemáticamente una cantidad tan inmensa de casos. Sin embargo, el argumento de la exploración exhaustiva es formalmente muy poderoso, y sí permite afirmar que todos los puzzles que involucran un espacio finito de posibilidades, o bien tienen solución encontrable, o se demuestra que no la tienen. En resumen, para puzzles como el del 15 siempre puede saberse si tiene solución o no la tiene, porque este puzzle involucra una cantidad finita (aunque grande) de combinaciones posibles», señala.

  Turing se planteó el problema de qué sucede en puzzles donde el espacio de posibilidades es infinito, y se preguntó: ¿existe un método sistemático capaz de determinar si un puzzle arbitrario dado tiene solución o no la tiene?

  La idea genial de la demostración es ver a un método sistemático como ¡un puzzle!

  Un método sistemático es un puzzle en el que hay a lo sumo un movimiento posible en cada jugada, y se le da significado a la jugada final. Lo que no se sabe de antemano es si alguna vez va a ser alcanzada una jugada final.

  Sobre la base de esta idea Turing demuestra que no hay ningún método sistemático capaz de resolver si un puzzle tiene solución o no. «Este es un teorema profundo, y vale la pena -recomienda- leer la demostración del artículo de 1954, o la versión formal del artículo de 1936 (ver referencias al final de esta nota). Lo profundo de este resultado es que al mismo tiempo que define el concepto de ‘método sistemático’ (o programa de computadora), identifica su limitación fundamental».

  Por último señala: «Una experiencia mundana de esta limitación intrínseca la tenemos cada vez que en el monitor de la computadora, Windows pregunta: ‘Su programa no responde, ¿qué desea hacer...?’».

  «Lo que Windows (ni nadie) no puede decidir es si nuestro programa responderá alguna vez o no. Este es un puzzle que en general no tiene solución», concluye Becher.

(*) Centro de Divulgación Científica - SEGBE - FCEyN.