랭턴의 개미
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
랭턴의 개미는 평면 격자 위에서 특정 규칙에 따라 움직이는 세포 자동자이다. 개미는 흰색 또는 검은색으로 칠해진 사각형 위를 이동하며, 사각형의 색깔에 따라 회전하고 색을 반전시킨 후 한 칸 이동하는 규칙을 따른다. 이러한 단순한 규칙에도 불구하고, 랭턴의 개미는 초기에는 대칭적인 패턴을 보이다가 혼돈 상태를 거쳐 무한히 반복되는 "고속도로" 패턴을 생성하는 복잡한 행동 양식을 보인다. 랭턴의 개미는 튜링 완전성을 가지며, 색상과 개미의 수를 확장하여 다양한 패턴을 만들 수 있다.
더 읽어볼만한 페이지
- 세포 자동자 - 라이프 게임
라이프 게임은 존 호턴 콘웨이가 발표한 세포 자동자로, 2차원 격자에서 셀들이 이웃 셀과의 상호작용을 통해 생존, 사멸, 탄생하며 다양한 패턴을 만들고 튜링 완전성을 가진다. - 세포 자동자 - 와이어월드
와이어월드는 네 가지 상태를 가진 2차원 세포 자동자이며, 주변 세포의 상태에 따라 변화하는 규칙을 통해 논리 회로, 논리 게이트, 튜링 머신 등을 구현할 수 있다. - 튜링 기계 - 튜링 완전
튜링 완전은 계산 이론에서 시스템이 튜링 기계와 동등한 계산 능력을 갖춰 튜링 기계가 계산할 수 있는 모든 함수를 계산하고 범용 튜링 기계를 시뮬레이션할 수 있음을 의미하며, 튜링 동등이라고도 한다. - 튜링 기계 - 비결정론적 튜링 기계
비결정론적 튜링 기계는 튜링 기계의 확장으로, 주어진 상태에서 여러 개의 가능한 다음 동작을 가질 수 있으며, P-NP 문제와 관련하여 계산 복잡도 이론에서 중요한 역할을 한다. - 표시 이름과 문서 제목이 같은 위키공용분류 - 라우토카
라우토카는 피지 비치레부섬 서부에 위치한 피지에서 두 번째로 큰 도시이자 서부 지방의 행정 중심지로, 사탕수수 산업이 발달하여 "설탕 도시"로 알려져 있으며, 인도에서 온 계약 노동자들의 거주와 미 해군 기지 건설의 역사를 가지고 있고, 피지 산업 생산의 상당 부분을 담당하는 주요 기관들이 위치해 있다. - 표시 이름과 문서 제목이 같은 위키공용분류 - 코코넛
코코넛은 코코넛 야자나무의 열매로 식용 및 유지로 사용되며, 조리되지 않은 과육은 100g당 354kcal의 열량을 내는 다양한 영양 성분으로 구성되어 있고, 코코넛 파우더의 식이섬유는 대부분 불용성 식이섬유인 셀룰로오스이며, 태국 일부 지역에서는 코코넛 수확에 훈련된 원숭이를 이용하는 동물 학대 문제가 있다.
| 랭턴의 개미 | |
|---|---|
| 기본 정보 | |
 | |
