This is a good article. Click here for more information.

규칙90번길

Rule 90
무작위 초기 조건이 있는 규칙 90의 시간 공간 다이어그램.픽셀의 각 행은 자동화의 구성이다. 시간은 위에서 아래로 수직으로 진행된다.

세포 자동자의 수학적 연구에서 규칙 90은 배타적 또는 기능에 기초한 기본적인 세포 자동이다.1차원 셀 배열로 구성되며, 각각 0 또는 1 값을 담을 수 있다.각 시간 단계에서 모든 값은 동시에 배타적 또는 두 인접 값으로 대체된다.[1]마틴, 오들리즈코 & 울프람(1984)은 이것을 "가장 단순한 비종교적 세포자동화"[2]라고 부르며, 스티븐 울프람의 2002년 저서 A New Kind of Science에 광범위하게 설명되어 있다.[3]

단일 라이브 셀에서 시작할 때, 규칙 90에는 시에르피에스키 삼각형 형태의 시간 공간 도표가 있다.다른 구성의 동작은 배타적 또는 기능을 사용하여 결합한 이 패턴의 복사본의 중첩으로 설명될 수 있다.미세하게 많은 수의 0이 아닌 셀만을 가진 어떤 환경설정도 결국 그 배열을 자신의 복사본으로 채우는 복제자가 된다.규칙 90이 임의의 초기 구성에서 시작되면, 규칙 90의 구성은 각 시간 단계에서 무작위로 유지된다.그것의 시간 공간 다이어그램은 크기가 다른 많은 삼각형 "창"을 형성하는데, 연속된 셀의 행이 동시에 0이 되고 그 다음 값 1을 가진 셀이 양 끝에서 점차적으로 이 행으로 이동하게 되는 패턴이다.

규칙 90에 대한 초기 연구들 중 일부는 연속된 소수들의 차이에 대한 숫자 이론의 미해결 문제인 길바테의 추측과 관련하여 만들어졌다.이 규칙은 굴드의 순서를 통해서도 다른 방식으로 숫자 이론과 연결된다.이 시퀀스는 단일 라이브 셀로 규칙 90을 시작한 후 각 시간 단계에서 0이 아닌 셀의 수를 계산한다.그것의 값은 2의 검정력이며, 지수들은 단계 번호의 이진 표현에서 0이 아닌 자릿수와 같다.규칙 90의 다른 적용에는 태피스트리 설계가 포함되었다.

규칙 90의 모든 구성에는 정확히 네 개의 이전 구성이 있으며, 한 단계 후에 주어진 구성을 구성하는 다른 구성이 있다.따라서, 콘웨이의 생명의 게임과 같은 다른 많은 세포 자동화와 대조적으로, 규칙 90에는 전임자가 없는 구성인 에덴 동산이 없다.그것은 (각 구성에는 이전 구성이 있지만) 주입은 하지 않는 셀룰러 자동화의 예를 제공한다. (이것은 동일한 후계자와 둘 이상의 구성을 가지고 있다.)규칙 90이 국소적으로 주입된다는 것은 에덴동산 정리(후계자가 같은 모든 구성은 무한한 수의 세포로 다양하다)에서 따온 것이다.

설명

규칙.

규칙 90에서 각 셀의 값은 이전 시간 단계에서 두 개의 인접 값 중 배타적 또는 두 개의 값으로 계산된다.

규칙 90은 기본적인 세포 자동이다.즉 0 또는 1의 단일 이항 값을 갖는 1차원 셀 배열로 구성된다.모든 셀에 값을 할당하는 것을 구성이라고 한다.자동화는 초기 구성이 주어지고, 그 다음, 일련의 이산 시간 단계에서 다른 구성을 통해 진행된다.각 단계에서 모든 셀은 동시에 업데이트된다.사전 지정된 규칙은 이전 값과 인접한 두 셀의 값의 함수로서 각 셀의 새로운 값을 결정한다.모든 세포는 동일한 규칙을 따르며, 이는 공식 또는 각 가능한 인접 값들의 조합에 대한 새로운 값을 지정하는 규칙 테이블로 주어질 수 있다.[1]

규칙 90의 경우, 각 셀의 새로운 값은 배타적 또는 두 인접 값이다.마찬가지로 이 특정 자동화의 다음 상태는 다음 규칙 표에 의해 관리된다.[1]

