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

패터슨의 벌레

Paterson's worms

패터슨의 웜은 마이크 패터슨과 존 호튼 콘웨이가 1971년 특정 선사시대 웜의 행동과 먹이 패턴을 모형화하기 위해 고안한 세포 자동자 군이다. 모델에서 지렁이는 선 세그먼트를 따라 삼각형 격자의 점 사이를 이동하며, 음식을 나타낸다. 그것의 회전은 현재 웜이 있는 지점에 인접한 먹거나 불편한 선 세그먼트의 구성에 의해 결정된다. 단순한 규칙에 지배당함에도 불구하고 벌레의 행동은 극도로 복잡할 수 있으며, 하나의 변종의 궁극적인 운명은 여전히 알려져 있지 않다.

이 벌레들은 1970년대 초반에 피터슨, 콘웨이, 마이클 비엘러에 의해 연구되었고 1973년 6월에 비엘러가 기술했으며 1973년 11월에 과학 아메리카에 있는 마틴 가드너의 "수학적 게임" 칼럼에 발표되었다.[1][2]

일렉트로닉 아츠(Electronic Arts)의 1983년 게임 웜즈(Worms)는 패터슨의 웜(Worms)의 인터랙티브 구현으로, 웜(Worms)이 규칙을 정하지 않는 방식으로 웜(Worms)을 회전시킬 때마다 사용자가 방향을 선택하도록 하는 것이다.

역사

화석화된 웜 트랙.

패터슨의 지렁이는 선사시대 지렁이의 행동을 흉내내기 위한 시도다. 이 생물들은 연못 바닥의 침전물을 먹고, 그들이 이미 여행했던 길들을 피했다. 왜냐하면 그곳에는 식량이 부족할 것이기 때문이다. 그러나 음식이 조각조각 발생했기 때문에, 이전의 길 근처에 머무는 것이 벌레의 관심사였다. 벌레의 종류마다 얼마나 멀리 가야 하는 길과, 언제 돌아야 하는지, 그리고 얼마나 날카로운 방향을 돌려야 하는지에 관한 타고난 규칙이 달랐다.[1] 1969년에 Raup과 Seilacher는 화석화된 웜 트레일에 대한 컴퓨터 시뮬레이션을 만들었고, 이러한 시뮬레이션은 Paterson과 Conway가 일반 그리드의 이상화된 웜을 연구하기 위한 간단한 규칙들을 개발하도록 영감을 주었다.[3]

