Las matemáticas que estudian los límites de los ordenadores

Hoy en día, los ordenadores están en todas partes: en la oficina, en nuestros teléfonos inteligentes o incluso en los automóviles. Funcionan mediante algoritmos –cada vez más potentes– que pueden realizar una enorme variedad de tareas, desde sumar dos números, a encontrar la mejor ruta para ir a un destino desconocido o detectar de forma automática transacciones financieras fraudulentas. La ubicuidad y el potencial de los ordenadores son tan grandes que es fácil creer que, antes o después, podrían resolver cualquier problema. Sin embargo, gracias a la llamada teoría de la computación, sabemos que los ordenadores –y los algoritmos– tienen límites fundamentales. El matemático británico Alan Turing (1912-1954) fue uno de los grandes impulsores del campo, hasta el punto de ser considerado por muchos el padre de la informática moderna.

El uso de algoritmos se remonta a los inicios de nuestra civilización. Los algoritmos son, en su forma más simple, una forma de resolver un problema dado siguiendo, paso a paso, una secuencia finita de instrucciones. Estas instrucciones utilizan un número finito de símbolos y se ejecutan, con el objetivo de obtener el resultado deseado, de manera “mecánica”, sin depender de ninguna forma especial de inteligencia –por ejemplo, no se requiere el uso de la “intuición” matemática o de otro tipo–.

Un algoritmo simple es, por ejemplo, el que usamos para multiplicar –a mano– dos números, como nos enseñan en la escuela, para obtener su producto. Otros ejemplos de algoritmos son el llamado algoritmo de Euclides, para obtener el máximo común divisor de dos números, o el método de Gauss, para resolver un sistema de ecuaciones lineales. En esencia, podemos ver los algoritmos como procedimientos automáticos que ofrecen soluciones a problemas matemáticos.

Unos años antes del nacimiento de las computadoras digitales, los matemáticos y los lógicos se plantearon qué tipo de problemas son computables, es decir, que se pueden resolver mediante algoritmos. Esta cuestión se convirtió en el motor inicial de la llamada teoría de la computación

Durante siglos, estos algoritmos debían realizarse a mano, en un proceso lento y tedioso, lo que, en la práctica, limitaba su uso. Sin embargo, con la aparición de dispositivos informáticos que automatizaban su implementación, las aplicaciones de los algoritmos empezaron a crecer vertiginosamente, principalmente para realizar cálculos –más o menos complicados–. Unos años antes del nacimiento de las computadoras digitales, los matemáticos y los lógicos se plantearon la siguiente cuestión: ¿qué tipo de problemas son computables, es decir, que se pueden resolver mediante algoritmos? Esta cuestión se convirtió en el motor inicial de la llamada teoría de la computación.

Mientras que es (relativamente) fácil verificar que un problema dado sí es computable –sólo hay que probar que un cierto algoritmo lo resuelve–, demostrar que, dado un problema, no hay ningún algoritmo que lo pueda solucionar, es un asunto mucho más delicado. Incluso si no podemos dar con ningún algoritmo para resolver el problema, ¿cómo descartar que, simplemente, aún no hemos dado con el algoritmo oportuno?

Parte de la dificultad de esta cuestión se debía a que, hasta hace poco tiempo, no existía una noción precisa de lo que es un algoritmo. En esta tarea fundamental, es destacable el trabajo de Alan Turing quién, a propósito, aparece en el nuevo billete de 50 £ y también presta su nombre al nuevo programa de intercambio de estudiantes, que sustituirá al programa Erasmus en el Reino Unido.

Durante la década de 1930, Turing, junto con otros matemáticos como Alonzo Church, propuso definiciones matemáticas precisas sobre la computabilidad

Durante la década de 1930, Turing, junto con otros matemáticos como Alonzo Church, propuso definiciones matemáticas precisas sobre la computabilidad. En concreto, definió lo que significaba que el valor de una función se pueda calcular mediante un algoritmo –o, empleando sus términos, que una función sea computable sobre los números naturales–.

Esto dio lugar a la llamada tesis de Church-Turing, que establece que cualquier función sobre los números naturales es computable, con la noción de algoritmo antes mencionada, si puede ser calculada por una máquina de Turing. La máquina de Turing es un modelo de computación introducido por el matemático, que puede verse simplemente como un programa de ordenador.

Turing también mostró que existen problemas no computables, como el llamado problema de la parada. Este problema busca determinar si, dada alguna máquina de Turing y un dato de entrada para ella, la máquina se detendrá o, por el contrario, continuará en un bucle infinito. Si pensamos en nuestros teléfonos inteligentes, el problema de la parada consistiría en saber si, al utilizar una aplicación, esta se “bloqueará” –es decir, se quedará para siempre en un bucle–, o si se detendrá y proporcionará una respuesta –aunque sea después de mucho tiempo.

Actualmente sabemos que existen muchos otros problemas no computables –por ejemplo, el famoso problema 10 de la lista de Hilbert–. Gracias a ello, podemos garantizar, por ejemplo, que no hay algoritmos capaces de confirmar que los programas informáticos estén libre de errores. Esto significa que, aunque disponemos de técnicas para mejorar la calidad del software, probablemente, tendremos que seguir tolerando que contenga errores –con suerte, menores–

Más allá del problema de la computabilidad, en la práctica se buscan algoritmos capaces de proporcionar respuestas, en un período de tiempo razonable –ya que, si tenemos que esperar diez millones de años para obtener una respuesta, ese software no sería de utilidad–. Esta cuestión también se estudia en el contexto de la teoría de la computación y, de hecho, ha dado lugar a preguntas muy interesantes como el problema P vs NP, cuya resolución está premiada con un millón de dólares, y que será el tema de otro artículo próximo.

Daniel Graça es profesor de la Universidad del Algarve e investigador del Instituto de Telecomunicaciones (Portugal)

Ágata Timón G-Longoria es coordinadora de la Unidad de Cultura Matemática del ICMAT y editora y coordinadora de esta sección

Café y Teoremas es una sección dedicada a las matemáticas y al entorno en el que se crean, coordinado por el Instituto de Ciencias Matemáticas (ICMAT), en la que los investigadores y miembros del centro describen los últimos avances de esta disciplina, comparten puntos de encuentro entre las matemáticas y otras expresiones sociales y culturales y recuerdan a quienes marcaron su desarrollo y supieron transformar café en teoremas. El nombre evoca la definición del matemático húngaro Alfred Rényi: “Un matemático es una máquina que transforma café en teoremas”.

Puedes seguir a MATERIA en Facebook, Twitter e Instagram, o apuntarte aquí para recibir nuestra newsletter semanal.