Sobre los autómatas celulares

Los autómatas celulares son modelos matemáticos que han tenido gran relevancia en numerosas áreas de la ciencia. Se tratan de modelos discretos en el sentido de que el espacio donde existen no varía continuamente: sus componentes están separados y son distintos entre sí. Su objetivo principal es capturar las propiedades fundamentales de algunos fenómenos del mundo físico: sus interacciones son locales y homogéneas en todo el espacio.

Inicialmente, los autómatas celulares fueron estudiados por John von Neumann, uno de los padres de las computadoras digitales, en un intento por diseñar sistemas artificiales autorreplicables. La idea de von Neumann estuvo motivada por el propósito de construir robots que pudieran copiarse a sí mismos.

Informalmente, la definición matemática de autómata celular es la siguiente.

Supongamos que G es una cuadrícula infinita en n dimensiones y que A es un conjunto de colores, o estados. A cada elemento de la cuadrícula lo llamamos una célula. Una configuración sobre G y A es una coloración de usando los colores de A. Por ejemplo, una configuración sobre la cuadrícula bidimensional y A = {rojo, verde, azul} es:

infinite grid colored 1

Una vez que fijamos la cuadrícula G y el conjunto A de colores/estados, denotamos como AG al conjunto de todas las configuraciones posibles sobre G y A. Un autómata celular es una función F : AG → AG  que satisface la siguiente propiedad:

⋆ Para cualquier configuración c, el color de cualquier célula en F(c) está establecido por una regla fija que sólo depende de los colores de una vecindad finita de la célula.

Esta propiedad es la que determina el comportamiento local y homogéneo de los autómatas celulares.

Algunos de los ejemplos más importantes de autómatas celulares son la Regla 110 y el Juego de la Vida de John H. Conway (explicado en este video en español por Eduardo Sáenz de Cabezón, y en este otro en inglés por el mismo Conway).

Los autómatas celulares tienen muchas conexiones interesantes con otras áreas de la ciencia. Aquí una lista de cinco de estas conexiones:


1. Sistemas dinámicos: los autómatas celulares han sido extensamente investigados como sistemas dinámicos discretos, donde el sistema evoluciona al iterar la función F : AG → AG. Por ejemplo, la siguiente animación ilustra la evolución de una configuración al iterar el Juego de la Vida:

Game_of_life_pulsar

Los puntos fijos, la periodicidad y la estabilidad de estas órbitas han sido temas centrales en estas investigaciones.


2. Física digital: algunos científicos han propuesto que las leyes físicas del universo podrían comportarse como un autómata celular. Esto podría resultar razonable en un modelo discreto del universo, ya que se cree que las mismas leyes físicas se aplican en cualquier punto del universo (excepto en las singularidades de los agujeros negros) y que estas leyes sólo dependen de una vecindad finita del punto. En esta plática de Ted, Stephen Wolfram habla sobre su exploración del universo computacional de los autómatas con la esperanza de encontrar un modelo del universo físico.


3. Teoría de la computación: algunos autómatas celulares, como la Regla 110 y el Juego de la Vida, pueden simular cualquier máquina de Turing. De acuerdo con la tesis de Church-Turing, esto significa que estos autómatas celulares tienen la capacidad de hacer los mismos cálculos que cualquier computadora programable. Este video muestra cómo es posible implementar una máquina de Turing universal usando el Juego de la Vida.


4. Teoría de grupos: la cuadrícula G de un autómata celular puede reemplazarse por cualquier grupo; esto es, por cualquier conjunto equipado con una operación binaria asociativa, con identidad y con inversos. Esta generalización proporciona conexiones muy interesantes entre la teoría de autómatas celulares y la teoría de grupos. Por ejemplo, existe una caracterización en términos de autómatas celulares de los grupos amenables, los cuales, coincidentemente, también fueron definidos por John von Neumann pero en un contexto totalmente diferente: surgieron en el estudio de descomposiciones paradójicas de grupos, al estilo del Teorema de Banach-Tarski.


5. Biología y química: los autómatas celulares pueden simular diversos procesos biológicos y químicos que involucran interacciones entre neuronas, células y moléculas. Un ejemplo famoso es el de las configuraciones producidas por la Regla 30, descubierta por Stephen Wolfram, ya que son muy similares a los patrones encontrados en las conchas de algunos caracoles.


3er Foro de Laureados en Heidelberg

IMG_0405IMG_0433


La semana pasada tuve la fortuna de participar en el 3er Foro de Laureados en Heidelberg, organizado en la Universidad de Heidelberg, Alemania. La idea de este foro, inspirado en el famoso Encuentro de Premios Nobel en Lindau, es que 200 jóvenes investigadores convivan y conversen con algunos académicos galardonados con los premios más prestigiosos en matemáticas y ciencias computacionales: el Premio Turing, la Medalla Fields y el Premio Abel.

