Receptes matemàtiques: els algoritmes.

Aunque el concepto de algoritmo existe, por lo menos, desde los tiempos de la antigua Grecia, no se le dio nombre hasta el siglo IX (en honor del matemático persa Al Juarismi), y hace menos de cien años que tiene una definición precisa. O varias, pues no hay un total acuerdo al respecto.El más famoso algoritmo de la antigüedad es el de Euclides, que nos suministra una sencilla “receta” para calcular el máximo común divisor de dos números. ¿Cuál es el máximo común divisor de 630 y 231? Dividimos 630 por 231 y el resto es 168; dividimos 231 por 168 y el resto es 63; dividimos 168 por 63 y el resto es 42; dividimos 63 por 42 y el resto es 21; dividimos 42 por 21 y el resto es 0: el mcd es 21.

El algoritmo de Euclides nos da una idea intuitiva bastante clara de lo que es un algoritmo: una serie de pasos preestablecidos que, ejecutados de forma mecánica, como quien sigue un sencillo manual de instrucciones o una receta de cocina, nos permite hallar un resultado a partir de unos datos iniciales.

Cuando efectuamos operaciones aritméticas con papel y lápiz, utilizamos algoritmos (“Siete por siete cuarenta y nueve, pongo el nueve y me llevo cuatro”). Y cuando las efectuamos con una calculadora, también, solo que en este caso se trata de un algoritmo muy simplificado (que consiste sencillamente en teclear los números y los signos correspondientes) que, a su vez, activa el algoritmo algo más complejo programado en la máquina.

Una de las más interesantes definiciones –o formalizaciones– del concepto de algoritmo es la que nos brinda la máquina de Turing, un aparato mental ideado por Alan Turing en los años treinta del pasado siglo para dar respuesta a una de las grandes preguntas planteadas por el matemático David Hilbert en 1900: ¿Son “decidibles” las matemáticas? Es decir, ¿existe algún método definido –un algoritmo– que, dada una sentencia matemática cualquiera, nos permita decidir si es verdadera o falsa? La máquina de Turing es sumamente sencilla: una cinta de papel tan larga como se desee puede correr en ambas direcciones bajo un cabezal de lectura/escritura que, en cada paso, lee el signo (un 0 o un 1 en la versión más simple) que hay en ese lugar de la cinta y, según el “estado” de la máquina en ese momento, lo cambia por otro signo o no. Con su sencillo dispositivo mental, Turing demostró que las matemáticas son indecidibles y abrió un apasionante debate, que aún persiste, sobre la inteligencia artificial.

Carlo Frabetti, Algoritmos, Público, 03/07/2011