세포 자동자 소개 | 생명 게임, 규칙 30, 규칙 110 등

네 가지 기본 요소

모든 세포 자동자는 같은 네 가지 요소로 이루어집니다. 격자는 세포가 사는 공간입니다. 1차원 선일 수도, 체스판 같은 2차원 평면일 수도, 심지어 3차원 공간일 수도 있습니다. 상태는 세포가 될 수 있는 값입니다. 가장 단순한 경우 세포는 이진값을 가집니다. 검은색 또는 흰색, 1 또는 0입니다. 이웃은 한 세포에 직접 영향을 주는 세포들의 집합입니다. 정사각형 격자에서는 보통 주위의 여덟 세포 전부인 무어 이웃이나, 북, 동, 남, 서만 포함하는 폰 노이만 이웃을 씁니다. 규칙은 자동자의 두뇌로, 각 세포에 새 상태를 주는 논리입니다. 예를 들면 이렇습니다. 내가 살아 있지만 살아 있는 이웃이 둘보다 적으면, 나는 외로워서 죽는다. 모든 세포가 같은 순간에 같은 규칙을 적용합니다.

1. 콘웨이의 생명 게임

규칙: B3/S23. 살아 있는 세포는 살아 있는 이웃이 2개나 3개이면 살아남습니다. 죽은 세포는 정확히 3개이면 살아납니다. 그 밖의 모든 세포는 다음 세대에 죽은 상태가 됩니다. 존 콘웨이가 1970년에 고안했고, 마틴 가드너가 사이언티픽 아메리칸에 쓴 칼럼 덕분에 유명해졌습니다. 글라이더, 진동자, 우주선이 생겨납니다. 같은 해 빌 고스퍼가 첫 글라이더 총을 찾았습니다. 30세대마다 새 글라이더를 영원히 발사하는 패턴입니다. 글라이더가 신호를 실어 나르고 논리 게이트처럼 충돌할 수 있으므로, 생명 게임은 계산을 수행할 수 있습니다. 무엇보다 단순한 규칙에서 복잡한 행동이 자라난다는 것을 보여 줍니다.

생명 게임에서 대각선으로 글라이더를 줄지어 발사하는 고스퍼 글라이더 총 — 330세대 후의 고스퍼 글라이더 총. PictorX에서 렌더링.

2. 규칙 30

유형: 1차원 기본 세포 자동자. 각 세포의 다음 상태는 자신과 양옆의 두 이웃에 따라 정해지며, 세대마다 이전 줄 아래에 새 줄로 그려집니다. 스티븐 울프럼이 1983년에 규칙 30을 소개했습니다. 검은 세포 하나에서 시작하면 혼돈스러운 삼각형이 자랍니다. 규칙이 결정론적인데도 무작위처럼 보이며, 그 가운데 열이 의사 난수 생성기로 쓰였을 정도입니다. 같은 종류의 삼각형이 Conus textile 고둥 껍데기의 색소 무늬에도 나타납니다.

검은 세포 하나에서 자란 규칙 30 삼각형, 오른쪽은 혼돈스럽고 왼쪽은 줄무늬 — 검은 세포 하나에서 시작해 224세대가 지난 규칙 30. PictorX에서 렌더링.

3. 규칙 110

유형: 규칙 30과 같은 1차원 기본 세포 자동자이지만, 여덟 개의 답으로 된 표가 다릅니다. 규칙 110은 계산 보편성이 증명되었습니다. 매슈 쿡은 알맞은 첫 줄이 있으면 규칙 110이 범용 컴퓨터가 수행할 수 있는 어떤 계산도 흉내 낼 수 있음을 보였습니다. 규칙 110에는 반복되는 배경 위를 이동하다가 만나면 상호작용하는 구조가 있습니다. 증명은 바로 이 충돌을 논리로 사용합니다. 아주 단순한 규칙이 임의의 계산을 흉내 낼 수 있음을 보여 줍니다.

