mir.pe (일반/어두운 화면)
최근 수정 시각 : 2024-06-27 00:38:54

랭턴의 개미


1. 개요2. Turmite3. 목록4. 프로세싱 코드

1. 개요



Langton's Ant.

이곳[1]나 이곳[2]에서 직접 해볼 수 있다.

컴퓨터과학자 크리스토퍼 랭턴(Christopher Langton)[3]이 1986년에 제안한 세포 자동자. 또다른 세포 자동자인 콘웨이의 생명 게임보다는 덜 유명하지만 간단한 규칙으로 복잡한 변화를 보여준다는 공통점이 있다. 보편 튜링 머신임이 2000년에 증명됐다.

랭턴의 개미가 이동하는 규칙은 다음과 같다.
만약 랭턴의 개미 한 마리가 모든 칸이 흰색인 사각형 격자에서 움직이기 시작한다면, 개미는 약 10000번 동안 마구잡이로 이동하다가 갑자기 104번 주기로 같은 움직임을 반복하며 한 방향으로 무한히 나아간다.




랭턴의 개미를 일반화하여, 흰색과 검은색 대신 여러 개의 색을 사용할 수 있다. 첫 번째 색의 개미는 이동하면서 두 번째 색으로 바꾸고, 두 번째 색의 개미는 이동하면서 세 번째 색으로 바꾸고, 이런 식으로 쭉 이어지다가 마지막 색의 개미는 이동하면서 첫 번째 색으로 바꾸게 하면 된다. 개미의 이동방향에 관한 규칙을 알파벳만으로 간단히 나타낼 수 있다.[4]




사각형 격자를 사용하는 대신, 육각형 격자나 펜로즈 타일 등 다양한 타일을 사용할 수도 있다. 3차원 격자도 가능하다.

2. Turmite

이동 규칙에 따라 칸의 상태 뿐만이 아니라 개미의 상태도 변화[5]하면 turmite[6]라고 한다. turmite는 칸의 상태 종류 갯수에 개미의 상태 종류 갯수를 곱한 만큼 이동 규칙이 필요하므로 훨씬 다양한 움직임 패턴을 나타낼 수 있다.

개미가 향하는 방향을 기준으로 개미를 회전시키면 relative turmite, 변하지 않는 방위(동서남북)를 기준으로 개미를 회전시키면 absolute turmite라고 한다. absolute turmite는 사실상 테이프가 2차원인 튜링 머신이다.

3. 목록


turmite까지 포함한 좀더 자세한 목록은 링크 참조[7]. 만약 칸의 상태가 n개일 때 반복 구간이 가장 늦게 나타나는 경우의 이동 횟수로 함수를 만든다면, 이는 정의가 비슷한 Maximum shifts function처럼 매우 빠르게 증가하여 정확한 값을 계산하는 것은 불가능하다.

