Estructura oscilante
La expresión 5! indica el producto 5 × 4 × 3 × 2 × 1, 19! significa el producto 19 × 18 × 17 × … × 3 × 2 × 1. Estas locuciones se leen «5 factorial» y «19 factorial», respectivamente, y no «¡cinco!» ni «¡diecinueve!» con una entonación exclamativa. Aunque principalmente se usan en probabilidad y en otras ramas de la matemática en las que hace falta contar todas las posibles realizaciones de un suceso, a veces pienso que sería bueno que la gente considerara a los demás como «factoriales históricos». Así, (Marta)! no significaría la Marta actual, sino el producto de todas sus experiencias pasadas.
Formalmente, establecemos que 1! es 1, y luego definimos (N + 1)! como (N + 1) × N!. Es decir, definimos el «factorial» explícitamente para el primer término y luego definimos su valor para cualquier otro término mediante los valores de los términos anteriores al mismo. Una definición de este tipo se llama recurrente, y podemos usarla para calcular el valor de 5!. Vale 5 por 4!. Pero ¿cuánto vale 4!? Pues, 4 por 3!. ¿Y 3!? 3 por 2!. ¿Y cuánto es 2!? Pues, 2 por 1!. Y, por fin, la definición nos dice cuánto vale 1!. Es 1. Reuniéndolo todo encontramos que 5! = 5 × 4 × 3 × 2 × 1. Tranquilos, no repetiré esta letanía para 19!.
De modo análogo, la definición recurrente de la suma nos dice cómo sumar cualquier número a X. Establece primero que X + 0 es X y define por recurrencia que X + (Y + 1) es igual a 1 más X + Y. (Ruego me disculpen si el resto del párrafo parece un chiste de esos que se estiran como una goma). Para determinar (8 + 3) aplicando la definición anterior, por ejemplo, observaremos que 8 + 3 = (8 + 2) + 1, que 8 + 2 = (8 + 1) + 1, que 8 + 1 = (8 + 0) + 1 y que 8 + 0 = 8. Reuniéndolo todo tenemos que 8 + 3 = 8 + 1 + 1 + 1. Y así hemos reducido la suma a contar. La definición por recurrencia de la multiplicación establece que X × 0 = 0 y luego se define X × (Y + 1) igual a (X × Y) más X. Aplicando la definición podemos determinar el valor de 23 × 9 reduciéndolo a una serie de sumas [23 × 9 = (23 × 8) + 23; 23 × 8 = (23 × 7) + 23; 23 × 7 = (23 × 6) + 23; …] las cuales se reducen a su vez a contar. Análogamente podemos definir el significado de elevar X a una potencia cualquiera. Primero establecemos que X0 es 1 y luego definimos X(Y + 1) como X por XY. Por tanto, 74 = 7 × 73, 73 = 7 × 72, etc. la exponenciación se ha reducido a la multiplicación, la cual se reduce a la suma, que a su vez se reduce a contar.
Aunque de entrada pueda parecer una tontería, la idea de expresar el valor de una función de (N + 1) por recurrencia, en términos de sus valores anteriores, es muy útil y en informática es inevitable. De hecho, la recurrencia constituye el mismísimo núcleo de la programación informática, con su empleo característico de bucles (la realización repetitiva de un mismo procedimiento para distintos valores de una misma variable), subrutinas y otras estrategias que permiten reducir procesos complejos a simples operaciones aritméticas. Las funciones matemáticas y los algoritmos que admiten una definición por recurrencia son precisamente los únicos que se pueden manejar con un ordenador. Es decir, si una función es recurrente, puede calcularla un ordenador, y si un ordenador puede calcular cierta función, ésta es recurrente. Además, estas definiciones recurrentes se pueden encajar unas en otras, se pueden iterar indefinidamente y, mediante las codificaciones y correspondencias apropiadas, se pueden generalizar para toda clase de actividades, aunque éstas no tengan aparentemente mucho que ver con el cálculo.
Estas funciones y definiciones tienen un papel importante en lógica pues precisan lo que quiere decirse con palabras tales como «mecánico», «regla», «algoritmo» y «demostración» (véase también la entrada sobre La inducción matemática). En gramática formal los lingüistas usan definiciones recurrentes para clarificar las reglas de la gramática y estudiar los procesos cognitivos. Demuestran cómo se pueden construir largos enunciados complejos a partir de frases y oraciones cortas. Si se usa en combinación con la autorreferencia, la recurrencia es todavía más potente. Algunos virus informáticos, por ejemplo, se reproducen de un modo parecido al de la frase siguiente que proporciona ella misma las instrucciones y el material para su propia réplica. Alphabetize and append, copied in quotes, these words: «these append, in Alphabetize and word: quotes, copied». Dicho en español y sin tanta concisión, la frase anterior manda ordenar alfabéticamente las palabras que siguen a los dos puntos y luego añadir, entre comillas y sin ordenar, estas mismas palabras. Y ¡abracadabra!: la frase se ha replicado a sí misma y lo mismo harán sus descendientes.
Estructura oscilante
La recurrencia tiene también un papel cada vez más importante en la descripción de fenómenos físicos, especialmente después de los avances de la teoría del caos, que ilustran gráficamente lo naturales y complicadas que pueden llegar a ser las estructuras definidas por recurrencia.
Relacionado con esto último, consideremos una sugestiva aplicación de una definición recurrente simple. El juego solitario «Vida» del matemático británico John Conway transcurre en un tablero de damas infinito que tiene alguno de sus cuadros ocupados por fichas. (El papel cuadriculado con algunos cuadros en oscuro también vale). Como cada cuadro del tablero tiene 8 vecinos (4 adyacentes y 4 en diagonal), cada ficha puede tener entre 0 y 8 vecinas. La distribución de fichas originaria es la primera generación, y el paso de una generación a la siguiente se rige por tres reglas. Cada ficha con 2 o 3 vecinas permanece en el tablero y pasa a la siguiente generación. Cada ficha con 4 vecinas o más se saca del tablero y no pasa a la generación siguiente, y lo mismo ocurre con las que tienen 0 o 1 vecina. Cada cuadro vacío que tenga exactamente 3 vecinos ocupados estará también ocupado por una ficha en la siguiente generación.
Estructura que se reproduce a sí misma
Los cambios dictados por las tres reglas tienen lugar todos a la vez, y el tictac discreto del reloj marca el paso de una generación a la siguiente para este «autómata celular». Es sorprendente cómo estas simples reglas recurrentes que rigen la supervivencia, muerte y nacimiento de las fichas pueden conducir a estructuras y movimientos sobre el tablero de una gran belleza y complejidad. Figuras parecidas a trenes y aviones saltan al tablero a medida que se van sucediendo las distintas generaciones. Algunas configuraciones iniciales mueren, otras se reproducen, mientras que otras engendran universos enteros de sapos, barcos y dibujos geométricos. Algunas oscilan o parpadean, otras sufren una sucesión cíclica de transformaciones mientras que otras nunca dejan de evolucionar.
Diagrama simplificado de una figura que se reproduce
Para hacerse una idea de cómo son estas estructuras cambiantes hay que empezar, ya sea con algunas fichas sobre un tablero de damas ya sea con cuadros oscuros sobre papel cuadriculado, y seguir las reglas sistemáticamente, o con una versión del juego para ordenador. Pruebe con varias distribuciones iniciales de fichas. Podría empezar, por ejemplo, con tres fichas en fila. Se obtiene una figura parpadeante, que oscila entre la vertical y la horizontal. Pruebe con algunas más. La configuración inicial de 4 fichas, 3 dispuestas en fila horizontal y 1 sobre la ficha del medio, da lugar a una evolución particularmente interesante.
Conway ha llegado a demostrar que ciertas configuraciones iniciales de fichas se pueden usar como ordenador, lento pero hecho y derecho, cosa que nos hace volver a las funciones recurrentes en los enteros. La esencia de «Vida», y posiblemente también de la vida, es la recurrencia (véase la entrada sobre Test de Turing). Los matemáticos, desde Pitágoras a Poincaré, han escrito que los números y el contar son la base de toda la matemática. Las definiciones recurrentes nos dan un punto de vista desde el que esta pretensión es verdaderamente modesta.