computación amorfa

La computación amorfa se refiere a sistemas computacionales que utilizan un gran número de procesadores paralelos idénticos, cada uno con capacidad computacional limitada e interacciones locales. El término computación amorfa fue acuñado en el MIT en 1996 en un artículo titulado "Manifiesto de la Computación Amorfa" por Abelson, Knight, Sussman y otros.

Ejemplos de computación amorfa que ocurren naturalmente se pueden encontrar en muchos campos, como la biología del desarrollo (el desarrollo de organismos multicelulares a partir de una sola célula), la biología molecular (la organización de compartimentos subcelulares y la señalización intracelular), las redes neuronales y la ingeniería química (sistemas fuera del equilibrio). El estudio de la computación amorfa es independiente del hardware ; no se ocupa del sustrato físico (biológico, electrónico, nanotecnológico, etc.), sino de la caracterización de algoritmos amorfos como abstracciones con el objetivo de comprender los ejemplos naturales existentes y diseñar sistemas novedosos. En última instancia, este campo se extiende a la Inteligencia Computacional , ya que esta técnica computacional es una extensión de la Inteligencia Artificial (más específicamente de la Inteligencia Artificial General ) para el desarrollo de la Computación Biológica .

Las computadoras amorfas tienden a tener muchas de las siguientes propiedades:

• Implementado mediante dispositivos redundantes, potencialmente defectuosos y de procesamiento masivamente paralelo .
• Dispositivos con memoria y capacidad de procesamiento limitadas.
• Los dispositivos son asíncronos.
• Dispositivos que no tienen conocimiento previo de su ubicación.
• Dispositivos que se comunican únicamente de forma local.
• Exhiben un comportamiento emergente o autoorganizado (patrones o estados mayores que los de un dispositivo individual).
• Tolerante a fallos, especialmente ante dispositivos defectuosos o perturbaciones de estado ocasionales.

(Algunos de estos algoritmos no tienen nombres conocidos. Cuando se desconoce un nombre, se proporciona uno descriptivo).

• Comunicación fickiana . Los dispositivos se comunican generando mensajes que se difunden a través del medio en el que se encuentran. La intensidad del mensaje sigue la ley del cuadrado inverso, tal como la describe la ley de difusión de Fick . Ejemplos de este tipo de comunicación son comunes en sistemas biológicos y químicos.
• Comunicación por difusión de enlaces . Los dispositivos se comunican propagando mensajes a través de enlaces cableados entre ellos. A diferencia de la comunicación fickiana, no existe necesariamente un medio difusivo en el que se encuentren los dispositivos, por lo que la dimensión espacial es irrelevante y la ley de Fick no es aplicable. Ejemplos de esto se encuentran en algoritmos de enrutamiento de Internet, como el algoritmo de actualización por difusión . La mayoría de los algoritmos descritos en la literatura sobre computación amorfa asumen este tipo de comunicación.
• Propagación de ondas (Ref. 1). Un dispositivo emite un mensaje con un contador de saltos codificado. Los dispositivos que no hayan visto el mensaje previamente incrementan el contador de saltos y lo retransmiten. Una onda se propaga a través del medio y el contador de saltos a través de este codifica, en efecto, un gradiente de distancia desde la fuente.
• "ID aleatorio" . Cada dispositivo se asigna un ID aleatorio, cuyo espacio aleatorio es lo suficientemente grande como para evitar duplicados.
• "Programa de puntos de crecimiento" . (Coore). Procesos que se mueven entre dispositivos según el "tropismo" (movimiento de un organismo debido a estímulos externos).
• "Coordenadas de onda" . Diapositivas de DARPA PPT . Pendiente de redacción.
• "Consulta de vecindario" . (Nagpal) Un dispositivo muestrea el estado de sus vecinos mediante un mecanismo de empuje o de atracción.
• «Presión de grupo» . Cada dispositivo mantiene un estado y lo comunica a sus vecinos. Cada dispositivo utiliza un sistema de votación para determinar si cambia o no de estado al de su vecino. El algoritmo divide el espacio según las distribuciones iniciales y es un ejemplo de algoritmo de agrupamiento.
• Línea autosostenible ( Lauren Lauren, Clement ). Se crea un gradiente desde un extremo de un plano cubierto de dispositivos mediante comunicación difusiva de enlace. Cada dispositivo conoce su valor en el gradiente y la identificación de su vecino más cercano al origen del mismo. El extremo opuesto detecta el gradiente e informa a su vecino más cercano que forma parte de una línea. Esta información se propaga a lo largo del gradiente, formando una línea robusta frente a perturbaciones en el campo. (Se necesita ilustración).
• "Formación de clubes" . ( Coore, Coore, Nagpal, Weiss ). Grupos locales de procesadores eligen un líder que actúa como centro de comunicación local.
• "Formación de coordenadas" ( Nagpal ). Se forman y utilizan múltiples gradientes para crear un sistema de coordenadas mediante triangulación.

