← 목록으로
계산 이론 · 복잡도 · 게임

게임, 컴퓨터가 되다

When a game becomes a computer — Turing & NP, played out

퍼즐 게임 안에서 진짜 컴퓨터를 만들 수 있다면? 그리고 우리가 즐기던 지뢰찾기·스도쿠가 세계 7대 수학 난제와 한통속이라면? 게임을 진지하게 분석하면, 계산이란 무엇인가라는 가장 깊은 질문에 가닿습니다.

0Baba is You가 컴퓨터라고?

Baba is You는 화면에 놓인 규칙 글자블록을 밀어서 규칙 자체를 바꾸는 퍼즐 게임입니다. BABA IS YOU(바바가 곧 나), WALL IS STOP(벽은 막힘), FLAG IS WIN(깃발은 승리) 같은 문장을 직접 조립하고 부수죠. 그런데 이 깜찍한 게임이, 놀랍게도 튜링 완전(Turing-complete) 하다는 사실이 밝혀졌습니다. 쉽게 말해 — 이 게임 안에 "컴퓨터"를 통째로 지어 넣을 수 있다는 뜻입니다.

1936년 앨런 튜링은 계산이라는 모호한 개념을, 무한한 테이프 위에서 기호를 읽고 쓰며 상태를 바꾸는 튜링 기계라는 극도로 단순한 모형으로 정의했습니다. 그리고 처치–튜링 명제는 말합니다 — "우리가 '계산'이라 부를 만한 것은 전부 튜링 기계로 할 수 있다." 그래서 어떤 시스템이 튜링 기계를 흉내 낼 수 있으면, 그것을 튜링 완전하다고 부르고, 그 시스템은 원리적으로 무엇이든 계산할 수 있습니다 — 당신의 노트북이 하는 모든 일을요.

하지만 컴퓨터가 못 하는 일도 있습니다. 그것도 "아직 못 한다"가 아니라 영원히, 원리적으로 불가능한 일이요. 이 이야기부터 시작하죠.

1컴퓨터가 풀 수 없는 문제 — 정지 문제

아주 자연스러운 질문 하나. "어떤 프로그램과 입력이 주어졌을 때, 이게 언젠가 멈출까, 아니면 영원히 돌까?"를 판정해 주는 만능 프로그램을 만들 수 있을까요? 이것이 정지 문제(halting problem)입니다. 튜링은 1936년, 그런 프로그램은 존재할 수 없음을 증명했습니다.

자기 자신을 무는 논리 — 대각선 논법
멈출지를 판정하는 \(\textsf{HALT}(P)\)가 있다고 칩시다. 이걸로 심술궂은 프로그램 \(D\)를 만듭니다 — "\(\textsf{HALT}(D)\)가 '멈춘다'라고 하면 일부러 영원히 돌고, '안 멈춘다'라고 하면 즉시 멈춰라." 이제 \(D\)는 멈출까요? 멈춘다면 정의상 영원히 돌아야 하고, 안 멈춘다면 즉시 멈춰야 합니다 — 어느 쪽도 모순입니다. 그러니 \(\textsf{HALT}\)는 애초에 존재할 수 없습니다. (칸토어의 대각선·러셀의 역설·괴델의 불완전성이 모두 이 한 가지 논법의 변주라는 이야기는 로비어 부동점 정리 편에서 한데 묶었습니다.)

이렇게 "알고리즘으로는 절대 풀 수 없는" 문제를 결정 불가능(undecidable)하다고 합니다. 정지 문제는 그 첫 번째 사례였고, 이후 수많은 문제가 정지 문제로 환원되어 "이것도 풀 수 없다"가 줄줄이 증명됩니다. 바로 이 환원이라는 무기가, 다음 이야기의 핵심입니다.

2튜링 완전과 "환원"이라는 무기

어떤 시스템(게임이든 언어든 기계든)이 튜링 완전함을 보이려면, 튜링 기계의 동작 하나하나를 그 안에서 재현해 보이면 됩니다. 그런데 튜링 기계를 직접 흉내 내는 건 번거로워서, 보통은 이미 튜링 완전하다고 밝혀진 더 단순한 시스템을 그 안에 심습니다. 이것이 환원(reduction)입니다 — "내 문제 안에 이미 만능인 X를 만들 수 있다 → 그러니 내 문제도 만능이다."