===# 칸의 상태가 2개 #===
<rowcolor=#FFFFFF> 이동 규칙 반복 구간
최초 등장 직전
이동 횟수 		반복 간격 반복 구간
최초 등장 직전
좌표 		반복 구간
1번 후
좌표 변화 		반복 구간
이동 속도
[8]
LR (RL) 9977 104 15, 10 2, -2 0.0272
UN 0 3 0, 0 0, 1 0.3333
NX 0 1 0, 0 0, 1 1
===# 칸의 상태가 3개 #===
<rowcolor=#FFFFFF> 이동 규칙 반복 구간
최초 등장 직전
이동 횟수 		반복 간격 반복 구간
최초 등장 직전
좌표 		반복 구간
1번 후
좌표 변화 		반복 구간
이동 속도
LNU (RNU) 6762만 43 92 218, -341 2, 0 0.0217
LUR (RUL) 267만 85 378 18, 3 2, -2 0.0075
LLU (RRU) 90 25 0, 0 0, 1 0.04
LUL (RUR) 46 15 0, 0 0, 1 0.0667
LLR (RRL) 39 18 2, -1 -1, -1 0.0786
LUN (RUN) 36 15 -1, 1 -1, 0 0.0667
UNU 2 3 0, 0 0, 1 0.3333
LRN (RLN) 0 18 0, 0 0, 2 0.1111
ULL (URR) 0 5 0, 0 0, 1 0.2
UUN 0 5 0, 0 0, 1 0.2
NXX 0 1 0, 0 0, 1 1
===# 칸의 상태가 4개 #===
<rowcolor=#FFFFFF> 이동 규칙 반복 구간
최초 등장 직전
이동 횟수 		반복 간격 반복 구간
최초 등장 직전
좌표 		반복 구간
1번 후
좌표 변화 		반복 구간
이동 속도
UNLU (UNRU) 965억 5714만 5085 174 -3290, 1 0, -2 0.0115
ULRR (URLL) 66억 5020만 9468 280 -1118, 136 -4, 0 0.0143
LUUR (RUUL) 15억 8910만 6747 1136 18, 3 2, -2 0.0025
ULRL (URLR) 14억 6870만 9636 638 -503, 515 0, 2 0.0031
LULN (RURN) 11억 6745만 4221 132 -563, -710 0, -2 0.0152
UUNL (UUNR) 6억 7427만 3232 79 395, 267 1, 0 0.0127
LLUR (RRUL) 2억 5506만 2383 18만 5236 -458, -805 -105, 69 0.0007
LLUU (RRUU) 1억 4855만 5690 32만 7776 -1007, 389 -37, 91 0.0003
LLNU (RRNU) 1억 1317만 1947 1204 224, -427 1, -9 0.0075
ULNU (URNU) 549만 9574 166 -107, 71 -3, -1 0.0190
LLRL (RRLR) 25만 6241 384 -47, 48 4, 4 0.0147
LUNN (RUNN) 24만 3061 67 -32, 15 -2, 1 0.0334
LURL (RULR) 4만 3564 339 23, 23 5, 0 0.0147
ULUR (URUL) 2만 869 220 16, 9 2, -2 0.0129
LURU (RULU) 1만 9449 196 16, 9 2, -2 0.0144
LRLR (RLRL) 1만 77 104 15, 8 2, -2 0.0272
LNNU (RNNU) 1656 57 2, 12 2, 1 0.0392
ULLL (URRR) 1019 52n+239 3, -4 2, -1
-2, -1
-2, 1
2, 1 		-
LUNL (RUNR) 605 34 5, 4 0, 2 0.0588
LLUL (RRUR) 429 162 -1, 0 -2, 0 0.0123
LLRU (RRLU) 271 9 1, 4 0, 1 0.1111
LLRN (RRLN) 135 28 -3, -2 -2, 0 0.0714
LLLR (RRRL) 79 52 2, -1 -2, -2 0.0544
LLLU (RRRU) 70 23 0, 0 0, 1 0.0435
LUUN (RUUN) 48 40 -1, 1 -2, 0 0.05
LRUN (RLUN) 47 24 1, 0 2, 0 0.0833
UNNN 8 5 0, 0 0, 1 0.2
UUNU 4 5 0, 0 0, 1 0.2
LULL (RURR) 3 9 0, -1 0, 1 0.1111
ULLU (URRU) 2 5 0, 0 0, 1 0.2
UNLR (UNRL) 2 5 0, 0 0, 1 0.2
UNUX 2 3 0, 0 0, 1 0.3333
LRUR (RLUL) 0 30 0, 0 0, 2 0.0667
LURR (RULL) 0 18 0, 0 0, 2 0.1111
ULRN (URLN) 0 9 0, 0 0, 1 0.1111
ULNR (URNL) 0 7 0, 0 0, 1 0.1429
UULL (UURR) 0 7 0, 0 0, 1 0.1429
UUUN 0 7 0, 0 0, 1 0.1429
NXXX 0 1 0, 0 0, 1 1
===# 칸의 상태가 5개 #===
<rowcolor=#FFFFFF> 이동 규칙 반복 구간
최초 등장 직전
이동 횟수 		반복 간격 반복 구간
최초 등장 직전
좌표 		반복 구간
1번 후
좌표 변화 		반복 구간
이동 속도
LUUUR (RUUUL) 2177억 9137만 6193 2810 18, 3 2, -2 0.0010
LULUN (RURUN) 1417억 4674만 4401 166 385, 4128 0, 2 0.0120
ULNRN (URNLN) 691억 5463만 4995 47 3062, -475 1, 0 0.0213
UNNLN (UNNRN) 413억 3188만 2915 138 -2425, -600 -2, 0 0.0074
LUNLU (RUNRU) 385억 2541만 2648 205 -1958, -3906 -3, 0 0.0146
UNNLU (UNNRU) 341억 2811만 7730 272 1314, -1384 0, -2 0.0074
LRRUR (RLLUL) 224억 8177만 6988 347 -533, 3667 -2, 1 0.0064
LNULL (RNURR) 137억 6970만 9086 639 1693, -1319 0, -5 0.0078
LURLL (RULRR) 97억 3152만 9411 179 -693, 2206 1, 2 0.0125
LLLRL (RRRLR) 88억 1770만 4078 332 1079, -1437 2, -2 0.0085
LLLNR (RRRNL) 70억 7182만 1517 1519 1296, 395 13, 6 0.0094
LRLUU (RLRUU) 48억 8215만 4969 32만 2274 -1955, -2736 9, -107 0.0003
ULNNR (URNNL) 31억 3020만 6318 94 844, -676 2, 0 0.0213
LLNRN (RRNLN) 14억 4154만 5729 96 885, -206 2, -2 0.0295
LUURL (RUULR) 10억 239만 1344 4953 -1364, 968 -17, 12 0.0042
UULLR (UURRL) 9억 2828만 3721 248 -318, -467 -2, 0 0.0081
LLUNN (RRUNN) 4억 9998만 1455 92 558, 227 2, 0 0.0217
LNLRU (RNRLU) 4억 8561만 7640 121 287, 787 0, 3 0.0248
LRULL (RLURR) 2억 7251만 6201 106 -492, 285 -2, 0 0.0189
UUNLN (UUNRN) 2억 878만 1501 59 -97, 406 0, 1 0.0169
LUULN (RUURN) 1억 6681만 492 124 -406, -10 -2, 0 0.0161
LUNUN (RUNUN) 1억 3884만 3634 124 257, -329 2, 0 0.0161
UULNU (UURNU) 1억 1983만 2858 270 17, -299 0, -2 0.0074
LLURR (RRULL) 7419만 635 80 -12, -303 0, -2 0.025
ULLNL (URRNR) 6630만 1186 102 -249, 155 0, 2 0.0196
LNLRN (RNRLN) 6512만 9519 64 328, 119 2, 0 0.0313
UUNNL (UUNNR) 5401만 9213 240 86, -147 2, 0 0.0083
LULRL (RURLR) 4992만 5920 310 187, 221 1, 3 0.0102
LNULN (RNURN) 4630만 1314 2284 20, -366 20, -12 0.0102
LLURL (RRULR) 2972만 9621 92 -232, -285 0, -2 0.0217
ULLRU (URRLU) 2820만 8033 190 217, -262 2, 0 0.0105
LUNLR (RUNRL) 1894만 5252 76 59, -175 0, -2 0.0263
LNLRL (RNRLR) 1403만 400 74 -84, -230 0, -2 0.0270
LNNUU (RNNUU) 752만 8251 816 -150, -319 8, -4 0.0110
UULNN (UURNN) 737만 6507 354 -86, -13 -4, 0 0.0113
ULUNN (URUNN) 584만 6137 220 -10, -119 0, -2 0.0091
LRNLL (RLNRR) 539만 1983 221 74, -123 -2, -5 0.0244
LLLUL (RRRUR) 188만 1903 3289 -25, -88 -5, -2 0.0016
LUNRL (RUNLR) 158만 5398 399 -25, 159 6, 3 0.0168
LUNRN (RUNLN) 157만 7324 71 -73, 61 -1, 2 0.0315
LRLUR (RLRUL) 142만 8927 2052 95, -72 6, -6 0.0041
LNUNL (RNUNR) 52만 9538 56 105, -37 0, -2 0.0357
LUURU (RUULU) 48만 9531 718 16, 5 2, -2 0.0039
LUNUU (RUNUU) 42만 1106 106 66, 52 6, 0 0.0566
LURLR (RULRL) 41만 2128 2294 32, -10 10, -10 0.0062
ULUUR (URUUL) 33만 1026 1078 19, 7 4, -4 0.0052
ULULR (URURL) 23만 1787 277 43, -50 1, -2 0.0081
LURLU (RULRU) 18만 719 366 -56, -79 -2, -2 0.0077
ULLRL (URRLR) 13만 1249 57 -29, 8 -1, 0 0.0175
LRNRN (RLNLN) 8만 3781 38 -1, 36 -1, 1 0.0372
ULLRR (URRLL) 5만 5780 68 -28, -2 0, -2 0.0294
LLRUN (RRLUN) 5만 4324 22 15, 25 -1, 1 0.0643
LNUNU (RNUNU) 2만 638 68 -22, 22 -2, 0 0.0294
LNLNR (RNRNL) 1만 7002 56 -11, 11 -2, 2 0.0505
LURRU (RULLU) 1만 5880 44 20, 8 2, 0 0.0455
LLUUU (RRUUU) 1만 4838 232 -5, 23 0, 2 0.0086
ULRRN (URLLN) 1만 4238 64 11, -1 2, 0 0.0313
LNNUL (RNNUR) 1만 3753 59 9, 22 2, 1 0.0379
LLUNR (RRUNL) 6467 67 4, -15 1, -2 0.0334
LULNU (RURNU) 6302 54 -6, 14 0, 2 0.0370
LLUUR (RRUUL) 6005 123 -9, -12 4, -1 0.0335
ULLRN (URRLN) 5948 56 -1, -7 2, 0 0.0357
UNLLL (UNRRR) 4426 64n+712 20, 0 2, 0
0, -2
-2, 0
0, 2 		-
LLLNU (RRRNU) 3469 132 -3, 6 -1, 3 0.0240
LRLNU (RLRNU) 3379 54 -6, -13 2, -2 0.0524
LLRLU (RRLRU) 3321 29 -5, -8 -1, 0 0.0345
ULRUR (URLUL) 2542 185 3, 5 1, 0 0.0054
LLURU (RRULU) 2305 48 9, -4 2, 0 0.0417
LLRLL (RRLRR) 1864 192n+572 8, 2 2, 2
2, -2
-2, -2
-2, 2 		-
LUUNU (RUUNU) 1202 48 0, 6 0, 2 0.0417
LUUNL (RUUNR) 1071 44 9, -6 2, 0 0.0455
LLULN (RRURN) 925 54 3, -6 0, -2 0.0370
UNLLR (UNRRL) 633 48 2, -5 0, -2 0.0417
LLLUR (RRRUL) 557 52 5, 0 2, 0 0.0385
ULRRR (URLLL) 511 48 -2, -3 0, -2 0.0417
LRLRN (RLRLN) 498 17 2, -4 0, -1 0.0588
LUNLN (RUNRN) 476 69 1, 7 2, 1 0.0324
ULLLL (URRRR) 326 116n+199 -2, -2 -1, 0
-1, 2
1, 0
1, -2 		-
LULRU (RURLU) 313 30 -2, -1 -1, -1 0.0471
LLLLU (RRRRU) 241 45 -1, 0 -1, 0 0.0222
ULLLU (URRRU) 210 208n+188 -1, -1 -1, -1
-1, 1
1, 1
1, -1 		-
ULUNU (URUNU) 179 83 1, 2 1, 2 0.0269
LULRR (RURLL) 176 246 -2, -2 -6, 0 0.0244
LLRNL (RRLNR) 145 28 -3, 0 -2, 0 0.0714
LLNNU (RRNNU) 143 9 3, -2 1, 0 0.1111
LULRN (RURLN) 129 32 0, -3 0, -2 0.0625
LLLLR (RRRRL) 103 68 2, -1 -2, -2 0.0416
LUULU (RUURU) 81 23 0, -1 1, 0 0.0435
ULUUN (URUUN) 70 52 -1, 1 -2, 0 0.0385
LUNLL (RUNRR) 68 38 2, -2 2, 0 0.0526
UNLUL (UNRUR) 61 80n+50 -1, -2 0, -2
-2, 0
0, 2
2, 0 		-
LUUUN (RUUUN) 60 50 -1, 1 -2, 0 0.04
LULUU (RURUU) 57 31 -1, 0 -1, 0 0.0323
LRUUN (RLUUN) 52 28 0, 0 2, 0 0.0714
LULUL (RURUR) 35 29 -1, 0 -1, 0 0.0345
LLRUL (RRLUR) 29 9 0, 1 0, 1 0.1111
LULLU (RURRU) 24 23 0, 0 0, 1 0.0435
UNNUN 24 9 0, 0 0, 1 0.1111
ULUUL (URUUR) 12 17 0, 0 -1, 0 0.0588
ULLNN (URRNN) 12 7 0, 0 0, 1 0.1429
UNLLN (UNRRN) 12 7 0, 0 0, 1 0.1429
ULULL (URURR) 11 11 -1, 0 -1, 0 0.0909
LRNLR (RLNRL) 10 18 -1, -1 0, 2 0.1111
UUNNN 10 7 0, 0 0, 1 0.1429
LRLUN (RLRUN) 8 29 0, 0 2, -1 0.0771
ULRNU (URLNU) 8 7 0, 0 0, 1 0.1429
UNNLL (UNNRR) 8 7 0, 0 0, 1 0.1429
UNNNU 8 5 0, 0 0, 1 0.2
LLULL (RRURR) 7 13 0, -1 0, 1 0.0769
UUUNU 6 7 0, 0 0, 1 0.1429
UULLU (UURRU) 4 7 0, 0 0, 1 0.1429
UUNLR (UUNRL) 4 7 0, 0 0, 1 0.1429
UUNUU 4 5 0, 0 0, 1 0.2
LUULL (RUURR) 3 24 0, -1 0, 2 0.0833
LULLL (RURRR) 3 22 0, -1 0, 2 0.0909
ULLLR (URRRL) 2 7 0, 0 0, 1 0.1429
ULNRU (URNLU) 2 7 0, 0 0, 1 0.1429
UNLNL (UNRNR) 2 7 0, 0 0, 1 0.1429
ULLUX (URRUX) 2 5 0, 0 0, 1 0.2
UNLRX (UNRLX) 2 5 0, 0 0, 1 0.2
UNUXX 2 3 0, 0 0, 1 0.3333
LRUUR (RLUUL) 0 36 0, 0 0, 2 0.0556
LURUN (RULUN) 0 32 0, 0 0, 2 0.0625
LUURR (RUULL) 0 22 0, 0 0, 2 0.0909
ULULN (URURN) 0 14 0, 0 -1, 1 0.1010
ULRUN (URLUN) 0 11 0, 0 0, 1 0.0909
UULRN (UURLN) 0 11 0, 0 0, 1 0.0909
UULUL (UURUR) 0 9 0, 0 0, 1 0.1111
UULNR (UURNL) 0 9 0, 0 0, 1 0.1111
UUULL (UUURR) 0 9 0, 0 0, 1 0.1111
UUUUN 0 9 0, 0 0, 1 0.1111
NXXXX 0 1 0, 0 0, 1 1

