17 de Marzo 2008
Tetravex, la computabilidad y un millon de dolares
El tetravex es un juego de encajar piezas cuadradas coincidiendo los numeros enfrentados. Como un dominó con cuatro valores por pieza, en vez de dos.
Aquí una versión flash bastante jugable.
Para encajar algunas veces las piezas hay que "podar" mentalmente el árbol de posibles colocaciones. (bueno, cada uno que piense su estrategia, no soy capaz de explicarla aquí, que voy fatal de tiempo).
El caso es que estas baldosas las usó el lógico chino Hao Wang para relacionar máquinas de Turing con mosaicos de baldosas. Por lo visto, cada máquina de Turing tiene un embaldosado equivalente. (Independientemente de esto, es un juego NP-completo: cualquier problema NP puede replantearse, en tiempo polinómico, como resolver cierto TETRAVEX. esto tengo que entenderlo algún día ). Hao Wang es también editor de obras de Gödel
Hay otros juegos que son NP-completos, como el buscaminas (aquí lo explica Ian Stewart en el contexto de "P=NP?", uno de los "millenium prizes" de 1000000$) y mi preferido, el sokoban.
Del Klotski (las piedras polacas, el burro rojo) no he encontrado mucha teoría matemática. Cuando acabe los 24 post me pongo
[9/24]
Escrito por juanlu a las 17 de Marzo 2008 a las 07:54 PMJuanlu, voy a ir, pa que te de un poquito el aire. Me recuerdas a Don Quijote Besos
Escrito por Gema a las 17 de Marzo 2008 a las 08:24 PM