랭턴의 고리

Langton's loops
Langton's Loop, 시작 구성에서.

랭턴의 고리는 1984년 크리스토퍼 랭턴에 의해 만들어진 세포 자동화 장치에 있는 인공 생명체의 특별한 "종"입니다. 그것들은 유전 정보를 포함하는 세포들의 고리로 구성되어 있고, 고리 주위를 계속해서 흐르고 딸 고리가 될 "팔"(또는 유사동물)을 따라 밖으로 흘러 나옵니다. "유전자"는 이 로봇에게 세 번의 좌회전을 지시하여 루프를 완성한 다음, 이 루프를 부모로부터 분리합니다.

역사

1952년 존 폰 노이만은 자가 복제 기계를 만드는 것을 목표로 최초의 세포 자동화 장치(CA)를 만들었습니다.[1] 이 자동화기는 계산 및 구축 보편성 때문에 반드시 매우 복잡했습니다. 1968년 에드가 F. 코드는 폰 노이만의 CA에서 29개 주에서 8개 주로 줄였습니다.[2] 크리스토퍼 랭턴이 보편성 조건을 없앴을 때, 그는 오토마톤의 복잡성을 크게 줄일 수 있었습니다. 자체 복제 루프는 주기적 방출기인 Codd의 오토마톤에서 가장 간단한 요소 중 하나를 기반으로 합니다.

사양

Langton's Loops는 8개의 상태를 가진 CA에서 실행되며 회전 대칭을 가진 폰 노이만 이웃을 사용합니다. 전환 테이블은 다음 [1]에서 확인할 수 있습니다.

Codd의 CA와 마찬가지로, Langton's Loops는 피복 와이어로 구성되어 있습니다. 신호는 신호가 전달되는 명령이 실행될 때 열린 끝에 도달할 때까지 와이어를 따라 수동적으로 이동합니다.

루프의 군락지. 중앙에 있는 사람들은 "죽었습니다".

식민지

루프의 "슈도포디아"의 특정한 특성 때문에, 루프는 다른 루프가 차지하는 공간으로 재생산할 수 없습니다. 따라서, 일단 고리가 둘러싸이면, 그것은 번식을 할 수 없게 되고, 그 결과, 활동적이지 않은 "죽은" 유기체들의 핵을 둘러싸고 있는 얇은 번식 유기체 층을 가진 산호와 같은 군체가 됩니다. 무제한 공간이 제공되지 않는 한 식민지의 크기는 제한됩니다. 모집단은 ⌊ A ⌋ {\A}{121right\rfloor}, 여기서 A는 셀 내 공간의 총 면적입니다.

게놈의 암호화

루프의 유전 코드는 일련의 0이 아닌 상태 쌍으로 저장됩니다. 상단의 그림은 표준 루프의 유전체를 나타낸 것으로, T-접합에서 시작하여 시계 방향으로 진행하는 일련의 번호 상태(70-70-70-70-70-70-70-40)로 표현할 수 있습니다. '70' 명령은 와이어 끝을 1셀씩 전진시키고, '40-40' 순서는 좌회전을 유발합니다. 상태 3은 여러 단계의 임시 마커로 사용됩니다.

0, 1, 2, 3, 4 및 7 상태의 역할은 Codd의 CA와 유사하지만 나머지 5 및 6 상태는 루프 복제 프로세스를 중재하는 데 사용됩니다. 루프가 완료된 후 상태 5는 부모 루프의 피복을 따라 반시계 방향으로 진행하여 다음 암을 다른 방향으로 생성합니다. 상태 6은 일시적으로 딸 고리의 유전체에 합류하여 성장하는 팔이 도달하는 다음 모서리에서 초기화됩니다.

게놈은 한 번은 원하는 위치로 유사체를 확장하고, 네 번은 루프를 완성하고, 다시 한 번은 딸 루프로 게놈을 옮기는 총 6번 사용됩니다. 분명히 이것은 루프의 4중 회전 대칭성에 의존합니다. 루프가 없으면 루프는 그것을 설명하는 데 필요한 정보를 포함할 수 없습니다. 유전체 압축을 위한 대칭의 동일한 사용은 20면체 아데노바이러스와 같은 많은 생물학적 바이러스에서 사용됩니다.

관련 CA 루프 비교