Los laureados que participaron en el foro al que yo asistí fueron:

  • 17 con el Premio Turing:
    1. Leslie Lamport (2013), galardonado “por sus contribuciones fundamentales a la teoría y práctica de sistemas distribuidos y concurrentes.”
    2. Leslie G. Valiant (2010), galardonado “por sus contribuciones transformadoras a la teoría de la computación, incluyendo […] la teoría de la computación paralela y distribuida.”
    3. Edmund Melson Clarke (2007), galardonado “por su papel en el desarrollo de la verificación formal para convertirla en una técnica de verificación tecnológica altamente efectiva que ha sido ampliamente adoptada en las industrias de software y hardware.”
    4. Peter Naur (2005), galardonado “por sus contribuciones fundamentales al diseño de lenguajes de programación y la definición de Algol 60.
    5. Vinton Gray Cerf (2004), galardonado “por su trabajo pionero en el desarrollo del Internet, incluyendo el diseño e implementación de los protocolos básicos de comunicación, TCP/IP, y por su inspirado liderazgo en redes.”
    6. Leonard Max Adleman (2002), galardonado “por la implementación práctica de la encriptación de llave pública” (ej. el código RSA).
    7. Andrew C. Yao (2000), galardonado “en reconocimiento por sus contribuciones fundamentales a la teoría de la computación.”
    8. Frederick Brooks (1999), galardonado “por sus contribuciones clave a la arquitectura de computadoras, sistemas operativos e ingeniería de software.”
    9. Manuel Blum (1995), galardonado “en reconocimiento por sus contribuciones a los fundamentos de la teoría de la complejidad computacional y sus aplicaciones en criptografía y verificación formal.”
    10. Richard Edwin Stearns (1993), galardonado “en reconocimiento por su artículo pionero en el cual estableció los fundamentos de la teoría de la complejidad computacional.”
    11. Butler W. Lampson (1992), galardonado “por sus contribuciones al desarrollo de ambientes computacionales distribuidos y personales, y por la tecnología de su implementación.”
    12. Ivan Sutherland (1988), galardonado “por sus contribuciones pioneras y visionarias a los gráficos por computadora.”
    13. Robert Endre Tarjan y John E. Hopcroft (1986), galardonados “por sus logros fundamentales en el diseño y análisis de algoritmos y estructuras de datos.”
    14. Richard Manning Karp (1985), galardonado “por sus contribuciones continuas a la teoría de algoritmos, […] notablemente, sus contribuciones a la teoría de NP-completitud.”
    15. Stephen A. Cook (1982), galardonado “por su profunda y significativa contribución a nuestro entendimiento de la complejidad computacional.”
    16. Sir Antony R. Hoare (1980), galardonado “por sus logros fundamentales en la definición y el desarrollo de la programación.”
  • 4 con la Medalla Fields:
    1. Andrei Okounkov (2006), galardonado “por sus contribuciones que conectan la probabilidad, la teoría de representaciones y la geometría algebraica.”
    2. Vladimir Voevodsky (2002), galardonado “especialmente por su trabajo en cohomología motívica, la teoría homotópica de variedades algebraicas y su demostración de la conjetura de Milnor.”
    3. Efim Zelmanov (1994), galardonado “por su trabajo en álgebra abstracta y teoría de grupos, en particular por la solución del problema de Burnside restringido.”
    4. Shigefumi Mori (1990), galardonado “por la demostración de la conjetura de Hartshorne y su trabajo en la clasificación de variedades algebraicas tridimensionales.”
  • 4 con el Premio Abel:
    1. Louis Nirenberg (2015), galardonado “por sus contribuciones pioneras a la teoría de ecuaciones diferenciales parciales no lineales y sus aplicaciones al análisis geométrico.”
    2. Endre Szemerédi (2012), galardonado “por sus contribuciones fundamentales en matemáticas discretas y ciencias computacionales teóricas, y en reconocimiento por el impacto profundo y duradero de esas contribuciones a la teoría aditiva de números y la teoría ergódica.”
    3. John Torrence Tate (2010), galardonado “por su impacto vasto y duradero a la teoría de números.”
    4. Srinivasa S. R. Varadhan (2007), galardonado “por sus contribuciones fundamentales a la teoría de la probabilidad y, en particular, por crear una teoría unificada de grandes desviaciones.”
  • 1 con la Medalla Fields y el Premio Abel:
    1. Sir Michael Francis Atiyah (1966/2004), galardonado “particularmente por su trabajo en topología algebraica, incluyendo la demostración del teorema del índice de Atiyah-Singer.”

Además de poder escuchar algunas conferencias brillantes impartidas por los laureados, este foro es una excelente oportunidad para conocer a otros jóvenes investigadores de todo el mundo, aprender sobre nuevas áreas de investigación y descubrir una hermosa ciudad. No deja de sorprenderme la sencillez y el genuino interés de los laureados hacia los proyectos de los jóvenes investigadores; siempre estuvieron dispuestos a preguntar y escuchar. Los organizadores del evento hicieron un trabajo impecable: se nota claramente su entusiasmo y su gran esfuerzo para hacer de este foro una experiencia memorable.

El próximo Foro de Laureados en Heidelberg será del 18 al 23 de septiembre de 2016. Pueden hacer solicitud para participar matemáticos o científicos de la computación en cualquier nivel desde licenciatura hasta postdoctorado.