Problema de sincronización del tirador

El problema de la sincronización de los tiradores es un problema del campo de la informática y de la teoría de los autómatas celulares .

Propuesto por primera vez por John Myhill en 1957 y publicado (con solución) en 1962 por Edward Moore [2] . El nombre está asociado con el comportamiento de los soldados durante la ejecución o un saludo de rifle : todos los soldados disparan al mismo tiempo en una señal.

Se formula de la siguiente manera: ¿es posible programar un autómata celular unidimensional de longitud finita de tal manera que desde el estado inicial G●●…●●● todas las células pasen simultáneamente al estado FFF…FFF, independientemente del longitud de la cadena, si la regla de transición ●●●→● es obligatoria y sus contrapartes para los extremos de la cadena ⌀●●→●, ●●⌀→●? En lenguaje sencillo [3] :

$n \geqslant 2$ los robots ( autómatas finitos ) con pistolas hacen cola. Los autómatas tienen al menos tres estados ●, G y F: "inicial", "comandante" y "disparo". Además de estos tres, puede agregar tantos estados intermedios como desee.
Los robots actúan de forma independiente según un programa y se comunican solo en cadena: según las señales del tambor (sincronizador), según su estado en ese momento y el estado de dos vecinos, pasan a un nuevo estado. La excepción son los robots extremos, que solo tienen un vecino; tienen sus propios programas. ${\ estilo de visualización t-1}$
Los tres programas, si el robot y sus vecinos están en el estado inicial, no deberían hacer nada.
Todos los robots permanecen en su estado original y no hacen nada. En el momento de la extrema izquierda, se trasladan al estado de "comandante". $t=0$
¿Existen esos tres programas (un conjunto de estados y tres conjuntos de reglas de transición, para el comandante, el remolque y otros robots) que en cualquier momento simultáneamente (en un golpe de tambor) pasan al estado de "disparo"? $norte$

Dado que la señal se propaga a lo largo de la línea a una velocidad de 1 posición por reloj (en la teoría de los autómatas celulares, esto se denomina "velocidad de la luz"), es obvio que el tiempo de sincronización aumentará con el aumento de . $norte$

Historia

problema matematico abierto

¿Existe una solución al problema de la sincronización de flechas en cinco estados, para cualquiera , no necesariamente óptimo en el tiempo? $norte$

La primera solución a este problema fue encontrada por John McCarthy y Marvin Minsky y publicada en Sequential Machines por Edward Moore.

En 1962, el profesor Eiichi Goto del MIT [4] encontró una solución que requería un tiempo mínimo . Utiliza varios miles de estados y requiere exactamente unidades de tiempo para los robots. Es fácil probar (ver más abajo) que no hay soluciones más eficientes en el tiempo. ${\ estilo de visualización 2n-2}$ $norte$

La solución óptima, utilizando solo seis estados (incluido el "disparo" final), fue encontrada por Jacques Mazoyer en 1987 [5] . Anteriormente, Robert Balzer demostró mediante enumeración por computadora que no hay soluciones con cuatro estados de celda [6] . Peter Sanders luego descubrió que el procedimiento de búsqueda de Balzer estaba incompleto, pero después de corregir el procedimiento, obtuvo el mismo resultado. En la década de 2010 , se obtuvieron cientos de soluciones diferentes con seis estados mediante enumeración evolutiva [7] . Todavía se desconoce si hay una solución con cinco estados de celda.

