Firing squad synchronization problem (original) (raw)
The firing squad synchronization problem is a problem in computer science and cellular automata in which the goal is to design a cellular automaton that, starting with a single active cell, eventually reaches a state in which all cells are simultaneously active. It was first proposed by John Myhill in 1957 and published (with a solution by John McCarthy and Marvin Minsky) in 1962 by Edward F. Moore.
| Property | Value |
|---|---|
| dbo:abstract | The firing squad synchronization problem is a problem in computer science and cellular automata in which the goal is to design a cellular automaton that, starting with a single active cell, eventually reaches a state in which all cells are simultaneously active. It was first proposed by John Myhill in 1957 and published (with a solution by John McCarthy and Marvin Minsky) in 1962 by Edward F. Moore. (en) 一斉射撃問題（いっせいしゃげきもんだい）は、計算機科学とセル・オートマトンにおける数学パズル的な問題の一つである。この問題の目標は、一つのセルのみが活動している状態から始めて、最終的に全てのセルが同時に特定の状態に到達するように、セル・オートマトンを設計することである。 この問題は1957年にジョン・マイヒル（en:John Myhill）によって提案された。出版物としては、1964年に、エドワード・ムーア（en:Edward F. Moore）の編集による、この問題が解法とともに収録された文献集が出版されている。 (ja) Зада́ча синхрониза́ции стрелко́в — задача из области информатики и теории клеточных автоматов. Впервые предложенная Джоном Майхиллом в 1957 году и опубликованная (с решением) в 1962 году Эдвардом Муром. Название связано с поведением солдат при расстреле или ружейном салюте — все солдаты стреляют одновременно по сигналу. Формулируется следующим образом: можно ли так запрограммировать одномерный клеточный автомат конечной длины, чтобы из стартового состояния G●●…●●● все клетки одновременно перешли в состояние FFF…FFF, независимо от длины цепочки, если обязательно правило перехода ●●●→● и его аналоги для концов цепочки ⌀●●→●, ●●⌀→●? Простым языком: * роботов (конечных автоматов) с ружьями стоят шеренгой. У автоматов как минимум три состояния ●, G и F — «исходное», «командир» и «выстрел». Помимо этих трёх, можно добавить сколько угодно промежуточных состояний. * Роботы действуют независимо по одной программе и общаются только по цепочке: по сигналам барабана (синхронизатора) в зависимости от своего состояния в момент и состояния двух соседей переходят в новое состояние. Исключение — крайние роботы, у которых только один сосед; у них собственные программы. * Все три программы, если робот и его соседи в исходном состоянии, ничего не должны делать. * Все роботы стоят в исходном состоянии и ничего не делают. В момент крайнего левого переводят в состояние «командир». * Существуют ли такие три программы (набор состояний и три комплекта правил перехода — для командира, замыкающего и остальных роботов), чтобы при любом они одновременно (на одном ударе барабана) перешли в состояние «выстрел»? Поскольку сигнал распространяется по шеренге со скоростью 1 позиция за такт (в теории клеточных автоматов это называется «скорость света»), очевидно, время синхронизации будет возрастать с возрастанием . (ru) Problem synchronizacji plutonu egzekucyjnego – zagadnienie z zakresu informatyki, polegające na próbie konstrukcji takiego automatu komórkowego, który zaczynając od pojedynczej nieaktywnej komórki, osiągnie stan, w którym wszystkie komórki osiągną jednocześnie stan aktywności. Problem został sformułowany przez Johna Myhilla w 1957, a pierwsze jego rozwiązanie opublikował w 1962 r. Edward Moore. (pl) Задача синхронізації стрільців — завдання з області інформатики і клітинних автоматів, уперше запропонована Джоном Мейгіллом в 1957 році і опубліковане (з рішенням) в 1962 році Едвардом Муром. Формулюється таким чином: Розглянемо кінцеве, але довільне число кінцевих автоматів (стрільців), розташованих в ряд. У момент часу t = 0 кожен солдат перебуває у вихідному стані, за винятком найлівішого солдата (командира). Стан кожного солдата у момент часу t > 0 залежить від стану його самого і двох його сусідів у момент часу t − 1(за винятком самих крайніх солдатів, у яких лише один сусід). Якщо солдат і його сусіди знаходяться в початковому стані, то в цьому ж стані вони і залишаються в наступні моменти часу. Завдання полягає в тому, щоб знайти кінцевий набір станів і правил переходу між ними, які допускали б одночасний перехід усіх солдатів в необхідний стан (вогонь). (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/FiringSquadProblem.svg?width=300 |
| dbo:wikiPageExternalLink | https://web.csulb.edu/~dgoldst2/research/formulations.pdf https://www.youtube.com/watch%3Fv=9swgG1Nmurg |
| dbo:wikiPageID | 7247677 (xsd:integer) |
| dbo:wikiPageLength | 8400 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1124569630 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Mathematical_problems dbr:John_Myhill dbr:Edward_F._Moore dbr:Computer_science dbr:File:FSSP_1d1.svg dbr:Peter_Sanders_(computer_scientist) dbr:Theoretical_Computer_Science_(journal) dbr:Cellular_automaton dbr:Journal_of_the_ACM dbr:Prime_number dbc:Cellular_automata dbr:John_McCarthy_(computer_scientist) dbr:Marvin_Minsky dbr:Cellular_automata dbr:Finite_state_machines dbr:Firing_squad dbr:Information_and_Control dbr:File:FiringSquadProblem.svg |
| dbp:authorlink | Eiichi Goto (en) Patrick C. Fischer (en) |
| dbp:first | Patrick (en) Eiichi (en) |
| dbp:last | Fischer (en) Goto (en) |
| dbp:title | Firing Squad Problem (en) |
| dbp:urlname | FiringSquadProblem (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harv dbt:Harvtxt dbt:Math dbt:Mathworld dbt:Mvar dbt:Harvs |
| dbp:year | 1962 (xsd:integer) 1965 (xsd:integer) |
| dct:subject | dbc:Mathematical_problems dbc:Cellular_automata |
| gold:hypernym | dbr:Problem |
| rdf:type | yago:WikicatCellularAutomata yago:Anomaly109606527 yago:Automaton109825519 yago:CausalAgent100007347 yago:LivingThing100004258 yago:Object100002684 yago:Organism100004475 yago:Person100007846 yago:PhysicalEntity100001930 yago:YagoLegalActor yago:YagoLegalActorGeo dbo:Disease yago:Whole100003553 |
| rdfs:comment | The firing squad synchronization problem is a problem in computer science and cellular automata in which the goal is to design a cellular automaton that, starting with a single active cell, eventually reaches a state in which all cells are simultaneously active. It was first proposed by John Myhill in 1957 and published (with a solution by John McCarthy and Marvin Minsky) in 1962 by Edward F. Moore. (en) 一斉射撃問題（いっせいしゃげきもんだい）は、計算機科学とセル・オートマトンにおける数学パズル的な問題の一つである。この問題の目標は、一つのセルのみが活動している状態から始めて、最終的に全てのセルが同時に特定の状態に到達するように、セル・オートマトンを設計することである。 この問題は1957年にジョン・マイヒル（en:John Myhill）によって提案された。出版物としては、1964年に、エドワード・ムーア（en:Edward F. Moore）の編集による、この問題が解法とともに収録された文献集が出版されている。 (ja) Problem synchronizacji plutonu egzekucyjnego – zagadnienie z zakresu informatyki, polegające na próbie konstrukcji takiego automatu komórkowego, który zaczynając od pojedynczej nieaktywnej komórki, osiągnie stan, w którym wszystkie komórki osiągną jednocześnie stan aktywności. Problem został sformułowany przez Johna Myhilla w 1957, a pierwsze jego rozwiązanie opublikował w 1962 r. Edward Moore. (pl) Зада́ча синхрониза́ции стрелко́в — задача из области информатики и теории клеточных автоматов. Впервые предложенная Джоном Майхиллом в 1957 году и опубликованная (с решением) в 1962 году Эдвардом Муром. Название связано с поведением солдат при расстреле или ружейном салюте — все солдаты стреляют одновременно по сигналу. Поскольку сигнал распространяется по шеренге со скоростью 1 позиция за такт (в теории клеточных автоматов это называется «скорость света»), очевидно, время синхронизации будет возрастать с возрастанием . (ru) Задача синхронізації стрільців — завдання з області інформатики і клітинних автоматів, уперше запропонована Джоном Мейгіллом в 1957 році і опубліковане (з рішенням) в 1962 році Едвардом Муром. Формулюється таким чином: (uk) |
| rdfs:label | Firing squad synchronization problem (en) 一斉射撃問題 (ja) Problem plutonu egzekucyjnego (pl) Задача синхронизации стрелков (ru) Задача синхронізації стрільців (uk) |
| owl:sameAs | freebase:Firing squad synchronization problem yago-res:Firing squad synchronization problem wikidata:Firing squad synchronization problem dbpedia-ja:Firing squad synchronization problem dbpedia-pl:Firing squad synchronization problem dbpedia-ru:Firing squad synchronization problem dbpedia-uk:Firing squad synchronization problem https://global.dbpedia.org/id/3sWhd |
| prov:wasDerivedFrom | wikipedia-en:Firing_squad_synchronization_problem?oldid=1124569630&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/FSSP_1d1.svg wiki-commons:Special:FilePath/FiringSquadProblem.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Firing_squad_synchronization_problem |
| is dbo:wikiPageDisambiguates of | dbr:FSSP dbr:Firing_squad_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Firing_squad_problem |
| is dbo:wikiPageWikiLink of | dbr:FSSP dbr:John_Myhill dbr:Patrick_C._Fischer dbr:Edward_F._Moore dbr:Eiichi_Goto dbr:Cellular_automaton dbr:Firing_squad_(disambiguation) dbr:CoDi dbr:Toy_problem dbr:Firing_squad_problem |
| is foaf:primaryTopic of | wikipedia-en:Firing_squad_synchronization_problem |
