| 講演名 | 1999/6/18 可逆的・保存的2次元セル空間への単純なコンピュータの埋め込み 森田 憲一, 戸島 康之, 今井 克暢, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 2次元可逆セル・オートマトンで非常に単純な遷移規則を持つ4^4状態モデルP_4を提案し、その空間に任意の可逆2カウンタ機械が簡潔に埋め込めることを示す。可逆2カウンタ機械の計算万能性は既に知られているので、これによりP_4の万能性が導かれる。P_4は可逆性に加え、物理的な保存性に対応する性質も持っている:つまり、各セルの状態を表す非負整数の合計が計算過程全体を通じて一定値を保つ。ここでは、P_4中での信号の処理・操作用に6種の素子を設計し、可逆2カウンタ機械がこれらの素子だけから構成できることを示す。 |
| 抄録(英) | We introduce a 4^4-stage two-dimensional reversible cellular automaton called P_4 having very simple state-transition rules. We show that any reversible two-counter machine can be embedded in a finite configuration of P_4 very concisely. Since a reversible two-counter machine is known to be universal, P_4 has thus universal computing ability. Besides reversibility, P_4 also satisfies the constraint of a number-conservation property, i. e., cells' states are represented by integers, and the total of the integers over the configuration is conserved throughout its evolving process. We give six kinds of basic elements for signal processing, and show that any reversible counter machine can be built only from them in P_4. |
| キーワード(和) | セル・オートマトン / 計算万能性 / 可逆性 / 保存性 |
| キーワード(英) | cellular automata / computation-universality / reversibility / conservation law |
| 資料番号 | COMP99-21 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1999/6/18(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 可逆的・保存的2次元セル空間への単純なコンピュータの埋め込み |
| サブタイトル（和） | |
| タイトル（英） | A simple Computer Embedded in a Reversible and Number-Conserving Two-Dimensional Cellular Space |
| サブタイトル（和） | |
| キーワード(1)（和/英） | セル・オートマトン / cellular automata |
| キーワード(2)（和/英） | 計算万能性 / computation-universality |
| キーワード(3)（和/英） | 可逆性 / reversibility |
| キーワード(4)（和/英） | 保存性 / conservation law |
| 第 1 著者 氏名（和/英） | 森田 憲一 / Kenichi MORITA |
| 第 1 著者 所属（和/英） | 広島大学工学部 Faculty of Engineering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 戸島 康之 / Yasuyuki TOJIMA |
| 第 2 著者 所属（和/英） | 広島大学工学部 Faculty of Engineering, Hiroshima University |
| 第 3 著者 氏名（和/英） | 今井 克暢 / Katsunobu IMAI |
| 第 3 著者 所属（和/英） | 広島大学工学部 Faculty of Engineering, Hiroshima University |
| 発表年月日 | 1999/6/18 |
| 資料番号 | COMP99-21 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 130 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |