정물(세포 자동)
Still life (cellular automaton)콘웨이의 게임 오브 라이프와 다른 세포 오토마타에서 정물생명은 한 세대에서 다음 세대로 변하지 않는 패턴이다.이 용어는 정물화나 사진이 무생물적인 장면을 묘사하는 미술계에서 유래되었다.세포 오토마타에서 정물생명은 단위주기가 있는 발진기로 생각할 수 있다.[1]
분류
사이비 정물생명은 둘 이상의 인접한 섬(연결된 구성요소)으로 구성되는데, 이 섬들은 (개별적으로 또는 집합적으로) 비연동적 하위 부분으로 분할될 수 있고, 이 섬들 역시 정물생명이기도 하다.이것은 이런 식으로 구획되지 않을 수도 있는 엄격한 정물화와 비교된다.엄격한 정물생활은 하나의 섬만 가질 수도 있고, 안정을 위해 서로 의지하는 여러 섬을 가질 수도 있어 분해될 수 없다.엄격한 정물생명은 그 안정성을 위해 필요한 여러 개의 연결된 요소들을 가질 수 있기 때문에 둘의 구별이 항상 분명한 것은 아니다.단, 관련 스큐-대칭 그래프에서 사이클을 검색하여 정물 패턴이 엄격한 정물인지 다항 시간대의 사이비 정물인지 판별할 수 있다.[2]
예
콘웨이의 인생 게임에는 자연적으로 발생하는 정물들이 많다.무작위 초기 패턴은 작은 진동기와 다양한 정물들을 포함하는 많은 파편들을 남길 것이다.
가장 흔한 정물(즉, 임의의 초기 상태에서 생성될 가능성이 가장 높은 정물)은 블록이다.[3]나란히 놓인 한 쌍의 블록(또는 바이블록)은 가장 단순한 사이비 정물이다.블록은 많은 복잡한 장치들에서 구성요소로 사용되는데, 예를 들면 고스퍼 글라이더 건이다.
 블록 |  바이블록 |
두 번째로 흔한 정물생물은 벌집이다.[3]벌집은 꿀농장이라고 알려진 형태로 4개 세트의 (비 상호 작용)
 벌집 |  꿀농장 |
세 번째로 흔한 정물화는 빵이다.[3]빵은 종종 바이로프라고 알려진 한 쌍에서 함께 발견된다.바이로브 자체는 종종 베이커리로 알려진 더 많은 (비인터랙션) 페어링에서 만들어진다.두 개의 빵집은 두 개의 다른 두 개의 양로자와 함께 네 개의 빵으로 알려진 한 세트를 형성하면서 서로 옆에 거의 형성되지 않는다.
 빵 |  바이로프 |  베이커리 |
욕조는 4개의 살아있는 세포로 이루어져 있다. 다이아몬드 모양으로 된 중앙 죽은 세포 둘레에 위치한다.대각선으로 중앙 세포에 여분의 살아있는 세포를 대각선으로 배치하는 것은 보트라고 알려진 또 다른 정물적인 생명을 준다.더 많은 살아있는 세포를 반대편에 놓는 것은 배라고 알려진 또 다른 정물을 준다.욕조, 배, 배 한 척을 더하면 바지선, 장선, 장선 등을 각각 증축할 수 있다.이 연장은 임의로 큰 구조물을 주기 위해 무한정 반복될 수 있다.
 왼쪽부터: 욕조, 바지선, 롱바지 등... |
 왼쪽부터: 보트, 롱보트 등... |
 왼쪽부터:배,장선 등... |
보트 한 쌍을 결합하면 보트타이(표피적으로 닮은 나비넥타이의 말장난)라고 알려진 또 다른 정물적인 생명을 줄 수 있다.이와 비슷하게, 한 쌍의 배가 배 넥타이로 결합될 수 있다.
 보트타이 |  선박타이 |
