| '''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
1. 개요
[1]
플레이 링크
Conway's Game of Life, 줄여서 Game of Life. 영국의 수학자 존 호튼 콘웨이[2]가 고안해낸 세포 자동자 게임이다. 바둑판처럼 정사각형의 여러 칸으로 나뉘어진 공간에서 한 칸에 한 마리씩 있는 세포들의 삶과 죽음이 펼쳐지는 게임이다. 말이 게임이지 실제로는 게임자가 처음 세포들의 위치를 입력하면 그 규칙에 따라 삶과 죽음이 일어나는 것을 재미있게 구경(…)하면 된다.
규칙은 단순하지만 만들어 낼 수 있는 패턴이 무수히 많아서 관심을 끈 게임이기도 하며, 컴퓨터과학에서도 다루고 있는 게임이다.
2. 규칙
다음 세대로 넘어갈 때 세포들의 생사가 결정되는데, 임의의 칸에 접한 8개의 칸을 기준으로 하며 그 기준은 다음과 같다.- 죽은 칸에 접한 8칸 중 정확히 3칸에 세포가 살아 있다면 해당 칸의 세포는 그 다음 세대에 살아난다.
- 살아있는 칸과 접한 8칸 중 2칸 혹은 3칸에 세포가 살아 있다면 해당 칸의 세포는 살아있는 상태를 유지한다.
- 그 이외의 경우 해당 칸의 세포는 다음 세대에 고립돼 죽거나 혹은 주위가 너무 복잡해져서 죽는다. 혹은 죽은 상태를 유지한다.
즉, 표로 정리하면 다음과 같다.
| 칸 구분 | 인접 세포 수 | |||
| 0~1 | 2 | 3 | 4~8 | |
| 세포가 살아있는 칸 | OFF | ON | ON | OFF |
| 세포가 죽은 칸 | OFF | OFF | ON | OFF |
주변에 3개의 세포가 살아있을 때 태어나고 주변에 2, 3개의 세포가 살아있을 때 생존하므로 이를 B3/S23 과 같이 표기한다.
이때 B는 탄생(Birth)을, S는 생존(Survive)을 뜻한다.
예를 들어, 세포 5마리가 다음과 같이 배열되어 있다고 하자.
| |
이들의 생사 진행은 다음과 같다. 세포가 살아있는 칸에서 X표시는 다음 세대에 죽음을, 세포가 살아있지 않은 칸에서 O표시는 다음 세대에 살아남을 의미한다.
| 0 | 1 | 2 | 3 |
| | | | |
| 4 | 5 | 6 | 7 |
| | | | |
| 8(6) | 9(7) | 10(6) | 11(7) |
| | | | |
1세대부터 7세대까지 진행되다가 8세대 이후는 6세대와 7세대의 패턴이 무한히 반복된다.[3]
3. 패턴
다양한 패턴이 존재한다.초기 생명을 임의로 배치하면 높은 확률로 전멸하거나, 정물, 진동자, 글라이더를 남기면서 안정화된다.
3.1. 무한 패턴
결국에는 모든 세포가 죽어버리는 패턴이 존재하는가하면, 세포가 전멸하지 않고 영원히 살아남거나 생사가 무한히 반복되는 패턴이 존재한다.적은 수의 세포 배열이 무한 패턴을 형성하는 예는 다음과 같다. 이 패턴은 외부 패턴과 충돌하지 않는 이상 무한으로 반복된다.
최소한의 세포로 무한 패턴이 가능한 세포 숫자는 3이며, 정물 패턴이 가능한 최소한의 세포 숫자는 4이다.
3.1.1. 정물 (Still Lifes)
멈춰있는 형태.주변 세포를 살리지 못하는데 살아있는 세포가 죽지도 않아 계속 가만히 있는 형태이다.
정의에 따라 주기가 1인 진동자로 분류되는 경우도 있는데, 겉보기에는 움직임이 없으나 연산 자체가 멈춰버린 것은 아니기 때문이다. 무한히 연산이 실행되고 반복된다는 점에서 진동자로 분류될 여지가 있다.
| | | | |
| 블록 | 벌집 | 빵 덩이 | 보트 |
3.1.2. 진동자 (Oscillators)
진동자는 회전자를 갖고 제자리에서 무한히 반복하는 형태이다.삶과 죽음을 반복하는 세포를 회전자(rotor), 영원히 살아있는 세포를 고정자(stator)라고 부른다.
대게 고정자를 함께 가지고 있지만 고정자가 없는 특수한 진동자도 있다.
| | | | | |
| 깜빡이 (2) | 두꺼비 (2) | 등대 (2) | 펄사 (3) | 펜타 데카트론 (15) |
특정 주기의 진동자는 극도로 희소해 찾기 힘들다. 예를 하나 들자면 주기가 19, 41인 진동자는 아주 오랫동안 발견되지 않았다.[4] 그 외에 주기가 34인 진동자 또한 꽤 늦게 발견되었다. 주기가 43 이상인 진동자는 Snark라고 하는 반사기를 이용해 구성할 수 있다.
3.1.3. 우주선 (Spaceships)
한 방향으로 계속 이동하면서 주기적으로 형태가 일정한 패턴을 말한다. 한 마디로 요약하자면 전진하는 진동자이다.| | |
| 글라이더 | 경량 우주선 (LWSS) |
우주선마다 각자의 속도(velocity)가 있다. 속도는 패턴이 몇을 주기로 반복되는가와, 한 주기동안 얼마나 이동하는가에 따라 측정하는데, y의 주기동안 x칸만큼 이동하면 xc/y라고 표기한다. c는 1세대당 1칸 이동하는 속도로, 생명 게임에서 정보가 이동할 수 있는 최대 속도여서 빛의 속도를 나타내는 c 표기한다. x와 y가 서로소가 아닐 경우 약분할 수 있다.
2016년 3월 현재 발견된 우주선의 속도는 수직이나 수평으로 움직이는 것이 c/2, 3c/7, c/3, c/4, c/5, 2c/5, c/6, c/7, 2c/7, 17c/45, 31c/240, c/10이 있으며, 대각선으로 움직이는 것이 c/4, c/5, c/6, c/7, c/12이 있다. 비스듬하게 움직이는 우주선 중 그나마 가장 빠른 패턴으로는 Waterbear(물곰)이 있었으나 2018년 3월 6일 (1,2)c/6의 속도를 가진 우주선인 Sir Robin(로빈 경)이 발견되었다. 속도를 더욱 명확히 하기 위해 상술한 Sir Robin의 속도 표기 처럼 가로로 움직인 거리와 세로로 움직인 거리를 따로 적어주는 경우도 있다.
3.1.4. 특수한 무한 패턴들
- 총 (gun): 한 자리에서 패턴을 무한히 반복하면서 우주선을 계속 생성한다. 개요에 나온 가스퍼의 글라이더 건(Gosper's Glider Gun)이 대표적인 예.
- 미끄럼총 (slidegun): 총과 비슷하나, 우주선의 궤적을 한쪽으로 조금씩 밀면서 쏜다.
- 기관차 (puffer): 패턴을 남기면서 계속 전진한다.
- 갈퀴 (rake): 기관차의 특수한 경우로 남기는 패턴이 모두 우주선인 경우다. [5]
- 심지 (wick): 특정한 패턴이 길게 반복되어 진동자처럼 일정한 주기를 가지고 진동한다.
- 심지늘이개 (wickscretcher): 기관차처럼 심지를 계속 늘린다.
- 한천 (agar): 심지의 2차원 버전이라고 할 수 있다.
- 우주채우개 (spacefiller): 한천을 사방으로 계속 늘린다.
- 우주안채우개(space nonfiller): 우주채우개와 비슷하나, 테두리만 있고 내부가 비어 있다.
- 사육사 (breeder): 기관차와 비슷하나, 패턴이 2차원적으로 퍼진다.
사육사는 또 다시 4가지로 분류된다.
MMS: 갈퀴가 기관차를 뿌리는 경우.
MSM: 기관차가 총을 뿌리는 경우.
SMM: 총이 갈퀴를 뿌리는 경우.
MMM: 갈퀴가 갈퀴를 뿌리는 경우.
가끔식 우주채우개도 사육사로 쳐 주는 경우도 있으며, 미끄럼총을 이용하면 MSS나 SSS등도 만들 수 있다.
3.2. 장수 (Methuselah)
세포들이 전멸하거나 진동자에 수렴하는 상태를 안정화라고 하는데, 이 안정화에 이르기까지 오랜 세대를 요하는 패턴을 장수 패턴이라고 부른다. 영어 명칭은 므두셀라의 이름을 땄다.아래는 몇 가지 장수 패턴들의 예
| | | | |
| R-펜토미노 | 다이하드 | 도토리 | 리드카 |
R-펜토미노를 보면 알겠지만 세포 수는 불과 다섯인데도 의외로 번식력이 질기다. 다이하드와 도토리도 겨우 7개뿐이고 리드카도 겨우 13개뿐인 세포가 보기에는 단명할 것 같은데도 실제로 해보면 엄청난 번식력을 자랑한다.[6] 특정 모양의 경우 남아있는 정물과 진동자가 워낙에 많아서 무려 3만 5천 세대나 가서야 겨우 완전히 안정화되는 사례도 있다.
화면 끝이 반대쪽과 서로 연결된 경우 안정화가 된 뒤에도 남아있는 우주선이 정물이나 진동자를 건드려 불안정한 패턴이 다시 이어지는 일도 있다.
3.3. 무한 성장 패턴
장수 패턴을 보이다가 기관차 등의 무한 생성 패턴을 반복한다.| | |
| 최소 세포로 무한 성장 (10) | 최소 면적으로 무한 성장 (2x12)[7] |
3.4. 복제자
Replicator자기 자신이 복제되는 형태의 무한 생성 패턴이다.
규칙을 바꾼 변종 세포 자동자에서는 모든 패턴이 복제자인 게임이나 간단한 복제자도 있지만, 콘웨이의 생명 게임에서는 2013년에 발견되었다.
3.5. 에덴 동산
에덴 동산 배열은 이전 세대가 다음 세대로 변화하는 과정으로는 만들어질 수 없는 배열이다. 즉 초기에 이 배열로 배치하지 않는 이상 나타나지 않는다.4. 프로그램
프로그래밍 떡밥으로도 워낙에 인기있는 게임이라, 공대 등에서 프로그래밍 과제로 나가기도 한다.(..)또한 이 게임을 보거나 직접 패턴을 만들어서 볼 수 있는 프로그램 및 앱들이 제법 존재한다.
그 중 많은 사람들이 PC에서 사용하는 'Golly'라는 프로그램이 유명하다. 이 프로그램은 이미 수많은 패턴이 포함되어 있어서 킬링 타임용으로 좋다.
세포 자동자들이 소리를 내게 해 음악처럼 들을 수 있게 하는 웹사이트 도 있다.[8]
난해한 프로그래밍 언어 중에서 상대적으로 유명한 브레인퍽이 구현할수 있는 가장 복잡한 프로그램이다.
5. 그 외
수십 년 동안 사람들이 파 오던 분야라서 생명이 꽤 많다.- 이름하야 메타픽셀, 이게 뭐하는 것이냐면... 콘웨이의 생명 게임으로 콘웨이의 생명 게임을 만들어서 구동시킨 것. 복잡한 상호작용 때문에 "칸막이"가 있다는 점만 빼면 아주 크고 느려터진 콘웨이의 생명 게임이다. # # [9]
- 소수(Prime) 번째 우주선만 내보내고 나머지는 먹어버리는 프라이머(Primer). 조금 응용하면 쌍둥이 소수만 내보내거나 페르마 소수만 내보낼 수도 있다.
- 충분히 큰(49 이상) 주기의 글라이더 건 및 진동자를 모두 만들 수 있게 해 주는 허셜 회로
- 튜링 머신. 이걸 좀 응용하면 수학적 상수 계산도 가능하다.
- 한 줄 짜리 이차함수적으로 성장하는 생명 및 23개[10]짜리 이차함수적으로 성장하는 생명
- 다양한 속도의 우주선. 270세대마다 102칸을 나가는 천만 개짜리 애벌레(Catepillar)가 좋은 예시.
- 2016년 4월 현재 Caterloopillar라는 우주선이 제작되었는데, 이 방식을 이용하면 c/4 미만의 속도를 가진 수직, 수평방향으로 이동하는 우주선을 모두 만들수 있다.
정작 창시자인 콘웨이는 한때 이 게임을 싫어했다고 한다. 다른 수학적 업적이 많은데도[11] 항상 콘웨이의 생명 게임에 대한 얘기만 나와서 묻혀버린 것 같은 느낌이 들어서라고. 물론 노년에 이른 지금에 와서는 그런 감정이 많이 없어졌다고 한다. 콘웨이가 직접 해설해 주는 생명 게임.
확장판으로 규칙을 수정해 대전 기능이 추가된 Game of Life and Death라는 게임이 있다.
검색어로 이스터 에그를 만들기로 유명한 구글의 검색창에 "콘웨이의 생명게임"라고 쳐 보면, 규칙에 따라 삶과 죽음을 반복하는 세포들이 화면을 아름답게(?) 수놓을 것이다.
Wolfram Alpha의 로딩 화면도 이 라이프게임으로 되어 있다.
The Powder Toy의 Game Of Life 탭에 여러 규칙의 라이프게임이 있다.
2016학년도 경찰대학 수학 영역으로도 출제되었다.
동방 프로젝트의 캐릭터인 야고코로 에이린의 스펠 카드 중 하나인 소활 "생명유희 -라이프 게임-"은 바로 이것을 의미하며, 실제로 비슷한 탄막 패턴을 보인다.
뉴럴 클라우드의 프리릴리즈 트레일러 비디오의 배경에서 콘웨이의 생명 게임이 많이 차용되었다.
Pictured as Perfect의 BGA 중간에 이 라이프게임이 등장한다.
6. 영상
OTCAmetapixel 패턴을 이용해 Kok's galaxy 패턴을 에뮬레이팅하는 패턴이다.
OTCAmetapixel 패턴을 이용해 거대 구조 경량 우주선을 에뮬레이팅하는 패턴이다.
위 메타픽셀 패턴의 완성작. '경량 우주선을 에뮬레이팅하는 과정을 에뮬레이팅하는 과정을 에뮬레이팅하는...' 식으로 무한히 반복된다.
여러가지 패턴들의 영상이다.
글라이더와 무기를 만들어 싸우는 듯한 느낌의 패턴.
디지털 시계.
7. 사이트
이것을 다루는 위키로 LifeWiki가 있다.[1] 이 패턴은 글라이더를 계속 양산하며 무한히 반복되는 패턴 중 하나인 가스퍼의 글라이더 건(Gosper's Glider Gun). 화면이 이어져 있지 않은 이상 완전 무한 반복이된다.[2] 보통 생명 게임으로 유명하지만, 군 이론 등 다양한 수학분야에서 업적을 남긴 수학자이다. 2020년 4월 11일 코로나바이러스감염증-19 감염으로 뉴저지의 자택에서 82세의 나이로 사망했다.[3] 이 패턴은 '신호등'(Traffic Light)라고 불린다.[4] 이 게임이 1969년 언저리부터 연구되었는데 저 주기로 진동하는 진동자는 각각 2023년 7월 14일, 21일에 발견되었다. 이름은 각각 Cribbage(19), 208P41(41). 19주기 진동자는 지금까지 저 진동자만 발견되었으며, 41주기 진동자는 2의 진동자가 더 발견되었다.[5] 그런데 남기는 패턴에 우주선이 포함되기만 해도 갈퀴로 쳐주는 경우도 있다.[6] R-펜토미노는 6개의 글라이더를 날려보낸 뒤 1103세대에 안정화되고, 다이하드는 130세대에 전멸하며, 도토리는 13개의 글라이더를 날려보낸 뒤 무려 5206세대에 안정화되며, 심지어 리드카는 무려 29053세대에 안정화된다.[7] 2009년까지는 5x5였는데 갱신됐다.[8] 깃허브 레포지토리[9] 2번 항목의 규칙을 콘웨이의 생명 게임으로 표현했다고 보면 된다.[10] 26개가 8년 동안 최소 기록이었는데 2014년에 갱신되었다.[11] 대표적으로 콜라츠 추측의 일반화가 불가능하다고 증명한 것이 있다.