실물과 같은 세포 오토마톤

Life-like cellular automaton

셀룰러 오토마톤(CA)은 다음 기준을 충족하는 경우(Conway의 Game of Life와 유사하다는 점에서) 라이프와 같습니다.

  • 오토마톤의 세포 배열은 2차원을 가지고 있다.
  • 오토마톤의 각 셀은 두 가지 상태(통상은 "살아있다"와 "죽었다" 또는 "켜졌다"와 "꺼졌다"라고 함)를 가지고 있습니다.
  • 각 셀의 근방은 Moore 근방입니다.대상 셀에 인접한8개의 셀과 (가능성이 있는) 셀 자체로 구성됩니다.
  • 자동화의 각 시간 단계에서, 세포의 새로운 상태는 살아있는 상태의 인접 세포 수와 세포 자체의 상태에 대한 함수로 표현될 수 있다. 즉, 규칙은 외부 전체론적이다(때로는 반절제론이라고도 불린다).

이 등급의 셀 오토마타는 가장 유명한 셀 오토마톤인 Game of Life(B3/S23)의 이름을 따서 명명되었으며, 이 모든 기준을 충족합니다.이 클래스를 설명하는 데 많은 다른 용어가 사용됩니다.이것을 「라이프 패밀리」라고 부르거나, 「라이프와 비슷하다」라고 하는 문구를 간단하게 사용하는 것이 일반적입니다.

규칙 표기법

이러한 규칙을 기술하기 위한 세 가지 표준 표기법이 있으며, 서로 유사하지만 호환되지 않습니다.Wolfram & Packard(1985)는 Wolfram 코드를 사용합니다.Wolfram 코드는 바이너리 표현에 포함되는 10진수이며, 그 10진수에는 네이버의 각 수와 셀 상태에 대응하는 비트가 포함되어 있습니다.이 숫자의 비트는 다음 [1]세대에서 데드 또는 얼라이브 상태이기 때문에 0 또는1이 됩니다.다른 두 개의 표기는 동일한 비트의 시퀀스를 사람이 더 쉽게 읽을 수 있는 문자열로 압축합니다.

Mirek의 Cellebation에서 사용되는 표기법에서 규칙은 문자열 x/y로 작성됩니다.여기서 x와 y는 숫자 순서대로 0에서 8 사이의 개별 자릿수 시퀀스입니다.x 문자열에 숫자d가 있으면 d개의 라이브네이버를 가진 라이브셀이 다음 세대에 패턴으로 존속하고 y 문자열에 d가 있으면 d개의 라이브네이버를 가진 데드셀이 다음 세대에 활성화됨을 의미합니다.예를 들어 이 표기법에서는 Conway의 Game of Life는 23/[2][3]3로 표시됩니다.

Golly 오픈소스 셀룰러 오토마톤 패키지가 사용하는 표기법 및 셀룰러 오토마톤 패턴을 격납하기 위한 RLE 형식에서 규칙을 By/Sx 형식으로 기술한다.여기서 x 및 y는 MCell 표기법과 동일하다.따라서 이 표기법에서는 Conway의 Game of Life는 B3/S23으로 표기된다.이 형식의 "B"는 "birth"를, "S"는 "survival"[4]을 나타냅니다.

실제와 같은 규칙 선택

디아모에바(B35678/S5678) 규칙의 혼돈 다이아몬드
시드(B2/S) 규칙의 폭발적 혼돈
Conway's Game of Life (B3/S23)
아닐(B4678/S35678)

가능한 Life-like 규칙은 2개18 = 262,196개이며, 그 중 극히 일부만 상세하게 연구되었다.다음 설명에서 모든 규칙은 Golly/RLE 형식으로 지정됩니다.

