Manuel López Michelone - Jugando a ser Dios

13Un mecanismo Turing completo quiere decir que es posible emular una máquina universal de Turing. Con respecto al Juego de la vida, lo que se hace es simular las compuertas AND y NOT, lo cual permite construir un álgebra booleana, lo que a su vez hace posible construir –en principio– una compuerta lógica arbitraria que permitiría crear un tipo de memoria RAM, generando así que el juego sea Turing-completo.

14http://www.igblan.free-online.co.uk/igblan/ca/.

15Véase http://groups.google.com/group/comp.theory.cell-automata/browse_thread/thread/c62c88b336a917ca/d26a604b1081e460?pli=1.

16La tesis fuerte de Church-Turing formula la equivalencia entre una función computable y una máquina de Turing que, expresado en términos simples, dice: “todo algoritmo es equivalente a una máquina de Turing”. Cabe decir que esto es una posición filosófica frente a un problema indecidible (http://es.wikipedia.org/wiki/Tesis_de_Church-Turing).

17Esta interesante conclusión surgió en una comunicación privada sostenida con el doctor Juan Claudio Toledo, del Instituto de Astronomía de la unam y un buen exestudiante mío y mejor amigo.

18Richard Dawkins (26 de marzo de 1941), científico británico, es autor de muchísimas obras de divulgación científica, como El gen egoísta (1976) y El fenotipo extendido (1982), en donde afirma que los efectos fenotípicos no están limitados al cuerpo de un organismo, sino que pueden extenderse incluso al entorno y a otros organismos.

19Richard Dawkins, The Blind Watchmaker, Nueva York, W. W. Norton & Company, Inc., 1996 [1986]. Hay una versión gratuita del libro de Dawkins en formato pdf en http://uath.org/download/literature/Richard.Dawkins.The.Blind.Watchmaker.pdf. Cabe señalar que no es versión pirata. Se han otorgado permisos para descargarla.

20La complejidad y la computabilidad son temas muy interesantes por sí mismos, pero en este trabajo no es el centro de la discusión, sino un tema periférico.

¿Piensas que soy un autómata?

¿Una máquina sin sentimientos?

Charlotte Brontë (Jane Eyre)

Los autómatas celulares de Von Neumann y de Conway sin duda despertaron la imaginación de otros investigadores. Una idea interesante es quitar una dimensión a los autómatas bidimensionales, como los del Juego de la vida, y ver qué pasa si ponemos a trabajar a los autómatas en una sola dimensión. Esto, en principio, podría sugerir una simplicidad mayor que al trabajar con autómatas como en el Juego de la vida, que ocurren en dos dimensiones; sin embargo, esta simplificación es aparente, pues en una dimensión los autómatas hallan desarrollos emergentes complejos.

Consideremos una línea recta de células —de casillas—, las cuales pueden estar ocupadas o vacías. Las reglas del autómata, ciegas, se basan simplemente en la vecindad de cada célula con la que se está trabajando en cada generación. De acuerdo con las reglas que se definen, podremos ver lo que pasa en la línea de células, generación tras generación. Además, para darnos una mejor idea, podemos colocar la primera generación (la configuración inicial), y ver el comportamiento, pintando la segunda generación debajo de la primera. Podemos hacer esto para cada ciclo t en el tiempo, y en un momento determinado tendremos decenas, centenas o miles de generaciones desplegadas. Con ello podremos hacer un análisis de lo que está pasando.

Formalmente podríamos decir que los autómatas, las células, tienen valor 1 si están en alguna casilla de la línea de cuadros disponibles, o bien, contienen un valor 0 (cero), es decir, no hay nada en una casilla. Las reglas de evolución se presentan solamente analizando la vecindad de cada casilla de interés, una por una.

Uno de los primeros científicos en estudiar cuidadosamente este tipo de autómatas fue Stephen Wolfram. Hijo de refugiados judíos, se le consideró como niño prodigio. Estudió en el Eton College después de que se le otorgara una beca por publicar su primer artículo sobre física de partículas, a los 16 años. Un año después se matriculó en la Universidad de Oxford. Consiguió su doctorado a la edad de 20 años, en física de partículas, por parte de CalTech.

Wolfram es más conocido por Mathematica, un programa de computadora que puede hacer matemáticas simbólicas. Sin embargo, gran parte de su trabajo lo ha enfocado al comportamiento de los autómatas celulares. En 1983 se trasladó a Princeton e hizo muchísimas simulaciones de computadora para entender el comportamiento de los autómatas celulares en una dimensión.

Stephen Wolfram.

De acuerdo con el trabajo de Wolfram, existen diversas clases de autómatas celulares que se han clasificado según su comportamiento. Hay cuatro grandes clases basadas en el nivel de predicción en su evolución:

Clase 1. Son aquellos cuya evolución está literalmente predeterminada (probabilidad 1), independientemente de su estado inicial o configuración.

Clase 2. Son aquellos en los que el valor de un sitio en particular, a muchos pasos del tiempo, está determinado por los valores iniciales en algunos sitios en una región limitada.

Clase 3. El valor de un sitio en particular depende de los valores de un número siempre creciente de sitios iniciales. Esto quiere decir, en términos coloquiales, que conducen a comportamiento caótico.

Clase 4. Son aquellos en los que en un sitio en particular pueden depender de muchos valores en la configuración inicial y en los que la evolución del autómata simplemente no se puede predecir. Hay que hacer la simulación explícita del mismo.

Esta definición tan formal puede confundirnos pero, como veremos, el entender cómo evolucionan estos autómatas es verdaderamente sencillo.

Wolfram habla de reglas locales de evolución, que no son otra cosa que las reglas ciegas que descubrió Conway en el Juego de la vida o las reglas en la Hormiga de Langton, como veremos más adelante. Estas reglas son las que definen el comportamiento en la evolución del autómata. Por ejemplo, consideremos una línea de células y las siguientes reglas locales:

↓↓

000 → 0

001 → 1

010 → 0

011 → 1

100 → 1

101 → 0

110 → 1

111 → 0

Reglas locales de un autómata en una dimensión

Por ejemplo, consideremos una línea que contenga dos células en medio de la misma, es decir:

000…001100…000

La evolución de la siguiente generación pide revisar cada célula en la línea. Cuando tenemos 000…000… no hay cambio alguno, pero llega un momento en que tenemos 001 (recuérdese, sólo hay dos células en la línea del autómata). Hallamos que tenemos que calcular el resultado cuando encontramos 001. Eso, de acuerdo con la tabla, da como resultado un 1. Se pone en la siguiente línea, debajo de la célula que estamos analizando. Ahora movemos nuestro apuntador a la siguiente célula y hallamos la configuración 011, la cual da como resultado un 1. Pasamos a la siguiente célula y encontramos la configuración 110, lo cual vuelve a darnos un 1. Seguimos con este procedimiento y hallamos los valores 100, lo cual de nuevo da un 1. Inmediatamente después todos los valores dan 0. El autómata quedará entonces así en la segunda generación (la primera generación es la inicial):

000…001100…000 [Generación inicial]

000…011110…000 [Segunda generación]

Este sencillo procedimiento se puede programar en una computadora para no tener que “hacerlo a mano”. En los apéndices puede hallarse un programa en Pascal para realizar esta simulación.