이터즈
정물화는 다른 물체를 개조하거나 파괴하는 데 사용될 수 있다.정물생명은 어떤 다른 패턴(흔히 글라이더, 우주선, 또는 더 복잡한 반응으로 생긴 파편)을 흡수하는 데 사용할 수 있고 충돌 후 원상태로 되돌아갈 수 있을 때 식객이라고 불린다.많은 예들이 존재하는데, 가장 눈에 띄는 것은 여러 종류의 우주선을 흡수할 수 있는 낚싯바늘(일명 식자 1)이다.유사한 장치는 들어오는 우주선의 방향을 바꾸는 '반사기'이다.비슷한 성질을 가진 오실레이터는 먹잇감이나 반사체라고도 할 수 있지만, 수정하는 패턴과 동기화해야 하므로 적용이 더 어렵다.반면에 정물생명은 식자나 반사체가 원래의 모양을 회복할 수 있도록 충분한 시간적 분리와 함께 연속적인 반응이 일어나는 한, 수정하는 패턴의 타이밍에 관계없이 정확하게 작동한다.
열거
주어진 수의 살아있는 세포에 대해 존재하는 콘웨이의 생명의 게임에서 엄격하고 사이비 정적인 생명체의 수는 최대 34개의 값까지 기록되었다(온라인 정수 순서 백과사전(OEIS)에서 각각 A019473과 A056613의 연속).[4][5]
| 살아있는 세포 | 엄격한 정물화 | 사이비 정물 | 예[1] |
|---|---|---|---|
| 1 | 0 | 0 | |
| 2 | 0 | 0 | |
| 3 | 0 | 0 | |
| 4 | 2 | 0 | 블록, 욕조 |
| 5 | 1 | 0 | 보트 |
| 6 | 5 | 0 | 바지선, 벌집, 운반선, 선박, 뱀 |
| 7 | 4 | 0 | 피시 후크, 빵, 긴 보트, 파이톤 |
| 8 | 9 | 1 | 카누, 망고, 긴 바지선, 연못 |
| 9 | 10 | 1 | 모자, 일체형 기호 |
| 10 | 25 | 7 | 테이블 위의 블록, 보트타이, 루프 |
| 11 | 46 | 16 | |
| 12 | 121 | 55 | 선박타이[citation needed] |
| 13 | 240 | 110 | |
| 14 | 619 | 279 | 바이로프[citation needed] |
| 15 | 1,353 | 620 | |
| 16 | 3,286 | 1,645 | |
| 17 | 7,773 | 4,067 | |
| 18 | 19,044 | 10,843 | |
| 19 | 45,759 | 27,250 | 이터2[citation needed] |
| 20 | 112,243 | 70,637 | |
| 21 | 273,188 | 179,011 | |
| 22 | 672,172 | 462,086 | |
| 23 | 1,646,147 | 1,184,882 | |
| 24 | 4,051,732 | 3,069,135 | |
| 25 | 9,971,377 | 7,906,676 | |
| 26 | 24,619,307 | 20,463,274 | |
| 27 | 60,823,008 | 52,816,265 | |
| 28 | 150,613,157 | 136,655,095 | |
| 29 | 373,188,952 | 353,198,379 | |
| 30 | 926,068,847 | 914,075,620 | |
| 31 | 2,299,616,637 | 2,364,815,358 | |
| 32 | 5,716,948,683 | 6,123,084,116 | |
| 33 | 14,223,867,298 | 15,851,861,075 | |
| 34 | 35,422,864,104 | 41,058,173,683 |
밀도
n×n 지역을 최대 밀도 정물생명으로 맞추는 문제가 제약 프로그래밍의 테스트 사례로 주목받았다.[6][7][8][9][10]무한히 큰 격자망의 한계에서는 평면의 세포의 절반 이상이 살 수 없다.[11]유한 사각 그리드의 경우 더 높은 밀도를 달성할 수 있다.예를 들어, 8×8 제곱 내의 최대 밀도 스틸 수명은 밀도 36/64 = 0.5625인 9블록의 정규 격자다.[6]최적 용액은 모든 크기의 정사각형으로 알려져 있다.[12]요크-스미스는 알려진 유한 최대 밀도 패턴 목록을 제공한다.[13]
참조
- ^ a b "Still Life - from Eric Weisstein's Treasure Trove of Life C.A." Retrieved 2009-01-24.
- ^ Cook, Matthew (2003). "Still life theory". New Constructions in Cellular Automata. Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press. pp. 93–118.
- ^ a b c Achim Flammenkamp. "Top 100 of Game-of-Life Ash Objects". Retrieved 2008-11-05.
- ^ 콘웨이의 라이프 게임(OEIS의 시퀀스 A019473)에서 안정적인 n-세포 패턴("정물 수명")의 수입니다.
- ^ 콘웨이의 라이프 게임(OEIS의 시퀀스 A056613)에서 n세포 사이비 스틸리프의 수.
- ^ a b Bosch, R. A. (1999). "Integer programming and Conway's game of Life". SIAM Review. 41 (3): 594–604. Bibcode:1999SIAMR..41..594B. doi:10.1137/S0036144598338252..
- ^ Bosch, R. A. (2000). "Maximum density stable patterns in variants of Conway's game of Life". Operations Research Letters. 27 (1): 7–11. doi:10.1016/S0167-6377(00)00016-X..
- ^ Smith, Barbara M. (2002). "A dual graph translation of a problem in 'Life'". Principles and Practice of Constraint Programming - CP 2002. Lecture Notes in Computer Science. Vol. 2470. Springer-Verlag. pp. 89–94. doi:10.1007/3-540-46135-3_27..
- ^ Bosch, Robert; Trick, Michael (2004). "Constraint programming and hybrid formulations for three Life designs". Annals of Operations Research. 130 (1–4): 41–56. doi:10.1023/B:ANOR.0000032569.86938.2f..
- ^ Cheng, Kenil C. K.; Yap, Roland H. C. (2006). "Applying ad-hoc global constraints with the case constraint to still-life". Constraints. 11 (2–3): 91–114. doi:10.1007/s10601-006-8058-9..
- ^ Elkies, Noam D. (1998). "The still life density problem and its generalizations". Voronoi's Impact on Modern Science, Book I. Proc. Inst. Math. Nat. Acad. Sci. Ukraine, vol. 21. pp. 228–253. arXiv:math.CO/9905194.
- ^ Chu, Geoffrey; Stuckey, Peter J. (2012-06-01). "A complete solution to the Maximum Density Still Life Problem". Artificial Intelligence. 184–185: 1–16. doi:10.1016/j.artint.2012.02.001.
- ^ Neil Yorke-Smith. "Maximum Density Still Life". Artificial Intelligence Center. SRI International.
