una máquina universal que puede ejecutar cualquier cálculo. De hecho, el Juego de la vida de Conway —como lo demostró el propio matemático— es una máquina de Turing.
10 Alan Turing, Intelligent Machinery, National Physical Laboratory (Report), 1948, p. 61.
11 Por ejemplo, http://www.delphidabbler.com/software/life es uno de tantos sitios en donde hay software para jugar con la idea de Conway (véanse los apéndices).
12 En términos generales, el Juego de Conway es un autómata celular en dos dimensiones. Se pueden explicar las manchas que pigmentan la piel de algunos animales, incluso de alguna familia de serpientes, utilizando un autómata celular en una sola dimensión, el cual, bajo reglas tan o más simples que las diseñadas por Conway, pueden generar patrones extremadamente complejos. Steven Wolfram (el creador del software Mathematica, ha trabajado extensivamente sobre autómatas celulares en una sola dimensión, y ha hallado propiedades sorprendentes (véase el capítulo correspondiente a los autómatas en una dimensión de Wolfram).
13 Un 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.
14 http://www.igblan.free-online.co.uk/igblan/ca/.
15 Véase http://groups.google.com/group/comp.theory.cell-automata/browse_thread/thread/c62c88b336a917ca/d26a604b1081e460?pli=1.
16 La 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).
17 Esta 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.
18 Richard 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.
19 Richard 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.
20 La 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.
Capítulo IV
La nueva ciencia de Stephen Wolfram
¿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