환원의 단골 표적이 바로 규칙 110(Rule 110)입니다. 한 줄로 늘어선 칸들이 "양옆과 나를 보고 다음 세대의 흑백을 정한다"는 초간단 규칙만 따르는 1차원 세포 자동자인데, 매튜 쿡이 2004년 이것이 튜링 완전함을 증명했죠. 세상에서 가장 단순해 보이는 규칙조차 만능 컴퓨터라는 충격이었습니다. 덕분에 "내 시스템 안에 규칙 110을 구현했다"만 보이면 튜링 완전성 증명이 끝납니다.

규칙 110 — 한 줄이 시간 따라 그려 내는 무늬

110 = 01101110
맨 윗줄이 0세대, 아래로 내려갈수록 다음 세대입니다. 각 칸은 자신과 좌·우 이웃(3칸)의 흑백 조합 8가지에 따라 아랫줄 값이 정해지죠(그 8개의 답을 이진수로 늘어놓은 게 곧 "110"). 윗줄 칸을 클릭해 초기 상태를 직접 바꿔 볼 수도 있습니다. 이 단순한 규칙이 빚어내는 복잡한 구조 — 비스듬히 흐르는 패턴(글라이더)들이 서로 충돌하는 그 안에서 — 만능 계산이 일어납니다.
튜링 완전이 주는 것
어떤 게임이 튜링 완전하면, 그 안에 논리 게이트(AND·OR·NOT), 기억장치, 무한 반복을 지을 수 있고, 따라서 원리적으로 그 게임판 위에서 다른 게임을 돌리는 일조차 가능합니다. 동시에, 1장의 정지 문제가 그대로 따라옵니다 — "이 게임의 이 배치가 언젠가 끝나는가?"를 판정하는 만능 알고리즘은 존재할 수 없습니다.

3Baba is You의 튜링 완전성

이제 0장으로 돌아갑니다. Baba is You가 특별한 건, 게임의 규칙이 게임판 위의 물체라는 점입니다. 규칙 글자블록을 밀어 문장을 만들고 부수며, 플레이어의 한 수가 규칙 전체를 바꿔 버리죠. 여기에 이 게임은 X IS Y뿐 아니라 X ON Y IS Z, X NEAR Y IS Z 같은 조건부 규칙까지 지원합니다.

이 두 가지 — 상태를 들고 있는 물체와 조건에 따라 발동하는 규칙 — 가 바로 계산의 두 기둥인 기억(memory)과 분기(if-then)에 정확히 대응합니다. 그래서 튜링 완전성 증명의 골자는 이렇습니다.

이렇게 규칙 110(또는 그에 준하는 만능 세포 자동자)의 동작을 게임판 위에 그대로 환원해 넣으면, "Baba is You ⊇ 만능 컴퓨터"가 됩니다. 즉, 충분히 큰 게임판만 주어지면 이 퍼즐 안에서 임의의 프로그램을 돌릴 수 있다는 뜻이죠.

4컴퓨터가 된 게임들

Baba is You만이 아닙니다. "진지하게 분석했더니 만능 컴퓨터였다"는 게임은 의외로 많습니다.

콘웨이의 라이프 게임 — 글라이더가 신호다

칸이 살고 죽는 단 두 줄짜리 규칙(이웃이 2~3이면 생존, 정확히 3이면 탄생)만으로 도는 이 세포 자동자는, 글라이더라는 움직이는 패턴을 신호선으로, 글라이더 건을 신호 발생기로 삼아 AND·OR·NOT 게이트를 전부 만들 수 있습니다. 실제로 라이프 안에 동작하는 튜링 기계가 통째로 지어졌죠. 아래에서 직접 돌려 보세요 — 특히 글라이더 건은 "신호를 끝없이 찍어 내는 공장"입니다.

라이프 게임 — 클릭으로 칸을 켜고, 패턴을 불러오세요

규칙은 단 두 줄인데, 그 안에서 임의의 회로가 자랍니다. 글라이더 건은 주기 30마다 글라이더 하나를 쏘아 보냅니다 — 이 글라이더 줄기들을 충돌시켜 논리 게이트를 만드는 게 라이프 컴퓨터의 출발점이죠.

