셀 오토마톤

Cellular automaton
Gosper's Glider Gun이 셀 오토매틱 Conway의 Game of[1] Life에서 "글라이더"를 만들어 냅니다.

셀 오토마톤(cellular automaton, 줄임말)CA)는 오토마타 이론에서 연구된 계산의 이산 모델이다.셀 오토마타는 셀 공간, 테셀레이션 오토마타, 균질 구조, 셀 구조, 테셀레이션 구조 및 반복 [2]배열이라고도 합니다.셀룰러 오토마타는 물리학, 이론 생물학, 미세구조 모델링 등 다양한 분야에서 응용되고 있습니다.

셀 오토마톤은 셀의 규칙적인 그리드로 구성되며, 각각은 (커플링된 맵 격자와 대조적으로) on과 off와 같은 유한한 수의 상태 중 하나에 있습니다.그리드는 유한한 수의 차원에 속할 수 있습니다.각 셀에 대해 네이버라고 불리는 셀 세트가 지정된 셀에 대해 정의됩니다.각 셀에 상태를 할당하여 초기 상태(시간 t = 0)를 선택합니다.셀의 현재 상태 및 근방의 셀 상태에 관해 각 셀의 새로운 상태를 결정하는 일정한 규칙(일반적으로 수학적 함수)[3]에 따라 새로운 세대가 생성된다(t를 1씩 진행).일반적으로 세포 상태를 업데이트하기 위한 규칙은 각 세포에 대해 동일하며 시간에 따라 변하지 않으며 확률적 세포 자동화와 비동기 세포 자동화와 같은 예외가 알려져 있지만 전체 그리드에 [4]동시에 적용된다.

이 개념은 1940년대 스타니슬라프 울람과 존 폰 노이만이 로스 알라모스 국립 연구소에서 동시대인이던 시절에 처음 발견했어요.1950년대와 1960년대에 걸쳐 일부 사람들에 의해 연구되었지만, 1970년대와 2차원 세포 자동 장치인 콘웨이의 삶의 게임이 되어서야 이 주제에 대한 관심이 학계를 넘어 확장되었다.1980년대에 Stephen Wolfram은 1차원 세포 오토마타, 즉 그가 기본 세포 오토마타라고 부르는 것에 대한 체계적인 연구에 참여했습니다; 그의 연구 조수 Matthew Cook은 이러한 규칙들 중 하나가 튜링 완전하다는 것을 보여주었습니다.

Wolfram에서 개략적으로 설명한 세포 자동화의 주요 분류는 1에서 4까지 번호가 매겨진다.패턴이 일반적으로 균질성으로 안정되는 오토마타, 패턴이 거의 안정되거나 진동하는 구조로 진화하는 오토마타, 패턴이 혼란스러워 보이는 형태로 진화하는 오토마타, 패턴이 매우 복잡해져 안정된 국소 구조를 가지는 오토마타입니다.이 마지막 클래스는 계산적으로 보편적이거나 튜링 기계를 시뮬레이션할 수 있는 것으로 생각됩니다.특별한 유형의 세포자동화(cellar automata)는 가역적이며, 단일 구성만이 후속 구성으로 직접 연결되며, 개별 세포의 미래 가치는 인접 세포 그룹의 총 가치에 달려 있다.셀룰러 오토마타는 생물학적 시스템 및 화학적 시스템을 포함한 다양한 실제 시스템을 시뮬레이션할 수 있습니다.

개요

빨간색 셀은 파란색 셀의 무어 근처입니다.
붉은 세포는 푸른 세포에 해당하는 폰 노이만 지역입니다.range-2 "cross neighbor"에는 분홍색 셀도 포함됩니다.

2차원 셀 오토마톤을 시뮬레이션하는 한 가지 방법은 셀이 따라야 할 일련의 규칙과 함께 무한한 그래프 용지를 사용하는 것입니다.각 사각형은 "셀"이라고 불리며 각 셀은 검은색과 흰색의 두 가지 가능한 상태를 가지고 있습니다.셀의 주변은 가까운 셀입니다.보통 인접한 셀입니다.가장 흔한 두 가지 유형의 이웃은 폰 노이만 이웃과 무어 [5]이웃이다.전자는 최초의 세포 자동 이론가의 이름을 따서 명명되었으며, 직교적으로 인접한 [5]4개의 세포로 구성되어 있다.후자는 대각선으로 인접한 4개의 [5]셀뿐만 아니라 폰 노이만 근방을 포함한다.이러한 셀과 그 Moore 부근의 경우 512(= 29)개의 패턴을 사용할 수 있습니다.규칙 테이블은 가능한 512개의 패턴 각각에 대해 다음 시간 간격에 중앙 셀이 검은색인지 흰색인지를 나타냅니다.콘웨이의 'Game of Life'는 이 모델의 인기 버전입니다.또 다른 일반적인 근린 유형은 확장 폰 노이만 근린으로, 각 직교 방향에서 가장 가까운 두 개의 셀을 포함하며, [5]총 8개의 근린이다.이러한 규칙 체계에 대한 일반적인 방정식은 k이며ks, 여기서 k는 셀의 가능한 상태의 수이고, s는 셀의 다음 [6]상태를 결정하기 위해 사용되는 인접 셀(계산되는 셀 자체를 포함한다)의 수이다.따라서 무어 근방이 있는 2차원 시스템에서 가능한 총 오토마타 수는 2 또는29 1.34×10입니다154.

보통 우주의 모든 셀은 다른 상태에 있는 한정된 수의 셀을 제외하고 같은 상태에서 시작한다고 가정합니다. 상태 값의 할당을 [7]구성이라고 합니다.보다 일반적으로, 때때로 우주가 주기적인 패턴으로 시작하며, 한정된 수의 세포만이 그 패턴을 위반한다고 가정합니다.후자의 가정은 1차원 셀 오토마타에서 일반적이다.

토러스, 트로이덜 모양

셀룰러 오토마타는 종종 무한 그리드가 아닌 유한 그리드에서 시뮬레이션됩니다.2차원에서 우주는 무한 평면 대신 직사각형일 것이다.유한 그리드의 분명한 문제는 가장자리에 있는 셀을 처리하는 방법입니다.처리 방법은 그리드 내의 모든 셀 값에 영향을 미칩니다.가능한 방법 중 하나는 셀의 값을 일정하게 유지하는 것입니다.또 다른 방법은 이러한 셀에 대해 네이버를 다르게 정의하는 것입니다.인접 라우터가 적다고 할 수 있지만, 엣지에 있는 셀에 대해 새로운 규칙을 정의해야 합니다.이들 셀은 보통 트로이덜 배열로 취급된다.하나가 위에서 벗어나면 하나는 아래쪽에 있는 대응하는 위치에 있고, 하나는 왼쪽에서 벗어나면 오른쪽에 있습니다.(이것은 기본적으로 무한 주기 타일링을 시뮬레이트하고, 편미분 방정식 분야에서는 때때로 주기적 방정식이라고 불립니다.)경계 조건).이것은 직사각형의 왼쪽과 오른쪽 가장자리를 테이핑하여 튜브를 형성한 다음 튜브의 위쪽과 아래쪽 가장자리를 테이핑하여 토러스(도넛 모양)를 형성하는 것으로 시각화할 수 있습니다.다른 차원의 우주도 비슷하게 취급됩니다.이를 통해 인근 지역과의 경계 문제가 해결되지만 모듈식 산술 함수를 사용하여 쉽게 프로그래밍할 수 있다는 것도 장점입니다.예를 들어 아래와 같은 1차원 셀 오토마톤에서 셀it x의 근방은 {xi−1t−1, xit−1, xi+1t−1}이며, 여기서 t는 시간 단계(수직), i는 1세대의 지수(수평)이다.

