En la Facultad de Ciencias doy un curso de Vida Artificial", la cual es una asignatura que trata de simulaciones -a través de la computadora- de manera que se puedan estudiar algunos conceptos de la vida misma, por ejemplo, la reproducción. Para ello se usan los autómatas celulares en una y dos dimensiones (en general), los cuales han sido estudiados ya en los años 70s, 80s y 90s del siglo pasado por Conway (Juego de la vida) y Wolfram (autómatas celulares en una dimensión). De hecho, existe mucha información en la red sobre este tema. Wolfram, por ejemplo, ha escrito un libro enorme, llamado "A New Kind of Science", el cual puede leerse gratuitamente aquí. Por otro lado, el sitio obligado para estudiar el Juego de la Vida de Conway es éste.
Pues bien, en el libro de Wolfram, (el cual a pesar de intimidar sólo por su tamaño, es bastante accesible y diría que en general es un libro de divulgación), se habla de los autómatas unidmensionales. Se analizan las 256 reglas. Se hace un análisis de la complejidad de las mismas, etcétera. Wolfram entonces experimenta cambiando reglas y situaciones para la reproducción de los autómatas. Eventualmente demuestra que con ciertas reglas de sustitución, se pueden crear los elementos fundamentales de la máquina de Turing, la cual es una máquina conceptual que puede hacer en principio, cualquier cálculo.
Por ejemplo, en la página 82 de su libro, pone el siguiente gráfico que ilustra un sistema simple de sustitución, el cual genera que se dupliquen los elementos en cada generación.
Y aunque Wolfram lo muestra con puntos de tonos de gris, su sistema de sustitución es simplemente:
A --> AB
B --> BA
Así, si tenemos una configuración inicial con solamente el elemento A, podeos sustituir y quedarnos lo siguiente:
A --> AB
AB --> ABBA
ABBA --> ABBABAAB
etcétera...
Si contamos los elementos que hay en cada generación, encontraremos que estos se duplican.
La serie de Fibonacci, por ejemplo, puede expresarse como el siguiente esquema de sustitución:
A --> B
B --> BA
Si tenemos la configuración inicial A obtendremos en las siguientes generaciones:
A --> B
B --> BA
BA --> BAB
BAB --> BABBA
BABBA --> BABBABAB
BABBABAB --> BABBABABBABBA
Si contamos los elementos en cada generación, obtendremos la secuencia de Fibonacci: 1, 2, 3, 5. 8. 13, etcétera.
Pues bien, defnir un autómata como un sistema de sustitución generauna gramática y esta es simplemente una serie de símbolos que se manipulan a través de ciertas reglas. Así, aplicando dichas reglas se obtienen las "frases" legales y válidas de acuerdo a la gramática definida.
Los autómatas formales, como los lenguajes, tienen en muchos casos la posibilidad de ser recursivos, se llaman así mismo. Por ejemplo, en el caso de las reglas de sustitución del autómata que duplica los valores de sus elementos en cada generación, podemos ver que A se sustituye por AB y B se sustituye por BA. Hay una suerte de llamada a sí misma en cada regla. Y esto es bastante común en los lenguajes. Por ejemplo, pensemos en la definición recursiva del factorial:
0! = 1 (condición terminal)
n! = n * (n-1)! (recursión)
Por ejemplo, para calcular 3! diremos lo siguiente:
3! = 3 * 2!
necesitamos ahora conocer cuánto es 2!
2! = 2 * 1!
necesitamos ahora conocer cuánto es 1!
1! = 1 * 0!
necesitamos ahora conocer cuánto es 0!, pero eso ya lo sabemos, 0! = 1.
Entonces empezamos a resolver cada ecuación:
1! = 1 * 0! = 1 * 1 = 1
entonces 2! = 2 * 1! = 2 * 1 = 2
por ende, 3! = 3 * 2! = 3 * 2 = 6.
Otro ejemplo de los lenguajes humanos: Si buscamos la definición de "perro", hallaremos que es "can". Si buscamos la definición de "can", se nos dirá que es "perro". Aquí hay una función recursiva que se cicla, porque no tiene una manera de terminar, de detenerse, como en el caso de la definición de factorial, en donde 0! termina con el cálculo y el ciclado infinito (porque 0! = 1).
Pues bien, se sabe que toda función recursiva se puede poner de forma iterativa. Por ejemplo, el factorial iterativo en Python (no recursivo) es:
def factorial(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
(gracias a chatgpt)
En cambio, en Python, el factorial recursivo se escribe así:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
(de nuevo, gracias a chatgpt)
La versión iterativa usa menos recursos de cómputo que la versión recursiva. Entonces, ¿por qué los autómatas celulares e incluso, los seres vivos, usan la recursión para crear otros seres vivos (a su imagen y semejanza)? ¿No debería la Naturaleza usaR la máxima economía en recursos?
Esta es la pregunta que no podía resolver, pero el otro día, caminando por avenida del IMAN, encontré una posible respuesta. De pronto me sentí como el episodio que narra Bertrando Russell cuando se dio cuenta del concepto de la verdad ontológica. Dice Russell que sintió una especie de iluminación, experiencia que pocas veces se da sin la necesidad de sustancias alucinógenas u otros artilugios.
Pues bien, la respuesta a las preguntas que me había planteado sobre los autómatas celulares y a que prácticamente todos usan la recursión, es porque en la misma se encuentra una imagen a escala de lo que está representando. En el caso de la iteracción, necesitamos pasarle los parámetros correctos para que se ejecuten los algoritmos que queremos, pero en la recursión, los datos se incluyen en el mismo algoritmo. Russell, por ejemplo, habla de la paradoja del barbero, en donde se puede expresar en Prolog, donde el paradigma de ese lenguaje hace que las instrucciones y los datos sean indistintos. Véase aquí para esa discusión.
Así, a mí me queda clarísima la razón por la cual los seres vivos usan funciones recursivas, que se llaman a sí mismas, para la reproducción y creación de los elementos hijos. Y sí, aparentemente ocupa más recursos pero la realidad es que es mucho más eficiente que los algoritmos iterativos.