현재 패턴 111 110 101 100 011 010 001 000
중심 세포의 새로운 상태 0 1 0 1 1 0 1 0

이름 지정

규칙 90의 명칭은 스테판 울프람의 1차원 세포 자동법칙 2진법 십진법 표기법에서 유래한다.규칙의 표기법을 계산하려면 규칙 테이블의 새 상태를 단일 이진수로 연결하고 숫자를 소수점 010110102 = 90으로10 변환하십시오.[1]규칙 90은 시어피에스키가 생성하는 삼각형 모양의 특징 때문에 시어피에스키 오토매틱이라고도 불리며,[4] 올리비에 마틴-오들리츠코-울프램 세포 오토매틱은 올리비에 마틴의 초기 연구인 앤드류 M의 연구 이후부터이다. 오들리츠코와 스티븐 울프람(1984)은 이 오토매틱에 출연했다.[5]

특성.

부가성, 중첩성, 분해성

규칙 90의 구성은 서로 상호작용하지 않는 두 개의 셀 하위 집합으로 분할될 수 있다.이 두 하위 집합 중 하나는 짝수 시간 단계에서 짝수 위치에 있는 셀과 홀수 시간 단계에 있는 홀수 위치에 있는 셀로 구성된다.다른 부분집합은 홀수 시간 단계에서 짝수 위치에 있는 셀과 짝수 시간 단계에서 홀수 위치에 있는 셀로 구성된다.이 두 하위 집합 각각은 세포의 절반만 가진 세포 자동화로 볼 수 있다.[6]이러한 각 하위 집합 내의 자동화에 대한 규칙은 (시간당 절반 셀의 이동은 제외) 각 셀의 새로운 상태가 그것의 이전 상태와 그것의 오른쪽 이웃의 배타적 또는 배타적인 또 다른 기본 셀 자동인 규칙 102와 동등하다.즉, 규칙 90의 동작은 기본적으로 규칙 102의 인터리브된 두 개의 복사본의 동작과 동일하다.[7]

규칙 90과 규칙 102는 적층 세포 오토마타라고 불린다.즉, 두 개의 초기 상태가 각각의 주 또는 배타적 상태를 계산하여 결합되는 경우, 그 이후의 구성은 동일한 방식으로 결합될 것이다.보다 일반적으로, 규칙 90의 어떤 구성을 분리 비제로 셀을 가진 두 개의 하위 집합으로 분할할 수 있으며, 두 하위 집합은 별도로 진화시킬 수 있으며, 두 하위 집합의 동일한 시간 단계에서 배타적 또는 구성의 연속적인 각각의 자동 구성을 계산할 수 있다.[2]

스턴트 나무와 삼각형 클리어

묘목 숲.이것은 시간 공간 다이어그램이지만, 시간이 위쪽으로 흐르는 것이지 아래쪽으로 흐르는 것은 아니다.흥미롭게도, 다섯 번째 나무는 할 수 있음에도 불구하고 양방향으로 싹이 트지 않았다.

규칙 90 자동(교대 셀의 두 독립 하위 집합 중 하나에 해당하는 형태)은 1970년대 초에 연속된 소수들의 차이에 대한 길버테의 추측에 대한 추가적인 통찰력을 얻기 위해 조사되었다.전방차 연산자를 반복적으로 적용하여 소수에서 생성된 숫자의 삼각형에서 대부분의 값은 0 또는 2인 것으로 나타난다.특히 길버테의 추측에 의하면 이 삼각형의 각 행에서 가장 왼쪽 값이 모두 0이나 2라고 한다.삼각형의 한 행에 있는 값들의 연속적인 연속성이 모두 0 또는 2인 경우, 규칙 90을 사용하여 다음 행의 해당 부속성을 결정할 수 있다.밀러(1970년)는 숲 속의 나무 성장을 비유하여 이 규칙을 설명하면서, "기절된 나무들의 시대적 숲"이라는 주제에 대한 논문의 자격을 부여했다.이 은유에서 나무는 가치가 1인 초기 구성의 각 위치에서 자라기 시작하고, 이 나무의 숲은 동시에 자라 각 단계마다 지상의 새로운 높이로 자란다.각 시간 단계에서 0이 아닌 각 셀은 자라는 나뭇가지에 의해 점유되는 위치를 나타낸다.각각의 연속적인 시간 단계에서, 가지는 동일한 셀을 위해 경쟁하는 다른 가지가 없을 때에만 그것의 좌우로 그 위에 있는 두 개의 셀 중 하나로 자랄 수 있다.이러한 규칙에 따라 자라는 나무의 숲은 규칙 90과 정확히 같은 행동을 한다.[8]