역사

스타니슬라프 울람은 1940년대 로스앨러모스 국립연구소에서 일하면서 단순한 격자망을 [8]모델로 크리스탈의 성장을 연구했다.동시에, Los Alamos의 Ulam의 동료인 John von Neumann은 자기 복제 시스템의 [9]문제를 연구하고 있었다.Von Neumann의 초기 디자인은 한 로봇이 다른 로봇을 만든다는 개념에 기초했다.이 디자인은 운동학적 [10][11]모형으로 알려져 있습니다.그가 이 디자인을 개발하면서, 폰 노이만은 자기 복제 로봇을 만드는 것의 큰 어려움과 복제품을 만들 수 있는 "부분의 바다"를 로봇에 제공하는 데 드는 큰 비용을 깨닫게 되었다.노이만은 1948년 [9]힉슨 심포지엄에서 오토마타의 일반적이고 논리적인 이론이라는 제목의 논문을 썼다.Ulam은 자기 [12][13]복제의 환원주의적 모델을 만들기 위해 이산 시스템을 사용할 것을 제안한 사람이다.Nils Aall Barricelli는 이러한 인공 생명체의 모델에 대한 많은 초기 탐사를 수행했다.

존 폰 노이만, 로스 알라모스 ID 배지

울람과 폰 노이만은 1950년대 말에 액체 운동을 계산하는 방법을 만들었다.이 방법의 구동 개념은 액체를 이산 단위의 그룹으로 간주하고 이웃의 행동을 [14]바탕으로 각각의 움직임을 계산하는 것이었다.이렇게 해서 세포 자동화의 첫 번째 시스템이 탄생했다.울람의 격자망처럼 폰 노이만의 셀룰러 오토마타는 알고리즘에 의해 구현되는 2차원이다.그 결과 세포 오토마톤 내에서 작동하는 범용 복사기 및 생성자는 작은 이웃(접촉하는 세포만 이웃하고 폰 노이만의 세포 오토마타는 직교 세포만 해당), [15]세포당 29개의 상태를 가지고 있었다.Von Neumann은 특정 패턴이 [15]20만 개의 세포 구성을 설계함으로써 주어진 세포 우주 내에서 끝없는 복제품을 만들 수 있다는 실존 증거를 제시했습니다.이 디자인은 테셀레이션 모델로 알려져 있으며 폰 노이만 유니버설 [16]컨스트럭터라고 불립니다.

또한 1940년대에 Norbert Wiener와 Arturo Rosenblueth는 세포 자동화의 [17]특징을 가진 흥분성 매체의 모델을 개발했습니다.그들의 특별한 동기는 심장 시스템의 충동 전도에 대한 수학적인 기술이었다.그러나 신호가 전파되는 매체는 연속적이고 파장은 [17][18]곡선이기 때문에 이러한 모델은 셀 오토마톤이 아닙니다.1978년 J. M. 그린버그와 S. P. 헤이스팅스에 의해 흥분성 매체의 진정한 세포 오토마톤 모델이 개발되고 연구되었습니다. 그린버그-헤이스팅스 세포 오토마톤을 참조하십시오.Wiener와 Rosenblueth의 원작은 많은 통찰력을 포함하고 있으며, 심장 부정맥과 흥분성 [19]시스템에 대한 최신 연구 출판물에서 계속 인용되고 있습니다.

1960년대에 셀 오토마타는 동적 시스템의 특정 유형으로 연구되었고 기호 역학의 수학 분야와의 연결이 처음으로 확립되었다.1969년, 구스타프 A. Hedlund는 세포 오토마타의 수학적 연구를 위한 중요한 논문으로 여전히 간주되고 있는 이 관점에[20] 따라 많은 결과를 정리했다.가장 근본적인 결과는 커티스의 특성화입니다.이동 공간의 연속된 내형성 집합으로서 세포 자동의 글로벌 규칙 집합의 Hedlund-Lyndon 정리.

1969년 독일의 컴퓨터 선구자 콘라드 추세는 우주의 물리적 법칙은 본질적으로 별개이며, 전 우주가 하나의 세포 자동화에 대한 결정론적 계산의 결과물이라고 제안하면서 그의 책인 "공간 계산"을 출판했다. "주스의 이론"은 디지털 [21]물리학이라고 불리는 연구 분야의 기초가 되었다.

또한 1969년 컴퓨터 과학자 Alvy Ray Smith는 일반 컴퓨터 등급으로서 CA의 첫 수학적 처리인 Cellular Automata Theory에 대한 스탠포드 박사 학위 논문을 완성했습니다.많은 논문이 이 논문에서 나왔다.그는 무어를 폰 노이만 이웃으로 만드는 방법과 어떤 이웃을 폰 노이만 [22]이웃으로 만드는 방법 등 다양한 형태의 이웃들이 동등하다는 것을 보여주었다.그는 2차원 CA가 계산 보편적이라는 것을 증명하고, 1차원 CA를 도입했으며, 그것들도 단순한 [23]이웃에도 계산 보편적이라는 것을 보여주었다.그는 복잡한 von Neumann 건설 보편성의 증명(그리고 자기 재생 기계)을 1차원 [24]CA의 계산 보편성의 결과로 반영하는 방법을 보여주었다.폰 노이만의 CA에 관한 독일어판 소개로, 그는 10년 이상 많은 나라의 많은 작가들에 의해 수십 건의 논문 참조와 함께 이 분야에 대한 조사를 썼고, 현대 CA [25]연구자들에 의해 종종 간과되었다.

1970년대에 Game of Life라는 이름의 2차원 셀룰러 오토마톤은 특히 초기 컴퓨팅 커뮤니티에서 널리 알려지게 되었습니다.존 콘웨이에 의해 발명되고 마틴 가드너에 의해 Scientific American [26]기사에서 대중화된 그것의 규칙은 다음과 같습니다.

  1. 살아있는 이웃이 두 명 미만인 살아있는 세포는 마치 인구 부족으로 인한 것처럼 죽는다.
  2. 살아있는 이웃이 두세 명 있는 살아있는 세포는 다음 세대로 살아간다.
  3. 이웃이 3명 이상 있는 살아있는 세포는 인구 과잉으로 죽는다.
  4. 살아있는 이웃이 정확히 세 개인 죽은 세포는 생식을 통해 살아있는 세포가 됩니다.

