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 ¨Ccada vez m¨¢s potentes¨C 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 ¨Cy los algoritmos¨C 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 ¨Cpor ejemplo, no se requiere el uso de la ¡°intuici¨®n¡± matem¨¢tica o de otro tipo¨C.

Un algoritmo simple es, por ejemplo, el que usamos para multiplicar ¨Ca mano¨C 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 ¨Cm¨¢s o menos complicados¨C. 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 ¨Cs¨®lo hay que probar que un cierto algoritmo lo resuelve¨C, 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 ¨Co, empleando sus t¨¦rminos, que una funci¨®n sea computable sobre los n¨²meros naturales¨C.

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¨¢¡± ¨Ces decir, se quedar¨¢ para siempre en un bucle¨C, o si se detendr¨¢ y proporcionar¨¢ una respuesta ¨Caunque sea despu¨¦s de mucho tiempo.

Actualmente sabemos que existen muchos otros problemas no computables ¨Cpor ejemplo, el famoso problema 10 de la lista de Hilbert¨C. 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 ¨Ccon suerte, menores¨C

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 ¨Cya que, si tenemos que esperar diez millones de a?os para obtener una respuesta, ese software no ser¨ªa de utilidad¨C. 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.