UNIVERSIDAD NACIONAL DE INGENIERÍA CICLO: 2014- IFIIS - INGENIERÍA DE SISTEMAS Fecha: 13/06/2014

TEORÍA GENERAL DE SISTEMASST 103 – V

TRABAJO DE INVESTIGACION

Autómatas Celulares

Profesor: Ing. Jorge Daniel Llanos Panduro

Alumno: Edinson Jesús J. Molina Zea Código: 20130264B

Criterios de Calificación Notas1. Láminas y ayudas gráficas

2. Presentación, Claridad y Estilo3. Contenido y Progresividad4. Enfoque de Sistemas5. Calidad de Respuestas

Total

Autómatas Celulares Página 1

1. INTRODUCCIÓN

Existen muchos sistemas naturales hasta el momento cuya complejidad ha desafiado al análisis cualitativo, casos en los cuales puede simularse mediante los sistemas dinámicos. Algunos problemas logran ser modelados matemáticamente o analíticamente, sin embargo, existe otra gran cantidad de problemas donde la cantidad de variable es indeterminable y dependen de varios factores.Es en este sentido que se hace necesaria la modelación de un sistema que logre recrear las variables de un problema de gran complejidad, y así poder evaluar el comportamiento de este.En la presente investigación se presentará el modelo de un sistema que puede resolver estos problemas cotidianos de alta complejidad en pasos iterativos que resultan ser sencillos; pero que enmarcan soluciones para situaciones de una complejidad asombrosa.Todo esto se conjuga con la genialidad de dos mentes de la época que logran hacer realidad este proyecto que emula la auto-reproducción biológica y que responde a muchas interrogantes de la época.

2. CONCEPTOS GENERALES

Vida Artificial. La vida artificial es el estudio de la vida y de los sistemas artificiales que exhiben propiedades similares a los seres vivos, a través de modelos de simulación. El científico Christopher Langton fue el primero en utilizar el término a fines de la década de 1980 cuando se celebró la "Primera Conferencia Internacional de la Síntesis y Simulación de Sistemas Vivientes" (también conocido como Vida Artificial I) en Laboratorio Nacional de Los Álamos en 1987.El área de vida artificial es un punto de encuentro para gente de otras áreas más tradicionales como lingüística, física, matemáticas,filosofía, psicología, ciencias de la computación, biología, antropología y sociología en las que sería inusual que se discutieran enfoques teóricos y computacionales. Como área, tiene una historia controvertida; John Maynard Smith criticó ciertos trabajos de vida artificial en 1995 calificándolos de "ciencia sin hechos", y generalmente no ha recibido mucha atención de parte de biólogos. Sin embargo, la reciente publicación de artículos sobre vida artificial en revistas de amplia difusión, como Science y Nature son evidencia de que las técnicas de vida artificial son cada vez más aceptadas por los científicos, al menos como un método de estudio de la evolución.Las aplicaciones de la vida artificial se pueden encontrar en alguno de estos casos:

Autómatas Celulares Página 2

Los sistemas complejos adaptativos, que han dado paso a una nueva generación de sistemas expertos, que son capaces de aprender y evolucionar.

Los autómatas celulares, que imitan funciones de los organismos celulares en programas complejos, aplicando el conocimiento biológico de los mismos a principios prácticos de organización en sistemas de cómputo.

Los agentes autónomos, que son cada día más usados en aplicaciones de búsqueda.

En el conocimiento de comportamientos adaptativos, para el desarrollo de robots adaptativos.

La computación cuántica, que a través del uso de las propiedades cuánticas de los átomos y sus desplazamientos, posibilitará una nueva forma de cálculos binarios.

En algunos campos de aplicación de la vida artificial se plantean dos tipos de simulaciones, basadas en el mundo real, las cuales ayudan a la toma de decisiones. Estas son:

La primera de ellas, se centra en los aspectos de "más alto nivel" en cada problema, utilizando fórmulas y reglas, o hechos históricos, que ayudan a la toma de decisiones. Un ejemplo de esto pueden ser las fórmulas del tiro parabólico, ya que estas pueden entenderse como modelos de simulación.

La segunda pone atención en los aspectos de "más bajo nivel", mediante fórmulas o reglas. Una de las ventajas de este tipo de simulaciones es que sus características son más sencillas, ya que suelen ser más fáciles de detectar los aspectos de bajo nivel que aquellos de alto nivel.

Inteligencia Artificial. La Inteligencia Artificial es una combinación de la ciencia del computador, fisiología y filosofía, tan general y amplio como eso, es que reúne varios campos (robótica, sistemas expertos, por ejemplo), todos los cuales tienen en común la creación de máquinas que pueden pensar.La de idea construir una máquina que pueda ejecutar tareas percibidas como requerimientos de inteligencia humana es un atractivo. Las tareas que han sido estudiadas desde este punto de vista incluyen juegos, traducción de idiomas, comprensión de idiomas, diagnóstico de fallas, robótica, suministro de asesoría experta en diversos temas.Es así como los sistemas de administración de base de datos cada vez más sofisticados, la estructura de datos y el desarrollo de algoritmos de inserción, borrado y locación de datos, así como el intento de crear máquinas capaces de

Autómatas Celulares Página 3

realizar tareas que son pensadas como típicas del ámbito de la inteligencia humana, acuñaron el término Inteligencia Artificial en 1956.La Inteligencia Artificial trata de conseguir que los ordenadores simulen en cierta manera la inteligencia humana. Se acude a sus técnicas cuando es necesario incorporar en un sistema informático, conocimiento o características propias del ser humano.Podemos interrogar a algunas bases de datos de Internet en lenguaje natural, o incluso charlar con ellas nuestro idioma, porque por detrás se está ejecutando un programa de Inteligencia Artificial.Otras herramientas inteligentes pueden utilizarse para escrutar entre los millones de datos que se generan en un banco en busca de patrones de comportamiento de sus clientes o para detectar tendencias en los mercados de valores.Las definiciones anteriores implican que las máquinas para ser consideradas inteligentes deben exhibir ciertas habilidades, suficientemente complejas como para ser tratadas como áreas independientes. La forma de abordaje de cada una de estas áreas suele ser tan disímil, que es difícil reconocerles un origen común.

1. Procesamiento del Lenguaje Natural2. Consulta inteligente de base de datos3. Robótica4. Programación Automática5. Sistemas Expertos6. Prueba automática de teoremas y matemáticas simbólica7. Problemas de optimización combinatorios y de itinerarios.8. Percepción y reconocimiento de patrones9. Autoaprendizaje

Teoría de Decisiones. La teoría de la decisión es una área interdisciplinaria de estudio, relacionada con casi todos los participantes en ramas de la ciencia, la Administración, Economía, la psicología(basados en perspectivas cognitivo-conductuales). Concierne a la forma y al estudio del comportamiento y fenómenos psíquicos de aquellos que toman las decisiones (reales o ficticios), así como las condiciones por las que deben ser tomadas las decisiones.La relación de esta teoría con los autómatas se ve reflejada dentro de las aplicaciones de estos; ya que como se mostrará más adelantados estos estarán orientados a campos como las evaluaciones estadísticas dentro de población, para determinar algunas medida que tomar dentro de la comunidad; también dentro del campo del trafico automovilístico, una de las aplicaciones más estrechamente relacionada a este campo ya que es la situación en la que decisiones más rápidas y eficaces deben darse.

Autómatas Celulares Página 4

Teoría de Juegos. La teoría de juegos es un área de la matemática aplicada que utiliza modelos para estudiar interacciones en estructuras formalizadas de incentivos (los llamados «juegos») y llevar a cabo procesos de decisión. Sus investigadores estudian las estrategias óptimas así como el comportamiento previsto y observado de individuos en juegos. Tipos de interacción aparentemente distintos pueden, en realidad, presentar estructura de incentivo similar y, por lo tanto, se puede representar mil veces conjuntamente un mismo juego.1Desarrollada en sus comienzos como una herramienta para entender el comportamiento de la economía, la teoría de juegos se usa actualmente en muchos campos, como en la biología, sociología, psicología y filosofía.Experimentó un crecimiento sustancial y se formalizó por primera vez a partir de los trabajos de John von Neumann y Oskar Morgenstern, antes y durante la Guerra Fría, debido sobre todo a su aplicación a la estrategia militar, en particular a causa del concepto de destrucción mutua garantizada. Desde los setenta, la teoría de juegos se ha aplicado a la conducta animal, incluyendo el desarrollo de las especies por la selección natural. A raíz de juegos como el dilema del prisionero, en los que el egoísmo generalizado perjudica a los jugadores, la teoría de juegos ha atraído también la atención de los investigadores en informática, usándose en inteligencia y cibernética.Aunque tiene algunos puntos en común con la teoría de la decisión, la teoría de juegos estudia decisiones realizadas en entornos donde interaccionan. En otras palabras, estudia la elección de la conducta óptima cuando los costes y los beneficios de cada opción no están fijados de antemano, sino que dependen de las elecciones de otros individuos. Un ejemplo muy conocido de la aplicación de la teoría de juegos a la vida real es el dilema del prisionero, popularizado por el matemático Albert W. Tucker, el cual tiene muchas implicaciones para comprender la naturaleza de la cooperación humana. La teoría psicológica de juegos, que se arraiga en la escuela psicoanalítica del análisis transaccional, es enteramente distinta.Los analistas de juegos utilizan asiduamente otras áreas de la matemática, en particular las probabilidades, las estadísticas y la programación lineal, en conjunto con la teoría de juegos. Además de su interés académico, la teoría de juegos ha recibido la atención de la cultura popular. La vida del matemático teórico John Forbes Nash, desarrollador del Equilibrio y que recibió un premio Nobel, fue el tema de la biografía escrita por Sylvia Nasar, Una mente maravillosa (1998), y de la película del mismo nombre (2001). Varios programas de televisión han explorado situaciones de teoría de juegos, como el concurso de la televisión de Cataluña (TV3) Sis a traïció (Seis a traición), el programa de la televisión estadounidense Friend or foe? (¿Amigo o enemigo?) y, hasta cierto punto, el concurso Supervivientes.

