규칙110번길
Rule 110 |
규칙 110 세포 자동(흔히 규칙 110으로 불림)은 안정성과 혼돈의 경계에서 흥미로운 행동을 하는 기본적인 세포 자동이다.이런 점에서 콘웨이의 '삶의 게임'과 비슷하다.라이프와 마찬가지로 특정 반복 배경 패턴이 있는 규칙 110은 튜링 완료로 알려져 있다.[1]이는 원칙적으로 모든 계산이나 컴퓨터 프로그램을 이 자동화를 사용하여 시뮬레이션할 수 있음을 의미한다.
정의
기본적인 세포 자동에서는 0초와 1초의 1차원 패턴이 간단한 규칙 집합에 따라 진화한다.패턴의 포인트가 신세대에서 0이 될지 1이 될지는 그 두 이웃의 포인트뿐만 아니라 그 현재 가치에 달려 있다.
규칙 110 자동 실행에는 다음과 같은 규칙 집합이 있다.
| 현재 패턴 | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| 중앙 셀의 새 상태 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
"규칙 110"이라는 이름은 이 규칙이 이진수 01101110으로 요약될 수 있다는 사실에서 유래되었다. 이진수로 해석하면 이것은 소수값 110에 해당한다.
역사
2004년에 매튜 쿡은 특정한 반복적인 배경 패턴을 가진 규칙 110이 튜링 완료, 즉 유니버설 연산이 가능하다는 증거를 발표했는데, 스티븐 울프람은 1985년에 추측했다.[1]쿡은 울프람의 책 A New Kind of Science가 출간되기 전 산타페 연구소 컨퍼런스 CA98에서 자신의 증거를 제시했다.이로 인해 울프람 리서치사와의 비공개 합의에 근거한 법적 사건이 발생하였다.울프램 리서치는 몇 년 동안 쿡의 증명서 발행을 막았다.[2]
흥미로운 특성
88개의 가능한 고유한 초등 셀룰러 오토마타 중에서, 몇 가지 유사한 규칙에 대한 증거가 간단한 골관(예: 규칙 110의 수평 반영인 규칙 124)으로 따라야 하지만, 규칙 110은 튜링의 완전성이 입증된 유일한 것이다.규칙 110은 거의 틀림없이 가장 단순하게 알려진 튜링 완결 시스템이다.[1][3]
규칙 110은 생명의 게임과 마찬가지로 울프람이 '4급 행동'이라고 부르는 것을 보여주는데, 이것은 완전히 안정적이지도 않고 완전히 혼란스럽지도 않다.국부적 구조는 복잡한 방식으로 나타나고 상호 작용한다.[4]
매튜 쿡은 주기 태그 시스템, 2태그 시스템, 그리고 튜링 머신을 연속적으로 모방함으로써 범용 연산을 지원할 수 있는 규칙 110을 증명했다.튜링 머신의 테이프는 단수 숫자로 암호화되어 있기 때문에 마지막 단계는 기하급수적인 시간 오버헤드를 가지고 있다.네리와 우즈(2006)는 2태그 시스템을 시계방향 튜링 머신으로 대체하고 다항식 오버헤드를 갖는 다른 구조를 제시했다.[5]
보편성의 증거
매튜 쿡은 A New Kind of Science 출판 전에 열린 산타페 연구소 컨퍼런스에서 규칙 110의 보편성에 대한 자신의 증거를 제시했다.울프램 리서치는 이번 발표가 쿡의 고용주와의 비공개 합의를 위반했다고 주장했으며, 쿡의 논문을 공개된 회의 절차에서 제외한 법원 명령을 받았다.그럼에도 불구하고 쿡의 증거의 존재는 알려지게 되었다.그의 증명에 대한 관심은 그것의 방법, 특히 그것의 건설의 기술적 세부사항에서 비롯되지 않았다.[6]쿡의 증거의 성격은 A New Kind of Science의 규칙 110에 대한 논의와는 상당히 다르다.쿡은 그 이후 그의 완전한 증거를 제시하는 논문을 썼다.[1]
쿡은 규칙 110이 범용(또는 튜링 완료)이라고 알려진 또 다른 계산 모델인 순환 태그 시스템을 모방하기 위해 규칙을 사용할 수 있다는 것을 보여줌으로써 범용(또는 튜링 완료)임을 증명했다.그는 먼저 규칙 110 우주에서 무한 반복 패턴으로 건설될 수 있는 다수의 우주선을 분리했다.그런 다음 그는 이러한 구조들의 조합이 연산에 이용될 수 있는 방식으로 상호작용하는 방법을 고안했다.
규칙 110호의 우주선
규칙 110의 유니버설 머신의 기능은 무한히 반복되는 배경 패턴 안에 한정된 수의 국부화된 패턴을 내장할 것을 요구한다.배경 무늬는 14개의 세포 폭이며 7번 반복할 때마다 정확히 반복된다.패턴은 00010011011111 입니다.
규칙 110 범용 기계에서는 세 가지 지역화된 패턴이 특히 중요하다.그것들은 반복적인 배경 패턴으로 둘러싸인 아래 이미지에 나타나 있다.가장 왼쪽의 구조는 오른쪽 두 세포로 이동하며 3대에 한 번씩 반복된다.그것은 위에 주어진 배경 패턴으로 둘러싸인 수열 0001110111과 이 수열의 서로 다른 두 개의 진화를 포함한다.
그림에서 시간은 위에서 아래로 흐른다: 맨 위 줄은 초기 상태를 나타내며, 다음 시간에는 각각 상태를 나타낸다.
중심 구조는 왼쪽 8개의 세포가 이동하며 30대마다 반복된다.그것은 위에 주어진 배경 패턴으로 둘러싸인 1001111 시퀀스와 이 시퀀스의 29가지 다른 진화로 구성된다.
가장 오른쪽 구조물은 정지 상태를 유지하며 7대마다 반복된다.그것은 위에 주어진 배경 패턴으로 둘러싸인 111 시퀀스와 이 시퀀스의 5가지 다른 진화로 구성된다.
아래는 번역(왼쪽)이 아닌 다른 상호작용을 하지 않고, 상호작용을 하지 않고 서로 통과해 제3구조(오른쪽)를 형성하는 첫 번째 구조물을 형성하기 위해 상호작용을 하는 모습(오른쪽).
규칙 110에는 수많은 다른 우주선들이 있지만, 그것들은 보편성 증명에서만큼 두드러지게 특징지지는 않는다.
순환 태그 시스템 구축
순환 태그 시스템 기계는 다음과 같은 세 가지 주요 구성 요소를 가지고 있다.
- 정지해 있는 데이터 문자열;
- 오른쪽에서 시작하여 왼쪽으로 이동하는 무한 반복적인 일련의 유한 생산 규칙
- 왼쪽에서 시작하여 오른쪽으로 이동하는 무한 반복 시계 펄스.
이 부품들 사이의 초기 간격은 가장 중요하다.셀룰러 자동화가 주기 태그 시스템을 구현하기 위해서는, 그 안에 포함된 다양한 국부적 구조가 고도로 질서 있게 상호작용하도록 자동화의 초기 조건을 신중하게 선택해야 한다.
주기 태그 시스템의 데이터 문자열은 위에 표시된 유형의 일련의 정지 반복 구조로 표시된다.이러한 구조들 사이의 수평 공간의 양은 1개의 기호와 0개의 기호를 구별하는 역할을 한다.이 기호들은 주기적인 태그 시스템이 작동하고 있는 단어를 나타내며, 첫 번째 그러한 기호는 모든 생산 규칙을 고려하여 파괴된다.이 선행 기호가 1이면 문자열 끝에 새 기호가 추가되고, 0이면 새 기호가 추가되지 않는다.이를 달성하기 위한 메커니즘은 아래에 설명되어 있다.
오른쪽에서 들어가는 것은 위에서 표시한 형식의 일련의 좌회전 구조로, 다양한 양의 수평 공간으로 분리된다.이러한 구조물의 많은 수가 서로 다른 스페이스와 결합되어 주기 태그 시스템의 생산 규칙에서 0과 1을 나타낸다.태그 시스템의 생산 룰은 프로그램 생성 시에 알려져 있고, 무한 반복되기 때문에, 초기 조건에서의 0과 1의 패턴은 무한 반복 문자열로 나타낼 수 있다.각 생산규칙은 생산규칙의 인코딩과 같은 속도로 왼쪽으로 이동하는 규칙 구분자(또는 블록 구분자)로 알려진 다른 구조로 다음 구조와 분리된다.
왼쪽 이동 규칙 구분 기호가 주기 태그 시스템의 데이터 문자열에서 고정 기호와 마주칠 경우, 처음 마주치는 기호가 파괴된다.그러나 문자열로 인코딩된 기호가 0이었는지 1이었는지에 따라 그 이후의 동작이 달라진다.0이면 규칙 구분 기호가 들어오는 생산 규칙을 차단하는 새로운 구조로 바뀐다.이 새로운 구조물은 다음 규칙 구분자를 만나면 파괴된다.
반면 문자열의 기호가 1이면 규칙 구분자는 들어오는 생산 규칙을 인정하는 새로운 구조로 바뀐다.새로운 구조물은 다음 규칙 분리기와 마주치면 다시 파괴되지만, 먼저 일련의 구조물이 왼쪽을 향해 통과할 수 있도록 허용한다.그런 다음 이러한 구조는 주기 태그 시스템의 데이터 문자열 끝에 자신을 추가하기 위해 만들어진다.이 최종 변환은 위에 표시된 오른쪽 이동 패턴에서 무한히 반복되고 오른쪽으로 움직이는 시계 펄스를 사용하여 수행된다.클럭 펄스는 생산 규칙에서 데이터 문자열의 고정 1 기호로, 생산 규칙에서 수신 0 기호는 데이터 문자열의 고정 0 기호로 변환한다.
주기 태그 시스템 작동
위의 그림은 규칙 110의 주기 태그 시스템 재구성에 대한 도식도 입니다.
참고 항목
참조
- ^ a b c d 조리 (2004)
- ^ 자일스(2002년).
- ^ 울프람(2002년), 페이지 169, 675–691
- ^ 울프람(2002년), 페이지 229
- ^ Neary & Woods(2006년).
- ^ Martinez, Genaro J.; Seck Tuoh Mora, Juan; Chapa, Sergio; Lemaitre, Christian (April 2019). "Brief notes and history computing in Mexico during 50 years". International Journal of Parallel, Emergent and Distributed Systems. 35 (2): 185–192. arXiv:1905.07527. doi:10.1080/17445760.2019.1608990. S2CID 150262966. Retrieved 2020-04-15.
인용된 작품
- Cook, Matthew (2004). "Universality in Elementary Cellular Automata" (PDF). Complex Systems. 15: 1–40.
- 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.
- Neary, Turlough; Woods, Damien (2006). "P-completeness of cellular automaton Rule 110". In Bugliesi, Michele; Preneel, Bart; Sassone, Vladimiro; Wegener, Ingo (eds.). Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I. Lecture Notes in Computer Science. Vol. 4051. Springer. pp. 132–143. doi:10.1007/11786986_13.
- Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media. ISBN 1-57955-008-8.
추가 읽기
- Cook, Matthew (2008). "A Concrete View of Rule 110 Computation". In Neary, T.; Woods, D.; Seda, A. K.; Murphy, N. (eds.). The Complexity of Simple Programs. Electronic Proceedings in Theoretical Computer Science. Vol. 1. pp. 31–55. arXiv:0906.3248v1. doi:10.4204/EPTCS.1.4. S2CID 10266058.
- Martínez, Genaro J.; Adamatzky, A.; Chen, Fangyue; Chua, Leon (2012). "On Soliton Collisions between Localizations in Complex Elementary Cellular Automata: Rules 54 and 110 and Beyond". Complex Systems. 21 (2): 117–142. arXiv:1301.6258. doi:10.25088/ComplexSystems.21.2.117. S2CID 10165042.
- Martínez, Genaro J.; Adamatzky, A.; Stephens, Christopher R.; Hoeflich, Alejandro F. (2011). "Cellular automaton supercolliders". Int. J. Mod. Phys. C. 22 (4): 419–439. arXiv:1105.4332. Bibcode:2011IJMPC..22..419M. doi:10.1142/S0129183111016348. S2CID 7508070.
- Martínez, Genaro J.; McIntosh, Harold V.; Mora, Juan C.S.T.; Vergara, Sergio V.C. (2003–2008). "Reproducing the cyclic tag systems developed by Matthew Cook with Rule 110 using the phases fi_1" (PDF). Journal of Cellular Automata. 6 (2–3): 121–161.
- Martínez, Genaro J.; McIntosh, Harold V.; Mora, Juan C.S.T.; Vergara, Sergio V.C. (2008). "Determining a regular language by glider-based structures called phases fi_1 in Rule 110". Journal of Cellular Automata. 3 (3): 231–270. arXiv:0706.3348v1. Bibcode:2007arXiv0706.3348J.
- Martínez, Genaro J.; McIntosh, Harold V.; Mora, Juan C.S.T.; Vergara, Sergio V.C. (2007). "Rule 110 objects and other constructions based-collisions" (PDF). Journal of Cellular Automata. 2 (3): 219–242.
- Martínez, Genaro J.; McIntosh, Harold V.; Mora, Juan C.S.T. (2006). "Gliders in Rule 110" (PDF). Int. J. Of Unconventional Computing. 2: 1–49.
- Martínez, Genaro J.; McIntosh, Harold V.; Mora, Juan C.S.T. (2003). "Production of gliders by collisions in Rule 110" (PDF). Lecture Notes in Computer Science. 2801: 175–182. doi:10.1007/978-3-540-39432-7_19. ISBN 978-3-540-20057-4.
- Martínez, Genaro J.; McIntosh, Harold V. (2001). "ATLAS: Collisions of gliders as phases of ether in rule 110".
- McIntosh, Harold V. (1999). "Rule 110 as it relates to the presence of gliders" (PDF).
- McIntosh, Harold V. (2002). "Rule 110 Is Universal!" (PDF).
외부 링크
 | 위키미디어 커먼즈에는 규칙 110과 관련된 미디어가 있다. |