규칙 90의 어떤 초기 구성에서든, 모든 정점들이 밀러의 은유에 나오는 나무들과 같은 나무들을 가진, 거의 하나의 나가는 가장자리를 가진 방향의 순환 그래프인 수학적 숲을 형성할 수 있다.숲에는 각 쌍(x,i)에 대한 꼭지점이 있어 i시점에서 셀 x가 0이 아니다.0시 정점에는 송신 에지가 없으며, 각각 숲에서 나무의 뿌리를 형성한다.i가 0이 아닌 각 꼭지점(x,i)에 대해 나가는 가장자리는 시간 단계 i - 1에서 x의 고유한 0이 아닌 이웃인 (x ± 1, i - 1)로 이동한다. 밀러는 이러한 숲이 평평한 하단 가장자리와 대각선으로 둘러싸인 0이 아닌 셀이 없는 시간 공간 다이어그램의 영역인 삼각 "지우기"를 개발한다는 것을 관찰했다.이러한 청결은 연속된 세포 순서가 한 번에 동시에 0이 되고, 그 다음 (나무 은유에서) 가지가 안쪽으로 자라 결국 그 순서의 세포들을 다시 덮게 되면 형성된다.[8]

무작위 초기 조건의 경우, 이런 식으로 형성된 나무들 사이의 경계선 자체가 겉보기에는 무작위적인 패턴으로 바뀌고, 나무는 종종 함께 소멸된다.그러나 그와 다른 사람들은 교대부 이론을 통해 나무들이 모두 영원히 살아 있는 초기 조건을 찾을 수 있었고, 성장의 패턴은 주기적으로 반복되며, 모든 청소는 크기에 제한을 두도록 보장받을 수 있었다.[8][9]밀러는 태피스트리의 디자인을 형성하기 위해 이러한 반복 패턴을 사용했다.밀러의 태피스트리 중 일부는 물리적 나무를 묘사하고 다른 것들은 추상적인 삼각형 패턴을 사용하여 규칙 90 자동화를 시각화한다.[8]

시에르피에스키 삼각형

규칙 90에 의해 생성된 시에르피에스키 삼각형

규칙 90의 시간 공간 다이어그램은 i번째 행이 1단계에서 자동화의 구성을 기록하는 플롯이다.초기 상태가 0이 아닌 하나의 셀을 가질 때, 이 도표는 삼각형을 더 큰 삼각형으로 결합하여 형성된 프랙탈인 시에르피에스키 삼각형의 모양을 가진다.규칙 18, 22, 26, 82, 146, 154, 210, 218 또한 하나의 셀로부터 시에르핀스키 삼각형을 생성하지만, 이들 모두가 완전히 동일하게 생성되지는 않는다.이 구조를 설명하는 한 가지 방법은 규칙 90에서 각 셀이 두 개의 이웃 또는 배타적이라는 사실을 사용한다.이것은 modulo-2 덧셈과 같기 때문에, 이것은 파스칼의 삼각형의 modulo-2 버전을 생성한다.도표는 파스칼의 삼각형이 홀수를 갖는 곳이면 1이고, 파스칼의 삼각형이 짝수를 갖는 곳이면 0이다.이것은 시에르피에스키 삼각형의 이산형이다.[1][10]

이 패턴의 각 행에 있는 살아있는 세포의 수는 2의 힘이다.ith 행에서 이 숫자는 2와k 같으며 여기서 k는 숫자 i의 이진 표현에서 0이 아닌 숫자의 수입니다.이 살아있는 세포의 수열은

1, 2, 2, 4, 4, 4, 4, 4, 8, 2, 4, 4, 4, 4, 4, 4, 4, 8, 8, 16, 2, 4, 8, 2, 4, 8, 8, 16, 2, 4, 8, 16, 8, 16, 8, 16, 16, 16, 16, 16, 16, 16, 16, 32, ... (OEIS에서 연속 A001316)