오른쪽 세포 하나에서 자라 중첩된 삼각형으로 왼쪽으로 퍼지는 규칙 110 — 오른쪽 가장자리의 검은 세포 하나에서 시작한 규칙 110. PictorX에서 렌더링.

4. Brian's Brain

상태: 꺼짐, 켜짐(발화), 불응기. 규칙: 꺼진 세포는 정확히 2개의 이웃이 켜져 있으면 켜집니다. 켜진 세포는 불응기가 됩니다. 불응기 세포는 꺼집니다. 브라이언 실버먼이 고안했습니다. 세포는 발화한 뒤 한 세대 동안 쉬어야 하므로, 모든 펄스는 지나온 자리에서 계속 멀어집니다. 그 결과 스스로 움직이는 패턴의 무리가 생기는데, 신경 조직이나 심장 근육 같은 흥분성 매질 속 파동을 닮았고 종종 살아 있는 유기체처럼 보입니다.

무작위 영역에서 퍼져 나가는 Brian's Brain, 발화하는 세포는 노란색, 사라지는 자취는 보라색 — 무작위 영역에서 70세대가 지난 Brian's Brain, 사라지는 자취 포함. PictorX에서 렌더링.

5. Wireworld

상태: 비어 있음, 전자 머리, 전자 꼬리, 도체. 규칙: 머리는 꼬리가 되고, 꼬리는 도체가 되며, 도체는 이웃 중 정확히 1개나 2개가 머리이면 머리가 됩니다. 빈 세포는 계속 비어 있습니다. Wireworld도 브라이언 실버먼이 1987년에 고안했습니다. 도체 세포는 전선이고, 머리 뒤에 꼬리가 따라오는 것이 전선을 따라 달리는 전자입니다. 전자 회로를 시뮬레이션할 수 있습니다. 전자 하나가 든 전선 고리는 클럭, 작은 홈은 다이오드가 되고, 세포 몇 개로 논리 게이트를 만들 수 있습니다. 그 안에 완전한 컴퓨터도 만들어졌습니다. 데이비드 무어와 마크 오언의 Wireworld 컴퓨터가 그 예로, 소수를 계산합니다.

클럭 고리 두 개, 다이오드 두 개, XOR 게이트 하나로 된 Wireworld 회로, 노란 전선 위의 파란색과 빨간색 전자 — Wireworld의 클럭 두 개, 다이오드 두 개, XOR 게이트. PictorX에서 렌더링.

울프럼의 256가지 규칙과 네 가지 클래스

두 이웃을 가진 1차원 세포는 111부터 000까지 여덟 가지 패턴 중 하나를 봅니다. 규칙은 각 패턴에 대해 새 상태를 정하므로 8비트이고, 기본 규칙은 2⁸ = 256가지입니다. 여덟 개의 답을 이진수로 읽으면 규칙의 이름이 됩니다. 규칙 30은 00011110이고, 규칙 110은 01101110입니다. 스티븐 울프럼은 규칙을 그 동작에 따라 질서에서 혼돈까지 분류했습니다. 1. 클래스 1은 균일한 상태로 안정됩니다. 2. 클래스 2는 안정되거나 반복되는 구조로 자리 잡습니다. 3. 클래스 3은 규칙 30처럼 혼돈스럽고 무작위처럼 보이는 상태로 남습니다. 4. 클래스 4는 규칙 110처럼 질서와 혼돈의 경계에서 움직이고 상호작용하는 구조를 만듭니다.

난이도 순위

생명 게임 ★☆☆☆☆ · 규칙 30 ★☆☆☆☆ · Brian's Brain ★★☆☆☆ · Wireworld ★★★★☆ · 규칙 110 ★★★★★. 처음 두 가지는 지켜보기만 해도 이해됩니다. 규칙 110은 움직이는 구조를 반복되는 배경 속에 숨깁니다.

시각적으로 가장 아름다운 것

