크리터(세포 자동자)

Critters (cellular automaton)
글라이더들이 중앙 랜덤 시드 영역에서 탈출
크리터의 전환 규칙.살아있는 세포는 녹색 세포로, 죽은 세포는 흰 세포로 나타난다.가능한 16개의 2×2블록(파란색으로 표시) 각각은 그림과 같이 변형된다.규칙은 파란색으로 표시된 블록을 사용하는 것과 빨간 점선으로 표시된 블록을 사용하는 것 사이에서 번갈아 나타난다.

크리터스는 1987년 토마소 토폴리, 노먼 마골러스가 처음 설명한 [1][2]콘웨이의 게임 오브 라이프와 유사한 역학관계를 가진 역전 블록 셀룰러 오토매틱이다.[3]

정의

크리터는 2차원 무한 그리드 셀에 정의되며, 이를 정수 격자로 식별할 수 있다.콘웨이의 생명의 게임에서와 같이, 어느 시점에서든 각 세포는 두 개의 상태 중 하나에 있을 수 있다. 즉, 생사 여부.Critters 규칙은 Margolus 지역을 사용하는 세포 자동 차단이다.즉, 각 단계에서 자동화의 셀은 2 × 2 블록으로 분할되고 각 블록은 다른 블록과 독립적으로 업데이트된다.한 번에 블록의 중심은 다음 번에 4블록의 구석이 되고, 반대로 4블록의 구석이 된다. 이런 식으로 각 블록의 4셀은 이전 칸막이의 4개의 다른 2×2블록에 속한다.[3]

Critters의 전이 함수는 한 블록에 있는 살아있는 세포의 수를 세고, 만약 이 숫자가 정확히 두 개라면 블록을 변경하지 않고 그대로 둔다.살아있는 세포의 수가 0, 1 또는 4인 경우, 전환 함수는 블록에 있는 모든 세포의 상태를 뒤집는다.그리고 마지막으로 살아있는 세포의 수가 정확히 3개일 경우 전환은 모든 상태를 뒤집은 다음 블록 전체를 180° 회전시킨다.이러한 연산을 결합하는 기능은 되돌릴 수 없기 때문에, 이러한 규칙에 의해 정의되는 자동화는 가역성 세포 자동이다.[3]활성 블록에서 떨어져 있는 블록의 세포는 연속적인 세대에 걸쳐 살아 있는 것과 죽은 것 사이에서 진동하기 때문에, 전 영역은 "플릭커"처럼 보일 것이다.Critter의 일부 구현에서 이 깜박임은 홀수 세대에 대한 이미지(셀 상태는 아님)를 반전시켜 제거된다.[4]

전환 함수의 대체 버전은 정확히 두 개의 활성 셀이 있는 블록에서만 상태를 뒤집고, 교대 시간 단계에서 3개의 활성 셀이 있는 블록이나 하나의 라이브 셀이 있는 블록 중 하나를 회전시킨다.원래의 전이 기능과 달리, 이것은 각 단계의 살아있는 세포 수를 보존하지만, 이미지 반전 단계가 필요 없이 기능의 원래 버전과 동등한 동적 거동을 초래한다.[2] (즉, 두 버전은 동일하며, 다른 모든 세대에 걸쳐 모든 상태를 뒤집는다.)[4]

역학

Critters 규칙에서, 가역 가능한 세포 자동화와 마찬가지로, 모든 세포가 임의로 선택한 상태를 취하는 초기 상태는 진화 과정 내내 구조화되지 않은 상태로 남아 있다.[1][3]그러나 죽은 세포의 더 큰 영역 내에 있는 작은 무작위 세포의 영역으로 시작했을 때, 생명의 글라이더와 유사한 많은 작은 패턴들이 중심 무작위 영역에서 탈출하여 서로 상호작용한다.[1][2][3]주기적인 경계 조건의 경우(세포 자동화의 전체 공간이 유한하도록) 전체 공간보다 충분히 작은 무작위 셀의 초기 장이 진동 디브리 필드를 무작위로 걸어가는 상태로 높은 확률로 이어질 것이라고 추측되었지만 입증되지는 않았다.s.[5]

콘웨이의 생활에서 글라이더의 충돌은 완전히 죽은 상태, 안정된 패턴, 또는 오실레이터를 초래할 수 있지만 크리터스에서는 이것이 가능하지 않다.대신 규칙의 가역성 때문에 두 개 이상의 글라이더가 충돌할 때마다 적어도 한 개 이상의 글라이더가 나타나는 패턴이 나타나야 하며,[1][5] 두 개의 글라이더가 대칭적으로 충돌할 때 그 결과 또한 두 개 이상의 글라이더가 충돌현장을 빠져나가는 대칭 집합이어야 한다.[1]이러한 충돌 장소를 주의 깊게 배열하는 초기 상태에서는 크리터 규칙이 당구공 컴퓨터를 시뮬레이션하도록 만들어 라이프와 마찬가지로 보편적 연산을 지원할 수 있다.[1]크래터스 법칙은 또한 무한히 다양한 주기의 오실레이터뿐만 아니라 다양한 속도의 더 복잡한 우주선을 지원할 수 있다.[2]

그 행동의 복잡함에도 불구하고, Critters는 특정한 보존 법칙과 대칭 규칙을 준수한다.예를 들어, 그리드의 특정 대각선을 따라 존재하는 셀 수의 비율은 업데이트 규칙에 의해 변경되지 않으며, 모든 크리터스 패턴의 진화 과정 내내 변하지 않는다.또한, 패턴이 한정된 수의 살아있는 세포로 시작되면 짝수 수의 스텝 후에 동일한 유한한 수의 살아있는 세포를 갖게 된다. (단계의 홀수 수가 지나면, 이 숫자는 패턴의 죽은 세포를 대신 계산한다.)[1]토폴리와 마골러스에 의해 연구된 다른 많은 가역 블록 세포 규칙과는 달리, 크리터스 규칙은 그 자체의 역이 아니기 때문에, 크리터스 패턴은 시간 역 대칭을 따르지 않지만, 오히려 시간 역전과 상태 보완의 조합 하에 대칭적이다.[3]

참조

  1. ^ a b c d e f g Margolus, Norman (1999), "Crystalline Computation", in Hey, Anthony J. G. (ed.), Feynman and Computation, Perseus Books, pp. 267–305, arXiv:comp-gas/9811002, Bibcode:1998comp.gas.11002M.
  2. ^ a b c d Marotta, Sebastian M. (2005), "Living in Critters' world", Revista Ciências Exatas e Naturais, 7 (1), archived from the original on March 19, 2012.
  3. ^ a b c d e f Toffoli, Tommaso; Margolus, Norman (1987), "12.8.2 Critters", Cellular Automata Machines: A New Environment for Modeling, MIT Press, pp. 132–134.
  4. ^ a b Margolus, Norm. "Critters Simulation". Critters Cellular Automaton. Retrieved 3 April 2022.
  5. ^ a b Virgo, Nathaniel; Ikegami, Takashi (July 2014), "There can be only one: Reversible cellular automata and the conservation of genki", Artificial Life 14: Proceedings of the Fourteenth International Conference on the Synthesis and Simulation of Living Systems, The MIT Press, doi:10.7551/978-0-262-32621-6-ch084.