También intentan batir el récord de la cantidad de reglas de transición involucradas (incluida la regla requerida pero no utilizada para el comandante ⌀●●→● [7] . Hay 119 reglas en la solución de Mazoyer. Hay una regla no óptima en el tiempo solución con seis estados y 78 reglas, y la óptima es a partir del 80.

Encuentre soluciones incompletas con cuatro estados, por ejemplo, sincronizando una línea de robots [1] . $2^{m}$

La solución más simple

La solución más simple al problema describe dos ondas de estados que se propagan a lo largo de una línea de robots, uno de los cuales se mueve tres veces más rápido que el otro. La onda rápida se refleja desde el borde más alejado de la fila y se encuentra con la onda lenta en el centro. Después de eso, dos ondas se dividen en cuatro, moviéndose en diferentes direcciones desde el centro. El proceso continúa, duplicando cada vez el número de ondas, hasta que la longitud de los segmentos de la fila sea igual a 1. En este momento, todos los robots disparan. Esta decisión requiere unidades de tiempo para los soldados. $3n$ $norte$

Solución que requiere un tiempo mínimo

Aquí se describe una solución bastante simple de 16 estados descrita por Abraham Waksman en 1966 [8] . El comandante envía señales con frecuencias al robot adyacente . La señal rebota en el extremo derecho de la fila y encuentra la señal (para ) en la celda . Cuando rebota, también crea un nuevo comandante en el extremo derecho. $S_{1},~~S_{2},~~S_{3}~~\puntos ~~S_{i}\puntos$ $1,~{\frac {1}{3)),~{\frac {1}{7)),~\puntos ~{\frac {1}{2^{i-1}-1} }\puntos$ $S_{1}$ $Si}$ $i\geq 2$ ${\ estilo de visualización n/2^{i-1}.}$ $S_{1}$

Las señales se generan utilizando señales auxiliares que se propagan hacia la izquierda. Cada segundo momento de tiempo, la señal normal genera una señal auxiliar que se propaga hacia la izquierda. se mueve de forma independiente a la velocidad 1, mientras que las señales más lentas se mueven solo cuando reciben señales auxiliares. $Si}$ $S_{1}$

Prueba de tiempo mínimo

Si entre el comandante (iniciador del tiro) y el extremo más cercano de los robots, la sincronización requiere al menos pasos [9] . $k$ ${\ estilo de visualización 2n-2-k}$

Un caso especial: si el comandante está al límite, entonces da un paso. ${\ estilo de visualización 2n-2}$

Prueba. Digamos que hay tres programas que resuelven el problema de sincronización, y para algunos , y serán capaces de disparar . Creemos que el comandante está más cerca del extremo izquierdo. $norte$ $k$ ${\ estilo de visualización t <2n-2-k}$

Cualquier señal viaja de robot a robot no más rápido que la llamada "velocidad de la luz": 1 posición por paso de tiempo. Las acciones del primer robot en este momento dependen de los dos primeros robots en este momento , de los tres primeros en este momento , …, de todos los robots en este momento . En este momento, el último robot todavía está en su estado inicial (la señal llega en el momento ). $t$ ${\ estilo de visualización t-1}$ ${\ estilo de visualización t-2}$ $norte$ $t_{1}=t-(n-1)\leqslant n-2-k$ ${\ estilo de visualización n-1-k}$

Esto significa que si agregamos los robots más al extremo derecho , en este momento el estado de los primeros robots será el mismo, nada cambiará para el primer robot y disparará en el mismo paso . El último th del paso permanecerá en su estado original: la señal no tendrá tiempo de alcanzarlo. Así que este trío de programas no es una solución. Contradicción. ${\ estilo de visualización (n + 2)}$ $t_{1}$ $norte$ $t$ ${\ estilo de visualización (2n+2)}$ $t$

El otro límite inferior, pasos, se prueba de la misma manera , pero el número no es menor. ${\ estilo de visualización n-1 + k}$ ${\ estilo de visualización 2n-2-k}$

Nota. Los requisitos adicionales en y , si no están limitados desde arriba, pueden dar una ganancia en el número de estados, pero no en el tiempo y, de hecho, existe una generalización de la solución de 17 estados de Waksman que funciona para cualquiera y para los pasos [10] . $norte$ $k$ $norte$ $norte$ $k$ ${\ estilo de visualización 2n-2-k}$

Generalizaciones

Se han propuesto y estudiado varias formulaciones más generales del problema, incluidas series ordenadas arbitrariamente, anillos cerrados, cuadrados, cubos, gráficos de Cayley y gráficos generales.

Si el conocimiento de que el comandante está en el borde de la formación lineal no logra ganar en el tiempo de sincronización, entonces en la formación bidimensional del conocimiento de que él es cuadrado, habrá una ganancia [11] .