Autómatas Celulares Página 5

Teoría de Caos. Teoría del caos es la denominación popular de la rama de las matemáticas, la física y otras ciencias que trata ciertos tipos de sistemas dinámicos muy sensibles a las variaciones en las condiciones iniciales. Pequeñas variaciones en dichas condiciones iniciales pueden implicar grandes diferencias en el comportamiento futuro, imposibilitando la predicción a largo plazo. Esto sucede aunque estos sistemas son en rigor determinísticos, es decir; su comportamiento puede ser completamente determinado conociendo sus condiciones iniciales.Es la teoría más estrechamente vinculada al tema de autómatas ya que toma en consideración que variaciones en las condiciones iniciales de ciertos sistemas como la configuración de un autómata, aunque sean mínimas, producirán un cambio en el comportamiento futuro del complejo.

Máquina de Turing. Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo a una tabla de reglas. A pesar de su simplicidad, una máquina de Turing puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de un CPU dentro de un computador.La máquina de Turing fue descrita por Alan Turing como una «máquina automática» en 1936 en la revista Proceedings of the London Mathematical Society,1 La máquina de Turing no está diseñada como una tecnología de computación práctica, sino como un dispositivo hipotético que representa una máquina de computación. Las máquinas de Turing ayudan a los científicos a entender los límites del cálculo mecánico.Turing dio una definición sucinta del experimento en su ensayo de 1948, «Máquinas inteligentes». Refiriéndose a su publicación de 1936, Turing escribió que la máquina de Turing, aquí llamada una máquina de computación lógica, consistía en:

...una ilimitada capacidad de memoria obtenida en la forma de una cinta infinita marcada con cuadrados, en cada uno de los cuales podría imprimirse un símbolo. En cualquier momento hay un símbolo en la máquina; llamado el símbolo leído. La máquina puede alterar el símbolo leído y su comportamiento está en parte determinado por ese símbolo, pero los símbolos en otros lugares de la cinta no afectan el comportamiento de la máquina. Sin embargo, la cinta se puede mover hacia adelante y hacia atrás a través de la máquina, siendo esto una de las operaciones elementales de la máquina. Por lo tanto cualquier símbolo en la cinta puede tener finalmente una oportunidad. (Turing 1948, p. 61)

Una máquina de Turing que es capaz de simular cualquier otra máquina de Turing es llamada una máquina universal de Turing (UTM, o simplemente una máquina

Autómatas Celulares Página 6

universal). Una definición más matemáticamente orientada, con una similar naturaleza "universal", fue presentada por Alonzo Church, cuyo trabajo sobre el cálculo lambda se entrelaza con el de Turing en una formal teoría de la computación conocida como la tesis de Church-Turing. La tesis señala que las máquinas de Turing de hecho capturan la noción informal de un método eficaz en la lógica y las matemáticas y proporcionan una precisa definición de un algoritmo o 'procedimiento mecánico'.Estudiando sus propiedades abstractas, la máquina de Turing produce muchas perspectivas en las ciencias de la computación y en la teoría de la complejidad.

Física Computacional. Se denomina física computacional a una rama de la física que se centra en la elaboración de modelos por ordenador de sistemas con muchos grados de libertad. En general, se efectúan modelos microscópicos en los cuales las "partículas" obedecen a una dinámica simplificada, y se estudia el que puedan reproducirse las propiedades macroscópicas a partir de este modelo muy simple de las partes constituyentes.La manera en que se realizan las simulaciones es resolviendo las ecuaciones que gobiernan el sistema. Por lo general, son grandes sistemas de ecuaciones diferenciales ordinarias o ecuaciones diferenciales a derivadas parciales, que no pueden ser resueltos de manera analítica.A menudo, la dinámica simplificada de las "partículas" tiene cierto grado de aleatoriedad. En general, esta vertiente se denomina Método de Montecarlo, nombre que le viene por los casinos de Montecarlo como forma jocosa de recordar que el método usa la aleatoriedad.Otras simulaciones se basan en que la evolución de una "partícula" en el sistema depende, exclusivamente, del estado de las partículas vecinas, y se rige mediante reglas muy simples y, en principio, determinadas. A esto se le llama simulaciones con autómatas celulares. Un ejemplo clásico, aunque más matemático que físico, es el famoso Juego de la vida, ideado por John Conway.La física computacional tiene sus aplicaciones más relevantes en física del estado sólido (magnetismo, estructura electrónica, dinámica molecular, cambios de fase, etc.), Física No Lineal, dinámica de fluidos, astrofísica (simulaciones del Sistema Solar, por ejemplo), Física de partículas (teoría de campos/teoría gauge en el reticulado espacio-temporal, especialmente para la Cromodinámica Cuántica (QCD) ).Las simulaciones que se realizan en física computacional requieren gran capacidad de cálculo, por lo que en muchos casos es necesario utilizar supercomputadores o clusters de computadores en paralelo. Tesis de Church. En su formulación más amplia, la Tesis de Church-Turing abarca tanto los algoritmos que producen una salida para cada entrada

Autómatas Celulares Página 7

como aquéllos que no terminan (ingresan en bucles infinitos) para algunas entradas. También se incluyen los algoritmos deterministas y los no deterministas.Para apreciar su significado y su alcance, hay que enfatizar que la Tesis de Church-Turing no es un enunciado matemático susceptible de demostración, ya que involucra la noción intuitiva de algoritmo. En otras palabras, la tesis no se puede demostrar. Se podría refutar, no obstante, exhibiendo un procedimiento efectivo, que todo el mundo acepte que es un verdadero algoritmo y que no pueda descrito por una máquina de Turing. Pero tal refutación no se ha producido hasta la fecha; de hecho, la experiencia acumulada durante décadas de investigación ha corroborado una y otra vez la Tesis de Church-Turing. Entre los hechos que contribuyen a apoyar la tesis podemos destacar los dos siguientes:

1. La adición de recursos computacionales a las máquinas de Turing (múltiples pistas o cintas, no determinismo, etc.) no incrementa el poder computacional del modelo básico. Esto es un indicativo de que el modelo de MT es lo suficientemente poderoso como para simular todas las acciones consideradas computacionalmente válidas.

2. Todos los modelos o mecanismos computacionales propuestos para describir formalmente la noción de algoritmo han resultado ser equivalentes a la máquina de Turing, en el sentido de que lo que se puede hacer con ellos también se puede hacer con una MT adecuada, y vice- versa. Entre los modelos de computación secuencial equivalentes a la máquina de Turing podemos citar: las funciones parciales recursivas (modelo de Gödel y Kleene, 1936), el calculo-λ (modelo de Church, 1936), los sistemas de deducción canónica (modelo de Post, 1943), los algoritmos de Markov (modelo de Markov, 1951) y las máquinas de registro (modelo de Shepherdson-Sturgis, 1963).

2.1. GLOSARIO Autómata. Instrumento o aparato que encierra dentro de sí el

mecanismo que le imprime determinados movimientos.

Auto reproducción biológica. Es un tipo más elaborado de proceso →auto-restructurativo, que hace referencia a la capacidad de los sistemas auto-organizativos que no solamente cambian su estructura en un sentido más o menos elegido por ellos mismos, sino que además introducen estas estructuras modificadas en un contexto más amplio: el de cómo hacer que éstas contribuyan a mantener su propia existencia. Aquí estructuras funcionales ya no son simples patrones, sino algo que contienen significado, y este algo será aquí

Autómatas Celulares Página 8

llamado símbolo, de modo que la producción de signos en esta etapa evolutiva de los sistemas vivos pasa de la formación de patrones a la formación de símbolos.

Computadores paralelos. Es una forma de cómputo en la que muchas instrucciones se ejecutan simultáneamente, operando sobre el principio de que problemas grandes, a menudo se pueden dividir en unos más pequeños, que luego son resueltos simultáneamente (en paralelo).

Recursividad. Es un concepto fundamental en matemáticas y computación.Es una alternativa diferente para implementar estructuras de repetición (ciclos). Los módulos se hacen llamadas recursivas.Se puede usar en toda situación en la cual la solución pueda ser expresada como una secuencia de movimientos, pasos o trasformaciones gobernadas por un conjunto de reglas no ambiguas.

Circuitos integrados. La idea de circuito integrado nace de la necesidad de reducir los circuitos eléctricos a uno mucho más sencillo y pequeño. Gracias a ellos, se evitaron la multitud de problemas que se daban a la hora de fabricar un circuito, como por ejemplo, que alguna de las miles de soldaduras que había que realizar estuviera defectuosa, o la reducción del espacio que ocupaban las válvulas de vacío, las cuales se vieron rápidamente obsoletas gracias a las mejoras que supuso la introducción de los circuitos integrados.

Iterativo. Significa el acto de repetir un proceso con el objetivo de alcanzar una meta deseada, objetivo o resultado. Cada repetición del proceso también se le denomina una "iteración", y los resultados de una iteración se utilizan como punto de partida para la siguiente iteración.

Radio control. Es la técnica que permite el gobierno de un objeto a distancia y de manera inalámbrica mediante una emisora de control remoto.En el radiocontrol entran en juego tres técnicas fundamentales: la electrónica que se encarga de transformas los comandos dados en ondas de radio en el transmisor y a la inversa en el receptor, la electricidad, encargada de proporcionar la energía necesaria a los dispositivos tanto el comando (o transmisor) como el receptor y mecánica encargada de mover los accionadores (o servos) que dan las señales eléctricas demoduladas o decodificadas en movimiento mecánico.

Autómatas Celulares Página 9

Bucle. Secuencia de instrucciones que se repite mientras se cumpla una condición prescrita. Generalmente, un bucle es utilizado para hacer una acción repetida sin tener que escribir varias veces el mismo código, lo que ahorra tiempo, deja el código más claro y facilita su modificación en el futuro.

Decremento. Se refiere a la disminución de algún proceso u objeto material.