단순함에도 불구하고, 시스템은 명백한 무작위성과 질서 사이에서 오락가락하는 인상적인 다양한 동작을 달성합니다.Game of Life의 가장 명백한 특징 중 하나는 그리드를 통해 스스로 움직이는 셀 배열인 글라이더가 자주 발생하는 것입니다.글라이더가 상호 작용하여 계산을 수행하도록 오토마톤을 배열하는 것은 가능하며, 많은 노력 끝에 생명의 게임이 보편적인 튜링 기계를 [27]에뮬레이트할 수 있다는 것이 증명되었다.그것은 주로 오락적인 주제로 여겨졌고 1970년대 [28]초반에는 삶의 게임의 특수성과 몇 가지 관련 규칙을 조사하는 것 외에는 거의 후속 작업이 수행되지 않았다.

스티븐 울프람은 열역학 [29]제2법칙에 위배되는 복잡한 패턴이 자연에서 어떻게 형성되는지를 고려한 후 독립적으로 세포 자동화에 대해 연구하기 시작했다.그의 연구는 처음에는 신경망과 [29]같은 모델링 시스템에 대한 관심으로 촉발되었다.그는 1983년 [2][29]6월에 초등 셀 오토마타를 조사하는 현대 물리학 리뷰(Reviews of Modern Physics investigation element cellar automata, 특히 규칙 30)에 첫 논문을 발표했다.이러한 간단한 규칙들의 행동의 예상치 못한 복잡성은 울프람이 자연계의 복잡성이 유사한 [29]메커니즘에 의한 것일 수 있다고 의심하게 만들었다.그러나 그의 연구는 셀룰러 오토마타가 신경망을 [29]모델링하는 데 서툴다는 것을 깨닫게 했다.게다가 이 기간 동안 울프램은 내재적 무작위성과 계산 불가확성의 [30]개념을 공식화했고 규칙 110은 보편적일 수 있다고 제안했는데, 이것은 나중에 울프램의 연구 조수 매튜 쿡에 의해 1990년대에 [31]증명되었다.

분류

Wolfram은 A New Kind of Science와 1980년대 중반의 여러 논문에서 셀룰러 오토마타와 다른 몇 가지 간단한 컴퓨터 모델을 그들의 행동에 따라 나눌 수 있는 4가지 클래스로 정의했다.세포 자동화에 관한 초기 연구는 특정 규칙에 대한 패턴 유형을 식별하려는 경향이 있었지만, 울프람의 분류는 규칙 자체를 분류하는 첫 번째 시도였다.클래스는 복잡성의 순서로 다음과 같습니다.

  • 클래스 1: 거의 모든 초기 패턴이 안정적이고 균일한 상태로 빠르게 진화합니다.초기 패턴의 랜덤성은 [32]모두 사라집니다.
  • 클래스 2: 거의 모든 초기 패턴은 안정적이거나 진동하는 구조로 빠르게 진화합니다.초기 패턴의 랜덤성 중 일부는 제외될 수 있지만 일부는 남아 있습니다.초기 패턴의 로컬 변경은 로컬로 [32]유지되는 경향이 있습니다.
  • 클래스 3: 거의 모든 초기 패턴은 의사 랜덤 또는 카오스 방식으로 진화한다.안정된 구조물은 주위의 소음에 의해 빠르게 파괴됩니다.초기 패턴에 대한 로컬 변경은 [32]무한히 확산되는 경향이 있습니다.
  • 클래스 4: 거의 모든 초기 패턴이 복잡하고 흥미로운 방식으로 상호작용하는 구조로 진화하며,[33] 장기간에 걸쳐 생존할 수 있는 국지적 구조가 형성된다.클래스 2 타입의 안정 또는 진동 구조가 최종적인 결과일 수 있지만, 초기 패턴이 비교적 단순한 경우에도 이 상태에 도달하기 위해 필요한 단계의 수는 매우 클 수 있다.초기 패턴에 대한 로컬 변경은 무기한 확산될 수 있습니다.Wolfram은 전부는 아니더라도 많은 클래스 4 셀 오토마타가 범용 연산을 할 수 있다고 추측했다.이것은 규칙 110과 Conway의 Game of Life에서 증명되었습니다.

이러한 정의는 본질적으로 질적이며 해석의 여지가 있다.Wolfram에 따르면, "...거의 모든 일반적인 분류 체계에서는 필연적으로 하나의 정의에 의해 하나의 클래스에 할당되고 다른 정의에 의해 다른 클래스에 할당되는 경우가 있습니다.셀룰러 오토마타도 마찬가지입니다.때로는 규칙이 있습니다.울프람의 [34]분류는 셀 오토마타 [35]출력의 압축 길이 군집화와 경험적으로 일치했다.

Wolfram의 분류에 영감을 받아 공식적으로 엄격한 클래스에서 셀룰러 오토마타를 분류하려는 시도가 여러 번 있었다.예를 들어, Culik과 Yu는 잘 정의된 3개의 클래스(그리고 이것들 중 어느 것도 일치하지 않는 오토마타에 대한 4번째 클래스)를 제안했는데, 이것은 때때로 Culik-Yu 클래스라고 불리며, 이러한 클래스들의 멤버쉽은 [36][37][38]결정되지 않는 것으로 판명되었다.울프램의 클래스 2는 안정적인(고정점)[39] 규칙과 진동하는(주기적) 규칙의 두 하위 그룹으로 분할할 수 있습니다.

4가지 동적 시스템이 있다는 생각은 (1) 열역학적 평형에 있는 시스템, (2) 공간/시간적으로 균일한 시스템, (3) 카오스 시스템, (4) 분산 스트럭을 가진 복잡한 불균형 시스템 등 4가지 종류의 열역학적 시스템을 식별한 노벨상 수상 화학자 일리야 프리고긴으로부터 비롯되었다.튜어(Nicolis 논문의 그림 1 참조)[40]

리버서블

주요 기사:가역 세포 오토마톤

셀 오토마톤은 셀 오토마톤의 모든 현재 구성에 대해 정확하게 하나의 과거 구성(프리이미지)[41]이 있는 경우 가역할 수 있습니다.셀룰러 오토마톤을 구성에 대한 함수 매핑 구성으로 생각한다면, 가역성은 [41]이 기능이 비사사적이라는 것을 의미합니다.세포 자동화가 가역적인 경우, 시간 역행동은 세포 자동화로도 설명할 수 있다. 이 사실은 커티스의 결과이다.Hedlund-Lyndon 정리, 세포 [42][43]자동화의 위상학적 특성.모든 구성에 프리이미지가 포함되어 있지 않은 셀룰러 오토마타의 경우 프리이미지가 없는 구성을 Garden of Eden [44]패턴이라고 합니다.

1차원 셀 오토마타의 경우 규칙이 가역인지 [45][46]불가역인지를 결정하기 위한 알려진 알고리즘이 있다.단, 2차원 이상의 셀 오토마타에 대해서는 가역성을 결정할 수 없다.즉, 오토마톤 규칙을 입력으로 받아들이고 오토마톤이 가역 가능한지 여부를 정확하게 판단할 수 있는 알고리즘이 없다.자코카리의 증명은 왕타일의 [47]타일 문제와 관련이 있다.