라이프 라이크 룰에 주목
규칙. 이름. 설명 및 출처
B1357/S1357 리플리케이터 Edward Fredkin의 복제 오토마톤: 모든 패턴은 결국 [2][3][4]자신의 여러 복사본으로 대체됩니다.
B2/S 씨앗들 모든 패턴은 봉황으로, 살아있는 모든 세포가 즉시 죽는다는 것을 의미하며, 많은 패턴들이 폭발적으로 무질서한 성장을 이끈다양한 패턴들이 있다.다만, 복잡한 동작을 수반하는 몇개의 가공된 패턴이 [2][5][6]알려져 있습니다.
B25/S4 이 규칙은 작은 자기 복제 패턴을 지원합니다.이 패턴을 작은 글라이더 패턴과 조합하면 글라이더가 의사랜덤워크로 [4][7]앞뒤로 흔들립니다.
B3/S012345678 죽음 없는 삶 잉크팟 또는 플레이크라고도 합니다.살아난 세포는 죽지 않는다.무질서한 성장과 임의의 부울회로를 [2][4][8][9]시뮬레이션하는 데 사용할 수 있는 보다 구조화된 사다리 모양의 패턴을 결합합니다.
B3/S23 인생 매우 복잡한 [10][11]행동입니다.
B34/S34 34 라이프 처음에는 컴퓨터 시뮬레이션에서 더 큰 패턴이 폭발하는 경향이 있다는 것을 발견하기 전까지 Life의 안정적인 대안으로 생각되었습니다.작은 발진기와 [2][12][13]우주선을 많이 가지고 있다.
B35678/S5678 Diamoeba 무질서하게 변동하는 경계와 함께 양식 큰 다이아몬드.첫째 딘 Hickerson, 1993년에 50달러 상금을 살아 있는 세포와 함께 공간을 채우는 패턴을 찾겠다고 제안했다, 상 1999년 데이비드 벨로 승리했습니다.[2][4][14]
B36/S125 2x2 패턴이 2x2 블록으로 구성되어 있으면 동일한 형태로 계속 진화합니다.이러한 블록을 2의 더 큰 거듭제곱으로 그룹화하면 동작은 동일하지만 속도가 느려집니다.소형 [2][15]글라이더뿐만 아니라 높은 주기의 복잡한 발진기를 가지고 있습니다.
B36/S23 하이라이프 Life와 비슷하지만 자기 복제 패턴이 [2][4][16]작습니다.
B3678/S34678 주간 및 야간 ON-OFF 반전 시 대칭입니다.매우 복잡한 동작을 [2][4][17]가진 조작된 패턴을 가지고 있습니다.
B368/S245 몰리 Stephen Morley의 이름을 따서 Move라고도 합니다.매우 주기가 길고 속도가 [2][4][18]느린 우주선을 지원합니다.
B4678/S35678 아닐 비틀린 다수결의 법칙이라고도 합니다.ON-OFF 반전 시 대칭입니다.활성 [19][20][21]셀과 비활성 셀 사이의 경계에서 원곡선 단축 흐름을 근사합니다.

MCell 규칙 목록과 Eppstein(2010)에[2] 의해 셀 필드의 배경이 각 [4]단계에서 활성과 비활성 사이를 번갈아 이동하는 B0의 규칙을 포함하여 몇 가지 규칙이 더 나열되고 설명된다.

요소 B1(예를 들어 B17/S78 또는 B145/S34)을 포함하는 위의 형태의 오토마톤은 유한 패턴에 대해 항상 폭발적입니다.어떤 단계에서든 켜져 있는 셀과 최소 y좌표를 가진 셀(x,y)을 고려하십시오.다음으로 셀(x-1, y-1)에 네이버가1개만 존재해야 합니다.다음 순서로 켜집니다.마찬가지로 패턴은 4개의 대각선 방향의 각 단계에서 커져야 합니다.따라서, 비어 있지 않은 시작 패턴은 폭발적인 [4]성장으로 이어집니다.

B0, B1, B2 또는 B3 중 하나를 포함하지 않는 상기 형태의 오토마톤은 패턴을 포함하는 직사각형 빌딩 박스 외부의 셀이 이웃에 최대 3개까지 있기 때문에 패턴의 이동 또는 확장을 지원할 수 없습니다.표기법이 B2로 시작하는 규칙에서 대부분의 유한 패턴과 B1로 시작하는 규칙에서 모든 유한 패턴은 빛의 속도로 움직이는 전면과 함께 제한된 크기의 유지보다는 모든 방향으로 성장합니다.따라서 나머지 "흥미로운" 규칙은 B3(Game of Life, Highlife, Morley, 2x2, Day & Night)로 시작하거나 B0으로 시작하는 규칙이다(그렇지 않으면 S8을 포함하지 않고 대신 [4]듀얼을 연구할 수 있다).

