Aprende matemáticas universitarias con humor

Las matemáticas estudian de manera teórica muchas cuestiones relacionadas con la computación, como, por ejemplo, ¿qué números pueden ser computados con un dispositivo mecánico?, ¿qué teoremas matemáticos pueden ser demostrados sistemáticamente a partir de un conjunto de axiomas y unas reglas de inferencia?, ¿cuál es el mínimo número de instrucciones con el que se puede elaborar un algoritmo que resuelva un problema?, ¿qué ordenador me puedo comprar que sea bueno, bonito y barato? (esta última, como habrán observado, es de broma).

El matemático Alan Turing planteó una máquina hipotética que consiste básicamente en una cinta infinita dividida en casillas y un cabezal de lectura y escritura que puede desplazarse sobre la cinta a derecha e izquierda (en la formulación original de Turing era la cinta la que se desplaza a derecha e izquierda por el cabezal. Como la cinta es infinita y, por tanto, tiene una masa infinita, esto plantearía un problema de eficiencia energética si existiera de verdad). La cinta contiene inicialmente una serie de símbolos de un alfabeto finito dado (considerándose el caso de que la casilla no contenga ningún símbolo como un caso especial de símbolo, llamado ‘blanco’). El cabezal, cuando está situado sobre un símbolo en una casilla, puede borrarlo y escribir otro. También, en cada etapa en la que el cabezal está en una casilla, dicho cabezal está en un estado concreto de entre los de un conjunto finito de posibles estados.

