친구가 재미있는 개념을 알려줬는데, 얘기를 하다보니 딱 pattern관련한 얘기라서 Game of Life에 대해서 알아보면 좋을 거 같다~!

Game of Life

The Game of Life는 간단히 Life라고도 알려져 있는데, 영국 수학자 John Horton Conway 가 고안한 세포 자동화(cellular automaton)이다. 이는 zero-player game으로, 세포의 진화가 초기 상태(initial state)에 의해 결정되고, 추가적인 입력이 더 필요 없다는 것이다. Game of Life는 초기 구성(initial configurtaion)을 만들고 그것이 어떻게 진화하는지 관찰함으로써 상호 작용합니다. 이는 Turing Complete하고, 보편적인 생성자나 다른 튜링 머신을 시뮬레이션할 수 있다는 의미이다. 이는 "Game of Life"가 아주 복잡한 계산을 할 수 있다는 의미입니다.

Turing Complete
이 게임이 이론적으로 컴퓨터처럼 작동할 수 있다는 뜻이다. 즉, Game of Life를 사용해서 우리가 컴퓨터로 할 수 있는 모든 계산을 할 수 있다는 것이다. 예를 들어, Game of Life 안에서 특별한 패턴을 만들어서 다른 컴퓨터처럼 동작할 수 있기 때문에 단순한 놀이가 아니라, 매우 강력한 계산 능력을 가지고 있는 시스템이라고 볼 수 있다.

Rule

"Game of Life"의 세계관은 무한히 확장되는 2차원의 직교 격자(grid)로 이루어져 있다. 각 격자는 두 가지 상태만 가질 수 있고, 살아있거나(live) 상태 또는 죽은 상태(dead)의 경우만 있다. 각 격자는 수평$\cdot$수직$\cdot$대각선으로 인접한 여덟 개의 이웃한 격자들과 상호작용한다. 각 시간 단위마다 Grid의 상태에 따라 변화가 일어난다:

• 살아 있는 격자가 이웃한 살아 있는 격자가 두 개 미만이면, 이는 과소 인구로 인해 죽는다.
• 살아 있는 격자가 이웃한 살아 있는 격자가 두 개 또는 세 개면, 다음 세대로 산다.
• 살아 있는 격자가 이웃한 살아 있는 격자가 네 개를 초과하면, 이는 과잉 인구로 인해 죽는다.
• 죽어 있는 격자가 이웃한 살아 있는 격자가 정확히 세 개면, 이는 번식으로 인해 살아 있는 격자가 살아난다.

예제

아래 그림처럼, 0 번째 세대(Generation)을 Seed(initial state)로 여러 세대를 거치면서, 패턴(rule)이 반복되고 51개에서 32개만 남게 되었다. (왠지 텅텅 비어서 씁쓸한..ㅎㅎ)

위키피디아에 가면 직접 도트를 찍어서 해볼 수 있다. (아래 Reference Link 참조)

기타

Surreal Number
수학에서 초현실수(超現實數, 영어: surreal number)는 모든 실수를 비롯하여 초실수의 무한대와 무한소까지 포함하도록 구성된, 집합이 아닌 전순서 모임(proper class)이다.

Reference
[1] Game of Life, https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
[2] Surreal number, https://en.wikipedia.org/wiki/Surreal_number