규칙 30

Rule 30
이 기사는 세포 자동화에 관한 것이다.미국 연방법원의 규칙은 연방 민사소송법 및 증빙(법률)을 참조한다.
외관이 규칙 30과 유사한 코너스 직물 껍질.[1]

규칙 30은 1983년 스티븐 울프램이 도입한 기본적인 세포자동화다.[2]울프람의 분류 체계를 사용하는 규칙 30은 3급 규칙으로, 주기적이고 혼란스러운 행동을 보여준다.

이 규칙은 단순하고 잘 정의된 규칙으로부터 복잡하고 겉보기에는 무작위적인 패턴을 만들어내기 때문에 특히 흥미롭다.이 때문에 울프람은 규칙 30, 그리고 일반적으로 세포 자동화가 어떻게 간단한 규칙이 자연에서 복잡한 구조와 행동을 만들어 내는지를 이해하는 열쇠라고 믿는다.예를 들어, 규칙 30과 유사한 패턴이 널리 퍼져있는 콘 달팽이종 코너스 섬유 껍질에 나타난다.규칙 30은 또한 마티매타에서 난수 생성기로 사용되어 왔으며,[3] 암호화에 사용할 수 있는 가능한 스트림 암호로도 제안되었다.[4][5]

규칙 30은 규칙 집합을 설명하는 가장 작은 울프램 코드이기 때문에(아래 설명에 따라) 그렇게 이름이 붙는다.규칙 30의 거울 이미지, 보완물, 거울보완물에는 각각 울프람 코드 86, 135, 149가 있다.

규칙 집합

울프램의 모든 초기 세포 자동자에서는 각 세포가 어떤 초기 상태에 있는 2개의 상태만을 가진 무한 1차원 세포 자동 세포 배열이 고려된다.분리된 시간 간격에서, 모든 세포는 그것의 현재 상태와 두 이웃의 상태에 기초하여 자연적으로 상태를 변화시킨다.규칙 30의 경우, 자동화의 다음 상태를 관리하는 규칙 집합은 다음과 같다.

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

해당 공식은 [left_cell XOR (central_cell OR right_cell)]이다.2진수, 000111102 = 30이기 때문에 규칙 30이라고 불린다.

다음 도표는 자신의 이웃의 이전 상태를 기준으로 색칠된 세포로 만들어진 패턴을 보여준다.어두운 색은 "1"을 나타내고 밝은 색은 "0"을 나타낸다.시간은 수직축을 따라 증가한다.

Cellular Automata running Wolfram-rule-30.svg

구조 및 특성

상태 1(검은색으로 표시)을 가진 단일 셀이 상태 0(흰색)을 가진 셀에 둘러싸인 초기 상태에서 다음과 같은 패턴이 나타난다.

Rule30-256-rows.png
규칙 30 셀룰러 오토매틱

여기서 수직축은 시간을 나타내며, 이미지의 수평 단면은 패턴 진화의 특정 지점에서 배열된 모든 세포의 상태를 나타낸다.이 구조에는 흰색 삼각형의 빈번한 출현과 왼쪽의 잘 정의된 줄무늬 패턴 등 여러 모티브가 있으나 전체적으로 볼 수 있는 패턴은 없다. 생성 시 검은색 셀 수는 시퀀스에 의해 지정됨

1, 3, 3, 6, 4, 9, 5, 12, 7, 12, 11, 14, 12, 19, 13, 22, 15, 19, ... (OEIS에서 연속 A070952)

그리고 대략 입니다

혼돈

울프람은 규칙 30을 주로 시각적 외관에 근거하여 혼돈으로 분류했으며,[citation needed] 이후 데바니와 크누드슨이 제안한 혼돈에 대한 보다 엄격한 정의를 충족하는 것으로 나타났다.특히, Devaney의 기준에 따르면, 규칙 30은 초기 조건에 대한 민감한 의존성을 나타낸다(소수의 셀에서만 다른 두 개의 초기 구성이 급속하게 분산됨), 그 주기적 구성은 구성의 공간에 있어 모든 구성의 공간에 밀도 있다(p가 있다).세포의 어떤 유한 패턴이 있는 시대적 구성), 그리고 그것은 혼합되고 있다(어떤 두 개의 유한 패턴의 경우, 결국 다른 패턴을 포함하는 구성으로 이어지는 하나의 패턴을 포함하는 구성이 있다).크누드슨의 기준에 따르면, 민감한 의존성을 표시하며, 고밀도 궤도(결국 어떤 유한한 세포 패턴도 표시하는 초기 구성)가 있다.규칙의 무질서한 행동에 대한 이러한 특성화는 규칙 30의 보다 단순하고 쉽게 검증할 수 있는 속성인 순열적인 것으로서, 즉 위치 i에서 두 가지 구성 C와 D가 단일 셀의 상태가 다를 경우, 한 단계 후에 새로운 구성이 셀 i + 1에서 바뀐다는 것을 의미한다.[6]

