Posts etiquetados ‘Bill Zwicker’

Un libro fantástico que, necesariamente, ha de estar en tu biblioteca es Razón, dulce razón. Una guía de campo de la lógica moderna de Tom Tymoczko y Jim Henle. Yo lo encontré por casualidad y muy barato, en un puestecillo de libros, y desde entonces no paro de volver a él una y otra vez. Es, desde luego, una auténtica tabla de salvación en estos días de confinamiento. Básicamente, consiste en un compendio de curiosidades lógicas: adivinanzas, retos, ejercicios… que de una manera muy entretenida y divertida (pero no por ello fácil. No es un libro básico), te enseñan sobre todos los vericuetos de la lógica moderna: formalización, lógica informal, autómatas, incompletitud, infinitos, etc. Es, por decirlo de alguna manera, una serie de golosinas hard para mentes inquietas. 

Hoy os traigo de allí una paradoja que no es demasiado conocida (yo, al menos, nunca la había oído), y que ilustra muy bien lo que es el problema de la parada de Turing, y que se parece mucho a otras paradojas como la del barbero de Russell o la de Jules Richard. Lo que me gusta de ella es que me parece aún más intuitiva y fácil de entender que las otras. Timoczko y Henle nos cuentan que su creador fue Bill Zwicker sobre los años 80 del siglo pasado.

Definamos juego finito como aquel que termina siempre después de un número finito de movimientos. El ajedrez, por ejemplo, parece un claro juego finito ¿Seguro? No tanto. Si jugamos una partida sin límite de tiempo, uno de los jugadores podría estar infinito tiempo pensando en la próxima jugada, por lo que no estaríamos ante un juego finito. El ajedrez, para ser finito, debe añadir un límite de tiempo. Entonces habría que especificar: el ajedrez relámpago o blitz, en el que cada jugador suele tener un máximo de diez minutos para realizar todas sus jugadas antes de que caiga la bandera y pierda, sí sería un juego finito. No obstante, por mor de la argumentación, aceptaremos como juego finito, aquel que tenga una naturaleza algorítmica, es decir, que suela resolverse en un número finito de pasos en un tiempo polinómico (razonablemente corto). El ajedrez, las damas, el parchís, el poker, etc. serían juegos finitos.

Vale, ahora definimos hiperjuego: es aquel juego entre dos jugadores que consiste en el que el primer jugador comienza eligiendo un juego finito. Entonces, ambos jugadores se ponen a jugar a ese juego hasta que se acaba. El primer movimiento del hiperjuego sería la elección del juego, el segundo sería el primer movimiento del juego finito, el tercero el segundo del juego finito, y así sucesivamente. Entonces el hiperjuego tiene siempre un movimiento más que cualquier juego finito posible ¿Todo claro? Sigamos.

¿Es el hiperjuego un juego finito? Claramente sí. Acabamos de decir que tiene un paso más que cualquier juego finito, y un juego finito más un paso, sigue siendo un juego finito, ergo, el hiperjuego es un juego finito.

¿Seguro? Esperad un momento. Supongamos que en el paso uno del hiperjuego, el primer jugador elije jugar al hiperjuego. Entonces, el segundo jugador tiene que realizar el primer paso del hiperjuego, es decir, de nuevo elegir juego. Supongamos que elije el hiperjuego. Entonces, cansinamente, el primer jugador debe otra vez elegir juego, y elije el hiperjuego, y así ad infinitum. Este caso sería un ejemplo de hiperjuego infinito, ergo el hiperjuego no es un juego finito como habíamos demostrado antes… ¡Paradoja al canto!

Feliz cuarentena máquinas. Intentaré escribir con más asiduidad aquí para intentar haceos más llevadero este aislamiento.