1. 세포 자동자(Cellular Automata)
세포 자동자(CA)란, 유한하게 정의된 상태를 가질 수 있는 셀을 규칙적으로 배치하여 서로 관련있는 셀들이 영향을 주고 받으며 변화하는 모형을 말합니다. 뭐라고 복잡한데 이런 문제가 있어요.
"익은" 상태의 토마토가 인접한 "익지 않은" 상태의 토마토를 익게 하는 규칙입니다. "토마토가 없는" 상태의 칸은 영향을 받지 않습니다. 이 문제는 3차원으로 나열된 각 칸이 셀이 되고 토마토가 익었거나 익지 않았거나 없는 3가지 상태를 갖는 세포 자동자라고 볼 수 있습니다.
2. 생명 게임(Game of Life)
존 콘웨이가 만든 게임입니다. 이 게임은 초기 상태만 정해주면 그 뒤는 규칙에 따라 알아서 흘러가는 감상 게임이에요. 존 콘웨이는 최대한 단순한 규칙에 따라 복잡하고 다양한 변화가 나타나도록 했습니다. 규칙은 다음 네 가지 뿐입니다.
- 탄생: 죽은 셀의 인접한 8칸 중 3칸이 살아있는 상태라면 해당 셀은 다음 세대에서 탄생한다.
- 생존: 살아있는 셀의 인접한 8칸 중 2~3칸이 살아있는 상태라면 해당 셀은 다음 세대에서 생존한다.
- 고독: 살아있는 셀의 인접한 8칸 중 2칸 미만의 셀이 살아있는 상태라면 해당 셀은 다음 세대에서 고독해서 죽는다.
- 과밀: 살아있는 셀의 인접한 8칸 중 3칸 초과의 셀이 살아있는 상태라면 해당 셀은 다음 세대에서 과밀하여 죽는다.
그러니까 예를 들면 다음과 같은 변화가 가능합니다.
이 변화는 3세대를 주기로 같은 상태가 반복되는 "진동자(Oscillators)"입니다.
이 외에도 생존 셀의 상태가 변화하지 않는 정물(Still Lifes), 한 방향으로 계속 이동하며 주기적으로 같은 형태를 반복하는 우주선(Spaceships) 등이 있습니다.
3. 랭턴의 개미(Langton's ant)
생명 게임보다 좀 더 단순한 규칙으로 작동합니다. 개미가 흰색 그리드 위에서 움직이기 시작합니다. 규칙은 다음 두 가지입니다.
- 흰색 칸: 현재 칸을 검은색으로 바꾸고 왼쪽으로 90도 회전하여 앞으로 한 칸 이동
- 검은색 칸: 현재 칸을 흰색으로 바꾸고 오른쪽으로 90도 회전하여 앞으로 한 칸 이동
색깔을 추가하고 규칙을 더해서 다양한 패턴을 만드는 것도 가능하다고 합니다.
...
이거 왜 갑자기 꽂혀서 글까지 쓰려고 한 걸까..?