4. 프로세싱 코드

모든 상태 변화를 일일히 보여주는 위의 사이트와는 달리 최종 결과만을 보여주므로 훨씬 속도가 빠르다. 프로세싱을 설치한 후, 새 스케치를 열고 아래 코드를 복사[13]하여 저장 후 실행하면 된다. 진행 과정을 보여주는 프로세싱 코드는 여기를 참고.

[ 코드 펼치기 · 접기 ]

// The following are adjustable parameters
String rule = "LR"; // Rule that the ant follows (L: turn left, R: turn right, U: turn 180, N: no change)
int initialDir = 0; // Initial direction of the ant (0: up, 1: left, 2: down, 3: right)
float cellSize = 1; // Size of cells in pixels
int numSteps = 100000000; // Number of steps done per frame
long stepLimit = 10000L*numSteps; // Maximum number of steps
int stepDisplayPeriod = 100000000; // How often showing the progress in console (Don't make it too low)

// The following are non-adjustable
Ant a; // The ant that moves around the field
int[][] field; // Array of values for cells in the field
int numColors = rule.length(); // Number of cell states
int w, h; // Width and height of screen in cells (rather than pixels)
long stepCounts = 0; // Total number of steps done

void setup() {
frameRate(1); // Frame rate per second
size(1000, 1000); // Size of screen in pixels (Adjust memory limit in settings for large size)
background(255);
noStroke();
w = int(width/cellSize);
h = int(height/cellSize);
a = new Ant(w/2, h/2, initialDir);
field = new int[w][h];
}