마인크래프트 — 레드스톤이라는 전선

마인크래프트의 레드스톤은 신호를 켜고 끄고 전달하는 회로 부품입니다. 횃불 하나로 NOT을, 배치로 AND·OR를 만들 수 있어 — 즉 논리적으로 완전합니다. 그래서 플레이어들은 게임 안에 가산기, 메모리, 심지어 화면과 CPU를 갖춘 동작하는 컴퓨터를 지어 왔습니다. (엄밀히는 무한한 공간이 있어야 진짜 튜링 완전이지만, 원리는 그렇습니다.)

매직 더 개더링 — 카드 게임 속 튜링 기계

가장 충격적인 사례. 2019년 처칠·비더먼·헤릭은 논문 "Magic: The Gathering is Turing Complete"에서, 특정한 카드 배치로 두 플레이어의 진행이 강제로 튜링 기계 한 대를 시뮬레이션하도록 만들 수 있음을 증명했습니다. 종이 카드 게임의 규칙만으로 만능 컴퓨터가 굴러간다는 뜻이고, 그 결과 "이 매직 게임이 언젠가 끝나는가?"조차 일반적으로는 결정 불가능합니다.

5P와 NP — 빨리 풀기 vs 빨리 확인하기

이제 "풀 수 있는가"를 넘어 "빨리 풀 수 있는가"로 질문을 좁힙니다. 컴퓨터 과학은 입력 크기 \(n\)에 대해 시간이 \(n^2,\ n^3\)처럼 다항식으로 늘면 "실용적으로 빠르다(P)"고 봅니다. 반대로 \(2^n\)처럼 늘면 \(n\)이 조금만 커져도 우주의 나이로도 모자라죠.

아래 부분합 문제가 NP의 전형입니다 — "이 숫자들 중 일부를 골라 목표값을 정확히 만들 수 있나?" 정답(고를 부분집합)을 알려 주면 더해 보기만 하면 되니 확인은 순식간이지만, 직접 찾으려면 \(2^n\)가지 조합과 싸워야 합니다.

부분합 — "찾기는 어렵고, 확인은 쉽다"

목표값 9를 만드는 부분집합을 골라 보세요(숫자를 눌러 선택). 정답을 알면 확인은 덧셈 한 번이지만, 무차별 탐색은 \(2^6=64\)가지 — \(n\)이 커지면 이 \(2^n\)이 곧 벽이 됩니다.

그런데 P에 속하는 문제는 당연히 NP에도 속합니다(직접 풀 수 있으면 확인은 더 쉽죠). 그렇다면 거꾸로, "빨리 확인되는 문제는 전부 빨리 풀리기도 할까?" 이것이 그 유명한 P = NP? 질문입니다.

100만 달러짜리 질문
\(\mathsf{P}\stackrel{?}{=}\mathsf{NP}\)는 클레이 수학연구소가 2000년에 내건 7대 밀레니엄 난제의 하나로, 상금이 100만 달러입니다(7개 중 풀린 건 푸앵카레 추측 하나뿐). 대부분의 학자는 \(\mathsf P \neq \mathsf{NP}\)라 믿지만, 아무도 증명하지 못했습니다. 만약 \(\mathsf P=\mathsf{NP}\)라면 — 암호, 물류, 단백질 접힘, 수학 정리 증명까지 세상이 통째로 뒤집힙니다.

6NP-완전과 SAT — 모든 어려움의 표준형

NP 안에는 "가장 어려운" 문제들이 있습니다. NP-완전(NP-complete) 문제란, NP에 속하면서 동시에 NP의 다른 모든 문제를 다항 시간에 자기 자신으로 환원시킬 수 있는 문제입니다. 무슨 뜻이냐면 — NP-완전 문제 단 하나라도 다항 시간에 풀린다면, NP 전체가 풀리고 \(\mathsf P=\mathsf{NP}\)가 됩니다. 이들은 NP 난이도의 "대표선수"인 셈이죠.