가역 셀 오토마타는 열역학의 법칙을 따르기 때문에 가스 및 유체 역학과 같은 물리적 현상을 시뮬레이션하기 위해 종종 사용됩니다.이러한 셀룰러 오토마타는 되돌릴 수 있도록 특별히 구성된 규칙을 가지고 있다.이러한 시스템은 토마소 토폴리, 노먼 마골루스 그리고 다른 사람들에 의해 연구되었다.몇 가지 기술을 사용하여 알려진 역순으로 가역 셀 오토마타를 명시적으로 구성할 수 있습니다.2차 세포 오토마톤과 블록 세포 오토마톤은 공통적인 것으로, 두 가지 모두 어떤 식으로든 세포 오토마톤의 정의를 수정하는 것을 포함한다.이러한 오토마타는, 상기의 정의를 엄밀하게 만족시키는 것은 아니지만, 충분히 큰 근방과 상태수를 가지는 종래의 셀 오토마타에 의해서 에뮬레이트 될 수 있기 때문에, 종래의 셀 오토마타의 서브셋이라고 생각할 수 있다.반대로, 모든 가역 세포 오토마톤은 블록 세포 오토마톤에 [48][49]의해 에뮬레이트 될 수 있는 것으로 나타났다.

전체주의

셀 오토마타의 특별한 클래스는 전체론적 셀 오토마타입니다.각 세포totalistic 휴대 automaton에 주는 수(일반적으로 정수 값은 유한 집합에서)가 세포의 시간 t에서 값 방면(아마도 세포 그 자체를 포함해)에 있는 세포들은 시점의 값의 합에 달려 있고 있t − 1.[50][51]만약, 국가의 세포에서 시간 t에 따라 부랑자.그 찾았다고시간 t - 1에 있는 자신의 상태와 그 이웃의 총합은 세포 자동화를 적절하게 외부 [51]전체주의라고 부른다.Conway's Game of Life는 셀 값이 0과 1인 외부 전체주의 셀 오토마톤의 예입니다. Life와 같은 무어 근린 구조를 가진 외부 전체주의 셀 [52][53]오토마타는 때때로 생명과 같은 셀 오토마타라고 불립니다.

관련 오토마타

세포자동화 개념에는 많은 가능한 일반화가 있다.

정사각형 대신 육각형 셀을 기반으로 하는 셀 오토마톤(규칙 34/2)

한 가지 방법은 직사각형(입방체 등) 그리드가 아닌 다른 것을 사용하는 것입니다.예를 들어, 평면이 일반 육각형으로 타일링되어 있는 경우, 그 육각형은 셀로 사용될 수 있습니다.많은 경우 결과 셀룰러 오토마타는 특별히 설계된 주변 및 규칙을 가진 직사각형 그리드를 가진 것과 동등하다.또 다른 변형으로는 펜로즈 [54]타일과 같이 그리드 자체를 불규칙하게 만드는 방법이 있습니다.

또한 규칙은 결정론적이라기보다는 확률론적일 수 있다.이러한 셀 오토마타는 확률적 셀 오토마타라고 불립니다.확률론적 규칙은 시간 t의 각 패턴에 대해 중앙 셀이 시간 t + 1에서 각 가능한 상태로 이행할 확률을 제공한다.때로는 간단한 규칙이 사용된다. 예를 들어, "규칙은 생명의 게임이지만, 각 시간 단계에서 각 셀이 반대 색상으로 이행할 확률은 0.001%이다."

주변이나 규칙은 시간이나 공간에 따라 변경될 수 있습니다.예를 들어, 처음에 셀의 새로운 상태는 수평으로 인접한 셀에 의해 결정될 수 있었지만, 다음 세대는 수직 셀을 사용할 것이다.

세포 오토마타에서 세포의 새로운 상태는 다른 세포의 새로운 상태에 영향을 받지 않는다.예를 들어, 2x2 셀 블록이 그 자체와 그 옆에 있는 셀에 의해 결정되도록 변경할 수 있습니다.

연속 오토마타가 있습니다.이들은 전체론적 셀 오토마타와 비슷하지만 규칙과 상태가 이산적인 대신(예: 표, 상태 {0,1,2} 사용), 연속 함수가 사용되며 상태가 연속적으로 된다(일반적으로 [0,1]의 값).로케이션의 상태는 한정된 수의 실수입니다.특정 세포 오토마타는 이러한 방식으로 액체 패턴의 확산을 일으킬 수 있습니다.

연속적인 공간 오토마타는 연속적인 위치를 가지고 있다.로케이션의 상태는 한정된 수의 실수입니다.시간 또한 연속적이며, 상태는 미분 방정식에 따라 진화한다.한 가지 중요한 예는 화학 반응이 얼룩말과 [55]표범의 반점에 어떻게 줄무늬를 만들 수 있는지를 설명하기 위해 Alan Turing이 제안한 반응 확산 텍스처입니다.이것들은 셀룰러 오토마타에 의해 근사될 때, 그들은 종종 유사한 패턴을 산출합니다.MacLennan[1]은 연속 공간 자동화를 계산 모델로 간주합니다.

연속 공간 오토마타의 알려진 예들이 있는데,[56] 이것은 생명의 게임에서 글라이더와 유사한 전파 현상을 나타낸다.

그래프 리라이트 오토마타는 그래프 리라이트 [57]시스템에 기반한 셀룰러 오토마타의 확장입니다.

기본 셀 오토마타

주요 기사:소세포 오토마톤

가장 단순한 비사소한 세포 자동화는 1차원이며, 각 세포에 2개의 가능한 상태를 가지며, 그 양쪽에 인접한 세포로 정의된다.1개의 셀과 그 2개의 네이버는 3개의 셀의 네이버를 형성하기 때문에 네이버에는3 2=8개의 패턴이 있습니다.규칙은 각 패턴에 대해 다음 세대에서 셀이 1인지 0인지를 결정하는 것으로 구성됩니다.그러면8 2 = 256개의 [6]규칙이 있습니다.

1D 셀룰러 오토마톤의 규칙이 다음 세대를 결정하는 방법에 대한 애니메이션입니다.

이 256개의 셀룰러 오토마타는 일반적으로 울프램 코드에 의해 참조됩니다.울프램은 각 규칙에 0부터 255까지의 번호를 부여하는 표준 명명 규칙을 발명했습니다.다수의 논문이 이 256개의 셀룰러 오토마타를 분석하고 비교했습니다.규칙 30과 규칙 110 셀룰러 오토마타는 특히 흥미롭다.다음 이미지는 시작 구성이 0으로 둘러싸인 1(각 이미지의 맨 위)로 구성된 경우의 각 이력을 보여 줍니다.픽셀의 각 행은 자동화의 역사에서 세대를 나타내며 t=0이 맨 위 행이다.각 픽셀은 0의 경우 흰색, 1의 경우 검은색으로 표시됩니다.