일반화

Game of Life에서 영감을 얻었지만, 이 기사에서 제시한 "life-like"의 정의에 맞지 않는 다른 셀 오토마타가 있습니다. 왜냐하면 그 동네가 무어 지역보다 크거나, 3차원 격자에 정의되어 있거나, 다른 격자 토폴로지를 사용하기 때문입니다.예를 들어 다음과 같습니다.

  • 비토털리즘 규칙은 네이버 라이브셀 설정에 따라 달라집니다.
    • 다른 방향으로 다르게 동작하는 비등방성 규칙입니다.이러한 종류의 규칙은 등방성 규칙을 포함하여 2⁄1.34*10입니다512154.
    • 등방성 비전체론적 규칙은 회전과 반사 하에서 동일하게 동작합니다.외부 전체론적 [22]규칙을 포함하여 이러한 종류의 규칙이 2⁄5.07*1030 있습니다102.
  • Liger Than Life는 켈리 미셸 에반스가 연구한 세포 오토마타 패밀리입니다.그들은 매우 큰 반경 지역을 가지고 있지만 콘웨이의 삶과 유사한 "생애/사망" 문턱값을 수행합니다.이러한 오토마타는 섬뜩한 유기적인 "활공"과 "깜빡이"[23] 구조를 가지고 있습니다.
  • RealLife는 Evan의 Liger Than Life CA의 "연속 한계"로, 인근 반경이 무한대로 이동하고 격자 간격이 0이 될 때의 한계입니다.엄밀히 말하면, 기본 "공간"은 이산 격자2 Z가 아닌 연속적인 유클리드 평면2 R이기 때문에 그것들은 전혀 세포 자동이 아니다.그것들은 Marcus Pivato에 [24]의해 연구되었다.
  • Carter Bays는 Z(3D Life)[25]에3 정의된 3차원 CA로 Game of Life의 다양한 일반화를 제안했습니다.Bays는 또한 삼각형 또는 육각형 [26][27]이웃이 있는 2차원 생명체와 같은 CA를 연구했다.