적용들

난수생성

위의 이미지에서 분명히 알 수 있듯이, 규칙 30은 임의 입력으로 합리적으로 간주될 수 있는 어떤 것이 없음에도 불구하고 무작위로 보인다.Stephen Wolfram은 그것의 중심 기둥을 유사수치 생성기로 사용할 것을 제안했다; 그것은 무작위성에 대한 많은 표준 테스트를 통과했고, Wolfram은 무작위 정수를 만들기 위해 Mathematica 제품에서 이전에 이 규칙을 사용했다.[7]

Sipper와 Tomassini는 무작위 번호 생성기 Rule 30이 다른 세포 자동 기반 생성기와 비교하여 모든 규칙 열에 적용될 때 카이 제곱 테스트에서 불량한 동작을 보인다는 것을 보여주었다.[8]저자들은 또 "규칙 30 CA에서 비교적 낮은 결과를 얻은 것은 울프램이 고려한 단일 시퀀스가 아닌 병렬로 생성된 N 랜덤 시퀀스를 고려했기 때문일 수 있다"[9]고 우려했다.

장식

케임브리지 북부 철도역 피복재 상세

케임브리지 북부 철도역은 규칙 30(또는 흑백 역전의 경우 동등하게 규칙 135)의 진화를 보여주는 건축 패널로 장식되어 있다.[10]이 디자인은 케임브리지 수학자 존 호튼 콘웨이가 연구한 다른 세포 자동인 콘웨이의 게임 오브 라이프(Game of Life)에서 영감을 받은 것으로 건축가에 의해 설명되었지만, 실제로는 라이프(Life)를 기반으로 한 것은 아니다.[11][12]

프로그래밍

셀 값이 하나 이상의 컴퓨터 워드 내의 비트로 표현되는 경우, 상태 업데이트는 비트 연산(bitwise operation)을 통해 신속하게 수행될 수 있다.여기 C++에 표시됨:

#include <stdint.h> #include <아이오스트림> 인트로 본래의() {   uint64_t 주 = 1u << 31;   을 위해 (인트로 i=0 ; i<32 ; ++i) {     을 위해 (인트로 j=64 ; j-- ;) {       찌꺼기::뻐드렁니가 나다 << 마를 뜨다(주 >> j & 1 ? '1' : '-');     }     찌꺼기::뻐드렁니가 나다 << '\n';     주 = (주 >> 1) ^ (주   주 << 1);   } }

참고 항목

참조

  1. ^ Stephen Coombes (February 2009). "The Geometry and Pigmentation of Seashells" (PDF). www.maths.nottingham.ac.uk. University of Nottingham. Retrieved 2013-04-10.
  2. ^ Wolfram, S. (1983). "Statistical mechanics of cellular automata". Rev. Mod. Phys. 55 (3): 601–644. Bibcode:1983RvMP...55..601W. doi:10.1103/RevModPhys.55.601.
  3. ^ "Random Number Generation". Wolfram Mathematica 8 Documentation. Retrieved 31 December 2011.
  4. ^ Wolfram, S. (1985). "Cryptography with cellular automata". Proceedings of Advances in Cryptology - CRYPTO '85. Lecture Notes in Computer Science 218, Springer-Verlag. p. 429. doi:10.1007/3-540-39799-X_32.
  5. ^ Meier, Willi; Staffelbach, Othmar (1991). "Analysis of pseudo random sequences generated by cellular automata". Advances in Cryptology: Proc. Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT '91. Lecture Notes in Computer Science 547, Springer-Verlag. p. 186. doi:10.1007/3-540-46416-6_17.
  6. ^ Cattaneo, Gianpiero; Finelli, Michele; Margara, Luciano (2000). "Investigating topological chaos by elementary cellular automata dynamics". Theoretical Computer Science. 244 (1–2): 219–241. doi:10.1016/S0304-3975(98)00345-4. MR 1774395.
  7. ^ Lex Fridman (2018-03-02), MIT AGI: Computational Universe (Stephen Wolfram), archived from the original on 2021-12-19, retrieved 2018-03-07
  8. ^ Sipper, Moshe; Tomassini, Marco (1996). "Generating parallel random number generators by cellular programming". International Journal of Modern Physics C. 7 (2): 181–190. Bibcode:1996IJMPC...7..181S. doi:10.1142/S012918319600017X.
  9. ^ 의 6페이지
  10. ^ Wolfram, Stephen (June 1, 2017), "Oh My Gosh, It's Covered in Rule 30s!", Stephen Wolfram's blog
  11. ^ Lawson-Perfect, Christian (May 23, 2017), "Right answer for the wrong reason: cellular automaton on the new Cambridge North station", The Aperiodical
  12. ^ Purtill, Corinne. "A UK train station's tribute to a famous mathematician got everything right except his math". Quartz. Retrieved 2017-06-12.

외부 링크