1. Brian's Brain · 2. 콘웨이의 생명 게임 · 3. 규칙 30 · 4. 규칙 110 · 5. Wireworld.

수학적으로 가장 중요한 것

1. 규칙 110: 보편성 · 2. 생명 게임: 보편성과 창발 · 3. 규칙 30: 혼돈과 무작위성 · 4. Wireworld: 디지털 논리 · 5. Brian's Brain: 흥분성 시스템.

자연, 물리학, 암호학 속에서

세포 자동자는 자연, 물리학, 암호학의 복잡계를 시뮬레이션하는 데 쓰입니다. 이 아이디어는 1940년대의 스타니스와프 울람과 존 폰 노이만으로 거슬러 올라가며, 두 사람은 세포 격자를 이용해 스스로를 복제할 수 있는 기계를 설계했습니다. 현실 세계에서는 일부 조개껍데기의 색소 무늬에서 세포 자동자를 볼 수 있습니다. Conus textile 고둥이 그 예로, 그 삼각형은 규칙 30과 닮았습니다. 또 보석도마뱀의 비늘은 세포 자동자에 가까운 규칙에 따라 초록색과 검은색 사이를 오갑니다. 물리학자들은 세포 자동자로 기체의 흐름, 모래 더미, 산불을 모형화합니다. 규칙 30은 겉보기에 무작위적이어서 난수 생성기와 스트림 암호의 후보가 되었습니다.

PictorX에서 살펴보기

세포 자동자를 열어 다섯 가지를 모두 실행해 보세요. 글라이더 총, 우주선 함대, 또는 안정되기까지 1,103세대가 걸리는 R-펜토미노를 지켜보세요. B36/S23 같은 아무 생명 게임 규칙이나 0부터 255까지의 아무 기본 규칙 번호를 입력하세요. 세포를 그리고 지우고, Wireworld 회로로 전자를 보내고, 가장자리를 연결하고, 컬러풀 모드로 바꿔 보세요. PNG로 저장하거나 캔버스를 PictorX 편집기에서 여세요.

자주 묻는 질문

세포 자동자란 무엇인가요?

모든 세포가 상태를 가지는 세포 격자입니다. 매 단계마다 모든 세포가, 한 세포와 그 이웃만 보는 하나의 고정된 규칙에 따라 함께 갱신됩니다. 규칙은 단순하지만, 무늬는 복잡하고 예측할 수 없을 수 있습니다.

세포 자동자는 누가 발명했나요?

1940년대 로스앨러모스의 스타니스와프 울람과 존 폰 노이만입니다. 존 콘웨이의 생명 게임(1970)이 이 아이디어를 대중화했고, 스티븐 울프럼은 1980년대에 256가지 기본 규칙을 연구했습니다.

어떤 세포 자동자가 튜링 완전한가요?

여기 있는 다섯 가지 중 규칙 110과 생명 게임은 보편성이 증명되었고, Wireworld는 완전한 컴퓨터를 담을 수 있습니다. 보편적이라는 것은 알맞은 시작 패턴이 있으면 범용 컴퓨터가 할 수 있는 어떤 계산도 수행할 수 있다는 뜻입니다.

울프럼의 네 가지 클래스는 무엇인가요?

클래스 1은 균일한 상태로 사라지고, 클래스 2는 안정되거나 반복되는 구조로 자리 잡고, 클래스 3은 규칙 30처럼 혼돈스러운 상태로 남고, 클래스 4는 규칙 110처럼 움직이며 상호작용하는 구조를 만듭니다.

규칙 30은 왜 무작위처럼 보이나요?

모든 단계는 정해져 있지만, 각 세포는 왼쪽 이웃을 나머지 둘과 섞는데, 그 방식이 작은 차이를 빠르게 퍼뜨립니다. 가운데 열에서는 아직 단순한 패턴이 발견되지 않았고, 그래서 난수를 만드는 데 쓰여 왔습니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

세포 자동자 체험하기