El algoritmo

Un algoritmo es una lista finita de instrucciones sin ambigüedad que un ejecutor puede seguir paso a paso, sin entenderlas, para transformar una entrada en una salida. La palabra es un apellido deformado: Muhammad ibn Musa al-Juarismi, matemático de la Bagdad del siglo IX, escribió hacia el año 825 un tratado de procedimientos de cálculo (del ŷabr de su título viene «álgebra») y cuando sus textos se tradujeron al latín, su nombre se convirtió en Algoritmi y las frases «dixit Algoritmi», «dijo Algoritmi», acabaron dando nombre a todo procedimiento mecánico de cálculo.

La propiedad que define a un algoritmo es la literalidad: el ejecutor hace exactamente lo que está escrito, nunca lo que se quiso decir. Esa es a la vez su virtud y su defecto. Virtud, porque un procedimiento literal lo puede ejecutar cualquiera (o cualquier cosa) sin talento ni criterio, y el resultado es siempre el mismo. Defecto, porque si la lista dice una tontería, la tontería se ejecuta con la misma fidelidad. Los programas no fallan por desobediencia; fallan por obediencia. Todo bug de la historia es una máquina haciendo con exactitud lo que se le ordenó y un humano descubriendo que no era lo que quería ordenar.

La figura pone un ejecutor literal en escena: un robot triangular sobre una cuadrícula de siete por cinco, con una casilla marcada como meta. El robot entiende dos órdenes (AVANZA, una casilla en la dirección en que mira, y GIRA, un cuarto de vuelta a la izquierda) y una construcción, REPITE n […], que ejecuta su contenido n veces. El selector ofrece tres programas, escritos a la derecha como una lista numerada: uno llega a la meta, otro choca con un muro y otro dibuja un cuadrado. Con «Un paso» se ejecuta una sola instrucción; con «Ejecutar» (que al pulsarlo pasa a ser «Pausa»), el programa entero a ritmo visible; «Reiniciar» devuelve el robot a la salida. Cada instrucción se ilumina en la lista en el momento de ejecutarse, y la lectura de abajo cuenta cuántas van, hacia dónde mira el robot y en qué casilla está.

Los tres programas enseñan lo mismo desde ángulos distintos. El primero llega a la meta sin que ninguna instrucción mencione la meta: ocho órdenes ciegas (cuatro avances, un giro y tres avances) componen una ruta; el robot no sabía adónde iba en ningún momento, y llegó. El segundo es la lección importante: la séptima instrucción dice AVANZA y el robot avanza, aunque frente a él no haya más cuadrícula; el programa se cumplió al pie de la letra y al muro no le importa lo que se quiso decir. El tercero muestra lo que es un bucle de verdad: REPITE 4 no significa «haz algo parecido cuatro veces», sino que el cuerpo (avanzar, avanzar, girar) se ejecuta literalmente cuatro veces, con lo que el robot traza un cuadrado y termina exactamente donde empezó, mirando exactamente adonde miraba.

Que una lista de instrucciones sea un algoritmo exige varias condiciones que Donald Knuth fijó en 1968, en el primer volumen de The Art of Computer Programming: ha de ser finita (termina), definida (cada paso tiene un único significado), efectiva (cada paso lo puede ejecutar el ejecutor con lápiz, papel o interruptores), y ha de recibir entradas y producir salidas. La condición de «definida» es la que separa los algoritmos de las recetas: «añade sal al gusto» no es una instrucción para un ejecutor literal; «añade cinco gramos de sal» sí. Con un ejecutor que no interpreta, la ambigüedad no se disimula: o muere al escribir el programa o mata al ejecutarlo.

La idea de algoritmo es tan vieja como la aritmética, pero dos textos la convirtieron en la base de la informática. En 1843, traduciendo un artículo sobre la máquina analítica de Charles Babbage, Ada Lovelace añadió unas notas que triplicaban el original: en la nota G escribió, paso a paso, cómo calcularía la máquina los números de Bernoulli (el primer algoritmo publicado pensado para ser ejecutado por una máquina) y vio lo que casi nadie veía, que un artilugio que opera con números según reglas puede operar con cualquier cosa que se represente con símbolos. En 1936 Alan Turing llevó la idea al límite en On Computable Numbers: definió una máquina imaginaria que solo sabe leer una casilla de una cinta, escribirla y moverse, y demostró que ese aparato miserable puede ejecutar cualquier algoritmo. Todo ordenador actual es, en esencia, el robot de la figura: un ejecutor literal con dos o tres órdenes y ninguna comprensión.

Eso sí, fíjate en lo que pasa al pulsar «Reiniciar»: el robot vuelve a la salida como si nada hubiera pasado, y entre una ejecución y la siguiente no queda rastro de lo recorrido, porque un programa así de rígido no recuerda nada. Ni siquiera durante la ejecución guarda el robot más que su posición y su rumbo. De dónde saca una máquina la memoria (cómo un puñado de celdas con nombre convierte un trámite ciego en un programa que acumula) va el próximo capítulo: la variable.