Regla 110: una de las reglas elementales del autómata celular introducida por Stephen Wolfram en 1983. Sorprendentemente, la regla 110 del autómata celular es universal. Los sistemas universales son efectivamente capaces de emular cualquier otro sistema.
Regla 30 : Otra de las reglas elementales del autómata celular introducida por Stephen Wolfram en 1983. La Regla 30 es de especial interés porque es caótica (871), con una columna central dada por 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1,… (OEIS A051023). De hecho, esta regla se usa como generador de números aleatorios para enteros grandes en Wolfram Language.
- A medida que comenzamos a planificar la próxima edición de Introducción a los algoritmos (CLRS), ¿qué debemos agregar y qué debemos eliminar si la cuarta edición no puede ser más grande que la tercera?
- ¿SDN ya está en uso en las redes actuales?
- Cómo alcanzar el nivel de matemáticas requerido para participar en el Concurso Internacional de Programación Colegiada
- ¿Por qué mi PC se congela al azar?
- ¿Cuál es el mejor kit de limpieza para computadora?
Juego de la vida : El juego de la vida es el autómata celular bidimensional más conocido, inventado por John H. Conway y popularizado en la columna Scientific American de Martin Gardner a partir de octubre de 1970. El juego de la vida se jugó originalmente (es decir, generaciones sucesivas se produjeron) a mano con contadores, pero la implementación en una computadora aumentó en gran medida la facilidad de explorar patrones. De hecho, dado que el juego de la vida incluye un patrón que es equivalente a una UTM (máquina universal de Turing), este algoritmo de “decisión”, si existiera, podría haberse utilizado para resolver el problema de detención, tomando el patrón inicial como el correspondiente a una entrada UTM + y el patrón posterior como el correspondiente a un estado de detención de la máquina con una cinta vacía (ya que se puede modificar la máquina Turing para borrar siempre la cinta antes de detenerse). Sin embargo, el problema de detención es demostrablemente indecidible y, por lo tanto, dicho algoritmo no existe.
WireWorld : descubrí una maravillosa maquinaria llamada WireWorld (enlace MathWorld). Es una CA simple propuesta por Brian Silverman en 1987 que puede simular todo tipo de circuitos eléctricos desde cables triviales hasta computadoras enteras. Lo más valioso es que es brutalmente simple. Imagina que tienes papel cuadriculado infinito. Las celdas vacías son ceros. Los cables (conductores) son 3s. Los electrones que se ejecutan en los cables están representados por 1 y 2, – 1 para la cabeza y 2 para la cola, por lo que sabemos la dirección donde se mueve el electrón. Estas son las reglas.
- Vacío → Vacío
- Cabeza de electrones → Cola de electrones
- Cola de electrones → Conductor
- Conductor → Cabezal de electrones si exactamente una o dos de las celdas vecinas son cabezas de electrones, o sigue siendo Conductor de lo contrario.
Ahora se sorprenderá: a pesar de esta simplicidad, WireWorld es Turing completo o computacionalmente universal.
