著者

今井 克暢 森田 憲一

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告. [プログラミング-言語基礎実践-]

巻号頁・発行日

vol.94, no.21, pp.121-128, 1994-03-09

---

一斉射撃問題を可逆(すなわち,逆向きにも決定的な)セル・オートマトン(RCA)で実現できるか考察した.まず従来の単一の射撃状態からなる一斉射撃解は構成できないことを証明した.そこで,RCAにおける一斉射撃解を複数の射撃状態を許したものとして定義し,この条件の下でMinskyの3n時間解を540状態のRCAに埋め込めることを示した.その際,分割セル・オートマン(PCA)を用いた.これはCAのサブクラスとみなすことができ,RCAの設計を容易にする.さらに3n時間解に基づく99状態の解を可逆PCAによって構成した.