セル・オートマトン
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/03 07:32 UTC 版)
セル・オートマトン（英: cellular automaton、略称：CA）とは、格子状のセルと単純な規則による、離散的計算モデルである。計算可能性理論、数学、物理学、複雑適応系、数理生物学、微小構造モデリングなどの研究で利用される。非常に単純化されたモデルであるが、生命現象、結晶の成長、乱流といった複雑な自然現象を模した、驚くほどに豊かな結果を与えてくれる。
- ^ Daniel Dennett (1995), Darwin's Dangerous Idea, Penguin Books, London, ISBN 978-0-14-016734-4, ISBN 0-14-016734-X
- ^ Wolfram, Stephen (1983). “Statistical Mechanics of Cellular Automata”. Reviews of Modern Physics 55 (3): 601–644. Bibcode: 1983RvMP...55..601W. doi:10.1103/RevModPhys.55.601.
- ^ a b c d Kier, Seybold & Cheng 2005, p. 15
- ^ a b Bialynicki-Birula & Bialynicka-Birula 2004, p. 9
- ^ Schiff 2011, p. 41
- ^ Pickover, Clifford A. (2009). The Math Book: From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics. Sterling Publishing Company, Inc. p. 406. ISBN 978-1402757969
- ^ a b Schiff 2011, p. 1
- ^ John von Neumann, “The general and logical theory of automata,” in L.A. Jeffress, ed., Cerebral Mechanisms in Behavior – The Hixon Symposium, John Wiley & Sons, New York, 1951, pp. 1-31.
- ^ John G. Kemeny, “Man viewed as a machine,” Sci. Amer. 192(April 1955):58-67; Sci. Amer. 192(June 1955):6 (errata).
- ^ Schiff 2011, p. 3
- ^ Ilachinski 2001, p. xxix
- ^ Bialynicki-Birula & Bialynicka-Birula 2004, p. 8
- ^ a b Wolfram 2002, p. 876
- ^ von Neumann, John; Burks, Arthur W. (1966). Theory of Self-Reproducing Automata. University of Illinois Press
- ^ Wiener, N.; Rosenblueth, A. (1946). “The mathematical formulation of the problem of conduction of impulses in a network of connected excitable elements, specifically in cardiac muscle”. Arch. Inst. Cardiol. México 16: 205.
- ^ Davidenko, J. M.; Pertsov, A. V.; Salomonsz, R.; Baxter, W.; Jalife, J. (1992). “Stationary and drifting spiral waves of excitation in isolated cardiac muscle”. Nature 355 (6358): 349–351. Bibcode: 1992Natur.355..349D. doi:10.1038/355349a0. PMID 1731248.
- ^ Hedlund, G. A. (1969). “Endomorphisms and automorphisms of the shift dynamical system”. Math. Systems Theory 3 (4): 320–3751. doi:10.1007/BF01691062.
- ^ Schiff 2011, p. 182
- ^ Gardner, Martin (1970). “Mathematical Games: The fantastic combinations of John Conway's new solitaire game "life"”. Scientific American (223): 120–123.
- ^ Paul Chapman. Life universal computer. November 2002
- ^ a b c d e Wolfram 2002, p. 880
- ^ Wolfram 2002, p. 881
- ^ a b c Ilachinski 2001, p. 12
- ^ Ilachinski 2001, p. 13
- ^ Wolfram 2002, p. 231
- ^ Zenil, Hector (2010). “Compression-based investigation of the dynamical properties of cellular automata and other systems”. Complex Systems 19 (1).
- ^ G. Cattaneo, E. Formenti, L. Margara (1998). “Topological chaos and CA”. In M. Delorme, J. Mazoyer. Cellular automata: a parallel model. Springer. p. 239. ISBN 978-0-7923-5493-2
- ^ Burton H. Voorhees (1996). Computational analysis of one-dimensional cellular automata. World Scientific. p. 8. ISBN 978-981-02-2221-5
- ^ Max Garzon (1995). Models of massive parallelism: analysis of cellular automata and neural networks. Springer. p. 149. ISBN 978-3-540-56149-1
- ^ a b Kari, Jarrko 1991, p. 379
- ^ Richardson, D. (1972). “Tessellations with local transformations”. J. Computer System Sci. 6 (5): 373–388. doi:10.1016/S0022-0000(72)80009-6.
- ^ Margenstern, Maurice (2007). Cellular Automata in Hyperbolic Spaces - Tome I, Volume 1. Archives contemporaines. p. 134. ISBN 978-2-84703-033-4
- ^ Schiff 2011, p. 103
- ^ Serafino Amoroso, Yale N. Patt, Decision Procedures for Surjectivity and Injectivity of Parallel Maps for Tessellation Structures. J. Comput. Syst. Sci. 6(5): 448-464 (1972)
- ^ Sutner, Klaus (1991). “De Bruijn Graphs and Linear Cellular Automata”. Complex Systems 5: 19–30.
- ^ Kari, Jarkko (1990). “Reversibility of 2D cellular automata is undecidable”. Physica D 45: 379–385. Bibcode: 1990PhyD...45..379K. doi:10.1016/0167-2789(90)90195-U.
- ^ Kari, Jarkko (1999). “On the circuit depth of structurally reversible cellular automata”. Fundamenta Informaticae 38: 93–107.
- ^ Durand-Lose, Jérôme (2001). “Representing reversible cellular automata with reversible block cellular automata”. Discrete Mathematics and Theoretical Computer Science AA: 145–154.
- ^ Wolfram 2002, p. 60
- ^ a b Ilachinski, Andrew (2001). Cellular automata: a discrete universe. World Scientific. pp. 44–45. ISBN 978-981-238-183-5
- ^ "life-like cellular automaton" という用語の初出は少なくとも Barral, Chaté & Manneville (1992) まで遡るが、この文献では外部総和型全般をそのように呼んでおり、2次元に限定していない。
- ^ Adamatzky, Andrew, ed (2010). Game of Life Cellular Automata. Springer. ISBN 978-1-84996-216-2 - こちらはより限定的な意味で "life-like" と呼んでいる。
- ^ http://www.newscientist.com/article/dn22134-first-gliders-navigate-everchanging-penrose-universe.html
- ^ Murray, J.. Mathematical Biology II. Springer.
- ^ Pivato, M: "RealLife: The continuum limit of Larger than Life cellular automata", Theoretical Computer Science, 372 (1), March 2007, pp.46-68
- ^ Giles, Jim (2002). “What Kind of Science is This?”. ネイチャー (417): 216–218.
- ^ Weinberg, Steven (October 24, 2002). “Is the Universe a Computer?”. The New York Review of Books (Rea S. Hederman) 2012年10月12日閲覧。.
- ^ a b c Coombs, Stephen (February 15, 2009), The Geometry and Pigmentation of Seashells, pp. 3–4 2012年9月2日閲覧。
- ^ Peak, West; Messinger, Mott (2004). “Evidence for complex, collective dynamics and emergent, distributed computation in plants”. Proceedings of the National Institute of Science of the USA 101 (4): 918–922. Bibcode: 2004PNAS..101..918P. doi:10.1073/pnas.0307811100. PMC 327117. PMID 14732685.
- ^ http://gilly.stanford.edu/past_research_files/APackardneuralnet.pdf
- ^ Yves Bouligand (1986). Disordered Systems and Biological Organization. pp. 374–375
- ^ A. K. Dewdney, The hodgepodge machine makes waves, Scientific American, p. 104, August 1988.
- ^ M. Gerhardt and H. Schuster, A cellular automaton describing the formation of spatially ordered structures in chemical systems, Physica D 36, 209-221, 1989.
- ^ a b The Evolution of Emergent Computation, James P. Crutchfield and Melanie Mitchell (SFI Technical Report 94-03-012)
- ^ http://www.santafe.edu/about/people/profile/Melanie%20Mitchell
- ^ a b The Evolutionary Design of Collective Computation in Cellular Automata, James P. Crutchfeld, Melanie Mitchell, Rajarshi Das (In J. P. Crutch¯eld and P. K. Schuster (editors), Evolutionary Dynamics|Exploring the Interplay of Selection, Neutrality, Accident, and Function. New York: Oxford University Press, 2002.)
- ^ Evolving Cellular Automata with Genetic Algorithms: A Review of Recent Work, Melanie Mitchell, James P. Crutchfeld, Rajarshi Das (In Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA'96). Moscow, Russia: Russian Academy of Sciences, 1996.)
- ^ Tomassini, M.; Sipper, M.; Perrenoud, M. (2000). “On the generation of high-quality random numbers by two-dimensional cellular automata”. IEEE Transactions on Computers 49 (10): 1146–1151.
- ^ Wolfram, S. "Cryptography with Cellular Automata", In Advances in Cryptology: CRYPTO '85 Proceedings [Williams, H. C. (Ed.)]. Lecture Notes in Computer Science 218. Springer-Verlag, 429–432, 1986.
- ^ "Cellular Automaton Public-Key Cryptosystem", Complex Systems, Vol. 1, No. 1 (1987).
- ^ Ilachinski 2001, p. 660
- ^ Ilachinski 2001, pp. 661–662
- ^ J. P. Crutchfield, "The Calculi of Emergence: Computation, Dynamics, and Induction", Physica D 75, 11-54, 1994.
- ^ M. Minsky, "Cellular Vacuum", International Journal of Theoretical Physics 21, 537-551, 1982.
- ^ K. Zuse, "The Computing Universe", Int. Jour. of Theo. Phy. 21, 589-600, 1982.
- ^ E. Fredkin, "Digital mechanics: an informational process based on reversible universal cellular automata", Physica D 45, 254-270, 1990
- ^ iLabs
- ^ F. Berto, G. Rossi, J. Tagliabue, The Mathematics of the Models of Reference, College Publications, 2010
- ^ Weisstein, Eric W.. “Cellular Automaton”. 2011年3月13日閲覧。
- ^ the Hacker Emblem page on Eric S. Raymond's site
- ^ Blackford, Russell; Ikin, Van; McMullen, Sean (1999). “Greg Egan”. Strange constellations: a history of Australian science fiction. Contributions to the study of science fiction and fantasy. 80. Greenwood Publishing Group. pp. 190–200. ISBN 978-0-313-25112-2
- ^ Hayles, N. Katherine (2005). “Subjective cosmology and the regime of computation: intermediation in Greg Egan's fiction”. My mother was a computer: digital subjects and literary texts. University of Chicago Press. pp. 214–240. ISBN 978-0-226-32147-9
- ^ Kasman, Alex. “MathFiction: Bloom”. 2011年3月27日閲覧。
- ^ http://www.sfwriter.com/syw1.htm
- ^ http://www.dezeen.com/2014/09/26/francis-bitonti-3d-printed-molecule-shoes-adobe-stratasys/
[続きの解説]
「セル・オートマトン」の続きの解説一覧
セル・オートマトン
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/01/30 07:28 UTC 版)
1980年代初頭からスティーブン・ウルフラムは1次元セル・オートマトンのルール（遷移関数）ごとの挙動を調査し、その挙動を以下のように4つにクラス分けした。 クラスI：均一な一定状態に漸近する挙動 クラスII：周期的な状態に漸近する挙動 クラスIII：ランダムな状態を維持する挙動 クラスIV：他のクラスほど厳密に定義されないが、上記の3クラスに当てはまらない挙動 ウルフラムはクラスIからIIIまでに対し、力学系の挙動とアナロジー的に該当するものを当て嵌めている。 クラスI：安定不動点 クラスII：リミットサイクル クラスIII：カオス ウルフラムによればクラスIVについては該当する力学系の挙動が存在しない。クラスIVでは非常に複雑な挙動が起こる。いくつかの局所的な構造が生み出され、それらはセル空間内を移動し、相互作用を起こし合う。また、ある初期値では全て一定状態に漸近したり、別の初期値では周期的状態に漸近したり、ランダム状態を維持したりなどの変化も見せる。以下の図はウルフラムのルール番号によってルール110と呼ばれるルールを採用したときのセル・オートマトンの挙動（時間発展）を示している。初期配置は黒一点のみが存在する場合である。クラスIVに分類される。 クリストファー・ラングトンはクラスIVについてさらに調べるために、次のようなパラメータを導入した。 ここで、k は状態数、 ρ は近傍数を意味し、kρ は可能な近傍の状態数となる。状態数 k の内の任意な一つの状態 q を「静止状態」と呼ぶとする。nq は kρ の内の次の時刻に静止状態（すなわち q ）となる数を示す。λ は静止状態とならない割合を示しており、一般には λ パラメータなどと呼ばれる。あるいは、ラングトン自身は λ パラメータのことを「あるレベルの挙動の複雑さに関連する統計量」と位置づけている。 nq の最小から最大までの範囲は、0 ≤ nq ≤ kρ なので、λ の範囲は 0 ≤ λ ≤ 1 となる。ラングトンによれば、λ = 0 で最少である複雑性は、λ の増加とともにも複雑性も増加し、λ がある値となったところで極大となり、その後は複雑性は減少していき、λ = 1 でまた最少となる。複雑性が極大となる臨界値は λc で表される。ウルフラムのクラスと一緒にまとめると、挙動とクラスと λ パラメータは以下のような関係の下に変化する。 挙動： 不動点 周期的 "複雑" カオス0 ウルフラムのクラス： クラス I ⇒ クラスII ⇒ クラスIV ⇒ クラスIII0 λ パラメータ： 0 λc ただし、上記の区分は k や ρ が大きな値のときは良く機能するが、小さいときはあまりうまく働かない。 このように、クラスIVはカオス的・ランダム的振る舞いと秩序的・静的振る舞いの境界に存在し、この領域を「カオスの縁」と呼ぶ。
※この「セル・オートマトン」の解説は、「カオスの縁」の解説の一部です。
「セル・オートマトン」を含む「カオスの縁」の記事については、「カオスの縁」の概要を参照ください。
セル・オートマトン
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/17 03:05 UTC 版)
2進数での写像は、en:Wolfram codeのen:Rule 102という形で、セル・オートマトンとして認識されている。またこれは、Martin-Odlyzko-Wolfram 図を通じて、en:Rule 90とも関連性を持つ。 en:Rule 102はシェルピンスキーのギャスケットを再生する。
※この「セル・オートマトン」の解説は、「ドゥッチ数列」の解説の一部です。
「セル・オートマトン」を含む「ドゥッチ数列」の記事については、「ドゥッチ数列」の概要を参照ください。
セル・オートマトン
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/21 04:22 UTC 版)
セル・オートマトンの問題にもパズル的なものがある。例えば「一斉射撃問題」など。
※この「セル・オートマトン」の解説は、「数学パズル」の解説の一部です。
「セル・オートマトン」を含む「数学パズル」の記事については、「数学パズル」の概要を参照ください。
ウィキペディア小見出し辞書の「セル・オートマトン」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
セル・オートマトンと同じ種類の言葉
- セル・オートマトンのページへのリンク