규칙 30


규칙 30 셀 오토마톤

전류 패턴 111 110 101 100 011 010 001 000
중앙 셀의 새 상태 0 0 0 1 1 1 1 0

규칙 30은 클래스 3 동작을 나타냅니다.즉, 표시된 것과 같은 단순한 입력 패턴조차도 혼란스럽고 랜덤해 보이는 이력을 발생시킵니다.

규칙 110


규칙 110 셀 오토마톤

전류 패턴 111 110 101 100 011 010 001 000
중앙 셀의 새 상태 0 1 1 0 1 1 1 0

규칙 110은 생명의 게임과 마찬가지로 울프램이 클래스 4라고 부르는 완전히 무작위적이거나 완전히 반복적이지 않은 행동을 보여줍니다.국지적인 구조물은 복잡하게 보이는 다양한 방식으로 나타나고 상호작용합니다.1994년 울프램의 연구 보조로서 새로운 종류의 과학을 개발하는 과정에서, 매튜 쿡은 이러한 구조물들 중 일부가 보편성을 뒷받침할 만큼 충분히 풍부하다는 것을 증명했다.이 결과는 규칙 110이 매우 단순한 1차원 시스템이기 때문에 특정 동작을 수행하기 위해 엔지니어링이 어렵기 때문에 흥미롭다.따라서 이 결과는 클래스 4 시스템이 본질적으로 보편적일 가능성이 높다는 울프램의 관점을 크게 뒷받침한다.쿡은 1998년 Santa Fe Institute의 셀룰러 오토마타 컨퍼런스에서 자신의 증거를 제시했지만 울프램은 A New Kind Science [58]출판 전에 그 증거를 발표하기를 원하지 않았기 때문에 그 증거가 컨퍼런스 진행에 포함되지 않도록 막았다.쿡의 증거는 쿡이 그것을 고안한 지 10년이 지난 2004년 울프램의 저널 '복잡한 시스템' (Vol. 15, No.1)에 마침내 발표되었습니다.규칙 110은 가장 작은 범용 튜링 [59]기계의 기초가 되어 왔다.

규칙 공간

기본 셀룰러 오토마톤 규칙은 8비트로 지정되며, 모든 기본 셀룰러 오토마톤 규칙은 8차원 단위 하이퍼큐브의 정점에 위치하는 것으로 간주할 수 있다.이 유닛 하이퍼큐브는 셀룰러 오토마톤 규칙 공간입니다.next-diaged cellular automata의 경우 규칙은 2=32비트로5 지정되며, cellular automaton 규칙 공간은 32차원 단위 하이퍼큐브이다.두 규칙 사이의 거리는 하이퍼큐브의 가장자리를 따라 첫 번째 규칙을 나타내는 한 정점과 다른 규칙을 나타내는 다른 정점에서 이동하는 데 필요한 단계 수로 정의할 수 있습니다.이 규칙 대 규칙 거리는 해밍 거리라고도 합니다.

셀룰러 오토마톤 규칙 공간은 유사한 동적 거동을 가진 규칙이 서로 "가까운"지 여부에 대한 질문을 할 수 있게 한다.2차원 평면에 고차원 하이퍼큐브를 그래픽으로 그리는 것은 여전히 어려운 작업이며, 하이퍼큐브 내의 규칙의 대략적인 로케이터 중 하나는 기본 규칙의 경우 8비트 문자열(또는 다음 인접 규칙의 경우 32비트 문자열)의 숫자입니다.규칙 공간의 이러한 슬라이스에 다른 Wolfram 클래스의 규칙을 그려보면 클래스 1 규칙은 비트1의 수가 적어 공간의 한 영역에 배치되는 경향이 있는 반면 클래스 3 규칙은 비트1의 [39]비율(50%)이 높은 경향이 있습니다.

더 큰 셀룰러 오토마톤 규칙 공간의 경우 클래스4 규칙이 클래스1 규칙과 클래스3 [60]규칙 사이에 배치되어 있는 것을 알 수 있습니다.이러한 관찰은 혼돈의 가장자리에 대한 기초이며 열역학에서의 위상 전이를 연상시킵니다.

적용들

생물학

원뿔 섬유는 껍질에 [61]세포 자동 무늬를 나타낸다.
상세정보: 자연계의 패턴

세포 자동화에 의해 여러 생물학적 과정이 발생하거나 시뮬레이션될 수 있습니다.

단순한 상태 공간을 가진 셀 오토마타에 의해 모델링된 생물학적 현상의 예는 다음과 같다.

  • 코누스속과 심비올라속과 같은 일부 조개껍질 패턴은 천연 세포 오토마타에 의해 생성된다.색소 세포는 껍데기의 입술을 따라 좁은 띠 안에 있습니다.각 세포는 인접한 색소세포의 활성화 및 억제 활성에 따라 색소를 분비하며 수학규칙의 [61]자연판을 따른다.세포 띠는 천천히 자라면서 껍질에 색깔 있는 패턴을 남깁니다.예를 들어, 널리 퍼진 종인 코너스 섬유는 울프람의 규칙 30 세포 오토마톤과 [61]유사한 패턴을 가지고 있다.
  • 식물은 세포 자동화 메커니즘을 통해 가스의 섭취와 손실을 조절한다.잎에 있는 각각의 기공은 [62]세포 역할을 한다.
  • 두족류 피부의 이동파 패턴은 확장 또는 수축된 [63]색소체에 대응하는 2상태, 2차원 세포 오토마타로 시뮬레이션할 수 있다.
  • 임계값 오토마타는 뉴런을 시뮬레이션하기 위해 발명되었으며 인식과 학습과 같은 복잡한 행동을 [64]시뮬레이션할 수 있습니다.
  • 섬유아세포는 각각의 섬유아세포가 [65]그 이웃과만 상호작용하기 때문에 세포 자동세포와 유사성이 있다.

또한 에이전트 속도의 명시적 모델링을 필요로 하는 생물학적 현상(예를 들어 집단 세포 이동에 관여하는 현상)은 생물학적 격자-가스 세포 오토마타와 같은 보다 복잡한 상태 공간과 규칙을 가진 세포 오토마타에 의해 모델화될 수 있다.여기에는 다음과 같은 의학적으로 매우 중요한 현상이 포함된다.

화학

벨루소프-자보틴스키 반응은 세포 자동화에 의해 시뮬레이션될 수 있는 시공간 화학 발진기입니다.1950년대 A. M. Zhabotinsky는 말론산, 산성 브롬산염, 세릭소금의 혼합물로 이루어진 얇고 균질한 층이 함께 섞였을 때, 그리고 방해받지 않고, 동심원과 나선과 같은 매혹적인 기하학적 패턴이 매체에 전파된다는 것을 발견했습니다.A. K. [69]듀드니는 사이언티픽 아메리칸 1988년 8월호 컴퓨터 레크리에이션 섹션에서 독일 빌레펠트 대학의 마틴 게르하르트와 하이케 슈스터에 의해 개발된 세포 자동화에[70] 대해 논의했다.이 오토마톤은 벨루소프-자보틴스키 반응과 유사한 파동 패턴을 생성합니다.