void draw() {
for (int c = 0; c < numSteps; c++)
if (stepCounts == stepLimit || a.xPos == 0 || a.xPos == w-1 || a.yPos == 0 || a.yPos == h-1) {
for (int m = 0; m < w; m++)
for (int n = 0; n < h; n++)
if (field[m][n] != 0) {
fill(255*((field[m][n]+numColors-1)%numColors)/(numColors-1));
rect(m*cellSize, n*cellSize, cellSize, cellSize);
}
if (stepCounts == stepLimit)
println("Total steps done:", stepCounts);
else {
fill(0);
rect(a.xPos*cellSize, a.yPos*cellSize, cellSize, cellSize);
println("Total steps done:", stepCounts+1);
}
save("ant_" + rule + ".png");
noLoop();
break;
}
else a.update();
}
class Ant {
int xPos, yPos, dir;
Ant(int tXPos, int tYPos, int tDir) {
xPos = tXPos;
yPos = tYPos;
dir = tDir;
}
void update() {
stepCounts++;
if (stepCounts % stepDisplayPeriod == 0)
println("current steps:", stepCounts, "(", xPos-w/2, "," , h/2-yPos, ")");
char rotation = rule.charAt(field[xPos][yPos]);
switch (rotation) {
case 'L':
dir++;
if (dir == 4) dir = 0;
break;
case 'R':
dir--;
if (dir == -1) dir = 3;
break;
case 'U':
dir = (dir+2)%4;
break;
}
field[xPos][yPos] = (field[xPos][yPos]+1)%numColors;
switch (dir) {
case 0:
yPos--;
break;
case 1:
xPos--;
break;
case 2:
yPos++;
break;
case 3:
xPos++;
break;
}
}
}
[1] 4방향 이동, 색 지정, 개미 수 지정, 상하좌우 루프( 토러스 격자) 기능 제공 [2] 속도 조절 기능 제공. 4방향 이동은 설정의 configuration에서 색 한 개당 (0,반시계방향회전각도,1)를 입력하면 구현할 수 있다. 예를 들어 LRUN은 (0,90,1),(0,-90,1),(0,180,1),(0,0,1)로 표현이 가능하다. [3] 인공생명체라는 용어를 처음으로 사용한 사람이기도 하다. [4] 예를 들어 LLRL이라는 규칙은 '1번째 색일 때 좌회전(L), 2번째 색일 때 좌회전(L), 3번째 색일 때 우회전(R), 4번째 색일 때 좌회전(L) 후 이동하면서 다음 색으로 변경'을 의미한다. [5] 색이 변하는 칸과는 달리 눈에 보이지는 않는다. [6] 튜링 머신(Turing Machine)과 흰개미(Termite)에서 글자를 따왔다. [7] Golly 프로그램에서의 표기법을 따라 {칸의 다음 상태, 회전 방향, 개미의 다음 상태}의 행렬로 표현한다. 회전 방향에서 1은 직진, 2는 우회전, 4는 U턴, 8은 좌회전을 의미. [8] ('반복 구간 1번 후 x좌표 변화량의 제곱' + '반복 구간 1번 후 y좌표 변화량의 제곱')의 제곱근 나누기 '반복 간격' [9] x좌표 또는 y좌표가 +-5000에 도달할 때까지 반복 구간이 등장하지 않음 [10] x좌표 또는 y좌표가 +-5000에 도달할 때까지 반복 구간이 등장하지 않음 [상하대칭] [상하대칭] [13] 그냥 복사해도 되지만, 들여쓰기 때문에 문서 편집창에서 복사하기를 추천한다.

분류