Intuitivamente, estos estados codifican de forma matemática abstracta el tipo de subtarea que está realizando el cabezal (por ejemplo, ‘buscar una cadena de tres símbolos 1 seguidos’, o ‘borrar todos los símbolos 2, desplazándose hacia la izquierda hasta encontrar un símbolo 1’, o ‘calcular la llevada en una suma binaria de dos bits’, o ‘contar el número de treses en un conjunto de casillas consecutivas precedidas y seguidas por un símbolo en blanco’. Como dijo el propio Turing, los estados simulan matemáticamente ‘estados de la mente’ en los que puede estar una persona al hacer los cálculos (el mío, particularmente, suele estar en una playa tropical con un Daiquiri). La fuerza impulsora que anima el cotarro viene del hecho de que el cabezal, al estar en un estado concreto en una casilla con un símbolo determinado, puede borrar el símbolo y escribir otro, desplazarse una casilla a la derecha o a la izquierda, o cambiar a otro estado.

Esto se codifica mediante una serie de ‘instrucciones’ que serían, como si dijéramos, el ‘software’ de la máquina de Turing. Estas instrucciones son cuádruplas, donde las dos primeras componentes de cada cuádrupla son el estado y el símbolo leído, la tercera componente puede ser o bien el nuevo símbolo escrito o una D que indicará moverse una casilla a la derecha o una I que indicará moverse una casilla a la izquierda. La cuarta componente indica el nuevo estado al que pasa la máquina.

Por ejemplo, si los posibles estados son s0, s1 y s2 y los posibles símbolos son ‘blanco’, 0, 1 y si la máquina está en el estado s0 sobre una casilla que contiene el símbolo 1 y hay una cuádrupla (s0, 1,D, s2), entonces el cabezal se mueve una casilla a la derecha (sin alterar el símbolo 1 de la casilla antigua, ya que es una instrucción ‘de desplazamiento’ y no ‘de sobreescritura’) y termina en el estado s2. Si, por ejemplo, la máquina está en el estado s1 sobre una casilla que contiene el símbolo 0 y si hay una cuádrupla (s1, 0, 1, s0), la máquina borra el 0 y escribe un 1 en su lugar y cambia de estado (como el agua) a s0.

Una vez que una cuádrupla hace su magia, se vuelven a examinar todas las cuádruplas hasta ver a cuál le toca actuar ahora y se repite el proceso hasta siempre o hasta que se llegue a un estado de parada, lo que antes suceda (en algunas formulaciones se admiten varios estados de parada, e incluso en algunas otras la máquina para cuando no hay ninguna cuádrupla en el ‘programa’ cuyas dos primeras componentes son el estado actual de la máquina y el símbolo leído, respectivamente. Hablando informalmente, cuando la máquina no sabe qué hacer).

Para que no haya ambigüedad, se pide también que no haya dos cuádruplas distintas con las mismas dos primeras componentes, es decir, que no haya dos acciones distintas a tomar cuando, en un estado concreto, el cabezal lee un símbolo concreto.

Huelga decir que la máquina de Turing no es, ni puede ser, una máquina física real de las que se le puede caer a alguien en el pie, ya que presupone una cinta infinita dividida en infinitas casillas, lo cual exigiría papel a cascoporro. Además, cuando Turing la ideó ni siquiera existían los ordenadores en el sentido actual del término. Por el contrario, es una estructura matemática que permite estudiar las preguntas realizadas al comienzo (excepto la de comprar el ordenador) y muchas otras más.

Dos de los tópicos analizados con las máquinas de Turing son los siguientes: el primero, saber si se puede construir una “máquina de Turing universal” que simule cualquier otra máquina de Turing, es decir, que si codificamos inicialmente en la cinta de la máquina universal de forma apropiada las cuádruplas de un ‘programa’ concreto, la máquina se comporte igual a como lo haría una máquina de Turing con ese ‘programa’. El propio Turing demostró que eso es fácil de conseguir y es lo que justifica la opinión no escrita de que lo que se puede hacer con un ordenador también se puede conseguir con otro, aunque sea de otra marca con características distintas, procesador diferente y con otro sistema operativo. Con la idea de máquina universal Turing fue un adelantado a la idea moderna de computador multiusos que según el programa que introduzcamos puede realizar una tarea u otra completamente distinta.

El otro tópico planteado por Turing es el “problema de la parada” y consiste en saber si se puede hallar una máquina de Turing en la que, si se le da como entrada el conjunto de cuádruplas (codificado adecuadamente) de otra máquina de Turing, determine si la otra máquina llegaría a detenerse en algún momento si la ejecutáramos o, si por el contrario, seguiría ejecutándose hasta que Don Limpio se deje melena. Para algunos programas concretos es fácil saber si van a terminar o no, pero Turing probó que la respuesta al problema de la parada para cualquier programa de entrada arbitrario es negativa y no se puede determinar usando una máquina de Turing si otra máquina va a terminar su ejecución en algún momento. Aunque no lo voy a desarrollar, es interesante señalar que el razonamiento de Turing para demostrar la irresolubilidad del problema de la parada se basa en el argumento diagonal de Cantor, del que ya se habló en y que permitía probar que el conjunto de los números reales no es numerable; ya ven que el argumento diagonal de Cantor lo mismo sirve para arreglar un roto que un descosido.

Si te has quedado con ganas de saber más sobre el uso de algoritmos matemáticos y de sus aplicaciones para encriptar mensajes, no puedes perderte los capítulos 1 y 4 del libro Profundiza en las matemáticas universitarias con humor. En este libro, además de descubrir curiosidades de este estilo, profundizarás en muchos otros temas imprescindibles de las matemáticas como:

• Algoritmos
• Espacios vectoriales
• Números enteros
• Aritmética modular
• Polinomios
• Desigualdades numéricas

Y si quieres partir de un nivel menos avanzado, el libro Adéntrate en las matemáticas universitarias con humor te introducirá a los aspectos más básicos de las matemáticas, y en él tratarás los siguientes temas:

• El lenguaje matemático
• Teoría de conjuntos
• Operaciones y estructuras algebraicas
• Combinatoria
• Trigonometría
• Números complejos

Las matemáticas universitarias suponen muchas veces un gran salto con respecto a las que se ven en el bachillerato. El humor puede ayudar a hacer éstas más llevaderas, sin perder la rigurosidad requerida.