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


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.


Cuando terminó la escuela secundaria, en 1858, el joven Samuel "Sam" Lloyd tenía ganada una sólida reputación como creador de problemas de ajedrez y juegos matemáticos. Lloyd vivía en Nueva York, donde el ajedrez ganaba cultores a diario, y comenzó a publicar problemas en revistas y diarios de la época hasta transformarse en columnista de Scientific American, donde publicó problemas combinando ajedrez y matemáticas.

En 1878, Lloyd presenta uno de los tantos juegos de ingenio que su incansable creatividad proponía, el Juego de 15. Los 15 cuadrados de madera, debidamente enumerados y embalados, fascinaron primero a los norteamericanos y luego al mundo. En la ilustración del siglo XIX, se ve al granjero que ha abandonado todas sus tareas cautivado por la invención de Sam Lloyd. Con más de un siglo de distancia, hoy podemos acceder a distintas versiones digitales del juego en varias páginas, como por ejemplo: http://www.holotronix.com/


Más información sobre el tema:

  • Alan Turing, «Solvable and Unsolvable problems», Science News 31, pp 7-23 (1954).

  • Alan Turing, «On computable numbers, with an application to the entscheidungsproblem», Proceedings of the London Mathematical Society 42, 230—265. (1936)

  • Pueden visitar también el archivo digital de Turing, http://www.turingarchive.org/
    University of Southampton and King’s College Cambridge

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

  Portada | Archivo

 
 

Buscador
powered by FreeFind



Suscríbase al resumen del Micro Semanario

Nombre:
E-mail:
   
 
PUBLICACIONES: CABLE SEMANAL | NOTICIAS | EXACTAMENTE

SECCIONESAGENDA | LIBROS Y REVISTAS | DOCUMENTOS
Editor Responsable:
Carlos Borches
Redacción y Edición:
Enrique Stroppiana
(Educación y Universidad)
Patricia Olivella
(Ciencia y Tecnología)

Agenda de Cursos:
Cecilia Palacios
Soporte Técnico:
Gabriel Platas
Contactese con el Microsemanario:
micro@de.fcen.uba.ar