• 検索結果がありません。

20世紀の名著名論:Robert Balzer : An 8-State Minimal Time Solution to the Firing Squad Synchronization Problem

N/A
N/A
Protected

Academic year: 2021

シェア "20世紀の名著名論:Robert Balzer : An 8-State Minimal Time Solution to the Firing Squad Synchronization Problem"

Copied!
1
0
0

読み込み中.... (全文を見る)

全文

(1)20 世紀の名著名論 Robert Balzer : An 8-State Minimal Time Solution to the Firing Squad Synchronization Problem Information and Control, Vol.10, pp.22-42(1967).  名著というより楽しいのを紹介する.一斉射撃問題. �. � �. ( 英語では Firing Squad Problem) である.やや異なる両端. � �. 以外は同じ有限セルオートマトンが n 個,同じ初期状態. �. で 1 列に並んでいる.片端にいるのを将軍,残りを兵士と. �. いう.オートマトンは同期して遷移し,時刻 t1 の状態は. � �. 時刻 t の自分と両隣の状態で決まるから状態は波状に伝わ � �. る.将軍が「準備できたら撃て」の命令を出すと,あとは 兵士達の状態変化だけで一斉射撃の状態にする方法 ; それ. �. までの時間を答える問題だ.自己増殖で子のセルの一斉起. �. �. �. �� � �. 動に必要である.1957 年に Myhill が考えたといわれる.  1961 年頃,東大高橋研に滞在していた D. E. Muller 先 生がお茶の時間にこの話を披露すると,いわゆる 3n 時間. k  図の右は 1/3, 1/7, 1/15, ... , 1/(2 1) の波の作り方を. 解はすぐできた.ところが後藤英一さんが MIT から帰国. 示す.左上 (0) から 1/1 の波が 0, 1, 0, 1 のリズムで右へ進. するなり,2n の解があるといい,輪講で話した.これは複. む.1 の時 (1) 左へ 1/1 の波を送る. この波は中央兵に. 雑な仕掛けで,状態数も何状態  何状態  ... という感じ. 当たるとマーカを生じ,それを 1 だけ右へ寄せる (2).ま. で,何千か何万かも定かでなかった.この書き物は残って. た 1/1 の波はマーカに出会うとマーカを 1 だけ右へ寄. いない.. せる (3).マーカも 0, 1, 0, 1 のリズムで右へ進むが,1 の.   や が て Waksman が 16 状 態 の 解 を 発 表 し,続 い て. 時,左へ 1/1 の波を送る (4).このようなマーカは 1/3,. Balzer が 8 状態のこの解を出す.私がこれを読み,高橋. k 1/7, 1/15, ... , 1/(2 1) の波になっているのが分かる.左. 秀俊先生に 8 状態でできるそうだと告げると, 「あの問題. へ遅い波を送るにはこの方式を反転する.. は本質的であり,本質的なものは簡単になる」とことも.  これだけできればあとはこの動きを生じるように状態. なげにいわれた.. を設定すればよい.状態は次の通り :.  図の左は縦が時,横が兵士である.時刻 0 に左端の将 軍が命令を発し (0),自分は太線で表す中央兵状態にな. M : 中央兵.   F : 射撃状態. る.同時に 1/1, 1/3, ... の波を右へ送る (1/3 は 3 時間単. L : 波を左に伝える媒体.   R : 波を右に伝える媒体. 位に 1 進むの意 ).1/1 の波は時刻 n に右端に達し (1),. C : 左に進む波とマーカ.   Q : 右に進む波とマーカ. 右端を中央兵状態にし,1/1, 1/3, ... の波を左へ送. B : マーカを左へ動かす右に進む波. る.1/1 は 1/3 の波と時刻 3n/2 に (2) で出会い,中央. A: マーカを右へ動かす左に進む波. (n/2) が分かる. 中央は中央兵状態になり,±1/1, ±1/3, ... の波を左右に送る.左へ進む 1/1 の波は n/4 の地. この他両端を示す X があるが,X は入力にだけ現れ,そ. 点 (3) で (0) から来た 1/7 の波と時刻 7n/4 に出会い,四. の結果 8 状態で十分であることが分かった.なかなか巧. 分点が分かる.同様にもう 1 つの四分点 (4) も分かる.こ. 妙にできていて,感心する.. のように半分ずつの地点が分かり,自分も両隣も中央兵.  Balzer 君とは 2 度会って話した.巻き毛,早口,聡明な. になったら撃つのである.正確な所要時間は 2n2 で. 若者であった.. ある.. (平成 16 年 3 月 10 日受付).        和田英一/ IIJ 技術研究所.        . 644. 45 巻 6 号 情報処理 2004 年 6 月.         [email protected] .

(2)

参照

関連したドキュメント

pole placement, condition number, perturbation theory, Jordan form, explicit formulas, Cauchy matrix, Vandermonde matrix, stabilization, feedback gain, distance to

By an inverse problem we mean the problem of parameter identification, that means we try to determine some of the unknown values of the model parameters according to measurements in

В данной работе приводится алгоритм решения обратной динамической задачи сейсмики в частотной области для горизонтально-слоистой среды

Keywords: continuous time random walk, Brownian motion, collision time, skew Young tableaux, tandem queue.. AMS 2000 Subject Classification: Primary:

A new method is suggested for obtaining the exact and numerical solutions of the initial-boundary value problem for a nonlinear parabolic type equation in the domain with the

A Darboux type problem for a model hyperbolic equation of the third order with multiple characteristics is considered in the case of two independent variables.. In the class

[2])) and will not be repeated here. As had been mentioned there, the only feasible way in which the problem of a system of charged particles and, in particular, of ionic solutions

This paper presents an investigation into the mechanics of this specific problem and develops an analytical approach that accounts for the effects of geometrical and material data on