Proyecto EDVAC1. Fue de los primeros ordenadores que existieron. A comparación de otros, este utilizaba un sistema binario en vez de decimal que era el sistema usado hasta el momento. Por primera vez en la historia de los ordenadores, los programas quedan almacenados en la memoria del ordenador. A partir de este descubrimiento, este sistema fue el impulsor de los ordenadores y computadoras de hoy en día. El grupo de genios que invento esta computadora se constituía por J. Presper Eckert y John William Mauchly y además un destacado matemático llamado John von Neumann. Esta computadora se acordó diseñarla en 1946. Estaba constituida por tecnologías muy avanzadas, que hasta ese momento no se habían descubierto.

Retículos o Lattice. En matemáticas, un retículo es una determinada estructura algebraica con dos operaciones binarias, o bien un conjunto parcialmente ordenado con ciertas propiedades específicas (siendo equivalentes ambos enfoques). El término “retículo” viene de la forma de los diagramas de Hasse. En teoría de conjuntos, un retículo, red o lattice es un conjunto parcialmente ordenado en el cual, para cada par de elementos, existen un supremo y un ínfimo.

Matusalenes. Patrones o configuraciones que debido a su forma, tardan muchos pasos para lograr estabilizarse.

Encriptación. es el proceso para volver ilegible información considera importante. La información una vez encriptada sólo puede leerse aplicándole una clave.Se trata de una medida de seguridad que es usada para almacenar o transferir información delicada que no debería ser accesible a terceros. Pueden ser contraseñas, nros. de tarjetas de crédito, conversaciones privadas, etc.Para encriptar información se utilizan complejas fórmulas matemáticas y para desencriptar, se debe usar una clave como parámetro para esas fórmulas.El texto plano que está encriptado o cifrado se llama criptograma.

Autómatas Celulares Página 10

Tupla. En matemáticas, es una secuencia ordenada de objetos, esto es, una lista con un número limitado de objetos (una secuencia infinita se denomina en matemática como una familia, aunque hay autores que consideran el término tupla para denominar no solo listas finitas). Las tuplas se emplean para describir objetos matemáticos que tienen estructura, es decir que son capaces de ser descompuestos en un cierto número de componentes.

Toroide. En geometría, es la superficie de revolución generada por una curva plana cerrada que gira alrededor de una recta exterior coplanaria (el eje de rotación situado en su mismo plano) con la que no se interseca. Su forma se corresponde con la superficie de los objetos que en el habla cotidiana se denominan donuts, argollas, anillos, aros o roscas. La palabra toroide también se usa para referirse a un poliedro toroidal, la superficie de revolución generada por un polígono que gira alrededor de un eje.

Computadora ENIAC. Nada podría haber explicado mejor el principal propósito de construir ENIAC (Electronic Numerical Integrator And Computer), conocida como la primera computadora electrónica digital programable. ENIAC marca varios precedentes importantes en la informática y electrónica, como el inicio de la computación de propósito general, la programación en lenguaje de máquina (digital), y la historia de seis mujeres ignoradas en su momento, hábiles en matemática y lógica, que se convirtieron en las primeras programadoras.

Percolación. Se refiere al paso lento de fluidos a través de los materiales porosos, ejemplos de este proceso es la filtración y la lixiviación. Así se originan las corrientes subterráneas. En las tres últimas décadas, la teoría de percolación, un amplio modelo de la percolación, ha traído nueva comprensión y técnicas para un amplio rango de materias en física, ciencia de materiales y geografía.

Fractal. Es un objeto cuya estructura se repite a diferentes escalas. Es decir, por mucho que nos acerquemos o alejemos del objeto, observaremos siempre la misma estructura. De hecho, somos incapaces de afirmar a qué distancia nos encontramos del objeto, ya que siempre lo veremos de la misma forma.

Triángulos de Sierpinski. es un fractal que se puede construir a partir de cualquier triángulo. Paso 1. Consiste en unir los puntos medios de los lados y "eliminar" el triángulo central.  Paso 2. Se repite el paso 1 con cada uno de los 3 triángulos restantes. Así iterativamente.

Autómatas Celulares Página 11

“XOR”. Es un tipo de disyunción de dos operandos que es verdad si solo un operando es verdad pero no ambos.

Máquina de Post. En Teoría de la computación y Teoría de la recursión, una máquina de Post, bautizada así en honor de Emil Leon Post, es una autómata determinista con una cola. No hay cinta de lectura separada. Al principio del cómputo, la cadena de entrada x es cargada en la cola. La cadena de entrad es seguida por un símbolo especial de fin de entrada. Al iniciarse el cómputo, la cola sólo contiene la configuración de entrada. El primer símbolo de x está al principio de la cola y el símbolo de final de entrada está luego del último carácter. Una máquina de transición de Post depende del símbolo al frente de la cola y del estado. Cada transición borrará el símbolo al principio de la cola. Una transición tiene dos componentes: el próximo estado y una cadena que se inserta al final de la cola. La cadena puede ser vacía.

Anidado. (llamado nesting en inglés) es la práctica de incorporar llamadas (calls) a funciones o procedimientos (una) dentro de otras, mediante la inclusión de diversos niveles de paréntesis.Debido a que la potencial acumulación de éstos últimos suele hacer que la edición y la detección de errores se vuelva un proceso engorroso, los entornos de programación modernos -así como los programas de planilla de cálculo- resaltan en negrita el par correspondiente a la posición que está editando el programador o usuario en cada momento. 

Estocástico. Proceso estocástico, modelo matemático en el que la ley de probabilidad que da la evolución de un sistema depende del tiempo.

Catálisis. Quím. Transformación química motivada por sustancias que no se alteran en el curso de la reacción.

Discretización. Consiste en tomar de un conjunto infinito de puntos un subconjunto infinito de modo que éste subconjunto tenga las mismas propiedades y características que el continuo.

Lenguaje Lisp. es una familia de lenguajes de programación de computadora de tipo multiparadigma con una larga historia y una sintaxis completamente entre paréntesis. Lisp fue creado originalmente como una notación matemática práctica para los programas de computadora, basada en el cálculo lambda de Alonzo Church. Se convirtió rápidamente en el lenguaje de programación favorito en la investigación de la inteligencia artificial (AI). Como uno de los primeros lenguajes de programación, Lisp fue pionero en muchas ideas en ciencias de la computación,

Autómatas Celulares Página 12

incluyendo las estructuras de datos de árbol, el manejo de almacenamiento automático, tipos dinámicos, y el compilador auto contenido. El nombre LISP deriva del "LISt Processing" (Proceso de LIStas).

Supeditado. Subordinar o condicionar una cosa al cumplimiento de otra.

3. ANTECEDENTE

Teoría de los autómatas.

La teoría de autómatas es una rama de las ciencias de la computación que estudia las máquinas abstractas y los problemas que éstas son capaces de resolver. La teoría de autómatas está estrechamente relacionada con la teoría del lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajes formales que son capaces de reconocer.Un autómata es un modelo matemático para una máquina de estado finito (FSM sus siglas en inglés). Una FSM es una máquina que, dada una entrada de símbolos, "salta" a través de una serie de estados de acuerdo a una función de transición (que puede ser expresada como una tabla). En la variedad común "Mealy" de FSMs, esta función de transición dice al autómata a qué estado cambiar dados un determinado estado y símbolo.La entrada es leída símbolo por símbolo, hasta que es "consumida" completamente (piense en ésta como una cinta con una palabra escrita en ella, que es leída por una cabeza lectora del autómata; la cabeza se mueve a lo largo de la cinta, leyendo un símbolo a la vez) una vez la entrada se ha agotado, el autómata se detiene.Dependiendo del estado en el que el autómata finaliza se dice que este ha aceptado o rechazado la entrada. Si éste termina en el estado "acepta", el autómata acepta la palabra. Si lo hace en el estado "rechaza", el autómata rechazó la palabra, el conjunto de todas las palabras aceptadas por el autómata constituyen el lenguaje aceptado por el mismo.Debido a ciertas etapas en los procesos de fabricación, se llegó a pensar en la posibilidad de dejar ciertas tareas tediosas, repetitivas peligrosas, se llegó a pensar en que no pudieran afectarle las condiciones ambientales adversas; así nació la máquina de automatización.En 1969 Fordy general Motor impusieron a los proveedores de automatismos , a medio camino entre los microcomputadores y la lógica cableada aparecen los primeros modelos autómatas limitados originalmente a tratamientos de lógica

Autómatas Celulares Página 13

secuencial, los autómatas se desarrollaron rápidamente y actualmente extienden sus aplicaciones del conjunto de sistemas de control de procesos y de máquinas.La teoría de autómatas “es el estudio de las máquinas o dispositivos abstractos con calidad de computación”.En la década de la de 1930 antes de que existieran las computadoras Turing estudio una máquina abstracta que poseía la misma capacidad que los computadores de hoy en día.En 1940 y 1950 otros investigadores estudiaron tipos de máquinas más sencillas hoy conocidas como “autómatas finitos “.A finales de 1950 Chomsky comenzó el estudio de las gramáticas formales.En 1969 Cook extendió los estudios realizados por Turing acerca de lo que se puede computar y lo que no.

4. CRONOLOGIA E HISTORIA

CRONOLOGIA

1947 – 1957: John Von Neumann, con la colaboración de Stanislaw Ulam. En la década de los 50, dos neurofisiólogos, Warren S. McCulloch y Walter

Pitts diseñaron un modelo matemático para representar el funcionamiento de las células cerebrales que fue el origen de los que hoy se conoce por redes neuronales. El modelo era una aproximación muy sencilla al comportamiento real de las neuronas, pero tenía grandes aplicaciones en otros contextos. En el campo puramente matemático, Kleene redefinió el modelo y dio lugar a los autómatas finitos, especie de máquinas ideales o modelos matemáticos, al modo de la máquina de Turing, con posibilidades bastante más reducidas, pero muy adecuadas para ciertos procesos de cálculo.

En 1952 se construyó una red de dos dimensiones, el primer autómata de esta clase, con 29 posibles colores para cada celda y un conjunto de reglas definidas para emular las operaciones que llevan a cabo los componentes de un computador y de diversos dispositivos mecánicos.

1966: Arthur W. Burks, terminación y publicación del libro Theory of Self-reproducing Automata, a nombre de Von Neumann.