물리

격자 가스 오토마톤의 시각화.개별 픽셀의 회색 음영은 해당 픽셀의 가스 입자 밀도(0 ~ 4)에 비례합니다.이 가스는 폐쇄된 공간을 만들기 위해 반사체 역할을 하는 노란 세포 껍질로 둘러싸여 있다.

확률론적 셀 오토마타는 유체 역학 및 위상 천이와 같은 현상을 연구하기 위해 통계 및 응축 물질 물리학에서 사용됩니다.Ising 모델은 각 셀이 "업" 및 "다운"이라는 두 가지 상태 중 하나에 있을 수 있는 프로토타입 모델로서 자석의 이상적인 표현입니다.모델의 파라미터를 조정함으로써 동일한 상태에 있는 셀의 비율을 변화시켜 강자석이 가열되었을 때 어떻게 소자되는지를 설명할 수 있다.또한, 소자상 전이를 연구한 결과는 액체를 기체로 증발시키는 것과 같은 다른 상 전이로 옮겨질 수 있습니다. 이러한 편리한 교차 적용성을 [71][72]보편성이라고 합니다.2차원 Ising 모델과 그 보편성 클래스의 다른 시스템에서의 위상 전이는 특히 흥미로웠다. 왜냐하면 그것은 [73]심도 있게 이해하기 위해 등각장 이론이 필요하기 때문이다.물리학에서 중요한 다른 셀 오토마타로는 유체 흐름을 시뮬레이션하는 격자 가스 오토마타가 있습니다.

컴퓨터 사이언스, 코딩,

셀룰러 오토마톤 프로세서는 CA 개념의 물리적 구현으로, 정보를 계산적으로 처리할 수 있습니다.처리요소는 동일한 셀의 규칙적인 그리드에 배치된다.그리드는 보통 2차원 또는 3차원의 정사각형 타일링 또는 테셀레이션입니다. 다른 타일링은 가능하지만 아직 사용되지 않았습니다.셀 상태는 인접 네이버셀과의 상호작용에 의해서만 결정됩니다.멀리 [74]있는 세포와 직접 통신할 수 있는 방법은 없습니다.이러한 셀룰러 오토매틱프로세서 어레이 구성의 하나가 수축기 어레이입니다.셀의 상호작용은 전하, 자기, 진동(양자 눈금의 소리) 또는 물리적으로 유용한 다른 수단을 통해 이루어질 수 있습니다.요소 사이에 와이어가 필요 없도록 여러 가지 방법으로 이를 수행할 수 있습니다.이는 오늘날 대부분의 컴퓨터에서 사용되는 프로세서(von Neumann 설계)와 매우 다른데, 와이어를 통해 원격 소자와 통신할 수 있는 소자를 가진 섹션으로 나뉩니다.

규칙 30은 원래 암호화에 사용할 수 있는 블록 암호로 제안되었습니다.2차원 셀 오토마타는 의사난수 [75]발생기 구축에 사용할 수 있다.

공개키 암호화에 대해 셀룰러 오토마타가 제안되었습니다.단방향 함수는 역행렬을 찾기 어려운 유한 CA의 진화입니다.이 법칙에 따라 누구나 미래의 상태를 쉽게 계산할 수 있지만 이전 상태를 계산하는 것은 매우 어려운 것으로 보인다.셀룰러 오토마타는 설계 오류 수정 [76]코드에도 적용되었습니다.

셀룰러 오토마타로 해결할 수 있는 다른 문제는 다음과 같습니다.

창작예술과 음악

상세 정보:창조적 예술

셀룰러 오토마타는 비디오[77] [79]게임의 생성 음악, 진화 음악 구성[78] 및 절차적 지형 생성에 사용되어 왔습니다.

특정 규칙

특정 유형의 셀룰러 오토마타는 다음과 같습니다.

「 」를 참조해 주세요.