굴드의 수열로 알려져 있다.출발 구성의 단일 라이브 셀은 톱니바퀴 패턴이다.이것은 어떤 단계에서는 살아있는 세포의 수가 임의로 크게 증가하는 반면 다른 단계에서는 무한히 종종 두 개의 살아있는 세포로만 되돌아오는 것을 의미한다.이 패턴의 성장률은 규칙 90과 비슷하게 작용하는 물리적 과정을 인식하는 데 사용할 수 있는 톱니 모양의 특징적인 성장형 톱니 파형을 가지고 있다.[4]

시에르피에스키 삼각형도 규칙 90의 어떤 구성의 진화에서 보다 미묘한 방법으로 발생한다.규칙의 진화에서 임의의 시간 단계 i에서, 어떤 셀의 상태는 초기 구성에서 셀의 배타적 또는 하위 집합으로 계산될 수 있다.저 부분집합은 시에르피에스키 삼각형의 ith 행과 같은 모양을 하고 있다.[11]

복제

시에르피에스키 삼각형에서, 정수 i의 경우, 2의i 배수로 번호가 매겨진 행은 최소 2단위i 간격으로 0이 아닌 셀을 가진다.따라서 규칙 90의 첨가물 특성 때문에, 초기 구성이 폭 2보다i 작은 비제로 셀의 유한 패턴 P로 구성되는 경우, 2의i 배수로 구성되는 단계에서는 시작부터 시작까지i 최소 2단위의 간격을 두고 P의 복사본으로 구성된다.이 간격은 복사본이 서로 간섭하지 않도록 충분히 넓다.사본의 수는 시에르피에스키 삼각형의 해당 행에 있는 0이 아닌 셀의 수와 동일하다.따라서, 이 규칙에서 모든 패턴은 복제자가 된다. 즉, 그것은 구성에 걸쳐 퍼져 있는 자신의 여러 복사본을 생성하여 결국 전체 배열을 채운다.Von Neumann의 보편적 생성자, Codd의 세포자동화자, 그리고 Langton의 루프를 포함한 다른 규칙들 또한 자신을 건설하기 위한 일련의 지시들을 들고 복사함으로써 작동하는 복제자들을 가지고 있다.대조적으로, 규칙 90의 복제는 단순하고 자동적이다.[12]

전대와 에덴 동산

규칙 90에서 무한 1차원 격자 위에 모든 구성은 정확히 네 개의 이전 구성을 가지고 있다.전임자에서는 어떤 연속된 두 개의 세포가 어떤 상태 조합을 가질 수도 있지만, 일단 그 두 세포의 상태가 선택되면, 나머지 세포의 상태에 대한 하나의 일관된 선택만이 있기 때문이다.따라서 규칙 90에는 전임자가 없는 구성인 에덴동산이 없다.단일 비제로 셀(다른 모든 셀 0 포함)로 구성된 규칙 90의 구성은 비제로를 정밀하게 많이 가진 선행 셀이 없다.그러나 이 구성은 무한히 많은 비제로를 가진 전임자들을 가지고 있기 때문에 에덴 동산이 아니다.[13]

모든 구성에는 전임자가 있다는 사실은 규칙 90이 절망적이라고 말해 요약할 수 있다.각 구성을 후계자에게 매핑하는 함수는 수학적으로 추태함수다.규칙 90도 주사하지 않는다.주입 규칙에서, 두 개의 다른 구성마다 다른 후계자를 가지고 있지만, 규칙 90은 동일한 후계자를 가진 한 쌍의 구성을 가지고 있다.규칙 90은 주입이 아닌 허탈한 세포 자동화의 예를 제공한다.무어와 마이힐의 에덴 동산 정리는 모든 주입식 세포자동차는 반드시 굴절적이어야 한다는 것을 암시하지만, 이 예는 그 반전이 사실이 아님을 보여준다.[13][14]

각 구성은 한정된 수의 선행자만 가지고 있기 때문에 규칙 90의 진화는 어떤 구성의 엔트로피를 보존한다.특히, 각 셀의 상태를 무작위로 독립적으로 선택하여 무한 초기 구성을 선택하는 경우, 두 상태가 동일하게 선택될 가능성이 있는 경우, 각각의 후속 구성을 정확하게 동일한 확률 분포로 설명할 수 있다.[2]