1967: Konrad Zuse enuncia su tesis planteando que el Universo es un gran autómata celular, siendo Edward Fredkin quien años más tarde popularizase el planteamiento.

1967: Ulam y Robert Schrandt investigaron autómatas celulares de dos estados, incluso estudiaron autómatas celulares en tres dimensiones.

Autómatas Celulares Página 14

1967 en adelante: Edgar Frank Codd plantea una variación del autómata de Von Neumann variando el número de estados posibles para cada célula.

1960 – 1969: Gustav A. Hedlund realiza un estudio matemático teórico sobre los autómatas, que culmina con la publicación de Endomorphisms and automorphisms of the shift dynamical system, Mathematical Systems Theory en 1969.

1970: John Conway crea el Juego de la Vida, el autómata celular más representativo. Publicado por Martin Gardner en la revista Scientifist American.

1980 - 1990: Stephen Wolfram, investigación en profundidad de los autómatas celulares y su clasificación.

1980 - 2000: Carter Bays, estudio de formaciones tridimensionales a partir de autómatas celulares.

Años treinta dinámica de fluidos greenshilds. Años cincuenta: macroscópica y microscópica. Años noventa: información estadística y poder de computo.

HISTORIA

Era de Von Neumann

La primera etapa la inicia von Neumann,1 quien una vez terminada su participación en el desarrollo y terminación de la primera computadora ENIAC tenía en mente desarrollar una máquina con la capacidad de construir a partir de sí misma otras máquinas (auto-reproducción) y soportar comportamiento complejo. Con la ayuda de su amigo Stanislaw Ulam, von Neumann implementa la teoría de los autómatas celulares en un vector de dos dimensiones   (donde   representa el conjunto de los enteros). El vector es llamado el espacio de evoluciones y cada una de las posiciones (llamadas células) en el vector toma un valor del conjunto de estados|k|=29. La función de transición que determina el comportamiento del autómata celular utiliza la vecindad de von Neumann, que consiste en un elemento central x (i , j)  (llamada célula central) y sus vecinos que son las células x (i , j−1 ) , x ( i , j+1 ) , x (i−1 , j ) y x (i+1, j) (es decir, la célula en cuestión y sus células vecinas más próximas, arriba, abajo, izquierda y derecha, respectivamente).

John von Neumann, cuando este trataba de desarrollar un modelo abstracto de auto-reproducción biológica.

1947 - Empezó a idear modelos de robótica basados en ecuaciones diferenciales. Aconsejado por Stanislaw Ulam, su modelo evolucionó en autómata celular, simplificando su modelo inicial de 3 dimensiones en una red de dos dimensiones.

Autómatas Celulares Página 15

1952 - Construyó el primer autómata de esta clase, con 29 posibles colores para cada celda y un conjunto de reglas definidas para emular las operaciones que llevan a cabo los componentes de un computador. Para asentar una prueba

John von Neumann elaboró un primer esbozo de una configuración de red de doscientas mil celdas con características evolutivas y de auto-reproducción, inspirado en la complejidad de los organismos biológicos y de los computadores electrónicos.

En los años 60, se relacionan los conceptos de auto-reproducción y computación universal sobre autómatas de este tipo. Se elaboraron construcciones concretas en las que el comportamiento del autómata mostraba características particulares importantes para alcanzar estos dos objetivos.

A comienzos de esa década se investigó el uso de autómatas celulares como computadores paralelos y se establecieron una serie de teoremas análogos a los que sientan las bases de las máquinas de Turing, que probaban estas capacidades computacionales. A finales de los 60, se propone el concepto de autómata celular aplicado a la matemática de los sistemas dinámicos. El interés por la investigación sobre autómatas celulares comenzó a descender a partir de 1970

Siguiendo en la década de los 60, se realizaron simulaciones de autómatas celulares con redes de dos dimensiones. Stanislaw Ulam elaboró una serie de ejemplos agrupados en lo que denominó objetos geométricos con definición recursiva, evolución del autómata celular de dos dimensiones.

Edgard Fredkin simuló en 1961 un autómata de dos dimensiones en un computador PDP-1, mostrando propiedades de auto-reproducción.

En 1983 sus ideas volvieron a resurgir, incrementándose el número de artículos publicados que trataban este tema, siendo recogidos en el Índice de Citas Científicas.

Era de John Horton Conway

En 1970, John Horton Conway dio a conocer el autómata celular que probablemente sea el más conocido: el Juego de la vida (Life), publicado por Martin Gardner en su columna Mathematical Games en la revista Scientific American. Life ocupa una cuadrícula (lattice bidimensional) donde se coloca al inicio un patrón de células "vivas" o "muertas". La vecindad para cada célula son ocho: los vecinos formados por la vecindad de Von Neumann y las cuatro células

Autómatas Celulares Página 16

de las dos diagonales (esta vecindad se conoce como vecindad de Moore). De manera repetida, se aplican simultáneamente sobre todas las células de la cuadrícula las siguientes 3 reglas:

1. Nacimiento: se reemplaza una célula muerta por una viva si dicha célula tiene exactamente 3 vecinos vivos.

2. Muerte: se reemplaza una célula viva por una muerta si dicha célula no tiene más de 1 vecino vivo (muerte por aislamiento) o si tiene más de 3 vecinos vivos (muerte por sobrepoblación).

3. Supervivencia: una célula viva permanecerá en ese estado si tiene 2 o 3 vecinos vivos.

Una de las características más importantes de Life es su capacidad de realizar cómputo universal, es decir, que con una distribución inicial apropiada de células vivas y muertas, Life se puede convertir en una computadora de propósito general (máquina de Turing).

Era de Stephen Wolfram

Stephen Wolfram ha realizado numerosas investigaciones sobre el comportamiento cualitativo de los A.C. Con base en su trabajo sobre AC unidimensionales, con dos o tres estados, sobre configuraciones periódicas que se presentan en el A.C., observó sus evoluciones para configuraciones iniciales aleatorias. Así, dada una regla, el A.C. exhibe diferentes comportamientos para diferentes condiciones iniciales.

De esta manera, Wolfram clasificó el comportamiento cualitativo de los A.C. unidimensionales. De acuerdo con esto, un AC pertenece a una de las siguientes clases:

Clase I. La evolución lleva a una configuración estable y homogénea, es decir, todas las células terminan por llegar al mismo valor.

Clase II. La evolución lleva a un conjunto de estructuras simples que son estables o periódicas.

Clase III. La evolución lleva a un patrón caótico.

Clase IV. La evolución lleva a estructuras aisladas que muestran un comportamiento complejo (es decir, ni completamente caótico, ni completamente ordenado, sino en la línea entre uno y otro, este suele ser el tipo de comportamiento más interesante que un sistema dinámico puede presentar).

Autómatas Celulares Página 17

5. DESCRIPCIÓN ESPECIALIZADA DEL TEMA

Un autómata celular describe una idealización matemática de la naturaleza, proporcionando modelos para un amplio margen de complejos fenómenos biológicos y físicos.Puede ser considerado como una idealización discreta de las ecuaciones diferenciales usadas para describir los sistemas naturales, y, en una segunda instancia, sus bases se asemejan a las de los computadores de procesamiento paralelo.A partir de los estudios de Von Neumann, un autómata celular es un modelo matemático para un sistema dinámico que evoluciona en pasos discretos. Es decir, es un modelo matemático para sistemas que soportan cambios; además, estos cambios se suceden cada tiempos constantes, razón por la cual, se usa una escala de enteros.Es un modelo matemático para un sistema dinámico que evoluciona en pasos discretos descubiertos dentro del campo de la física computacional por John von Neumann en la década de 1950. La teoría de los autómatas celulares se inicia con su precursor John von Neumann a finales de la década de 1940 con su libro Theory of Self-reproducing Automata (editado y completado por A. W. Burks).Los Autómatas Celulares son una clase de sistemas dinámicos discretos cuyas características los hace un candidato idóneo para el estudio de sistemas con un nivel alto de complejidad, ya que estos pueden emplearse en una gran variedad de campos, por ejemplo en física, biología y sistemas de cómputo.

La evolución del conjunto de células (se dice "de la configuración") síncronos, lo que quiere decir que todas las células cambian de estado al mismo tiempo.

Un modelo matemático para un sistema que evoluciona en pasos discretos. Es adecuado para modelar sistemas naturales que puedan ser descritos como una colección masiva de objetos simples que interactúen localmente unos con otros.

Desde un punto de vista matemático los autómatas celulares son sistemas dinámicos discretos que presentan patrones de comportamiento tan complejos como los sistemas dinámicos continuos más clásicos, pero pueden ser simulados sin error en un ordenador por su carácter completamente discreto. Desde un punto de vista computacional son un modelo de computación en paralelo y descentralizado. 

Tipos de patrones:

Autómatas Celulares Página 18

Patrones estáticos ("vidas estáticas", en inglés still lifes) Patrones recurrentes ("osciladores", oscillators, un conjunto de vidas

estáticas) Patrones que se trasladan por el tablero ("naves espaciales", spaceships).

Los nombres son más conocidos en inglés, por lo que también se muestra el nombre de estas estructuras en dicho idioma.

Un Autómata Celular es un sistema dinámico discreto el cual involucra reglas simples determinísticas, como en cualquier sistema los cambios de variables están en función de sus valores predichos, se considera una idealización matemática en donde el espacio y el tiempo son caracterizados de manera discreta, así las cantidades relacionadas toman valores discretos. De acuerdo a la definición y generalización que acabamos de dar podemos especificar de qué es lo que consta un AC.

1. El tiempo es discreto y en pasos progresivos.2. El espacio es particionado en células discretas, teniendo una geometría

dada. D-dimensional.3. Las condiciones pueden ser definidas en un espacio finito.

En un sistema celular uno puede formularse, precisar y gobernar con reglas simples la operación del sistema. Camino intuitivo por el cual el Autómata finito se auto reproduce, la lista finita de estados para el sistema, por cada célula es un estado distinguible y una regla la cual da el estado de cada célula.Los primeros autómatas celulares