메모들

  1. ^ Daniel Dennett(1995), 다윈의 위험한 생각, 펭귄 북스, ISBN978-0-14-016734-4, ISBN0-14-016734-X
  2. ^ a b 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. Archived from the original on 21 September 2013. Retrieved 28 February 2011.
  3. ^ Toffoli, Tommaso; Margolus, Norman (1987). Cellular Automata Machines: A New Environment for Modeling. MIT Press. p. 27. ISBN 9780262200608.
  4. ^ Schiff, Joel L. (2011). Cellular Automata: A Discrete View of the World. Wiley & Sons, Inc. p. 40. ISBN 9781118030639.
  5. ^ a b c d Kier, Seybold, Cheng 2005, 15페이지
  6. ^ a b 비알리니키 비룰라, 비알리니카 비룰라 2004, 페이지 9
  7. ^ 쉬프 2011, 페이지 41
  8. ^ 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.
  9. ^ a b 쉬프 2011, 페이지 1
  10. ^ 존 폰 노이만, "자동자동차의 일반적이고 논리적인 이론"입니다. Jeffress, ed., Crainal Mechanism in Behavior – The Hixon Symposium, John Wiley & Sons, New York, 1951년 페이지 1~31.
  11. ^ 시서 1955; 192:6 (에라타Kemeny, John G. (1955). "Man viewed as a machine". Sci. Am. 192 (4): 58–67. Bibcode:1955SciAm.192d..58K. doi:10.1038/scientificamerican0455-58.)
  12. ^ 쉬프 2011, 페이지 3
  13. ^ 일라친스키 2001, 페이지 xxix
  14. ^ 비알리니키 비룰라, 비알리니카 비룰라 2004, 페이지 8
  15. ^ a b 울프램 2002, 876페이지
  16. ^ von Neumann, John; Burks, Arthur W. (1966). Theory of Self-Reproducing Automata. University of Illinois Press.
  17. ^ a b 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 (3): 205–65. PMID 20245817.
  18. ^ Letichevskii, A. A.; Reshodko, L. V. (1974). "N. Wiener's theory of the activity of excitable media". Cybernetics. 8 (5): 856–864. doi:10.1007/bf01068458. S2CID 121306408.
  19. ^ 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. S2CID 4348759.
  20. ^ Hedlund, G. A. (1969). "Endomorphisms and automorphisms of the shift dynamical system". Math. Systems Theory. 3 (4): 320–3751. doi:10.1007/BF01691062. S2CID 21803927.
  21. ^ 쉬프 2011, 페이지 182
  22. ^ Smith, Alvy Ray. "Cellular Automata Complexity Trade-Offs" (PDF).
  23. ^ Smith, Alvy Ray. "Simple Computation-Universal Cellular Spaces" (PDF).
  24. ^ Smith, Alvy Ray. "Simple Nontrivial Self-Reproducing Machines" (PDF).
  25. ^ Smith, Alvy Ray. "Introduction to and Survey of Cellular Automata or Polyautomata Theory" (PDF).
  26. ^ Gardner, Martin (1970). "Mathematical Games: The fantastic combinations of John Conway's new solitaire game "life"". Scientific American. 223 (4): 120–123. doi:10.1038/scientificamerican1070-120.
  27. ^ 폴 채프먼입니다라이프 유니버설 컴퓨터http://www.igblan.free-online.co.uk/igblan/ca/ 2002년 11월
  28. ^ 웨인라이트 2010, 페이지 16
  29. ^ a b c d e 울프램 2002, 페이지 880
  30. ^ 울프램 2002, 881페이지
  31. ^ Mitchell, Melanie (4 October 2002). "Is the Universe a Universal Computer?". Science. 298 (5591): 65–68. doi:10.1126/science.1075073. S2CID 122484855.
  32. ^ a b c 일라친스키 2001, 12페이지
  33. ^ 일라친스키 2001, 13페이지
  34. ^ 울프람 2002, 페이지 231
  35. ^ Zenil, Hector (2010). "Compression-based investigation of the dynamical properties of cellular automata and other systems" (PDF). Complex Systems. 19 (1): 1–28. doi:10.25088/ComplexSystems.19.1.1. S2CID 15364755.
  36. ^ G. Cattaneo; E. Formenti; L. Margara (1998). "Topological chaos and CA". In M. Delorme; J. Mazoyer (eds.). Cellular automata: a parallel model. Springer. p. 239. ISBN 978-0-7923-5493-2.
  37. ^ Burton H. Voorhees (1996). Computational analysis of one-dimensional cellular automata. World Scientific. p. 8. ISBN 978-981-02-2221-5.
  38. ^ Max Garzon (1995). Models of massive parallelism: analysis of cellular automata and neural networks. Springer. p. 149. ISBN 978-3-540-56149-1.
  39. ^ a b Li, Wentian; Packard, Norman (1990). "The structure of the elementary cellular automata rule space" (PDF). Complex Systems. 4: 281–297. Retrieved 25 January 2013.
  40. ^ Nicolis (1974). "Dissipative Structures, Catastrophes, and Pattern Formation: A Bifurcation Analysis" (PDF). PNAS. 71 (7): 2748–2751. Bibcode:1974PNAS...71.2748N. doi:10.1073/pnas.71.7.2748. PMC 388547. PMID 16592170. Retrieved 25 March 2017.
  41. ^ a b 카리, 자르코 1991, 379페이지
  42. ^ Richardson, D. (1972). "Tessellations with local transformations". J. Comput. Syst. Sci. 6 (5): 373–388. doi:10.1016/S0022-0000(72)80009-6.
  43. ^ Margenstern, Maurice (2007). Cellular Automata in Hyperbolic Spaces – Tome I, Volume 1. Archives contemporaines. p. 134. ISBN 978-2-84703-033-4.
  44. ^ 쉬프 2011, 페이지 103
  45. ^ Amoroso, Serafino; Patt, Yale N. (1972). "Decision Procedures for Surjectivity and Injectivity of Parallel Maps for Tessellation Structures". J. Comput. Syst. Sci. 6 (5): 448–464. doi:10.1016/s0022-0000(72)80013-8.
  46. ^ Sutner, Klaus (1991). "De Bruijn Graphs and Linear Cellular Automata" (PDF). Complex Systems. 5: 19–30.
  47. ^ Kari, Jarkko (1990). "Reversibility of 2D cellular automata is undecidable". Physica D. 45 (1–3): 379–385. Bibcode:1990PhyD...45..379K. doi:10.1016/0167-2789(90)90195-U.
  48. ^ Kari, Jarkko (1999). "On the circuit depth of structurally reversible cellular automata". Fundamenta Informaticae. 38: 93–107. doi:10.3233/FI-1999-381208.
  49. ^ Durand-Lose, Jérôme (2001). "Representing reversible cellular automata with reversible block cellular automata". Discrete Mathematics and Theoretical Computer Science. AA: 145–154. Archived from the original on 15 May 2011.
  50. ^ 울프램 2002, 페이지 60
  51. ^ a b Ilachinski, Andrew (2001). Cellular automata: a discrete universe. World Scientific. pp. 44–45. ISBN 978-981-238-183-5.
  52. ^ "생활과 같은 셀룰러 오토마톤"이라는 문구는 적어도 Barral, Chaté & Manneville(1992)로 거슬러 올라갑니다.그는 이 문구를 반드시 2차원이 아닌 외부의 전체주의적 오토마타를 지칭하기 위해 더 넓은 의미로 사용했습니다.여기에서 주어진 보다 구체적인 의미는 Adamatzky(2010)의 여러 장에서 사용되었다.참조:
  53. ^ 엡스타인 2010, 72~73페이지
  54. ^ Jacob Aron. "First gliders navigate ever-changing Penrose universe". New Scientist.
  55. ^ Murray, J. D. (2003). Mathematical biology (3rd ed.). New York: Springer. ISBN 0-387-95228-4.
  56. ^ Pivato, M: "RealLife:Large than life cellular automata", 이론 컴퓨터 과학, 372 (1), 2007년 3월, 페이지 46–68
  57. ^ Tomita, Kohji; Kurokawa, Haruhisa; Murata, Satoshi (2009). "Graph-Rewriting Automata as a Natural Extension of Cellular Automata". Adaptive Networks. Understanding Complex Systems. pp. 291–309. doi:10.1007/978-3-642-01284-6_14. ISBN 978-3-642-01283-9.
  58. ^ Giles, Jim (2002). "What Kind of Science is This?". Nature. 417 (6886): 216–218. Bibcode:2002Natur.417..216G. doi:10.1038/417216a. PMID 12015565. S2CID 10636328.
  59. ^ Weinberg, Steven (24 October 2002). "Is the Universe a Computer?". The New York Review of Books. Retrieved 12 October 2012.
  60. ^ Wentian Li; Norman Packard; Chris G Langton (1990). "Transition phenomena in cellular automata rule space". Physica D. 45 (1–3): 77–94. Bibcode:1990PhyD...45...77L. CiteSeerX 10.1.1.15.2786. doi:10.1016/0167-2789(90)90175-O.
  61. ^ a b c Coombs, Stephen (15 February 2009), The Geometry and Pigmentation of Seashells (PDF), pp. 3–4, archived from the original (PDF) on 7 January 2013, retrieved 2 September 2012
  62. ^ Peak, West; Messinger, Mott (2004). "Evidence for complex, collective dynamics and emergent, distributed computation in plants". Proceedings of the National Academy of Sciences. 101 (4): 918–922. Bibcode:2004PNAS..101..918P. doi:10.1073/pnas.0307811100. PMC 327117. PMID 14732685.
  63. ^ "Archived copy" (PDF). Archived from the original (PDF) on 25 July 2010. Retrieved 14 September 2008.{{cite web}}: CS1 maint: 제목으로 아카이브된 복사(링크)
  64. ^ 일라친스키 2001, 275쪽
  65. ^ Yves Bouligand (1986). Disordered Systems and Biological Organization. pp. 374–375.
  66. ^ Ilina, Olga; Gritsenko, Pavlo G.; Syga, Simon; Lippoldt, Jürgen; La Porta, Caterina A. M.; Chepizhko, Oleksandr; Grosser, Steffen; Vullings, Manon; Bakker, Gert-Jan; Starruß, Jörn; Bult, Peter (September 2020). "Cell–cell adhesion and 3D matrix confinement determine jamming transitions in breast cancer invasion". Nature Cell Biology. 22 (9): 1103–1115. doi:10.1038/s41556-020-0552-6. ISSN 1465-7392. PMC 7502685. PMID 32839548.
  67. ^ Reher, David; Klink, Barbara; Deutsch, Andreas; Voss-Böhme, Anja (11 August 2017). "Cell adhesion heterogeneity reinforces tumour cell dissemination: novel insights from a mathematical model". Biology Direct. 12 (1): 18. doi:10.1186/s13062-017-0188-z. ISSN 1745-6150. PMC 5553611. PMID 28800767.
  68. ^ Hatzikirou, H.; Basanta, D.; Simon, M.; Schaller, K.; Deutsch, A. (1 March 2012). "'Go or Grow': the key to the emergence of invasion in tumour progression?". Mathematical Medicine and Biology. 29 (1): 49–65. doi:10.1093/imammb/dqq011. ISSN 1477-8599. PMID 20610469.
  69. ^ A. K. Dewdney, 잡동사니 기계는 파문을 일으킨다, Scientific American, 페이지 104, 1988년 8월.
  70. ^ Gerhardt, M.; Schuster, H. (1989). "A cellular automaton describing the formation of spatially ordered structures in chemical systems". Physica D. 36 (3): 209–221. Bibcode:1989PhyD...36..209G. doi:10.1016/0167-2789(89)90081-x.
  71. ^ Sethna, James P. (2008). Statistical Mechanics: Entropy, Order Parameters, and Complexity. Oxford University Press. ISBN 978-0-198-56677-9. OCLC 845714772.
  72. ^ Kardar, Mehran (2007). Statistical Physics of Fields. Cambridge University Press. ISBN 978-0-521-87341-3. OCLC 920137477.
  73. ^ Cappelli, Andrea; Zuber, Jean-Bernard (2010). "A-D-E Classification of Conformal Field Theories". Scholarpedia. 5 (4): 10314. arXiv:0911.3242. Bibcode:2010SchpJ...510314C. doi:10.4249/scholarpedia.10314. S2CID 18207779.
  74. ^ Muhtaroglu, Ali (August 1996). "4.1 Cellular Automaton Processor (CAP)". Cellular Automaton Processor Based Systems for Genetic Sequence Comparison/Database Searching. Cornell University. pp. 62–74.
  75. ^ 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. doi:10.1109/12.888056.
  76. ^ Chowdhury, D. Roy; Basu, S.; Gupta, I. Sen; Chaudhuri, P. Pal (June 1994). "Design of CAECC - cellular automata based error correcting code". IEEE Transactions on Computers. 43 (6): 759–764. doi:10.1109/12.286310.
  77. ^ 버라스톤, 데이브, 어니스트 에드먼즈."생성적인 일렉트로닉 음악과 소닉 아트에서의 셀룰러 오토마타: 역사적이고 기술적인 리뷰"디지털 크리에이티브 16.3 (2005) : 165 ~185 。
  78. ^ 미란다, 에두아르도 레크"진화하는 셀룰러 오토마타 음악: 음향 합성부터 작곡까지."2001년 '뮤지컬 어플리케이션용 인공생명모델 워크숍'의 진행.2001.
  79. ^ Ashlock, Daniel; Kreitzer, Matthew (2020). "Evolving Diverse Cellular Automata Based Level Maps". Proceedings of 6th International Conference in Software Engineering for Defence Applications. Advances in Intelligent Systems and Computing. Vol. 925. pp. 10–23. doi:10.1007/978-3-030-14687-0_2. ISBN 978-3-030-14686-3. S2CID 85562837.