• Hal Abelson , MIT
• Jacob Beal , estudiante de posgrado del MIT (lenguajes de alto nivel para computación amorfa).
• Daniel Coore , Universidad de las Indias Occidentales (lenguaje de puntos de crecimiento, tropismo, serie inversora de crecimiento)
• Nikolaus Correll , Universidad de Colorado ( materiales robóticos )
• Tom Knight , MIT (computación con biología sintética )
• Radhika Nagpal , Harvard (sistemas autoorganizados)
• Zack Booth Simpson , Laboratorio Ellington, Universidad de Texas en Austin. (Detector de bordes bacterianos)
• Gerry Sussman , Laboratorio de IA del MIT
• Ron Weiss , MIT (activación de reglas, lenguaje de colonias microbianas, formación de patrones de E. coli)

• Computación no convencional

1. Página principal de Computación Amorfa

   Una colección de artículos y enlaces del laboratorio de IA del MIT.

2. Computación amorfa (Comunicaciones de la ACM, mayo de 2000)

   Un artículo de revisión que muestra ejemplos del lenguaje de puntos de crecimiento de Coore, así como patrones creados a partir del lenguaje de activación de reglas de Weiss.

3. "Computación amorfa en presencia de perturbaciones estocásticas"

   Un artículo que investiga la capacidad de las computadoras amorfas para lidiar con componentes defectuosos.

4. Diapositivas sobre computación amorfa de una charla de DARPA en 1998.

   Panorama general de ideas y propuestas para su implementación.

5. Presentación en PowerPoint sobre computación amorfa y celular de una conferencia de la NASA de 2002.

   Casi lo mismo que lo anterior, en formato PPT.

6. Infraestructura para la emergencia controlada en redes de sensores/actuadores , Beal y Bachrach, 2006.

   Un lenguaje informático amorfo llamado "Proto".

7. Patrones topológicos autorreparables Clement, Nagpal.

   Algoritmos para líneas de autorreparación y automantenimiento.

8. Métodos robustos de sincronización amorfa , Joshua Grochow

   Métodos para inducir la sincronización temporal global.

9. Autoensamblaje programable: Construcción de formas globales mediante interacciones locales de inspiración biológica y matemáticas del origami y diapositivas asociadas . Tesis doctoral de Nagpal.

   Un lenguaje para compilar instrucciones de interacción local a partir de una descripción de alto nivel de una estructura plegada similar al origami.

10. Hacia un material programable , diapositivas asociadas de Nagpal

    Esquema similar al del artículo anterior.

11. Estructuras autorreparables en computación amorfa Zucker

    Métodos para detectar y mantener topologías inspirados en la regeneración biológica.

12. Ejecución serial resiliente en máquinas amorfas , tesis de maestría de Sutherland

    Un lenguaje para ejecutar procesos en serie en computadoras amorfas.

13. Paradigmas para la estructura en una computadora amorfa , 1997 Coore, Nagpal, Weiss

    Técnicas para crear orden jerárquico en computadoras amorfas.

14. Organización de un sistema de coordenadas global a partir de información local en una computadora amorfa , 1999 Nagpal.

    Técnicas para la creación de sistemas de coordenadas mediante la formación de gradientes y análisis de los límites de precisión.

15. Computación amorfa: ejemplos, matemáticas y teoría , 2013 W Richard Stark.

    Este artículo presenta cerca de 20 ejemplos que varían de simples a complejos; se utilizan herramientas matemáticas estándar para demostrar teoremas y calcular el comportamiento esperado; se identifican y exploran cuatro estilos de programación; se demuestran tres resultados de incomputabilidad; y se esbozan los fundamentos computacionales de un sistema de inteligencia complejo y dinámico.