Los estudios sobre autómatas finitos, máquinas de Turing, y otros modelos que siguen la misma filosofía configuran lo que se ha denominado Teoría de Autómatas y Máquinas de Turing, o simplemente Teoría de Autómatas, dentro de la Teoría de la Computación.Por otra parte el inglés Turing consiguió definir conceptualmente una máquina de cálculo que se considera universal, es decir, el mecanismo de procesar cualquier

Autómatas Celulares Página 19

algoritmo. Turing diseñó un modelo matemático de autómata que siguiendo unas reglas simples conseguía solucionar una gran gama de problemas. En principio, la máquina de Turing constituye el instrumento de cálculo universal, el más general. No es posible dar una demostración rigurosa de esto, aunque sí se tiene una gran cantidad de indicios, agrupados en lo que se conoce como Tesis de Church, que puede plantearse así: "No existen funciones que puedan ser definidas por personas, y cuyo cálculo sea descrito por algún algoritmo, que no puedan computarse con una máquina de Turing". Basándose en la máquina de Turing, Von Neumann trabajó en una máquina autor reproductiva que llamó kinematon y en la idea de autómata celular.Los autómatas celulares son redes de autómatas simples conectados localmente. Cada autómata simple produce una salida a partir de varias entradas, modificando en el proceso su estado según una función de transición. Pueden considerarse como una buena alternativa a las ecuaciones diferenciales.

Autómatas Celulares

Una de las principales áreas de la Vida Artificial es la de los Autómatas Celulares (AC). La mejor definición de AC que he encontrado es:

"...Es una cuadrícula espacial regular de "células", cada una de las cuales puede tener uno de un número finito de estados. El estado de las células en la cuadrícula se actualiza simultáneamente y el estado de la cuadrícula completa avanza en pasos de tiempo discretos. El estado de cada célula en la cuadrícula se actualiza de acuerdo a una regla local que puede depender del estado de la célula y sus vecinos en el paso temporal anterior...”

Existen dos ejemplos muy buenos de ACs. El autómata celular unidimensional de Wolfram (Wolfram's 1D CA) y El Juego de la Vida de Conway (Conway's Life), un autómata celular de dos dimensiones.

Autómatas celulares unidimensionales

En una escala lógica, el autómata celular unidimensional es el primer paso para entender la dinámica de los autómatas celulares. Consiste en una sola fila de células a los que se aplica un principio de vecindad básico de dos vecinos por célula y a los que igualmente se pueden aplicar las diversas condiciones de frontera que hemos nombrado anteriormente.

Autómatas Celulares Página 20

Como ejemplo, podemos tomar un autómata celular unidimensional con un radio de vecindad r=1, dos estados (0 y 1) y una condición de frontera de tipo periódico, como el que se muestra en la imagen. Usaremos para este caso un tamaño de diez células y unas funciones de transición basadas en lo siguiente:

Si ambos vecinos de la célula tienen el mismo estado, el estado de la célula a la que se aplica la función cambiará.

Si ambos vecinos de la célula tienen distinto estado, el estado de la célula a la que se aplica se mantendrá igual.

Planteamos por tanto unos valores iniciales: 0001010011.

Autómatas Celulares Página 21

Stephen Wolfram clasificó el comportamiento de los autómatas celulares unidimensionales. Según Wolfram, todo autómata celular pertenece a una de las siguientes clases:

Clase I. La evolución lleva a una configuración estable y homogénea, es decir, todas las células terminan por llegar al mismo valor.

Clase II. La evolución lleva a un conjunto de estructuras simples que son estables o periódicas.

Clase III. La evolución lleva a un patrón caótico1. Clase IV. La evolución lleva a estructuras aisladas que muestran un

comportamiento complejo (es decir, ni completamente caótico, ni completamente ordenado, sino en la línea entre uno y otro, este suele ser el tipo de comportamiento más interesante que un sistema dinámico puede presentar).

Autómatas celulares bidimensionales

Es el más común de los autómatas celulares a nivel de simulación y estudio. Consiste en la consabida cuadrícula compuesta por células (ℤ x ℤ), implantada por Von Neumann por consejo y Stanislaw Ulam. Este tipo de autómata celular, por ser el más estudiado, ha sido variado en múltiples ocasiones.

Ya hemos hablado del principio de vecindad de Von Neumann, que implicaba cuatro vecinos para cada célula, pero este no es el único. En 1970 se dio a conocer el juego de la vida de John Conway, que se basada en un principio de vecindad diferente. Este principio se conoce con el nombre de vecindad de Moore, y aplica ocho vecinos a cada célula, es decir, los cuatro que consideraba Von Neumann más las cuatro células de las diagonales respectivas. Además, se basaba en una condición de frontera de tipo periódico y dos estados posibles. Este juego de la vida consideraba tres reglas fundamentales para su funcionamiento:

1. Nacimiento: se reemplaza una célula muerta por una viva si dicha célula tiene exactamente 3 vecinos vivos.

2. Muerte: se reemplaza una célula viva por una muerta si dicha célula no tiene más de 1 vecino vivo (muerte por aislamiento) o si tiene más de 3 vecinos vivos (muerte por sobrepoblación).

Autómatas Celulares Página 22

3. Supervivencia: una célula viva permanecerá en ese estado si tiene 2 o 3 vecinos vivos.

Producto del amplio estudio que han realizado múltiples expertos y estudiantes, se han descubierto y catalogado una serie de patrones característicos. Se diferencian entonces cuatro tipos de patrones: estáticos, patrones que no varían; recurrentes, patrones que varían de una posición a otra indefinidamente; patrones con movilidad, que se reproducen y se mueven por toda la cuadricula; matusalenes, que son patrones que tardan muchos pasos en estabilizarse.

Especial atención merecen estos últimos, los matusalenes. Son una serie interesante de patrones que evolucionan durante varias generaciones antes de estabilizarse. Diehard es uno de estos patrones, que se estabiliza tras 130 turnos, desapareciendo, mientras que Acorn llega a 5206 transiciones antes de estabilizarse en múltiples formaciones recurrentes y fijas, incluidos algunos planeadores.

Autómatas Celulares Página 23

En cuanto a los planeadores o patrones de movilidad, una de las aportaciones originales de Conway fue el descubrimiento de la estructura de cinco células vivas llamada Glider, que resulta encajar en el papel de planeador realizando un viaje en diagonal por la cuadricula. Las transiciones se ven representadas en la siguiente figura:

Autómatas celulares tridimensionales

Ampliamente estudiados por Carter Bays, los autómatas celulares de tres dimensiones se enfocan principalmente para encontrar una regla de evolución en tres dimensiones que sea la sucesora del Juego de la Vida en el espacio tridimensional, muchos de sus resultados son de tipo cuantitativo, basados principalmente en la simulación de varias reglas de evolución en pequeños espacios tridimensionales para encontrar estructuras que sean similares al Juego. La aplicación de estos autómatas celulares se centra en el estudio en campos estadísticos.Son autómatas celulares que se desarrollan en un ámbito de ℤ x ℤ x ℤ, que usan el principio de vecindad de Moore a nivel tridimensional. Esto implica que la

Autómatas Celulares Página 24

función de transición ha de tener en cuenta el estado de veintiséis células vecinas además del estado de la célula en cuestión.Los autómatas celulares tridimensionales pueden seguir los mismos principios que los anteriores, aunque dado el incremento de la complejidad de los cálculos y el procesamiento, su puesta en práctica no es simple. Sin embargo, y puesto que se pueden considerar autómatas celulares tridimensionales con las mismas variables de tipo frontera en el ámbito teórico, se debe considerar que la representación de los autómatas celulares tridimensionales considerando una frontera periódica es en forma de toroide.

Los patrones evolutivos en tres dimensiones son considerados distintos, de forma que se catalogan en complejos, caóticos o triviales.

Descripción

No existe una definición formal y matemática aceptada de Autómata Celular; sin embargo, se puede describir a un A.C. como una tupla, es decir, un conjunto ordenado de objetos caracterizado por los siguientes componentes:

Una rejilla o cuadriculado (lattice) de enteros (conjuntoZ) infinitamente extendida, y con dimensión d ϵ Z+¿¿ . Cada celda de la cuadrícula se conoce como célula.

Cada célula puede tomar un valor en   a partir de un conjunto finito de estados   .

Cada célula, además, se caracteriza por su vecindad, un conjunto finito de células en las cercanías de la misma.

De acuerdo con esto, se aplica a todas las células de la cuadrícula una función

de transición (   ) que toma como argumentos los valores de la célula en cuestión y los valores de sus vecinos, y regresa el nuevo valor que la célula

tendrá en la siguiente etapa de tiempo. Esta función   se aplica, como ya se dijo, de forma homogénea a todas las células, por cada paso discreto de

Autómatas Celulares Página 25

tiempo. El decidir qué celdas son vecinas viene dado por dos modelos diferentes

Modelo de von Neumann: considera las celdas situadas en las

posiciones inmediatamente superior, inferior y laterales.

Modelo de Moore: considera los del modelo de von Neumann más las celdas situadas en las diagonales.

Condiciones de frontera

Dentro del ámbito de los A.C., se pueden implementar numerosas condiciones de frontera, en función de lo que el problema real requiera para su modelado. Por ejemplo:

Frontera abierta. Se considera que fuera de la lattice residen células, todas con un valor fijo. En el caso particular del juego de la vida y de otros A.C.

Autómatas Celulares Página 26

con dos estados en su conjunto , una frontera se dice fría si las células fuera de la frontera se consideran muertas, y caliente si se consideran vivas.

Frontera periódica. Se considera a la lattice como si sus extremos se tocaran. En una lattice de dimensión 1, esto puede visualizarse en dos dimensiones como una circunferencia. En dimensión 2, la lattice podría visualizarse en tres dimensiones como un toroide.

Frontera reflectora. Se considera que las células fuera de la lattice "reflejan" los valores de aquellas dentro de la lattice. Así, una célula que estuviera junto al borde de la lattice (fuera de ella) tomaría como valor el de la célula que esté junto al borde de la lattice, dentro de ella.

