Las matemáticas en el campo de la teoría de la computación comenzó a florecer en la década de 1930 con los trabajos de matemáticos como Alan Turing.
Hoy en día, los ordenadores están en todas partes y 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 incluso 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 fue uno de los grandes impulsores del campo, hasta el punto de ser considerado por muchos el padre de la informática moderna.
Los Algoritmos en las Matemáticas
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 paso a paso, siendo 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.
Un algoritmo simple es el que usamos para multiplicar dos números, 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.
Durante siglos, estos algoritmos debían realizarse a mano, en un proceso lento y tedioso, lo que en 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.
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? (que se pueden resolver mediante algoritmos9. 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.
La Implementación de Algoritmos
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.
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á”.
La Computabilidad en la Actualidad
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, 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.
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. 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.
Fuente: El País
Más noticias sobre Ingeniería Mecatrónica…