| 유형 | 튜링 기계 |
| 차원 | 2차원 |
| 창시자 | 크리스토퍼 랭턴 |
| 발표 연도 | 1986년 |
| 규칙 | |
| 상태 | 두 가지 상태 (일반적으로 "검은색"과 "흰색"으로 표현) |
| 이동 규칙 | 현재 칸이 '흰색'이면 '오른쪽'으로 90도 회전하고 칸 색깔을 '반전'시킨 후 다음 칸으로 이동한다. 현재 칸이 '검은색'이면 '왼쪽'으로 90도 회전하고 칸 색깔을 '반전'시킨 후 다음 칸으로 이동한다. |
| 변형 | 다양한 색상과 회전 규칙을 가진 개미들이 존재한다. |
| 동작 | |
| 초기 단계 | 비교적 단순한 패턴을 보인다. |
| 후기 단계 | 복잡하고 예측 불가능한 '고속도로' 패턴을 생성한다. |
| 특징 | |
| 결정론적 | 규칙에 따라 명확하게 결정되는 동작을 보인다. |
| 창발성 | 간단한 규칙에서 복잡한 패턴이 나타나는 창발성을 보인다. |
| 활용 | |
| 응용 분야 | 복잡계 연구 자기 조직화 연구 인공 생명 연구 |
| 참고 자료 | |
| 관련 연구 | 스티븐 울프럼의 "새로운 종류의 과학" (A New Kind of Science) 中 |
2. 규칙
평면은 격자 모양으로 나뉘어 있고, 각 칸은 검은색 또는 흰색으로 칠해져 있다. 이 중 하나의 칸을 "개미"로 정한다. 개미는 각 단계마다 네 방향(상, 하, 좌, 우) 중 한 방향으로 이동할 수 있으며, 다음 규칙을 따른다.
- 현재 있는 칸이 흰색이면, 개미는 방향을 오른쪽(시계 방향)으로 90° 바꾸고, 칸의 색을 검은색으로 뒤집은 뒤, 앞으로 한 칸 이동한다.
- 현재 있는 칸이 검은색이면, 개미는 방향을 왼쪽(시계 반대 방향)으로 90° 바꾸고, 칸의 색을 흰색으로 뒤집은 뒤, 앞으로 한 칸 이동한다.
랭턴의 개미는 세포 자동자로도 설명될 수 있다. 이 관점에서 격자는 검은색 또는 흰색으로 칠해지고, "개미"가 있는 칸은 개미의 현재 상태(바라보는 방향과 현재 칸의 색 조합)를 나타내기 위해 8가지 상태 중 하나를 가진다.[5]
3. 행동 양식
랭턴의 개미는 매우 단순한 규칙을 따르지만, 그 결과는 놀랍도록 복잡한 행동으로 이어진다. 개미는 평면 격자 위를 움직이며, 각 칸은 흰색 또는 검은색으로 칠해져 있다. 개미의 이동 규칙은 다음과 같다.[2]
- 흰색 칸에 있을 때: 90° 오른쪽으로 방향을 틀고, 칸 색깔을 검은색으로 바꾼 뒤, 앞으로 한 칸 이동한다.
- 검은색 칸에 있을 때: 90° 왼쪽으로 방향을 틀고, 칸 색깔을 흰색으로 바꾼 뒤, 앞으로 한 칸 이동한다.
완전히 흰색인 격자에서 시작할 경우, 개미의 움직임은 일반적으로 세 가지 뚜렷한 단계를 거친다.[2]
# '''단순성''': 처음 수백 번의 움직임 동안에는 매우 단순하고 종종 대칭적인 패턴을 만든다.
# '''혼돈''': 약 수백 번의 움직임 이후, 크고 불규칙해 보이는 흑백 사각형 패턴이 나타난다. 이 단계에서 개미는 약 10,000번의 움직임까지 무작위처럼 보이는 경로를 따라 움직인다.
# '''출현하는 질서''': 약 10,000번의 움직임 이후, 개미는 마침내 104단계마다 반복되는 "고속도로"(highway)라고 불리는 패턴을 만들며 한 방향으로 계속 나아가기 시작한다.
지금까지 테스트된 모든 유한한 초기 상태에서는 결국 이 "고속도로" 패턴으로 수렴하는 것으로 관찰되었다. 이는 "고속도로"가 랭턴의 개미 시스템의 끌개(attractor)일 가능성이 높다는 것을 시사한다. 하지만 모든 가능한 초기 상태에 대해 이것이 항상 참이라는 사실은 아직 수학적으로 증명되지 않았다. 다만, 개미의 경로는 초기 상태가 어떻든 간에 항상 무한히 계속된다는 것은 증명되었는데,[3] 이를 코헨-콩 정리라고 한다.[4]
랭턴의 개미는 각 칸의 색깔(흑/백)과 개미의 상태(위치 및 방향)를 고려하는 세포 자동자의 한 예로 볼 수도 있다. 이 경우, 개미가 바라보는 방향(4가지)과 현재 칸의 색깔(2가지)을 조합하여 총 8가지 상태를 가진다고 해석할 수 있다.
4. 계산적 성질
2000년, 가야르도 등은 랭턴의 개미의 단일 인스턴스 궤적을 이용하여 모든 불리언 회로를 계산하는 구성을 제시했다.[5] 이는 랭턴의 개미가 튜링 완전(Turing complete)하다는 것을 의미한다.
5. 확장
랭턴의 개미는 원래의 흑백 규칙을 넘어 다양한 방식으로 확장될 수 있다.[10][11] 가장 기본적인 확장은 두 가지 이상의 색을 사용하는 것이다. 이 경우 색깔은 순환적으로 바뀌며, 개미는 각 색깔에 따라 왼쪽 또는 오른쪽으로 방향을 틀어 이동한다. 또한, 여러 마리의 개미가 동시에 상호작용하며 움직이는 방식으로도 확장될 수 있다. 이러한 확장된 규칙들은 더욱 복잡하고 예측하기 어려운 다양한 패턴을 만들어낸다.
5. 1. 다색 확장
그렉 터크(Greg Turk)와 짐 프롭(Jim Propp)은 랭턴의 개미를 확장하여 두 가지 색상 대신 더 많은 색상을 사용하는 것을 고려했다.[6] 이 확장된 버전에서는 색상이 순환적인 방식으로 수정된다. 각 색상에 대해 개미가 왼쪽으로 회전할지('L') 오른쪽으로 회전할지('R')를 나타내는 문자를 사용하여 간단한 명명 규칙을 사용한다. 예를 들어, 원래의 흑백 랭턴의 개미는 이 명명 방식에서 "RL"이라는 이름을 갖는다.확장된 랭턴의 개미 중 일부는 반복적으로 대칭을 이루는 패턴을 생성한다. 가장 간단한 예 중 하나는 "RLLR" 규칙을 따르는 개미이다. 이러한 대칭 패턴이 발생하는 충분 조건 중 하나는 개미의 규칙 이름이 순환 목록으로 간주될 때, 연속적인 동일한 문자 쌍("LL" 또는 "RR")으로 구성되는 경우이다. (여기서 "순환 목록"이란 마지막 문자가 첫 번째 문자와 짝을 이룰 수 있음을 의미한다.) 이 조건의 증명에는 트루셰 타일(Truchet tiles)이 사용된다.
랭턴의 개미는 사각형 격자뿐만 아니라 육각형 격자에서도 정의될 수 있다. 육각형 격자에서는 최대 6가지 다른 회전이 가능하다. N(회전 없음), R1(시계 방향 60°), R2(시계 방향 120°), U(180°), L2(반시계 방향 120°), L1(반시계 방향 60°)으로 표기한다.
다음은 랭턴의 개미 다색 확장의 몇 가지 예시 패턴이다:
5. 2. 다개체 확장
여러 랭턴의 개미는 2차원 평면에서 공존할 수 있으며, 이들의 상호 작용은 복잡하고 고차원적인 오토마타를 생성하여 다양한 조직화된 구조를 함께 구축한다. 개미의 상호 작용을 모델링하는 데는 여러 가지 방법이 있으며, 시뮬레이션 결과는 선택에 따라 크게 달라질 수 있다.[8]
랭턴의 개미를 확장한 개념으로 터마이트(Turmite)가 있다. 이는 튜링 머신의 여러 상태를 고려하는 방식으로, 마치 개미 자체가 색상을 변경할 수 있는 것과 같다. 터마이트는 "튜링 머신 흰개미"를 합쳐 만든 용어이다. 터마이트의 일반적인 행동으로는 고속도로 생산, 혼돈적인 성장, 나선형 성장이 있다.[7]
아래는 몇 가지 터마이트의 예시이다:
나선형 성장 패턴을 보이는 터마이트. 
부분적으로 혼돈적인 성장 패턴을 보이는 터마이트. 
혼돈적인 성장 기간 후 고속도로를 생성하는 터마이트. 
독특한 질감으로 혼돈적인 성장을 하는 터마이트. 
확장되는 프레임 내부에서 독특한 질감으로 성장하는 터마이트. 
피보나치 수열과 유사한 나선형 구조를 만드는 터마이트. - --
여러 터마이트 역시 서로 만났을 때 발생하는 일을 정의하는 규칙이 있다면 2차원 평면에서 공존할 수 있다. 예를 들어, 에드 페그 주니어(Ed Pegg, Jr.)는 두 터마이트가 만났을 때 각각 왼쪽과 오른쪽으로 방향을 바꾸고, 이후 서로 소멸하는 규칙을 가진 경우를 연구했다.[9]
참조
[1]
논문
Studying artificial life with cellular automata
https://deepblue.lib[...]
[2]
서적
The Science Of Discworld
Ebury Press
[3]
논문
Recurrence properties of Lorentz lattice gas cellular automata
[4]
논문
The Ultimate in Anty-Particles
http://dev.whydomath[...]
2013-05-06
[5]
논문
Complexity of Langton's ant
http://www.dim.uchil[...]
2002-03-15
[6]
논문
Further Travels with My Ant
[7]
웹사이트
Turmite
http://mathworld.wol[...]
From MathWorld--A Wolfram Web Resource, created by [[Eric W. Weisstein]]
2009-10-15
[8]
논문
Robustness of Multi-agent Models: The Example of Collaboration between Turmites with Synchronous and Asynchronous Updating
https://hal.inria.fr[...]
2012
[9]
웹사이트
Math Puzzle
http://www.mathpuzzl[...]
2009-10-15
[10]
논문
Further Travels with My Ant
http://www.math.suny[...]
[11]
간행물
2次元チューリングマシンとチョロアリが平面に描く軌跡
別冊日経サイエンス コンピューターレクリエーションIV 遊びの展開
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com