Sin frontera. Haciendo uso de implementaciones que hagan crecer dinámicamente el uso de memoria de la lattice implementada, se puede asumir que cada vez que las células deben interactuar con células fuera de la lattice, esta se hace más grande para dar cabida a estas interacciones. Obviamente, existe un límite (impuesto por la memoria disponible) para esta condición. Es muy importante no confundir esta condición de frontera con la definición original de A.C. cuya lattice es inicialmente infinita. En el caso de un A.C. sin frontera, la lattice comienza con un tamaño definido y finito, y conforme se requiera va creciendo en el tiempo, lo cual no lo hace necesariamente un modelo más cercano a la realidad, pues si se inicializara la lattice aleatoriamente, con esta condición sólo se pueden inicializar las células dentro de la lattice inicial finita, mientras que en el caso de la definición original, en teoría todas las células de la lattice infinita deberían ser inicializadas.

Variaciones

Pueden variar en algunas características, derivando en autómatas celulares no estándar. Por ejemplo:Se asume que las células son cuadros. Esto no es necesariamente un requisito, y se puede variar el A.C. para presentar una geometría triangular o hexagonal.También puede variarse el conjunto de estados   que cada célula puede tomar,

para que la función de transición   ya no sea homogénea; se conoce como A.C. probabilístico), variar las vecindades de cada célula, etc.Una familia de reglas para la evolución del autómata celular se obtiene a través de funciones cuyo valor en un sitio determinado es obtenido de los valores del propio sitio y de sus vecinos más cercanos en el paso de tiempo anterior. Cada regla lleva a modelos que difieren en detalles, sin embargo parece que entran en solo

Autómatas Celulares Página 27

cuatro clases cualitativas, las cuales por su conducta pueden caracterizarse de la siguiente manera:

Clase 1: La evolución lleva a un estado homogéneo. Sin tener en cuenta el estado inicial, el sistema evoluciona siempre a un único estado homogéneo o punto fijo. Por ejemplo, después de un periodo de “transición", todos los sitios tendrán valor 0.

Clase 2: La evolución lleva a estructuras periódicas que están separadas (temporalmente) y son simples. En este caso, los efectos de las reglas en los sitios tienen un rango nito. Esto es: un cambio en el valor de un solo sitio afecta solo una región finita de sitios alrededor de él, incluso después de un número infinito de pasos de tiempo.

Clase 3: La evolución lleva a estructuras que siguen un modelo caótico. Aquí los efectos de las reglas se propagan a los sitios vecinos a una velocidad fija pero con un rango indefinido. Si el estado inicial se desordena, esta dependencia puede llevar a una sucesión aparentemente caótica de valores para un sitio particular

Clase 4: La evolución lleva a estructuras complejas, que no se explican por las clases anteriores. Los efectos de las reglas también se propagan indefinida- mente a los sitios vecinos, pero a diferencia de los de clase 3, a varias velocidades.

La existencia de solo cuatro clases cualitativas indica la universalidad en la conducta del autómata celular; muchos rasgos del autómata celular solo dependen de la clase a la que pertenecen y no de los detalles precisos de su evolución.

Las tres primeras clases de conducta del autómata celular mencionadas son análogas a tres clases de conducta encontradas en sistemas dinámicos continuos.

La clase 1 es análoga a las soluciones con un punto fijo. La clase 2 es análoga a orbitas periódicas. Finalmente la clase 3 es análoga a sistemas que tienen dependencia sensible a las condiciones iniciales (sistemas dinámicos caóticos).

Sin embargo, en la clase 4 las estructuras propagadas permiten que el valor de un sitio afecte a sitios arbitrariamente distantes después de un tiempo suficientemente largo. Es de notar que ninguna conducta análoga a las de clase 4 se ha encontrado todavía en un sistema dinámico continuo. La complejidad de esta conducta hace pensar en la conjetura de que estos sistemas pueden representar máquinas de cómputo universal.

Autómatas Celulares Página 28

Otra diferencia fundamental es que a diferencia de otros sistemas dinámicos reversibles, los autómatas celulares son, en general, irreversibles (esto es la regla que describe el cambio de una con curación a otra, no es una función inyectiva) y por lo tanto contradicen la segunda ley de termodinámica.

Reglas destacadas

Regla 30

Esta regla fue presentada por Stephen Wolfman en 1983 y la representa el número binario 00011110. A continuación se muestra la regla de manera gráfica, y una retícula en la que se ha ejecutado 15 veces la regla 30.

Esta regla también se puede representar mediante una secuencia de números, pasando las filas de binario a decimal. La primera fila sería 12 = 1</sub>10, la segunda 1112 = 710, la tercera 110012=2510, y así sucesivamente.

De todas formas el mayor interés de esta regla se encuentra en su columna central (1101110011000101 en nuestro ejemplo de 15 iteraciones), ya que es aparentemente caótica, es decir, no sigue ningún patrón. Actualmente, no existe ninguna demostración determinante que encuentre patrón alguno en el primer millón de elementos. Debido a esto, suele ser usado en algoritmos para generar números aleatorios muy grandes.

Como curiosidad, indicar que la regla 30 aparece tiene su presencia en la naturaleza, concretamente en las conchas de la especie de caracol Conus Textile, que presenta patrones extremadamente similares a los generados por este autómata.

Autómatas Celulares Página 29

El caparazón de Conus textile muestra un patrón caracterizable en términos de

autómatas celulares.

Regla 90

Esta regla también fue presentada por Stephen Wolfman en 1983 y se representa con el binario 01011010. A continuación mostramos su representación gráfica y una retícula tras pasar por 15 iteraciones.

Zoom "infinito" sobre un triángulo de Sierpiński

Esta regla produce un fractal. Concretamente se trata de los triángulos de SierpińskiEsta regla tiene varias propiedades curiosas: el resultado de una situación corresponde a la suma en módulo 2 de los vecinos izquierdo y derecho (0+0=0; 0+1=1; 1+0=1; 1+1=0). Se puede ver fácilmente que esta suma es equivalente a la operación lógica XOR.

Autómatas Celulares Página 30

Esta regla 90 es usada en algunos algoritmos de cifrado como equivalente de un registro de desplazamiento con retroalimentación lineal.

Regla 110

Esta regla viene representada por el binario 01101110 y a continuación mostramos su representación gráfica y una retícula con 15 iteraciones de esta regla:

Puede ser usado como un sistema Turing completo. Además, se ha demostrado que la emulación de una máquina Turing con la regla 110 es un problema P-Completo.A la hora de representar datos, se parte de patrones formados por ciertas figuras llamadas “naves espaciales”. Como se puede suponer, para generar estos patrones y que las relaciones entre estos generen otros patrones ya determinados, requiere de una cuidadosa elección del estado inicial del autómata.

Regla 184

La regla 184 viene representada por el binario 10111000, y a continuación mostramos su representación gráfica y un ejemplo de una retícula tras 16 iteraciones con esta regla.

Autómatas Celulares Página 31

Veamos sus 2 principales usos:Como predictor del flujo de tráfico en una carretera de un sólo carril.

Representación de la aniquilación de materia.

Como autómata que simula el comportamiento de partículas de materia y antimateria que se van aniquilando. Además, este autómata ligeramente modificado, sirve para detectar en un texto paréntesis anidados.

Las reglas de los autómatas de dos dimensiones fueron utilizadas en el campo del procesamiento digital de imágenes con el objetivo de eliminar el ruido en aplicaciones como reconocimiento óptico de caracteres.

6. EXPLICACIÓN DE LA APLICACIÓN.

Permiten modelar las leyes del comportamiento climático de una determinada zona o representar una simulación de la propia vida y su evolución, sistemas termodinámicos, etc.Tales sistemas tienen el potencial preciso para llevar a cabo cálculos complejos con un alto grado de robustez y eficiencia, útiles para la elaboración de modelos del comportamiento de los sistemas naturales. También han servido como modelos abstractos para el estudio de sistemas complejos basados en conciencia colectiva.Estos autómatas han sido utilizados para modelar fenómenos biológicos y físicos como la formación de galaxias, terremotos, fluidos, etc. Las aplicaciones realizadas con los autómatas celulares a día de hoy son tan amplias que abarcan profesiones tan dispares como psicología e informática.

Autómatas Celulares Página 32

Método de control estadístico para encontrar patrones aparentemente no triviales en espacios de evoluciones a gran escala, o como elemento de nueva introducción en ámbitos como la arquitectura o la química.En realidad, podemos generalizar las aplicaciones de los autómatas celulares en tres ideas fundamentales: simulación de sistemas naturales, estudios teóricos y realización de tareas específicas.En el primero, simulación de sistemas naturales, podemos nombrar áreas de la psicología (estudio de comportamiento de masas), medicina (patrones de pigmentación de la piel), ingeniería (mecánica de fluidos), química (modelos de reacciones químicas) o geología y ciencias de materiales (estudio de crecimiento de cristales). Incluso se contempla su uso en la resolución de incendios y su propagación. En segundo lugar, los estudios teóricos se extienden desde el estudio de los sistemas caóticos a la computación en paralelo, la computación universal o el estudio de patrones fractales. Por último, en cuando a la realización de tareas específicas, que se pueden extender desde finalidades artísticas a procesamiento de imágenes y encriptación de datos. Actualmente, ciertas líneas de investigación se centran en la creación de modelos paralelos de sistemas físicos y el procesamiento de datos en paralelo optimizado, mediante autómatas celulares.

Modelado del flujo de tráfico y de peatones.

Modelado de fluidos (gases o líquidos).

Modelado de la evolución de células o virus como el VIH.

Modelado de procesos de percolación.

Área de física, matemáticas y ciencias computacionales, destacan mecánica de fluidos, generadores de números aleatorios, mejor entendimiento de sistemas dinámicos continuos, y máquinas de computo universal.

Autómatas Celulares e Inteligencia Artificial

Dentro de la Vida Artificial, los Autómatas Celulares son el más claro ejemplo de este rodeo en la búsqueda de la inteligencia. Es bastante extraño decir que los Autómatas Celulares son inteligentes, no lo parecen en absoluto. En cambio, poseen muchos de los aspectos fundamentales de la vida en cuanto a procesos.

