랭턴의 개미
랭턴의 개미는 평면 위의 격자에서 작동하는 결정론적 튜링 기계의 일종이다. 1986년 크리스토퍼 랭턴이 발명했으며, 간단한 규칙에도 불구하고 복잡한 행동 양상을 보이는 대표적인 인공생명 모델 중 하나로 여겨진다.
작동 방식:
랭턴의 개미는 다음과 같은 규칙에 따라 움직인다.
- 현재 개미가 위치한 격자 칸의 색깔을 확인한다. (일반적으로 흰색 또는 검은색)
- 칸의 색깔에 따라 정해진 방향으로 개미를 회전시킨다. (예: 흰색 칸에서는 오른쪽으로 90도 회전, 검은색 칸에서는 왼쪽으로 90도 회전)
- 현재 칸의 색깔을 반전시킨다. (흰색은 검은색으로, 검은색은 흰색으로)
- 개미를 회전한 방향으로 한 칸 이동시킨다.
특징:
- 초기 행동: 초반에는 비교적 예측 가능한 패턴으로 움직이는 듯 보이지만, 곧 혼돈스러운 움직임을 보인다.
- 고속도로 (Highway): 일정 시간이 지나면 개미는 주기적인 패턴을 그리며 격자를 가로지르는 "고속도로"를 건설하는 경향이 있다. 이 고속도로는 규칙적인 간격으로 반복되는 검은색과 흰색 칸들로 이루어져 있다.
- 튜링 완전성: 랭턴의 개미는 튜링 완전한 것으로 추정되지만, 아직 증명되지는 않았다.
의의:
랭턴의 개미는 단순한 규칙으로부터 복잡한 행동이 나타날 수 있다는 것을 보여주는 좋은 예시이다. 이는 자기 조직화, 창발성 등의 개념을 이해하는 데 도움을 주며, 복잡계 과학 연구에 영감을 주었다. 또한, 튜링 기계의 개념을 시각적으로 이해하기 쉽도록 돕는 교육적인 도구로도 활용된다.