레퍼런스

외부 링크

Wikimedia Commons에는 셀룰러 오토마타와 관련된 미디어가 있습니다.
Wikibooks는 다음과 같은 토픽에 관한 책을 가지고 있습니다: Cellular Automata
  • Berto, Francesco; Tagliabue, Jacopo. "Cellular Automata". In Zalta, Edward N. (ed.). Stanford Encyclopedia of Philosophy.
  • Mirek의 Cellebration – MCell 및 MJCell 셀룰러 오토마타 탐색 소프트웨어 및 규칙 라이브러리를 무료로 이용할 수 있습니다.소프트웨어는 다수의 1D 및 2D 규칙을 지원합니다.이 사이트에서는 광범위한 규칙 어휘와 규칙 예가 로드된 많은 이미지 갤러리를 제공합니다.MCell은 Windows 응용 프로그램이고 MJCell은 Java 애플릿입니다.소스 코드를 사용할 수 있습니다.
  • 최신 셀룰러 오토마타– Java 애플릿을 탑재한 라이브 컬러 2D 셀룰러 오토마타의 인터랙티브한 전시.여기에는 기존 규칙, 가역 규칙, 육각형 규칙, 다단계 규칙, 프랙탈 생성 규칙 및 패턴 생성 규칙이 포함되어 있습니다.보기 위해 수천 개의 규칙이 제공됩니다.무료 소프트웨어를 사용할 수 있습니다.
  • 셀룰러 공간에서의 자기 리플리케이션 루프– Java 애플릿에 의한 자기 리플리케이션 루프 표시
  • 10개 이상의 셀룰러 오토마타 애플릿 컬렉션(Monash University의 Virtual Lab)
  • Golly는 von Neumann, Nobili, GOL 및 기타 셀룰러 오토마타의 많은 시스템을 지원합니다.Tomas Rokicki와 Andrew Trevorrow가 개발했습니다.현재 이용 가능한 시뮬레이터 중 폰 노이만 타입의 자기 복제를 증명할 수 있는 유일한 시뮬레이터입니다.
  • 푸리에 라이프 - 랜덤 셀 필드에서 자발적으로 나타나는 자기 복제 패턴을 나타내는 규칙 모음입니다.대부분의 규칙은 자가 복제를 감지하기 위해 푸리에 변환을 사용하는 알고리즘을 사용하여 발견되었습니다.
  • Wolfram Atlas – 다양한 유형의 1차원 셀 오토마타 지도책입니다.
  • 콘웨이 라이프
  • 생명 시뮬레이터에서 생성된 최초의 복제 생물
  • 참조 모델의 수학 - CA에 대한 일반 튜토리얼, 인터랙티브 애플릿, 자유 코드 및 기초 물리학 모델로서의 CA에 대한 리소스를 특징으로 합니다.
  • Fourmilab 셀룰러 오토마타 연구소
  • Busy Box(3D, 리버서블, SALT 아키텍처 CA)
  • Cellular Automata Repository (CA 연구원, 이력 링크, 무료 소프트웨어, 서적 등)
  • 256 규칙의 셀룰러 오토마타 (256 기본 규칙의 단일 시트 인터랙티브 시각화)
  • Petri - Go 셀룰러 오토마타 프레임워크