1971년 쿡과 (독립적으로) 레빈은 SAT(부울 논리식이 참이 되게 하는 변수 배정이 있는가?)가 최초의 NP-완전 문제임을 증명했습니다(쿡–레빈 정리). 그 뒤로는 환원이 일을 합니다 — 새 문제 \(B\)가 NP-완전임을 보이려면, ① \(B\)가 NP에 속하고, ② 이미 NP-완전인 문제(SAT 등)를 \(B\)로 다항 환원할 수 있음을 보이면 끝입니다. 1972년 카프가 이 방식으로 단숨에 21개 문제를 NP-완전으로 묶었죠.

대표적인 NP-완전 문제가 그래프 3-색칠입니다 — "이웃한 두 꼭짓점이 같은 색이 안 되게 세 가지 색으로 칠할 수 있는가?" 칠해진 답을 받으면 확인은 변을 훑기만 하면 되지만(NP), 직접 찾기는 일반적으로 지독히 어렵습니다. 아래에서 직접 칠해 보세요.

그래프 3-색칠 — 모든 변의 양 끝을 다른 색으로

꼭짓점을 클릭하면 색이 바뀝니다(회색→파랑→주황→초록→…). 같은 색끼리 이은 변은 빨갛게 변하죠. 이 그래프는 두 색으로는 절대 안 되고 딱 세 색이면 됩니다 — 한번 찾아보세요.

7당신이 하던 그 게임, 전부 NP-완전

여기서 반전. 우리가 심심풀이로 하던 퍼즐들이 알고 보면 죄다 이 "가장 어려운 부류"에 속합니다.

지뢰찾기 — 지뢰밭으로 회로를 짓다

리처드 케이는 2000년, 지뢰찾기의 "이 숫자 단서들과 모순 없는 지뢰 배치가 존재하는가?" 문제가 NP-완전임을 증명했습니다. 방법이 기막힙니다 — 칸들의 숫자 제약으로 0/1 신호가 흐르는 전선을 만들고, 교차로 모양의 칸 배치로 AND·OR·NOT 게이트를 만든 거죠. 그러면 임의의 부울 회로(SAT)를 그대로 지뢰밭으로 번역할 수 있어, "회로가 만족 가능 ⇔ 모순 없는 지뢰밭 존재"가 됩니다. 지뢰찾기가 곧 SAT였던 셈입니다.

스도쿠 — 무한히 커지면 최악의 난제

우리가 푸는 9×9 스도쿠는 크기가 고정이라 이론적으로는 "상수 시간"이지만, 이를 일반화한 \(n^2 \times n^2\) 스도쿠는 NP-완전입니다(야토·세타, 2003). 라틴 방진 완성 문제(역시 NP-완전)를 스도쿠 판으로 환원해 보였죠. 그러니 "어떤 크기든 빠르게 푸는 스도쿠 알고리즘"을 만든다면, 그건 곧 \(\mathsf P = \mathsf{NP}\)의 증명입니다.

테트리스 그리고 친구들

2003년 디메인 등은 (조각 순서를 미리 다 알아도) 테트리스에서 "주어진 조각들로 빈 줄을 \(k\)개 이상 지울 수 있는가" 같은 문제가 NP-완전임을 보였습니다. 슈퍼마리오·캔디크러시·팩맨도 NP-난해(NP-hard)임이 증명됐고요. 게임의 즐거운 난이도가, 알고 보면 수학적으로 측정된 "진짜 어려움"이었던 겁니다.

사실 더 어려운 녀석들도 있다
모든 게임이 NP-완전인 건 아닙니다. 한 수가 다음 수에 길게 영향을 주는 소코반은 NP를 넘어선 PSPACE-완전이고, 일반화한 체스·바둑은 그보다 더한 EXPTIME-완전입니다. "어렵다"에도 엄연한 등급이 있고, 게임은 그 등급들을 보여 주는 훌륭한 표본실인 셈이죠.

그러니 다음에 지뢰찾기나 스도쿠 앞에서 막막해진다면, 너무 자책 마세요. 당신은 지금 세계 7대 난제와 한통속인 문제와 씨름하는 중이니까요. 게임을 진지하게 파고들면, 그 끝에는 늘 — 계산이란 무엇이고 무엇이 정말로 어려운가라는, 수학의 가장 깊은 질문이 기다리고 있습니다.

참고 자료