콘웨이의 원래 모델은 직교 격자 위에 있는 벌레였지만, 이것은 단지 세 종류의 다른 벌레만을 생산했고, 모든 것이 다소 흥미 없는 행동을 했다. 패터슨은 삼각망 위의 벌레들을 생각했다.[1] 패터슨의 지렁이는 메사추세츠 공과대학교 AI 메모(#[1])에서 비엘러에 의해 설명되어 1973년 11월 과학아메리칸의 마틴 가드너의 '수학적 게임' 칼럼에 실렸으며,[2] 이후 가드너 1986년에 다시 실렸다.[4] 이러한 시뮬레이션은 세포와 그것들 사이의 관계에 초점을 맞춘 비슷한 시기에 개발된 다른 세포 자동화와 접근방식이 달랐다.[5] 이와 같은 단순한 컴퓨터 모델은 실제 생물체의 행동을 정확하게 묘사하기에는 너무 추상적이지만, 그들은 아주 단순한 규칙이라도 그들의 흔적을 닮은 패턴을 만들어 낼 수 있다는 것을 보여준다.[6]

규칙.

그 벌레는 무한 삼각 격자의 어느 지점에서 시작한다. 그것은 각 지점에서[6] 만나는 6개의 격자선 중 하나를 따라 움직이기 시작하고, 일단 한 단위의 거리를 이동하면 새로운 지점에 도달한다. 그런 다음, 지렁이는 가로지른 격자선과 가로지르지 않은 격자선의 분포에 기초하여 어떤 방향으로 갈 것인지를 결정한다. 방향은 벌레의 관점에 따라 다르다. 만약 벌레가 이러한 정확한 분포를 경험하지 않았다면, 그것은 어떤 방해받지 않은 격자선을 따라 떠날 수 있다. 그때부터, 만약 그 분포를 다시 만나게 된다면, 그것은 같은 방식으로 움직여야 한다. 사용할 수 있는 추적되지 않은 격자선이 없으면 웜이 죽고 시뮬레이션이 종료된다.[1]

토론

새로운 형태의 교차로와 마주쳤을 때 어느 방향으로 돌느냐에 따라 많은 종류의 벌레가 있다. 다양한 종류의 웜은 모든 방향에서 번호를 부여하고 새로운 유형의 교차로와 마주칠 때마다 선택한 사항을 나열함으로써 체계적으로 분류될 수 있다.[7]

6개의 방향은 다음과 같이 번호가 매겨진다.

PatersonWormDirections.png

따라서 방향 0은 지렁이가 앞으로 계속 직진하고 있음을 나타내며, 방향 1은 지렁이가 60°의 우회전을 하고 다른 방향도 마찬가지로 우회전을 할 것임을 나타낸다. 벌레는 3방향으로 이동할 수 없다. 왜냐하면 그것이 방금 가로지른 격자선이기 때문이다. 따라서 규칙 {1,0,5,1}을(를) 가진 웜은 처음 선택을 해야 할 때는 방향 1로, 다음에 선택을 해야 할 때는 방향 0으로 이동하기로 결정한다. 이용 가능한 격자선이 하나뿐이면 벌레가 가져갈 수밖에 없고 이는 일반적으로 명시적으로 나열되지 않는다.

패터슨의 벌레가 규칙 {2,0,0}을(를) 가지고 있다.

규칙 집합이 0으로 시작하는 벌레는 영원히 일직선으로 계속된다. 이것은 사소한 경우라 보통 지렁이가 격자선만 불편하게 하는 점을 만나면 반드시 방향을 틀도록 규정되어 있다. 더 나아가 거울-이미지 대칭 복제물을 피하기 위해서는 벌레의 첫 번째 순서가 오른손 순서가 되어야 한다.[1] 벌레는 세 번째로 원점으로 돌아오면 죽는다. 왜냐하면 그 때 사용할 수 있는 탐색되지 않은 가장자리가 없기 때문이다. 오직 기원만이 지렁이에게 치명적일 수 있다.[8]

1296개의 가능한 웜 규칙 조합이 있다.[4] 이는 다음과 같은 논거로 알 수 있다.

  1. 만약 벌레가 방금 먹은 것 외에 먹힌 부분이 없는 노드와 마주친다면, 그것은 급커브를 하거나 부드럽게 돌 수 있다. 위 그림에 나타난 상황이다. 처음의 좌우를 선택하면 단순히 서로 거울로 보는 조합이 만들어지기 때문에 사실상 다르지 않다.
  2. 만약 그것이 하나의 먹힌 세그먼트가 있는 노드와 마주친다면, 그것은 나머지 4개 중 어느 하나를 따라 떠날 수 있다. 지렁이의 첫 번째 원점 복귀만이 이런 성격을 가지고 있다.
  3. 두 개의 섭취된 세그먼트의 경우 섭취된 세그먼트의 위치가 중요하다. 존재할 수 있는 유일한 2-세그먼트 교차로 유형은 첫 번째 규칙에 의해 생산되는 것으로, 4개의 뚜렷한 접근 방향이 있으며, 각각 3개의 출발 방향의 선택을 제공한다. 이것은 규칙을 선택할 때 81가지의 다른 대안을 허용한다.
  4. 만약 이 벌레가 원점으로 돌아온다면, 그것은 세 개의 먹은 부분을 만나게 될 것이고, 그들의 분포와 상관없이 남아있는 두 개의 불편한 부분들 중에서 선택해야 한다.
  5. 4개의 먹은 분절의 경우, 불안정한 분절만 남았고 벌레는 그것을 가져가야 한다.

따라서 2×4×81×2×1=1,296개의 다른 규칙 조합이 있다. 이들 중 다수는 다른 거울과 이미지의 복제품이며, 다른 것들은 규칙 집합에서 모든 선택을 해야 하기 전에 죽어서 411종의 구별되는 종(무한 직선 지렁이를 포함하면 412종)을 남긴다.[8] 이 중 336종은 결국 죽는다. 73개의 패턴은 무한한 행동을 보인다. 즉, 그것들은 원점으로 돌아가지 않는 반복적인 패턴으로 정착한다. 더 많은 두 개는 무한하다고 강하게 믿어지고 하나는 미해결 상태로 남아있다. 그 규칙들 중 11개는 복잡한 행동을 보인다. 수십억 번을 반복해도 죽지 않으며, 명백히 무한한 패턴을 채택하지도 않는다. 그들의 궁극적인 운명은 벤자민 채핀이 그들을 해결하는 새로운 방법을 개발하기 전까지 알려지지 않았다. 여러 시간의 컴퓨터 시간이 흐른 후 열한 가지 규칙 중 아홉 가지가 해결되어 벌레들은 규칙 {1,0,4,2,0,0}과(와) {1,0,4,2,0,1,5}[7]을(를) 남겼다. 이 중 첫 번째는 토마스 로키키에 의해 해결되었는데, 그는 57조 (5.7×1013) 타임스테프가 지나면 중단된다고 판단하여 겨우 {1,0,4,2,0,1,5}개만 미해결 상태로 남겨두었다. 로키키에 따르면, 이 벌레는 5.2×1019 타임스테프 이후에도 여전히 활동 중이다. 그는 빌 고스퍼의 해시라이프에 기반을 둔 알고리즘을 사용하여 엄청난 속도로 웜을 시뮬레이션했다.[8] 이 동작은 16개의 세그먼트에 불과한 가장 긴 경로를 가진 관련 직사각형 그리드 웜보다 상당히 복잡하다.[6]

서로 다른 두 종의 지렁이가 같은 경로를 반드시 같은 순서로 가로지르지는 않지만, 같은 경로를 생성하는 것은 가능하다.[1] 가장 일반적인 경로도 가장 짧다: 7점 "방사능 활동 기호"[4]이다. 이 경로의 한 예는 위의 애니메이션 그림에서 볼 수 있다. 총 299개의 다른 길이 있으며, 이 중 209개는 단 한 종에 의해 생산된다.[1]

참고 항목

참조

  1. ^ Jump up to: a b c d e f g Beeler, Michael (June 1973). "Paterson's Worm". Massachusetts Institute of Technology. hdl:1721.1/6210. Cite 저널은 필요로 한다. journal= (도움말)
  2. ^ Jump up to: a b Gardner, Martin (November 1973). "Mathematical Games: Fantastic patterns traced by programmed 'worms'". Scientific American. 229 (5): 116–123. doi:10.1038/scientificamerican1173-116. closed access
  3. ^ "Paterson's Worms". WolframMathworld. Retrieved 2008-08-15.
  4. ^ Jump up to: a b c Gardner, Martin (1986), Knotted doughnuts and other mathematical entertainments, W. H. Freeman, Bibcode:1986kdom.book.....G, ISBN 978-0-7167-1799-7, MR 0857289
  5. ^ Parikka, Jussi (2007). Digital Contagions: a Media Archaeology of Computer Viruses. New York: Peter Lang Publishing. p. 234. ISBN 978-1-4331-0093-2.
  6. ^ Jump up to: a b c Hayes, Brian (September–October 2003). "In Search of the Optimal Scumsucking Bottomfeeder". American Scientist. 95 (5): 392–396. doi:10.1511/2003.5.392. open access
  7. ^ Jump up to: a b Pegg Jr., Ed (October 27, 2003). "Math Games: Paterson's Worms Revisited". MAA Online. Archived from the original on 2004-03-23. Retrieved 2008-08-15.
  8. ^ Jump up to: a b c Chaffin, Benjamin. "Paterson's Worms". Archived from the original on June 7, 2011.

외부 링크