콘웨이의 생명 게임(Conway's Game of Life)은 두 사람이 겨루는 게임이 아닙니다. 시작할 때 살아 있는 칸을 정하면 이후에는 아무도 개입하지 않고 정해진 규칙에 따라 격자가 변합니다. 각 칸은 살아 있음과 죽어 있음 두 상태만 가지며, 다음 상태는 주변 8칸 가운데 살아 있는 칸의 수로 결정됩니다. 규칙은 매우 짧지만 멈춰 있는 모양, 주기적으로 진동하는 모양, 이동하는 모양이 생깁니다. 특정 구조물을 의도적으로 조립하면 논리 연산과 기억, 신호 전달까지 구현할 수 있어 보편 계산이 가능합니다. 단순히 아무 초기 무늬나 두면 컴퓨터가 저절로 생긴다는 뜻은 아닙니다. 계산 능력은 필요한 부품을 정확히 배치한 구성으로 증명됩니다.
무한한 정사각 격자와 두 가지 상태
표준 생명 게임은 경계가 없는 2차원 정사각 격자를 가정합니다. 각 칸은 살아 있으면 1, 죽어 있으면 0으로 표시할 수 있습니다. 한 칸과 변을 공유하는 상하좌우 4칸뿐 아니라 대각선 4칸도 이웃이므로 이웃은 모두 8개입니다. 시간은 세대라는 이산 단계로 흐릅니다. 한 세대의 모든 칸은 이전 세대의 상태를 기준으로 동시에 갱신됩니다. 왼쪽 위부터 차례로 즉시 바꾸면 이미 바뀐 값이 뒤 칸의 계산에 섞여 표준 규칙과 다른 결과가 나옵니다. 프로그램에서는 현재 격자와 다음 격자를 나누거나, 다음 상태를 별도 자료구조에 기록한 뒤 한꺼번에 교체합니다.
B3/S23으로 줄여 쓰는 네 가지 규칙
살아 있는 칸은 이웃이 2개 또는 3개이면 다음 세대에도 살아남습니다. 이웃이 0개나 1개이면 과소밀도로 죽고, 4개 이상이면 과밀도로 죽습니다. 죽은 칸은 살아 있는 이웃이 정확히 3개일 때 새로 태어납니다. 이를 B3/S23이라고 적습니다. B는 birth, S는 survival을 뜻합니다. 죽은 칸의 탄생 조건은 3, 살아 있는 칸의 생존 조건은 2와 3이라는 의미입니다. ‘주변 8칸 중 세 칸이 살아 있으면 무조건 생존한다’고만 외우면 현재 칸의 상태를 빼먹게 됩니다. 현재 죽은 칸과 살아 있는 칸에 적용되는 조건이 서로 다릅니다.
| 현재 상태 | 살아 있는 이웃 수 | 다음 상태 |
|---|---|---|
| 죽음 | 정확히 3 | 탄생 |
| 죽음 | 그 밖의 수 | 죽음 유지 |
| 생존 | 2 또는 3 | 생존 유지 |
| 생존 | 0, 1 또는 4 이상 | 죽음 |
작은 무늬가 보여 주는 세 가지 행동
2×2로 꽉 찬 블록은 다음 세대에도 바뀌지 않는 정물(still life)입니다. 각 살아 있는 칸에는 이웃이 세 개 있고, 바깥의 죽은 칸에는 정확히 세 이웃이 생기지 않도록 배치되어 있기 때문입니다. 일렬로 붙은 세 칸인 블링커(blinker)는 가로와 세로 모양을 번갈아 나타내는 주기 2의 진동자입니다. 글라이더(glider)는 다섯 칸으로 된 작은 무늬로 네 세대가 지나면 대각선 방향으로 한 칸 이동한 같은 모습이 됩니다. 격자 전체가 정지하거나 무작위로 흩어지기만 하는 것이 아니라, 안정·주기·이동이라는 서로 다른 행동이 같은 규칙에서 나옵니다.
글라이더는 생명 게임에서 신호처럼 사용할 수 있습니다. 특정 방향과 시점에 글라이더를 보내면 다른 구조와 충돌해 사라지거나 진행 방향이 바뀌고, 새로운 글라이더를 만들 수 있습니다. 글라이더 건(glider gun)은 일정한 주기로 글라이더를 계속 방출하는 유한한 무늬입니다. 1970년에 발견된 고스퍼 글라이더 건은 유한한 초기 무늬가 무한히 성장할 수 있다는 사실을 보여 준 중요한 구성입니다. 다만 글라이더나 건의 존재 자체만으로 보편 계산이 자동 증명되는 것은 아닙니다. 신호를 조합해 필요한 논리와 기억을 구현하는 단계가 더 필요합니다.
논리 게이트를 격자 위에서 만드는 방법
디지털 회로는 AND, OR, NOT 같은 논리 게이트를 조합해 계산합니다. 생명 게임에서는 글라이더의 존재를 1, 부재를 0으로 해석하고 충돌을 이용할 수 있습니다. 두 방향에서 오는 글라이더가 특정 지점과 시간에 충돌할 때만 출력 글라이더가 남도록 구성하면 AND에 해당합니다. 입력 신호를 다른 주기 신호와 충돌시켜 입력이 없을 때만 출력이 통과하도록 만들면 NOT 동작을 구성할 수 있습니다. 신호의 경로를 교차시키거나 지연하는 배치도 필요합니다. 이렇게 만들어진 부품은 일상적인 반도체 회로보다 훨씬 크고 느리지만, 계산 가능성을 증명하는 데는 물리적 효율이 아니라 논리적 동작의 정확성이 중요합니다.
튜링 완전하다는 말의 정확한 뜻
어떤 체계가 충분한 시간과 기억 공간을 사용할 수 있을 때 보편 튜링 기계가 수행하는 계산을 모사할 수 있으면 튜링 완전하다고 합니다. 생명 게임의 무한 격자는 필요에 따라 확장되는 기억 공간 역할을 할 수 있고, 글라이더와 안정 구조를 조합해 신호 처리와 저장 장치를 만들 수 있습니다. 로버트 웨인라이트는 1974년 논문 ‘Life is universal!’에서 생명 게임 형태가 컴퓨터를 모사할 수 있는 구성을 설명했습니다. 이후 생명 게임 안에서 작동하는 튜링 기계와 보편 튜링 기계가 실제 패턴으로 제작되었습니다. 이는 B3/S23이라는 지역 규칙이 원리상 일반 계산을 표현하기에 충분하다는 구성적 결과입니다.
튜링 완전성은 모든 초기 상태의 미래를 빠르게 예측할 수 있다는 뜻과 반대에 가깝습니다. 계산할 수 있는 모든 절차를 담을 수 있으므로, 특정 패턴의 장기 행동에 관한 질문은 일반 프로그램의 정지 여부만큼 어려운 문제를 포함할 수 있습니다. 하지만 이 사실을 ‘생명 게임의 모든 질문은 풀 수 없다’고 확대해서는 안 됩니다. 블록이나 블링커처럼 직접 계산할 수 있는 패턴이 많고, 유한한 시간까지의 상태는 규칙을 반복 적용해 정확히 구할 수 있습니다. 보편성은 가능한 구성의 범위에 관한 말이지 모든 작은 무늬가 복잡하다는 말이 아닙니다.
무한 격자와 실제 프로그램의 유한 화면
수학적 정의는 무한 격자를 사용하지만 컴퓨터 화면과 메모리는 유한합니다. 구현 방식에 따라 가장자리 밖을 항상 죽은 칸으로 취급하거나, 반대편 가장자리와 이어 붙인 토러스 형태로 만들거나, 살아 있는 칸 주변만 희소 집합으로 저장할 수 있습니다. 같은 초기 무늬도 경계에 닿으면 방식에 따라 결과가 달라집니다. 튜링 완전성에 관한 표준 설명은 충분히 큰 또는 무한한 평면에서 필요한 구조를 놓을 수 있다는 조건을 사용합니다. 작은 고정 격자에는 가능한 상태가 유한개뿐이므로 언젠가 이전 상태를 반복하게 되며, 무제한 기억을 요구하는 보편 계산과는 조건이 다릅니다.
상태 수와 완전 탐색이 빠르게 커지는 이유
가로 W칸, 세로 H칸인 유한 격자에는 칸이 WH개 있습니다. 각 칸이 0 또는 1이므로 가능한 전체 상태는 2^(WH)개입니다. 10×10 격자만 해도 2^100, 약 1.27×10^30가지입니다. 한 상태의 다음 상태를 계산하는 일은 각 칸의 8개 이웃을 세면 되므로 격자 크기에 비례하지만, 모든 초기 상태를 조사하는 일은 지수적으로 커집니다. 지역 갱신 규칙이 단순하다는 사실과 전체 상태 공간이 작다는 주장은 서로 다릅니다. 생명 게임이 복잡한 양상을 보이는 한 이유는 이 거대한 상태 공간 안에서 충돌과 반복, 이동 구조가 함께 나타나기 때문입니다.
세대 계산을 손으로 확인하는 순서
- 현재 살아 있는 칸과 그 주변 후보 칸을 표시합니다.
- 후보마다 주변 8칸의 살아 있는 수를 셉니다.
- 현재 살아 있는 칸은 이웃이 2개 또는 3개인지 확인합니다.
- 현재 죽은 칸은 이웃이 정확히 3개인지 확인합니다.
- 판정을 별도 표에 적고 모든 칸을 동시에 다음 세대로 바꿉니다.
- 유한 격자라면 가장자리 조건이 무엇인지 먼저 정합니다.
결정론인데도 매번 새로 계산해야 하는 까닭
생명 게임에는 주사위나 난수가 없습니다. 같은 초기 상태에서는 언제나 같은 다음 상태가 나오므로 완전히 결정론적입니다. 그런데 결정론적이라는 말은 멀리 떨어진 미래를 간단한 공식으로 항상 건너뛸 수 있다는 뜻이 아닙니다. 정물과 진동자는 주기를 찾아 빠르게 예측할 수 있지만, 신호 충돌을 계산 장치로 꾸민 패턴은 내부 계산 과정을 따라가야 결과를 알 수 있습니다. ‘규칙이 단순하다’, ‘결과가 결정되어 있다’, ‘결과를 쉽게 예측할 수 있다’는 서로 다른 명제입니다.
생명 게임을 정확하게 이해하는 핵심
- 각 칸은 주변 8칸을 보고 모든 칸이 동시에 갱신됩니다.
- 탄생은 죽은 칸의 이웃이 3개일 때, 생존은 살아 있는 칸의 이웃이 2개 또는 3개일 때입니다.
- 글라이더는 이동 신호로 쓸 수 있고 글라이더 건은 주기적으로 신호를 만듭니다.
- 보편 계산은 논리 게이트와 기억장치를 의도적으로 구성한 패턴으로 증명됩니다.
- 아무 무작위 패턴이나 컴퓨터가 되는 것은 아니며 튜링 완전성은 가능한 구성의 존재를 뜻합니다.
- 유한 프로그램에서는 경계 조건에 따라 표준 무한 격자와 결과가 달라질 수 있습니다.
콘웨이의 생명 게임은 네 줄로 요약되는 지역 규칙에서 얼마나 다양한 전체 행동이 나올 수 있는지 보여 줍니다. 이웃 수를 세는 계산만으로 정물, 진동자, 이동 패턴이 생기고, 정교하게 배치한 글라이더와 안정 구조는 논리 회로를 이룹니다. 따라서 생명 게임의 튜링 완전성은 규칙의 신비함을 주장하는 표현이 아니라, 실제 계산 부품을 격자 위에 구성할 수 있다는 수학적·공학적 결과입니다.
패턴의 주기와 이동 속도를 읽는 법
패턴이 p세대 뒤 같은 위치에서 같은 모양으로 돌아오면 주기 p의 진동자입니다. 다른 위치로 옮겨 같은 모양이 되면 우주선(spaceship)으로 분류할 수 있습니다. 글라이더는 4세대 동안 대각선으로 한 칸 이동하므로 속도를 c/4라고 표현합니다. 여기서 c는 생명 게임 격자에서 정보가 한 세대에 이동할 수 있는 자연스러운 거리 척도이며 진공의 실제 광속을 뜻하지 않습니다. 수평·수직 이동과 대각선 이동은 가능한 전파 상한이 달라질 수 있으므로 패턴 속도 표기는 생명 게임의 격자 좌표와 세대를 기준으로 읽어야 합니다.
주기를 확인할 때 화면에 보이는 일부만 비교하면 멀리 이동한 글라이더를 놓칠 수 있습니다. 전체 유한 상태를 저장해 과거 상태와 비교하거나, 이동 벡터까지 고려해 같은 형태인지 검사해야 합니다. 무한 평면을 희소하게 구현할 때는 살아 있는 칸의 좌표 집합을 정규화해 형태를 비교할 수 있습니다. 이 과정은 생명 게임이 단순한 그림 감상에 그치지 않고 상태 전이, 주기 탐지, 해시와 집합 자료구조를 실험하는 계산 모델로도 쓰이는 이유를 보여 줍니다.
참고 자료
- Robert T. Wainwright, Life is universal!, Winter Simulation Conference (1974): https://doi.org/10.1145/800290.811303
- Wainwright 논문 공개 PDF: https://informs-sim.org/wsc74papers/1974_0045.pdf