Se pudo encontrar la existencia de una solución para un sistema lineal, si cada robot debe dar una señal de relojes antes del disparo, el robot conoce el máximo y el suyo propio , y se programa en consecuencia [12] . La solución más sencilla es dar a los robots estados adicionales y el mismo número de ciclos para sincronizar, pero puede prescindir de este retraso si la formación es lo suficientemente larga. La complejidad de cada programa individual (de hecho, recuerda el estado del robot de la tarea clásica). ${\ estilo de visualización \ tau _ {i}}$ ${\ estilo de visualización \ tau _ {i}}$ ${\ estilo de visualización \ max \ tau _ {i}}$ $a^{2\max \tau _{i}+1}$ $2\max \tau _{i}+1$

El tiempo de sincronización mínimo exacto en diferentes escalas
(se encontró una solución y se demostró que no podía ser más rápido)

Forma de acción	tiempo minimo
Línea, entre el comandante y el borde cercano de los robots $k$	${\ estilo de visualización 2n-2-k}$ [9]
Anillo	$n-1$ [9]
Anillo con propagación de información unidireccional	$2n-2$ [9]
Kare con el comandante en la esquina $m\veces n$	$m+n+\operatorname {máx} \{m,n\}-3$ [once]
Plaza con el comandante en la esquina $n\veces n$	${\ estilo de visualización 2n-2}$ [once]
Cubo con un comandante en la parte superior ${\ estilo de visualización n \ veces n \ veces n}$	${\ estilo de visualización 3n-3}$ [once]

Notas

↑ 1 2 https://www.researchgate.net/publication/220977377_About_4-States_Solutions_to_the_Firing_Squad_Synchronization_Problem
↑ FR Moore, GG Langdon, Un problema generalizado del pelotón de fusilamiento . Información y Control, Volumen 12, Número 3, marzo de 1968, páginas 212-220. DOI
↑ [Confetti] Problema de sincronización de Firing Squad - YouTube
↑ Ir a E. Una solución de tiempo mínimo del problema del pelotón de fusilamiento. Notas de curso resumidas para Matemáticas aplicadas, vol.298, pp.52-59. Universidad de Harvard, Cambridge (1962)
↑ Jacques Mazoyer, Una solución de tiempo mínimo de seis estados para el problema de sincronización del pelotón de fusilamiento . Informática Teórica, 1987, vol. 50 págs. 183-238 DOI
↑ Robert Balzer, Una solución de tiempo mínimo de 8 estados para el problema de sincronización del pelotón de fusilamiento . Información y Control, 1967, vol.10, pp.22-42 DOI
↑ 1 2 Accueil - Archivo abierto HAL
↑ Abraham Waksman, Una solución óptima al problema de sincronización del pelotón de fusilamiento . Información y Control, 1966, vol.9, pp.66-78 DOI
↑ 1 2 3 4 El problema del pelotón de fusilamiento
↑ https://www.sciencedirect.com/science/article/pii/S0019995868903094
↑ 1 2 3 4 Shinahr, Ilka. Problema de sincronización bidimensional y tridimensional del pelotón de fusilamiento // Información y Control : diario. - Prensa Académica, 1974. - Vol. 24 . - pág. 163-180 . - doi : 10.1016/S0019-9958(74)80055-0 .
↑ V. I. Varshavsky, V. B. Marakhovsky, V. A. Peschansky, “Algunas variantes del problema de la sincronización de cadenas de autómatas”, Probl. peredachi inform., 4:3 (1968), 73-83; Problemas Informar….

Literatura

Shinahr, Ilka. Problema de sincronización bidimensional y tridimensional del pelotón de fusilamiento // Información y Control : diario. - Prensa Académica, 1974. - Vol. 24 . - pág. 163-180 . - doi : 10.1016/S0019-9958(74)80055-0 .

Enlaces

El juego de la vida de Conway y otros autómatas celulares

Clases de configuración

Configuraciones

Planeador
Bloquear
R-pentominó
Pentadecatlón

Términos

Otras naves espaciales en una
red bidimensional

Natural	Día y noche Vida sin muerte buena vida semillas
Otro	modelo de pila de arena Fusil de asalto Von Neumann Mundo de alambre Hormiga Langton Criaturas Gusanos de Paterson

Nave espacial unidimensional

Software y algoritmos

Caramba
Celebración de
hashlife

investigadores de ka