CA 주의 수 이웃의 셀 수(typical) 복제기간(typical) 썸네일
랭턴의 고리[3](1984): 원래 자가 재생 루프입니다. 8 폰 노이만 86 151
Byl's loop[4] (1989): Byl은 내부 피복을 제거하여 루프의 크기를 줄였습니다. 6 폰 노이만 12 25
추-레지아[5] 루프(1993): 모든 칼집을 제거하여 루프를 더욱 줄입니다. 8 폰 노이만 5 15
템페스티 루프[6](1995): Tempesti는 그의 루프에 건설 기능을 추가하여 복제 후 루프 안에 패턴을 쓸 수 있게 했습니다. 10 무어 148 304
페리어 루프[7](1996): Perrier는 Langton의 루프에 프로그램 스택과 확장 가능한 데이터 테이프를 추가하여 계산 가능한 모든 것을 계산할 수 있게 했습니다. 64 폰 노이만 158 235
SDSR 루프[8](1998): Langton의 루프에 구조 분해 상태가 추가되어 SDSR 루프의 수명은 제한적이며 수명 주기가 끝나면 용해됩니다. 이를 통해 세대의 지속적인 성장과 턴오버가 가능합니다. 9 폰 노이만 86 151
Evoloop[9](1999): SDSR 루프의 확장인 Evoloop은 진화뿐만 아니라 이웃 루프와의 상호작용도 가능합니다. 종종 Evoloops 군체에서 가장 큰 선택 압력은 공간 경쟁이며 자연 선택은 존재하는 가장 작은 기능 루프를 선호합니다. 추가 연구는 에볼루프 시스템에서 원래 생각했던 것보다 더 복잡한 것을 보여주었습니다.[10] 9 폰 노이만 149 363
Sexy loop[11](2007): Sexy loop은 스스로 재생하는 루프가 섹스의 능력을 가지고 있는 Evoloop을 수정한 것입니다. 이 능력으로 루프는 유전 물질을 다른 루프로 전달할 수 있습니다. 이것은 새로운 종류의 루프의 진화에서 다양성을 증가시킵니다. 10 폰 노이만 149 363

참고 항목

참고문헌

  1. ^ von Neumann, John; Burks, Arthur W. (1966). "Theory of Self-Reproducing Automata.". www.walenz.org. Archived from the original (Scanned book online) on 2008-01-05. Retrieved 2008-02-29.
  2. ^ Codd, Edgar F. (1968). Cellular Automata. Academic Press, New York.
  3. ^ C. G. Langton (1984). "Self-reproduction in cellular automata" (PDF). Physica D. 10 (1–2): 135–144. doi:10.1016/0167-2789(84)90256-2. hdl:2027.42/24968.
  4. ^ J. Byl (1989). "Self-Reproduction in small cellular automata". Physica D. 34 (1–2): 295–299. doi:10.1016/0167-2789(89)90242-X.
  5. ^ J. A. Reggia; S. L. Armentrout; H.-H. Chou; Y. Peng (1993). "Simple systems that exhibit self-directed replication". Science. 259 (5099): 1282–1287. doi:10.1126/science.259.5099.1282. PMID 17732248.
  6. ^ G. Tempesti (1995). "A New Self-Reproducing Cellular Automaton Capable of Construction and Computation". Advances in Artificial Life, Proc. 3rd European Conference on Artificial Life. Granada, Spain: Lecture Notes in Artificial Intelligence, 929, Springer Verlag, Berlin. pp. 555–563. CiteSeerX 10.1.1.48.7578.
  7. ^ J.-Y. Perrier; M. Sipper; J. Zahnd (1996). "Toward a viable, self-reproducing universal computer". Physica D. 97 (4): 335–352. CiteSeerX 10.1.1.21.3200. doi:10.1016/0167-2789(96)00091-7.
  8. ^ Sayama, Hiroki (1998). "Introduction of Structural Dissolution into Langton's Self-Reproducing Loop". Artificial Life VI: Proceedings of the Sixth International Conference on Artificial Life. Los Angeles, California: MIT Press. pp. 114–122.
  9. ^ Sayama, Hiroki (1999). "Toward the Realization of an Evolving Ecosystem on Cellular Automata". Proceedings of the Fourth International Symposium on Artificial Life and Robotics (AROB 4th '99). Beppu, Oita, Japan. pp. 254–257. CiteSeerX 10.1.1.40.391.
  10. ^ Chris Salzberg; Hiroki Sayama (2004). "Complex genetic evolution of artificial self-replicators in cellular automata". Complexity. 10 (2): 33–39. doi:10.1002/cplx.20060. Archived from the original on 2013-01-05.
  11. ^ Nicolas Oros; C. L. Nehaniv (2007). "Sexyloop: Self-Reproduction, Evolution and Sex in Cellular Automata". The First IEEE Symposium on Artificial Life (April 1–5, 2007, Hawaii, USA). pp. 130–138. hdl:2299/6711.

외부 링크

Wikimedia Commons에는 자기 복제 루프와 관련된 미디어가 있습니다.