다른 시스템에 의한 에뮬레이션

HighLife의 Bowtie 파스타 복제자(bowtie pasta replicator)는 규칙 90을 에뮬레이트하는 데 사용할 수 있는 1차원 배열이다.

많은 다른 세포 자동화와 다른 계산 시스템은 규칙 90의 동작을 모방할 수 있다.예를 들어 규칙 90의 구성은 다른 기본 셀룰러 자동 규칙 22로 변환될 수 있다.번역은 각 규칙 90 셀을 규칙 22 셀 세 개 연속하여 대체한다.규칙 90 셀 자체가 0이면 이 셀들은 모두 0이다.0이 아닌 규칙 90 셀은 1에 이어 2개의 0으로 변환된다.이러한 변환을 통해 규칙 22 자동화의 6단계마다 규칙 90 자동화의 단일 단계를 시뮬레이션한다.규칙 90의 유사한 직접 시뮬레이션도 특정 문자열 재작성 시스템과 태그 시스템 및 와이어월드를 포함한 일부 2차원 셀룰라 오토마타에서 기본 셀룰라 오토마타 규칙 45와 규칙 126에 가능하다.규칙 90도 같은 방법으로 자신을 시뮬레이션할 수 있다.규칙 90 구성의 각 셀이 첫 번째 셀 값을 포함하는 연속 셀 쌍과 두 번째 셀이 0을 포함하는 경우, 이 이중 구성은 절반의 속도로 원래 구성과 동일한 동작을 가진다.[15]

다양한 다른 세포 자동화는 복제자를 지원하는 것으로 알려져 있으며, 복제자는 그들 자신의 복제본을 만드는 패턴이며, 대부분은 규칙 90의 나무 성장 모델에서와 같은 행동을 공유한다.공간이 비어 있는 한 새로운 복사본이 복제자 패턴의 양쪽에 배치된다.그러나 두 복제자가 모두 동일한 위치에 자신을 복사하려고 하면 공백이 남게 된다.어느 경우든 복제자 자신이 소멸하여 복제본을 계속 보관한다.이러한 행동의 표준적인 예는 2차원 하이라이프 규칙의 "보티 파스타" 패턴이다.이 규칙은 콘웨이의 생명의 게임처럼 여러 가지 방법으로 작용하지만, 그런 작은 복제자는 생명에는 존재하지 않는다.자동화가 동일한 성장 패턴을 가진 복제자를 지원할 때마다, 1차원 복제자 배열은 규칙 90을 시뮬레이션하는 데 사용될 수 있다.[16]규칙 90(유한 셀 행의)은 "2x2"라고도 하는 2차원 생명체 같은 세포 자동자 B36/S125의 블록 오실레이터에 의해서도 시뮬레이션될 수 있으며, 규칙 90의 동작은 이러한 오실레이터의 가능한 기간을 특징짓는 데 사용될 수 있다.[17]

참고 항목

