[6.5 Autómatas Celulares como computadores]
Estudiar a los Autómatas Celulares como computadores requeriría un curso en si mismo.
Lo que voy hacer aqui es dar un resumen corto. Pero voy a agregar algunas lecturas opcionales
en la sección de Materiales del Curso de la página Web, para que los consultes.
Empecemos por explicar lo que queremos decir cuando decimos Computación
Computación es el procesamiento de información...
En un cómputo, información es 'entrada' al sistema
'almacenada' en memoria (en cierta forma)
'transferida' de una ubicación de memoria a otra
y 'combinada' con otra información. La cuaĺ también se podría llamar 'procesada'.
Finalmente, la información procesada se imprime como 'salida'
para el usuario o para el sistema y ser usada de alguna forma
Un diagrama: tenemos 'Entrada', un 'Programa' que hace los cómputos y después imprime una 'Salida'.
Algunas veces, en un Sistema Dinámico, la 'Salida' se usará nuevamente como 'Entrada'.
Un concepto importante en las Ciencias de la Computación y en Sistemas Complejos...
es el concepto de 'Cómputación Universal'. Básicamente, se refiere a un computador que puede ser "programado".
Es decir, un Computador Universal es un computador que puede ejecutar cualquier programa. Como el computador en tu escritorio...
si tuviera una memoria infinita, podría ejecutar cada programa posible y calcular cada función (computable) posible.
La idea es, que aqui, en vez de simplemente tener una 'entrada', tenemos una 'Entrada' y un 'Programa'
que van al computador universal, y el resultado se imprime en la 'Salida'. Puedes verlo como el computador en tu escritorio...
al que le entras datos; un programa en memoria que ha sido entrado (por ti o por alguien más)
tu computador actua como un computador universal y ejecuta ese programa con los datos de entrada y después...
crea una 'salida'. Uno de los triunfos de las ciencias de la computación, es haber descubierto que
[solo es necesario un conjunto reducido de operaciones para soportar computación universal!]
Cuando digo: soportar computación universal, quiero decir que es posible construir
un computador programable. Lo cual quiere decir que se puede implementar un conjunto particular...
de operaciones y usarse, o combinarse de distintas formas. Sería posible, por ejemplo tener un computador...
que podría ejecutar cualquier programa con cualesquiera datos de 'entrada'.
Ese es un computador universal.
Como ya mencioné, John Von Neumann fue uno de los primeros científicos que estudió
los Autómatas Celulares como modelos de sistemas complejos
en especial, él exploró la idea de auto-replicación en 'máquinas' (o autómatas)
[Teoría de Autómatas Celulares Autoreplicables. por John von Neumann] Él construyo un Autómata Celular en dos dimensiones:
Cada célula puede estar en uno de 29 estados.
Ese autómata podía replicar cualquier 'patrón' que se le diera como entrada, inclusive a si mismo.
Aqui un diagrama de este tipo de autoreplicación. Podemos ver una máquina compleja,
que tiene un espacio de entrada, un espacio de salida y que crea una copia de si misma.
o cualquier otro patrón que se le de como entrada.
von Neumann también lo convirtió en un Computador Universal.
Es decir, no solo puede replicarse a si mismo, sino tambien calcular funciones computables.
Muchos han simplificado el Autómata Celular autoreplicable de von Neumann a tener menos estados
pero esta fue la primera creación de un Computador Universal en un Autómata Celular.
Se ha comprobado tambien que El Juego de la Vida ("Life") soporta computación universal
[1970: Conway demostró que "Life" puede implementar operaciones lógicas simples, necesarias para computación universal...
e hizo los diseños de cómo un computador universar podría ser construido]
[1990s: Paul Rendall construyó un computador universal con "Life"]
Esta es una fotografía de parte del computador universal construido. Es un poco dificil de ver, pero
usa algunas de las estructuras que ya vimos, como planeadores (gliders), cañones (glider guns)
e implementa las operaciones lógicas necesarias en computación universal.
Debo decir que implementar esta clase de cálculos en un autómata celular
es una empresa fantásticamente complicada.
[Computación en Automatas Celulares Elementales (ACE)]
Por mucho tiempo Stephen Wolfram pensó que un Automata Celular Elemental
podría soportar computacion universal.
Lo cual es importante, dado que un ACE es extremadamente sencillo.
La pregunta era: ¿Es posible que el comportamiento complejo que pueden crear
sea lo suficientemente complejo para implemetar formas más poderosas de procesamiento de información?
La hipotesis de Wolfram era que todo AC clase 4 podría soportar computación universal.
Recordemos que AC clase 4 son todos los AC entre peridicos y caóticos. (AC "al borde de lo caótico").
Esta hipotesis es dificil de evaluar:
Uno de los problemas es que no hay una definición formal de lo que es un AC clase 4.
También ha sido dificil demostrar que cierto sistema soporta computación universal.
Sin embargo, Wolfram y su compañero Matthew Cook, tuvieron éxito al demostrar que la Regla 110 soporta computación universal.
Esta prueba se muestra en un capítulo largo de su libro: "Un Nuevo Tipo de Ciencia"
El cual se puede leer online. Hay un enlace en la página Web de Materiales del curso.
Es una demostración un poco técnica, pero la idea general es que la Regla 110 hace uso
de las llamadas Particulas Móviles, es decir estas estructuras restringidas que se mueven en el espacio y en el tiempo
El tiempo baja por la vertical y el espacio va a lo largo de la linea horizontal en una dimension
y estas Particulas Móviles
pueden incorporar información de ubicaciones espaciales diferentes
y chocar unas con otras. De esta forma, por ejemplo, aqui podemos ver esta
partícula chocando con esta otra, creando una nueva partícula
La idea es que se puede 'almacenar' informacion estos patrones regulares.
'tranferir' a través de estas partículas, y 'procesar' en las colisiones de partículas.
En principio, este [AC] puede soportar computación universal.
En la práctica, sin embargo es muy dificil, sino imposible, programar este autómata celular
y lograr que haga algo útil.
["Computación útil" en ACs]
Mientras la computación universal en ACs es bien interesante, incluso sorprendente,
con lo sencillos que son, (en especial los ACEs), no son la manera más práctica de hacer un cómputo.
Es demasiado lento simular un Computador Universal en un Autómata Celular.
También son muy dificil de programar.
En realidad nadie hace computos con propósitos prácticos usando...
las habilidades de computación universal de los ACs.
Sin embargo, ACs han sido empleados en procesamiento paralelo.
Por ejemplo en procesamiento de imagenes.
No voy a hablar mucho de eso ahora, pero en la siguiente unidad voy a mostrar un projecto...
en el que Algoritmos Geneticos fueron usados...
para evolucionar ACs para desempeñar computos prácticos.
Finalmente, voy a decir unas palabras sobre [La importancia de los ACs en Sistemas Complejos]
Hemos visto que los Autómatas Celulares son Sistemas Complejos ideales...
que pueden producir comportamientos complejos
con relgas simples
hemos visto que se pueden modelar Sistemas Complejos naturales usando arquitecturas en forma de Autómatas Celulares,
y que Autómatas Celulares nos dan un marco para entender como dinámicas complejas...
pueden producir procesamiento colectivo de informacion
Es decir, procesamiento de informacion que "aparece" de una coleccion de componentes sencillos...
en un sistema "vivo", donde "vivo" significa: descentralizado,
con componententes relativamente sencillos, comunicación limitada entre los componentes, etcétera.