Sobre deportes “computables”

Hace unos meses andaba con unos amigos viendo un partido de tenis y surgió la cuestión de pronosticar cuándo acabaría el partido. La conclusión sorprendente es que un partido de tenis puede durar un tiempo infinito porque en el fondo es un problema no computable. Me explicaré.

Desde los orígenes de la computación (teórica antes que real) se admite que existen problemas computables y problemas no computables, es decir, siendo más concretos, existen algoritmos que terminan su ejecución en un número finito de pasos, mientras que otros nunca terminan su ejecución. En 1936, Alan Turing demostró que es imposible enunciar un algoritmo general que determine si un algoritmo particular terminará o no su ejecución. Esto no es otra cosa sino una reformulación del Teorema de Incompletitud de Gödel para el dominio de la algorítmica, o una versión de la paradoja de Bertrand Rusell sobre si el conjunto de conceptos que no forman parte de ellos mismos forma parte de sí mismo o no. También tenemos un antecedente histórico en la paradoja de Epiménides.

¿Qué quiere esto decir, en la práctica? Pues simplemente que es imposible establecer un procedimiento de decisión general para determinar si un algoritmo terminará su ejecución antes de proceder a ejecutarlo. Obviamente, si procedemos a ejecutar el algoritmo puede suceder que este termine, pero si su ejecución se prolonga no podremos decir en algunos casos si efectivamente terminará o no.

A este tipo de problemas pertenece el tenis. El tie break se inventó para intentar deshacer uno de estos posibles infinitos, ya que el partido nunca acabaría si los dos jugadores llegaran a un tanteo de 6-6 y ninguno de ellos ganara 2 juegos seguidos. En realidad hasta la fecha todos los partidos de tenis han terminado (que yo sepa), aunque teóricamente sea imposible afirmar que todos lo harán en el futuro (aunque la probabilidad tiende a cero a medida que consideramos partidos de duración cada vez más larga). Parece que el record de duración lo han batido recientemente Fabrice Santoro y Arnaud Clement.

Pero el tie break no es suficiente, ya que el tenis no tiene una única posible rama infinita, sino muchas, y además el tie break introduce su propio infinito (el tie break más largo de la historia parece ser que llegó a 38 puntos). Durante el partido, que debía ser bastante aburrido para permitirnos derivar es esta discusión, enunciamos las siguientes:

• Un juego en que se llegue a iguales y ningún jugador gane 2 puntos seguidos.
• Un tie break en el que se llegue a 6 iguales y ningún jugador gane 2 puntos seguidos.
• Un serie infinita de saques que tocan el borde de la red y luego entran en el cuadro reglamentario.
• Una serie infinita de puntos en los que la pelota rebota en algún elemento que provoque que el punto sea considerado “nulo”. Por ejemplo, que la pelota bote contra otra pelota que se encuentre en el campo (esto no pasa si hay recogepelotas, claro) o contra el juez de silla.
• Una serie infinita de puntos en los que el juez considere que hay que repetir el primer saque porque no está claro si la pelota entró o no.

Así pues, el tenis no es computable …pero oiga ¡a ver si nos callamos ya, que esto es un partido de tenis, no una clase de filosofía informática!

Publicado originariamente en Computación creativa y otros sueños (Libro de Notas) el 25/12/2005