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.
Más información
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.
