Automatas

Tema: Autómatas Celulares y Computación Emergente

La universalidad de Autómatas Celulares Primaria

Mateo Cook,

Sistemas Complejos, vol. 15 (1), 2004, pp 1-40.

Este resultado fue descrito por primera vez en A New Kind of Science, Wolfram Media, 2002.

Una diversa exposición de la prueba, junto con los detalles de cómo la construcción puede trabajar en tiempo polinomial usando resultados de Neary & Woods, fue publicado más tarde en una vista concreta del artículo 110 del Reglamento Computación , CSP 2008, pp 31-55 .

Contenido:

En este trabajo pruebo una conjetura desde hace mucho tiempo (desde 1985) de Wolfram, que uno de los autómatas celulares más simple posible (número 110) es capaz de computación universal. La prueba consiste en una construcción larga y compleja. Esta construcción produce significativamente menor máquinas de Turing universales que se conocían anteriormente.

Impacto:

Numerosos comentarios han discutido mi prueba, incluyendo:

Naturaleza (Jim Giles, vol 417, 216-218, 16 de mayo de 2002.): "De especial interés"

Science (Melanie Mitchell, vol 298 (5591), 65-68, 04 de octubre 2002.): "Un resultado impresionante"

Información y Computación Cuántica (Scott Aaronson, vol 2 (5), 410-423, 2002.): "Una construcción notable"

Este trabajo también se ha referido en un comic (que muestra una parte de la construcción donde un poco se va a leer) y un rap .

Patrones Circuito autoensambladas

Mateo Cook, Paul WK Rothemund y Erik Winfree

ADN Computers 9, LNCS vol. 2943, 2004, pp 91-107 .

Contenido:

En este trabajo se muestra cómo varios circuitos digitales comunes (incluyendo demultiplexores, memoria de acceso aleatorio, y se transforma Walsh) se pueden construir de manera ascendente con una forma de auto-ensamblaje inspiración biológica. En este trabajo se resuelve una apuesta entre yo y Paul Rothemund, en la que afirmó que le parecía imposible que un autómata celular fijo para crear un patrón arbitrariamente grande Walsh Transformar la matriz, mientras que afirmé que debe ser posible. En este trabajo me doy una construcción para un autómata tales celular.

Impacto:

La principal referencia en los circuitos auto-ensambladas, este trabajo se convirtió en lectura obligatoria en los cursos de computación química, como por Goel en Stanford y por Savage en Brown.

La combinación de reparación automática y corrección de auto-ensamblaje

David Soloveichik, Matthew Cook, y Erik Winfree

Computación Natural, vol. 7 (2), 2008, pp 203-218 .

Contenido:

Este artículo presenta una construcción detallada para la conversión de cualquier cerámica algorítmica dirigido establecer en un conjunto de baldosas que hace que el mismo patrón en una escala más grande, pero al mismo tiempo es resistente tanto a la eliminación por mayor de azulejos y para la incorporación de azulejos incorrectos.

Impacto:

El trabajo previo mostró la posibilidad de robustez con respecto a los errores de acreción, y con respecto a las grandes pinchazos, pero diferentes construcciones y diferentes argumentos se había utilizado en los dos casos, dejando investigadores seguro de si los dos tipos de corrección de errores se podrían combinar. Esta papel resuelve este dilema de manera afirmativa.

1 Temperatura de auto-ensamblaje: conjunto determinista en el montaje de 3D y probabilística en 2d

Mateo Cook, Yunhui Fu y Robert T. Schweller

SODA (SIAM Simposio sobre algoritmos discretos) 2011, la acción sigue en producción.

ArXiv 0912.0027, pp 1-40 .

Contenido:

Este artículo examina el auto-ensamblaje de las estructuras que crecen a "temperatura 1", lo que significa que no se necesita cooperatividad para la unión de elementos nuevos -. Si un partidos de bonos, la partícula puede pegar en este caso, es muy difícil combinar la información , y sin embargo, la combinación de la información es una parte necesaria de cualquier tipo de computación significativa. La única solución es el uso de la geometría de la misma como una forma de información de la estructura.

Impacto:

Temperatura 1 cristales, mientras que mucho más fácil crecer experimentalmente, han sido rechazados por los experimentadores, debido a la falta de métodos teóricos para conseguir que hagan algo interesante. En particular, cuando se limita al montaje determinista en el avión, hay un sistema de montaje de temperatura 1 ha sido se muestra la construcción de una forma con una complejidad azulejo más pequeño que el diámetro de la forma. Yendo a tres dimensiones (o conjunto probabilístico), este trabajo es el primero en presentar los resultados positivos que muestran las formas en que los sistemas de temperatura 1 pueden calcular las mismas cosas que 2 sistemas normales de temperatura.

Aún Teoría Vida

Mateo Cook,

En Nueva Construccion en autómatas celulares, Oxford University Press, 2003, pp 93-118 .

Contenido:

En este trabajo se desarrollo una nueva línea de investigación, en cuanto a la complejidad hora de decidir si un patrón de dos dimensiones satisface una de las definiciones más básicas relativas a las formaciones en "Juego de la Vida" de Conway, el de ser un "Still Life" (una sola objeto estable). Entre otros hallazgos, que presenta un algoritmo de tiempo cuadrático para este problema, que se había asumido previamente para requerir tiempo exponencial.

Impacto:

El problema para el que me encontré con un algoritmo de tiempo cuadrática es aquella para la que mucha gente había escrito anteriormente código tomar tiempo exponencial de resolver. fui invitado a presentar este trabajo en la combinatoria Game Workshop MSRI Teoría de la Investigación, Berkeley, 2000.

Tema: Combinatoria

Intercalado óptima de Tori

Andrew Jiang, Matthew Cook, y Jehoshua Bruck

SIAM Journal on Matemática Discreta, vol. 20 (4), 2006, pp 841-879 .

Versión de la conferencia apareció como óptimo t-Intercalado de Tori en

IEEE Simposio Internacional sobre Teoría de la Información 2004 (ISIT '04), p. 22 .

Original del informe técnico: Caltech Paradise ETR 059, 14 de abril de 2004, pp 1-40 .

Contenido:

En este trabajo se presenta una construcción complicada para la coloración óptima ningún suficientemente grande rejilla toroidal para que cualquiera de los dos sitios del mismo color por lo menos t pasos el uno del otro. (Esta generalización de la coloración de grafos regulares se llama 'entrelazado'.)

...