레퍼런스

  1. ^ Wolfram, Stephen; Packard, N. H. (1985), "Two-dimensional cellular automata", Journal of Statistical Physics, 38 (5–6): 901–946, Bibcode:1985JSP....38..901P, doi:10.1007/BF01010423 에서 재인쇄되었습니다.
  2. ^ a b c d e f g h i j k 를 클릭합니다Wójtowicz, Mirek, Cellular Automaton Rules Lexicon — Family: Life, Mirek's Cellebration.
  3. ^ a b 를 클릭합니다Wuensche, Andrew (2011), "16.10 The game-of-Life and other Life-like rules – rcode", Exploring Discrete Dynamics: The DDLAB manual, Luniver Press, pp. 145–146, ISBN 978-1-905986-31-6.
  4. ^ a b c d e f g h i j k 를 클릭합니다Eppstein, David (2010), "Growth and decay in life-like cellular automata", in Adamatzky, Andrew (ed.), Game of Life Cellular Automata, Springer, pp. 71–98, arXiv:0911.2890, doi:10.1007/978-1-84996-217-9_6, ISBN 978-1-84996-216-2.
  5. ^ 를 클릭합니다Silverman, Brian, "Changing the Rules", The Virtual Computer, Mathematical Association of America.
  6. ^ 제이슨 서머스가 수집한 씨앗의 패턴.
  7. ^ 를 클릭합니다Nivasch, Gabriel (2007), The photon/XOR system.
  8. ^ 를 클릭합니다Toffoli, Tommaso; Margolus, Norman (1987), "1.2 Animate-by-numbers", Cellular Automata Machines: A New Environment for Modeling, MIT Press, pp. 6–7.
  9. ^ 를 클릭합니다Griffeath, David; Moore, Cristopher (1996), "Life without Death is P-complete", Complex Systems, 10: 437–447.
  10. ^ 를 클릭합니다Gardner, Martin (October 1970), "Mathematical Games - The fantastic combinations of John Conway's new solitaire game "life"", Scientific American, 223: 120–123.
  11. ^ 를 클릭합니다Berlekamp, E. R.; Conway, John Horton; Guy, R.K. (2004), Winning Ways for your Mathematical Plays (2nd ed.), A K Peters Ltd.
  12. ^ 를 클릭합니다Poundstone, William (1985), The Recursive Universe: Cosmic Complexity and the Limits of Scientific Knowledge, Contemporary Books, p. 134, ISBN 978-0-8092-5202-2.
  13. ^ 를 클릭합니다Eisenmann, Jack, 34 LIFE.
  14. ^ 를 클릭합니다Gravner, Janko; Griffeath, David (1998), "Cellular automaton growth on Z2: theorems, examples, and problems", Advances in Applied Mathematics, 21 (2): 241–304, doi:10.1006/aama.1998.0599, MR 1634709.
  15. ^ 를 클릭합니다Johnston, Nathaniel (2010), "The B36/S125 "2x2" Life-Like Cellular Automaton", in Adamatzky, Andrew (ed.), Game of Life Cellular Automata, Springer, pp. 99–114, arXiv:1203.1644, Bibcode:2010golc.book...99J, doi:10.1007/978-1-84996-217-9_7, ISBN 978-1-84996-216-2.
  16. ^ 를 클릭합니다Bell, David, HighLife - An Interesting Variant of Life.
  17. ^ 를 클릭합니다Bell, David, Day & Night - An Interesting Variant of Life.
  18. ^ 를 클릭합니다Morley, Stephen (2005), b368s245 Guns, archived from the original on 2006-03-11.
  19. ^ 를 클릭합니다Vichniac, Gérard Y. (1986), "Cellular automata models of disorder and organization", in Bienenstock, E.; Fogelman Soulié, F.; Weisbuch, G. (eds.), Disordered Systems and Biological Organization, NATO ASI Series, vol. 20, Springer-Verlag, pp. 3–20, doi:10.1007/978-3-642-82657-3_1.
  20. ^ 를 클릭합니다Pickover, Clifford A. (1993), "Lava lamps in the 21st century", The Visual Computer, 10 (3): 173–177, doi:10.1007/bf01900906.
  21. ^ 를 클릭합니다Chopard, Bastien; Droz, Michel (1998), "2.2.4 The annealing rule", Cellular automata modeling of physical systems, Collection Aléa-Saclay: Monographs and Texts in Statistical Physics, Cambridge University Press, Cambridge, pp. 37–38, doi:10.1017/CBO9780511549755, ISBN 0-521-46168-5, MR 1669736.
  22. ^ Sapin, Emmanuel (2010), "Larger than Life: threshold-range scaling of Life's coherent structures", in Adamatzky, Andrew (ed.), Game of Life Cellular Automata, pp. 135–165, doi:10.1007/978-1-84996-217-9_9
  23. ^ 를 클릭합니다Evans, Kellie Michele (2003), "Larger than Life: threshold-range scaling of Life's coherent structures", Physica D, 183 (1–2): 45–67, Bibcode:2003PhyD..183...45E, doi:10.1016/S0167-2789(03)00155-6.
  24. ^ 를 클릭합니다Pivato, Marcus (2007), "RealLife: the continuum limit of Larger than Life cellular automata", Theoretical Computer Science, 372 (1): 46–68, arXiv:math.DS/0503504, doi:10.1016/j.tcs.2006.11.019.
  25. ^ 를 클릭합니다Bays, Carter (2006), "A note about the discovery of many new rules for the game of three-dimensional life", Complex Systems, 16 (4): 381–386.
  26. ^ 를 클릭합니다Bays, Carter (2007), "The discovery of glider guns in a game of life for the triangular tessellation", Journal of Cellular Automata, 2 (4): 345–350.
  27. ^ 를 클릭합니다Bays, Carter (2005), "A note on the game of life in hexagonal and pentagonal tessellations", Complex Systems, 15 (3): 245–252.

외부 링크