참조

  1. ^ a b c d e 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.
  2. ^ a b c Martin, Olivier; Odlyzko, Andrew M.; Wolfram, Stephen (1984), "Algebraic properties of cellular automata", Communications in Mathematical Physics, 93 (2): 219–258, Bibcode:1984CMaPh..93..219M, doi:10.1007/BF01223745.
  3. ^ 이 책의 색인은 규칙 90에 대한 50개 이상의 뚜렷한 하위 주제를 열거하고 있다Wolfram, Stephen (2002), A New Kind of Science, Wolfram Media.
  4. ^ a b Claussen, Jens Christian; Nagler, Jan; Schuster, Heinz Georg (2004), "Sierpinski signal generates 1/f α spectra", Physical Review E, 70 (3): 032101, arXiv:cond-mat/0308277, Bibcode:2004PhRvE..70c2101C, doi:10.1103/PhysRevE.70.032101, PMID 15524560.
  5. ^ Misiurewicz, Michał; Stevens, John G.; Thomas, Diana M. (2006), "Iterations of linear maps over finite fields", Linear Algebra and Its Applications, 413 (1): 218–234, doi:10.1016/j.laa.2005.09.002.
  6. ^ McIntosh, Harold V. (1993), Ancestors: Commentaries on "The Global Dynamics of Cellular Automata" by Andrew Wuensche and Mike Lesser (Addison-Wesley, 1992) (PDF), Instituto de Ciencias, Universidad Autónoma de Puebla.
  7. ^ Kawaharada, Akane (2014), "Ulam's cellular automaton and Rule 150", Hokkaido Mathematical Journal, 43 (3): 361–383, doi:10.14492/hokmj/1416837570, MR 3282639: "사소한 CA를 제외하고 나머지 4개의 선형 초등 CA인 Rule 60, Rule 90, Rule 102 및 Rule 150은 기본적으로 Rule 90 또는 Rule 150과 동등하다."
  8. ^ a b c d Miller, J. C. P. (1970), "Periodic forests of stunted trees", Philosophical Transactions of the Royal Society of London, Series A, Mathematical and Physical Sciences, 266 (1172): 63–111, Bibcode:1970RSPTA.266...63M, doi:10.1098/rsta.1970.0003, JSTOR 73779.
  9. ^ ApSimon, H.G.(1970년),"정기적인 숲이 최대 clearings는 크기 3의", 왕립 학회 런던의 철학 연보(PhilosophicalTransations)시리즈 A, 수학 및 물리적 과학, 266(1172년):113–121, Bibcode:1970RSPTA.266..113A, doi:10.1098/rsta.1970.0004, JSTOR 73780, ApSimon, H.G.,(1970년)"가 최대 clearings s를 점검해 보는 숲Ize n4" ≥, 철학적 거래의 왕립 협회 런던 시리즈 A, 수학 및 물리적 과학, 266(1538년):399–404, Bibcode:1970RSPSA.319..399A, doi:10.1098/rspa.1970.0185, JSTOR 73780.규칙 90에서 주기적인 구성과 비슷한 분석은 또한 울프램(2002년),p. 954년에 나타납니다.
  10. ^ 울프람(2002년), 페이지 25–26, 270–271, 870.
  11. ^ Kar, B. K.; Gupta, A.; Chaudhuri, P. Pal (1993), "On explicit expressions in additive cellular automata theory", Information Sciences, 72 (1–2): 83–103, doi:10.1016/0020-0255(93)90030-P.
  12. ^ 활동 분야, 아브라함(1969년),"복제의 모델"면 필기장은 ACM의 16개(1):178–188, doi:10.1145/321495.321509, 아모 호주, Serafino, 쿠퍼, 제럴드(1971년),"임의의 패턴의 번식을 위해 Tessellation 구조"면 필기장 컴퓨터 및 시스템 과학, 5(5):455–464, doi:10.1016(71)80009-0.울프램(1983년)(Fig.33과 주변 텍스트)또한,뿐만 아니라 활동, 아모 호주, 그리고 쿠퍼를 이유로 그는 미발행 작품에 에드워드 Fredkin에 의해 1981년에 관측 있었다고 한다가 같은 속성에 대해 언급한다.
  13. ^ a b Skyum, Sven (1975), "Confusion in the Garden of Eden", Proceedings of the American Mathematical Society, 50 (1): 332–336, doi:10.1090/S0002-9939-1975-0386350-1
  14. ^ Sutner, Klaus (1991), "De Bruijn Graphs and Linear Cellular Automata" (PDF), Complex Systems, 5: 19–30. 울프람(2002), 페이지 959–960.마틴, 오들리츠코 & 울프람(1984)은 주기적인 경계 조건을 가진 유한한 세포 집합에 대해 동일한 규칙의 전임자에 대한 유사한 분석을 제공한다.
  15. ^ 울프람(2002), 페이지 269–270, 666–667, 701–702, 1117.
  16. ^ Griffeath, David (1996), "Recipe for the week of July 1–7: Replicating Skeeters", The Primordial Soup Kitchen.
  17. ^ Johnston, Nathaniel (2010), "The B36/S125 "2x2" Life-like cellular automaton", in Adamatzky, Andrew (ed.), Game of Life Cellular Automata, Springer-Verlag, pp. 99–114, arXiv:1203.1644, Bibcode:2010golc.book...99J, doi:10.1007/978-1-84996-217-9_7.

외부 링크