セル・オートマトンとビリヤードボール・コンピュータ

ショートカット: 違い、類似点、ジャカード類似性係数、参考文献。

セル・オートマトンとビリヤードボール・コンピュータの違い

セル・オートマトン vs. ビリヤードボール・コンピュータ

Daniel Dennett (1995), ''Darwin's Dangerous Idea'', Penguin Books, London, ISBN 978-0-14-016734-4, ISBN 0-14-016734-X セル・オートマトン（cellular automaton、略称：CA）とは、格子状のセルと単純な規則による、離散的計算モデルである。計算可能性理論、数学、物理学、複雑適応系、数理生物学、微小構造モデリングなどの研究で利用される。非常に単純化されたモデルであるが、生命現象、結晶の成長、乱流といった複雑な自然現象を模した、驚くほどに豊かな結果を与えてくれる。 正確な発音に近いセルラ・オートマトンとも呼ばれることがある。セルは「細胞」「小部屋」、セルラは「細胞状の」、オートマトンは「からくり」「自動機械」を意味する。他に「セル空間」「埋め尽くしオートマトン」「homogeneous structure」「tessellation structure」「iterative array」といった呼称もある。 有限種類の（多くは2から数十種類の）状態を持つセル（細胞のような単位）によってセル・オートマトンは構成され、離散的な時間で個々のセルの状態が変化する。その変化は、ある時刻 t においてのセルの状態、および近傍のセルの内部状態によって、次の時刻t+1 、すなわち新たな「ジェネレーション」（世代）での各セルの状態が決定される。初期状態（時刻 t. ビリヤードボール・コンピュータ（Billiard-ball computer）は、ボールの力学的な運動を基にした可逆計算モデルである。エドワード・フレドキンとトマソ・トフォリによって1982年に提案された。エレクトロニクスによるコンピュータが電流電圧により情報を伝達し、またいわゆる能動素子を利用して論理演算を行うのに対し、ビリヤードボール・コンピュータでは摩擦のない理想的なビリヤードボールの慣性による等速直線運動と完全弾性衝突による反発が情報を運び論理演算を行う。可逆計算を考察する上で有用なモデルのひとつである。.

可逆計算

可逆計算（かぎゃくけいさん、Reversible computing）とは、可逆な、すなわち計算過程において常に直前と直後の状態が一意に定まる計算。可逆計算は、計算過程において情報が消失しないため非破壊的計算（Non-destructive computing）としても知られている。.

セル・オートマトンと可逆計算 · ビリヤードボール・コンピュータと可逆計算 · 続きを見る »

チューリング完全

計算理論において、ある計算のメカニズムが万能チューリングマシンと同じ計算能力をもつとき、その計算モデルはチューリング完全（チューリングかんぜん、Turing-complete）あるいは計算完備であるという。 チャーチ＝チューリングのテーゼによれば「計算可能関数」は、それを計算しようとする計算モデルがチューリング完全であれば計算できる。 一般的なプログラミング言語の背景にある計算モデルの多くはチューリング完全である。一見単純な機能しか持たない言語がチューリング完全な例としては、Lazy K、Brainfuckなどがある。究極的に単純な計算モデルとしては「がチューリング完全であると証明されている。 チューリング完全かどうかという事は、計算可能性理論の問題である。計算複雑性の分野の問題である時間や記憶容量の消費量については考えない。表計算における数式の処理などで、繰り返し処理を「どうやっても実現できなければ」それはチューリング完全ではない。 コンピュータ言語のうち、少なくともチューリング完全でなければプログラミング言語とは呼ばれない。逆にチューリング完全であるにも関わらず慣例的にプログラミング言語とは呼ばれないものもある。.

セル・オートマトンとチューリング完全 · チューリング完全とビリヤードボール・コンピュータ · 続きを見る »

トマソ・トフォリ

トマソ・トフォリ（、1943年 - ）は、ボストン大学の電気情報工学学部の特任教授。.

セル・オートマトンとトマソ・トフォリ · トマソ・トフォリとビリヤードボール・コンピュータ · 続きを見る »

エドワード・フレドキン

ドワード・フレドキン（Edward Fredkin、1934年 - ）は、計算機科学者、物理学者である。理論計算機科学の分野、特に可逆計算とセル・オートマトンでの業績が知られている。デジタル物理学の先駆者の1人でもあるが、近年のworkでは「デジタル哲学」という語を使っている。フレドキンの考案した可逆計算ゲートであるフレドキンゲートは、コンラート・ツーゼが可逆計算の重要性を示唆した著書 Calculating Space（1969年）において、可逆計算を実装する基盤として引用されている。.

エドワード・フレドキンとセル・オートマトン · エドワード・フレドキンとビリヤードボール・コンピュータ · 続きを見る »

コンピュータ

ンピュータ（Computer）とは、自動計算機、とくに計算開始後は人手を介さずに計算終了まで動作する電子式汎用計算機。実際の対象は文字の置き換えなど数値計算に限らず、情報処理やコンピューティングと呼ばれる幅広い分野で応用される。現代ではプログラム内蔵方式のディジタルコンピュータを指す場合が多く、特にパーソナルコンピュータやメインフレーム、スーパーコンピュータなどを含めた汎用的なシステムを指すことが多いが、ディジタルコンピュータは特定の機能を実現するために機械や装置等に組み込まれる組み込みシステムとしても広く用いられる。電卓・機械式計算機・アナログ計算機については各項を参照。.

コンピュータとセル・オートマトン · コンピュータとビリヤードボール・コンピュータ · 続きを見る »

決定可能性

決定可能（けっていかのう、decidable）は、論理学において、論理式の集合のメンバーシップの決定をする実効的（effectiveな）方法が存在することを指す。決定可能性（けっていかのうせい、decidability）は、そのような属性を指す。命題論理のような形式体系は、論理的に妥当な論理式（または定理）の集合のメンバーシップを実効的に決定できるなら、決定可能である。ある決まった論理体系における理論（論理的帰結で閉じている論理式の集合）は、任意の論理式がその理論に含まれるか否かを決定する実効的方法があれば、決定可能である。.

セル・オートマトンと決定可能性 · ビリヤードボール・コンピュータと決定可能性 · 続きを見る »