Además, esto se intenta conseguir con la máxima simplicidad posible, por lo que podrían ser el fundamento, al menos teórico, de la vida, y por extensión, de la inteligencia.

Autómatas Celulares Página 33

Utilizados para modelar sistemas físicos, como interacciones entre partículas, formación de galaxias, cinética de sistemas moleculares y crecimiento de cristales, así como diversos sistemas biológicos a nivel celular, multicelular y poblacional.

Ejemplos de Autómatas CelularesEstos tres que se presentan son ejemplos de autómatas desarrollados en los últimos años:

El juego de la vida de Conway

Uno de los autómatas celulares más conocidos es el que John Horton Conway llamó el juego VIDA (Life Game). El juego VIDA es un autómata celular bidimensional en cuadrícula con dos estados por celda. Cada celda o célula puede estar viva o muerta y en cada generación se aplica un algoritmo que sigue estas tres reglas:

1. Cada célula viva con dos o tres células vecinas vivas sobrevive a la siguiente generación.

2. Cada célula viva con ninguna, una, o más de tres células vivas a su alrededor pasa a estar muerta.

3. Cada célula muerta con tres células vecinas vivas resucita en la siguiente generación.

El juego VIDA presenta configuraciones finales estables, periódicas o no. Langton defiende que presenta propiedades de catálisis (acciones de construcción arbitrarias), de transporte (borrando estructuras y reconstruyéndolas en otro lugar del espacio celular), estructurales (como elementos estáticos, barreras, etc.), de regulación, defensa e incluso informativas, y que por tanto estos autómatas virtuales tienen capacidades computacionales suficientes para cumplir los papeles funcionales que juegan las macromoléculas en la lógica molecular de la vida. En definitiva, que funcionalmente, los autómatas son equiparables a los componentes básicos de la vida en nuestro planeta.

El programa "Células" de Peter Donnelly

El programa "células" es en esencia una curiosidad científica propuesta por primera vez por Peter Donnelly del University College de Swansea, Gales, y Dominic Welsh, de la universidad de Oxford. El programa fue descrito en detalle por A. K. Dewdney en su artículo "Cinco piezas sencillas" para Scientific American. En este artículo se bautiza al programa con el nombre de "votación", ya que según

Autómatas Celulares Página 34

el autor pretende simular una votación política algo particular. Citando textualmente:

"Las casillas de un cuadriculado rectangular están coloreadas de blanco o negro, aleatoriamente. Se supone que cada color refleja la opinión política de una persona residente en esa casilla. Un color podría representar 'demócrata' y el otro 'republicano'. [...] A cada señal de reloj, se selecciona al azar uno de los votantes y su opinión política se somete a cambio: se selecciona al azar uno de sus ocho vecinos y la convicción política del elector se transforma en la de este vecino, independientemente de cuál fuera su opinión anterior. [...] Al hacer funcionar este modelo, confesadamente simplista, del proceso político, ocurren cosas llamativas y extrañas. Primero se desarrollan grandes bloques de voto homogéneo. Estos bloques son zonas geográficas donde todo el mundo es de la misma opinión política. Seguidamente tales bloques van migrando en torno al cuadriculado y, durante cierto tiempo luchan, como buscando su predominancia.Finalmente, el sistema bipartidista se viene abajo, por acabar todo el mundo votando de igual manera".Además de esta interpretación de la ejecución del programa, hay otra más aproximada, y mucho más sugerente para los interesados en la vida artificial y temas afines. Podemos llegar a apreciar comportamientos "cuasi-biológicos" si observamos la evolución de los votantes como un ejemplo de la coexistencia-competitividad de dos especies similares en un mismo medio con abundancia de alimento, como podría ser el caso de dos especies de bacterias en un fluido rico en nutrientes.La interpretación es la siguiente: Cada posición de la matriz representa una célula de una especie determinada. En cada ciclo se elige aleatoriamente una de las células de la matriz. Esa célula muere, dejando un espacio libre. Ese espacio es ocupado inmediatamente de la siguiente forma: Se elige a una de las ocho células contiguas a ese espacio vacío para reproducirse, y el lugar dejado por la célula muerta lo ocupa una nueva célula, hija de la escogida, y por lo tanto de su misma especie.A partir de este comportamiento tan simple podremos observar como el caos inicial, en el que las células de ambas especies se hallan mezcladas, da paso a una forma de organización en la que las células de una misma especie forman amplios grupos. Que se desplazan, se estiran y se contraen mientras tratan de sobrevivir.Si se deja el programa funcionando durante un tiempo una de las especies pasa a ser dominante, pudiendo llegar a hacer desaparecer a la otra especie.

Autómatas Celulares Página 35

Finalmente, y como curiosidad, podríamos pensar en realizar en cada ciclo la reproducción de las células de un modo algo más inusual...¿Qué ocurriría si al reproducirse una célula para ocupar el espacio vacío dejado por otra célula muerta, tuviera una hija de la otra especie, y no de la suya propia? ¿Seguiría produciéndose la homogeneidad, o el caos inicial se extendería hasta el infinito? A partir del código fuente del programa, y realizando una pequeña modificación se puede resolver esta trascendental duda.

Hormigas y Plantas

Hormigas y Plantas es un programa que requiere de una cierta justificación para considerarse como autómata. Para ello se distinguirán varios tipos de autómatas en función de su objetivo. Esta discusión continúa en la sección Discretización del tiempo en los autómatas del documento "Autómatas como analogías de nuestro Universo"

1. Introducción a los tipos de autómatas

En cuanto a los autómatas que tratan de resolver un problema determinado, probablemente los más numerosos sean los compiladores, analizadores léxicos, sintácticos o semánticos, en definitiva, traductores de algún tipo. Estos autómatas son capaces de leer una secuencia de símbolos escrita de acuerdo a una norma o gramática, generando como salida otra secuencia ajustada a otra gramática diferente. La entrada puede ser un texto en castellano, un programa escrito en lenguaje C o un fichero de datos con una determinada estructura (por ejemplo, cierta cabecera, cuerpo y pie). La salida correspondiente podría ser entonces el texto en holandés, el programa de ordenador en lenguaje Lisp u otro fichero de datos con una composición diferente. Otro tipo de autómatas que están siendo muy utilizados son las Redes Neuronales Artificiales, sobre todo en aplicaciones de clasificación (reconocimiento) y predicción.Dentro del segundo grupo de autómatas, más orientados hacia la representación y la simulación que hacia la resolución, hay un gran subgrupo de autómatas que pretenden nada menos que la simulación de los procesos de la vida. Entre ellos se encuentra el programa "Hormigas y Plantas".

2. Hormigas y Plantas como autómata

En el programa "Hormigas y Plantas", cada una de las celdas de la rejilla en 2 dimensiones es un autómata simple con los siguientes estados posibles:

Autómatas Celulares Página 36

Vacío  Ocupado por una hormiga  Ocupado por una planta  Ocupado por un obstáculo

Cada celda cambia de estado en función del estado de las celdas vecinas. Por ejemplo, una celda en estado "planta" pasa a estado "vacío" si hay una hormiga próxima a la planta: la hormiga se come la planta. Otros cambios de estado están supeditados además al resultado de una función pseudo aleatoria uniforme, y se producen, si se cumplen las otras condiciones, según una cierta probabilidad. Por ejemplo, una celda en estado "vacío" pasa a estado "hormiga" sólo si hay una hormiga próxima a la planta y además con una cierta probabilidad (solo si la hormiga "decide" tomar esa dirección).El estado de cada celda puede estar definido por distintas variables: las hormigas, así como las plantas, poseen una cierta cantidad de energía. Pero además, las hormigas poseen una inercia en cuanto a la dirección del movimiento, que provoca una tendencia a moverse en la misma dirección, y un "tipo", ya que hay hormigas "rojas", "rosas", "naranjas", "amarillas" y "verdes" que corresponden con distintas probabilidades de moverse, regar, pelearse o reproducirse.En este autómata, los cambios de estado están dirigidos únicamente por las "hormigas", de forma que la "ejecución" de una hormiga provoca un cambio de estado en sí misma y en otras posibles celdas de tipo "planta". Este último punto lleva a la posibilidad de contemplar el programa desde otro punto de vista: como un conjunto de autómatas simples móviles cuyo estado se define, entre otros, por su posición en los ejes X e Y. Es decir, en vez de ver una rejilla cuyas celdas cambian de estado, vemos un conjunto de hormigas que se mueven por unos ejes cartesianos. Efectivamente, el autómata no se ha programado como un conjunto de celdas con distintas propiedades, sino como varios conjuntos (o varios autómatas superpuestos): un conjunto de hormigas, otro de plantas y otro de obstáculos, controlando que cualquiera de ellos no exista en la misma posición que otro.

Los mundos de Pixel

Los mundos de Pixel son un conjunto de autómatas celulares desarrollados en JavaScript. La mayoría de ellos utilizan las reglas de replicación RS y SR de René Reynaga y B. Sandi.La Vida Artificial y la IA presentan una buena simbiosis. La Vida Artificial estudia los algoritmos que pueden reproducir el comportamiento de la naturaleza y sus formas -- autómatas celulares, simulaciones de comportamiento de grupos

Autómatas Celulares Página 37

(hormigas, por ejemplo) -- dónde la IA tiende a estudiar la imitación (¿creación?) de la inteligencia humana.

Wolfram's 1D-CA

Wolfram fue un genio para su edad, y mostró como a partir de reglas y estructuras simples podía emerger una increíble complejidad. Wolfram creó un programa dónde cada una de las células estaban activadas o desactivadas (viva o muerta). Empezaba con una configuración inicial (con una célula, o una cadena aleatoria de ellas), las células de la línea inferior son determinadas por la línea anterior. Existen ocho posibles combinaciones para la Línea A que determinará la Línea B - 000, 001, 010, 011, 100, 101, 110, 111. Los resultados dependen del grupo de reglas (existen 256 posibilidades).“Recientemente (23/8/99), he creado (James Matthews) un programa de Windows 95 que te permite crear tus propias Autómatas Celulares de una dimensión. El programa puede generar algunos resultados muy interesantes, y puede generar resultados desde un punto o una línea. Este programa reemplaza el antiguo programa que había hecho de Wolfram en Pascal.”Durante esas dos décadas, tipos específicos de autómatas celulares de una y dos dimensiones fueron usados en diversos dispositivos electrónicos y computadores de propósito general. Las reglas de los autómatas de dos dimensiones fueron utilizadas en el campo del procesamiento digital de imágenes con el objetivo de eliminar el ruido en aplicaciones como reconocimiento óptico de caracteres. En los 60, una amplia línea de sistemas lógicos de procesamiento de gráficos fueron implementados mediante autómatas celulares, con reglas que definían un comportamiento simple, aunque con la posibilidad de generar patrones alternativos.Los esquemas de circuitos integrados estuvieron basados inicialmente en la disposición de componentes lógicos distribuidos en forma de rejilla, formando arrays (arreglos) celulares. Se iniciaron investigaciones sobre estos arrays (arreglos) con datos que se ejecutarían de forma iterativa sobre estos sistemas, pero se alcanzaron pocos diseños finales y la tecnología de elaboración de circuitos con circuitos más elaborados se desarrolló a un ritmo vertiginoso, a pesar de que sus fundamentos eran más complejos que los que sostienen las bases de cualquier autómata celular sencillo.Dispositivos para el almacenamiento de datos como los registros de desplazamiento de una máquina pueden ser simulados mediante autómatas celulares de una dimensión con un número concreto de celdas. Se llevó a cabo un amplio estudio algebraico de su comportamiento, concentrándose en situaciones como la repetición de estados en períodos de tiempo finitos. Los autómatas de una dimensión están asociados con registros de desplazamiento con

Autómatas Celulares Página 38

retroalimentación no lineal, siendo aplicados por Solomon Golomb a finales de los años 50 en aplicaciones de radio control, derivando en dos líneas: registros lineales (usados en telecomunicaciones) y no lineales (utilizados en criptografía).Tipos especiales de autómatas celulares aparecieron a finales de los 50 y comienzos de los 60, basados principalmente en redes unidimensionales y pensadas para estudiar un método de optimización de las operaciones aritméticas en los circuitos. A su vez, las redes neuronales respondían en ocasiones al modelo celular, esto es, nodos localizados en una red que se relacionan con sus vecinos para decidir su valor en el siguiente paso evolutivo, concretamente, autómatas celulares de dos dimensiones. Esta misma clase de autómatas se utilizaron para la modelización de sistemas biológicos basados en acción-reacción, respondiendo a estados de “excitación”.

Otra de las aplicaciones de los autómatas celulares se da en la simulación básica de incendios forestales, para determinar la duración de estos y el alcance geográfico que pueda llegar a tener.Para esto se debe entender a un autómata como un conjunto de objetos situado sobre una región geográfica o asociados a puntos de un espacio y susceptibles de adquirir ciertos estados según transcurre el tiempo, siempre en forma discreta o a saltaos. Estos objetos cambian sus estados en función de sus propios estados previos y de los de aquellos otros entes situados en su vecindad. El problema es entonces saber cuál será la evolución de la configuración del sistema según avance el tiempo.Simulación de evacuación de barcos y salas de cine, estudio de mercado y efectos de publicidad, diversión, arte, investigación, etc.

8. CONCLUSIONES

Como claramente se ha expresado en el trabajo, no se ha llegado aún a un acuerdo común de lo que vendría a ser la definición de un autómata celular, sin embargo hay componentes del mismo que están bien determinados.Cabe resaltar la importancia de estos autómatas en campos como las geografía, computación e incluso el tránsito; aplicaciones que le permiten manejar una serie de problemas de un alto nivel de complejidad en varios campos, no solo de la ciencia sino de la realidad.A pesar de esto, no se ha vinculado mucho estos autómatas con la Teoría del caos; dicha relación resulta ser un poco obvia al momento de leer este documento, esta relación se puede determinar en el simple hecho de comparar conceptos para aplicar uno dentro del otro.

Autómatas Celulares Página 39

En este caso, es obvio que esta relación se encuentra en el hecho que define a los autómatas celulares, que es la incertidumbre o dependencia del estado inicial de la configuración, estado que según se dijo, define el estado final o meta a la que llega un autómata en ejecución, después de una cantidad de pasos.Después de todo se debe, también, resaltar la gran cantidad de aplicaciones que se han desarrollado a partir de estos autómatas; aplicaciones que se ubican dentro de diferentes campos como la biología; campo del cual podría saltar la interrogante de si, a partir de lógicas como la de estos autómatas, se podría llegar a una auto reproducción en la especie humana, planteamiento que en algún momento será desarrollado y complementado por este línea de investigación.Los autómatas celulares solucionan el peso de encriptación de imágenes, ya que recorren más espacio en menos tiempo.

9. BIBLIOGRAFÍA

http://es.wikipedia.org/wiki/Vida_artificial http://inteligenciaartificialudb.blogspot.com/2008/01/concepto-

caractersticas-y-metodologas.html http://www.secyt.frba.utn.edu.ar/gia/inteligencia_artificial.htm http://es.wikipedia.org/wiki/Teor%C3%ADa_de_la_decisi%C3%B3n http://es.wikipedia.org/wiki/Teor%C3%ADa_de_juegos http://es.wikipedia.org/wiki/Teor%C3%ADa_del_caos http://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing http://www.sinewton.org/numeros/numeros/43-44/Articulo33.pdf “Aplicación de Autómatas Celulares a Simulación Básica de Incendios

Forestales”. Peredo Marco, Ramallo Ramiro, Universidad Católica Boliviana San Pablo, Cochabamba, Bolivia.

http://cala.unex.es/cala/epistemowikia/index.php?title=Aut%C3%B3matas_celulares._El_juego_de_la_vida#Aut.C3.B3matas_y_computabilidad

http://www.enelnombredetux.com/project.php?project=autcel http://es.wikipedia.org/wiki/Aut%C3%B3mata_celular http://semana.mat.uson.mx/MemoriasXVII/XII/Espinoza%20Aurora.pdf http://pageperso.lif.univ-mrs.fr/~pierre-etienne.meunier/

es.cellular_automata.html http://cala.unex.es/cala/epistemowikia/index.php?title=Aut

%C3%B3matas_celulares_elementales http://www.redcientifica.com/gaia/ac/auto_c.htm http://andres-sistemasia.blogspot.com/

Autómatas Celulares Página 40

“Simulación de Sistemas Naturales usando Autómatas Celulares”. Tesis, Ing. Huerta, Iliac. Instituto Politécnico Nacional, Centro de Investigación en Computación. Diciembre, 2009.

"Introducción a la Vida Artificial y Autómatas Celulares". López Ana. Departamento de Aplicación de Microcomputadoras. Instituto de Ciencias. Universidad Autónoma de Puebla. Agosto, 2011.

"Aplicación de los Autómatas Celulares a la generación de bits". Hernández L., et.al. Dpt. Tratamiento de la Información y Codificación, Instituto de Física Aplicada. Dpto. Matemática Aplicada, Universidad de Salamanca.

"Introducción a la Simulación de Procesos con Autómata Celular". Juárez Genaro. Dprt. de Posgrado, Escuela Superior de Computo. Instituto Politécnico Nacional. México DF. Agosto-Octubre, 2006.

"Autómatas Celulares". Suárez Mariano. Dpt. de Matemática, Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires. Argentina. Abril, 2011.

"Modelos de Computación inspirados en Biología". Ortega, Alfonso, et.al. http://personal.us.es/garcia/page3/page2/page2.html http://www.virtual.unal.edu.co/cursos/ciencias/2001018/lecciones/

Cap6s8.pdf http://es.wikipedia.org/wiki/Física_computacional http://es.wikipedia.org/wiki/Computación_paralela http://www.uv.mx/personal/ocastillo/files/2011/04/Recursividad.pdf http://es.wikipedia.org/wiki/Iteración http://es.wikipedia.org/wiki/Bucle_(programación) http://www.wordreference.com/definicion/bucle http://www.slideshare.net/ticdevirginia/neumann-y-el-computador-edvac http://es.wikipedia.org/wiki/Retículo_(matemáticas) http://www.alegsa.com.ar/Dic/encriptacion.php http://es.wikipedia.org/wiki/Tupla http://www.chw.net/2010/09/158-eniac-la-primera-computadora-electronica-

programable/ http://es.wikipedia.org/wiki/Percolación http://sierpinski-vc.blogspot.com/ http://es.wikipedia.org/wiki/Disyunci%C3%B3n_exclusiva http://enciclopedia_universal.esacademic.com/45854/M

%C3%A1quina_de_Post http://es.wikipedia.org/wiki/Anidamiento_(inform%C3%A1tica) http://es.thefreedictionary.com/estoc%C3%A1stico http://lema.rae.es/drae/srv/search?id=U8GTxIJeqDXX2ueOM42t http://foro.migui.com/vb/showthread.php/3350-Definici%C3%B3n-de-

discretizar

Autómatas Celulares Página 41

http://es.wikipedia.org/wiki/Lisp https://es.answers.yahoo.com/question/index?

qid=20080905175025AAHQ7oW http://ingeniatic.net/index.php/tecnologias/item/403-circuito-integrado

Autómatas Celulares Página 42

7. RESUMEN

Autómatas Celulares Página 43

Autómatas Celulares

Breve historia

Stanislav Ulam

Método de Montecarlo

John von Neumann

Theory of Self-

Reproducing Automata

Componentes

Rejilla o Cuadrícula Célula Frontera Vecinda

dFunción de Transición

toma los valores

de la célula y

los vecinos

Tipos

Clase I

Evoluciona a una

configuración estable y

honogénea

Clase II

Conjunto de

estrucras simples que

son periódicas

Clase III

Patrón caótico

Clase IV

Estructuras aisladas con

comportamiento complejo

Aplicaciones

Predictor del flujo de tráfico

Simulan el comportamiento de particulas de

materia y antimateria que

se aniquilan

Modelado de evolución de células o virus como el VIH

Estudio de campos

estadísticos

Un modelo matemático para un

sistema dinámico que evoluciona en pasos

discretos