Gödel 1931 · Turing 1936 · Church 1936 · Cook 1971

계산의 한계 컴퓨터가 절대 풀 수 없는 문제들

충격적인 사실: 컴퓨터로 풀 수 있는 문제와 풀 수 없는 문제가 있다 — 계산 속도나 메모리의 문제가 아니라, 어떤 컴퓨터를 써도, 얼마나 오래 기다려도, 원리적으로 답을 낼 수 없는 문제가 존재한다.

배경 — 힐베르트의 꿈

1900년 독일의 수학자 다비트 힐베르트는 야심찬 프로그램을 제시했다: 수학을 완전하고 무모순적인 공리 체계 위에 세우자. 모든 참인 수학 명제는 증명될 수 있고, 모든 수학 문제는 원리적으로 풀 수 있어야 한다고 믿었다.

30년 후, 두 명의 젊은 수학자가 이 꿈을 산산조각 냈다.

괴델의 불완전성 정리 (1931)

쿠르트 괴델은 25살에 수학의 역사를 바꿨다. 그의 증명은 충격적이었다: 충분히 강력한 모든 공리 체계는 다음 두 성질을 동시에 가질 수 없다.

제1불완전성 정리

충분히 강력한 일관된 공리 체계에는 그 체계 안에서 증명도 반증도 할 수 없는 참인 명제가 반드시 존재한다.

즉 "수학은 완전할 수 없다". 항상 참이지만 증명할 수 없는 명제가 있다.

제2불완전성 정리

그 체계가 일관적이라면, 자기 자신의 일관성을 그 체계 안에서 증명할 수 없다.

즉 수학은 자기 자신이 모순이 없다는 것을 스스로 증명하지 못한다.

괴델의 핵심 트릭 — 자기 참조:
괴델은 수학 명제에 번호를 매기는 방법(괴델 수)을 발명해서, 수학이 자기 자신에 대해 이야기할 수 있게 만들었다. 그리고 다음과 같은 명제 $G$를 구성했다:

"이 명제 $G$는 증명 불가능하다."

$G$가 참이면 → 증명 불가능한 참인 명제가 존재 (불완전).
$G$가 거짓이면 → 거짓인 명제가 증명됨 (모순적).
일관된 체계라면 첫 번째 경우 → 항상 증명 안 되는 참인 명제가 있다.

튜링과 정지 문제 (1936)

앨런 튜링은 컴퓨터라는 개념 자체를 수학적으로 정의(튜링 기계)하고 나서, 계산 가능성의 한계를 탐구했다. 그는 괴델의 방법을 활용해 정지 문제(Halting Problem)를 정식화했다.

정지 문제: 임의의 프로그램 $P$와 입력 $I$가 주어졌을 때, $P(I)$가 유한한 시간 안에 종료하는지(halt) 아니면 무한 루프에 빠지는지를 결정하는 알고리즘이 존재하는가?

튜링의 답: 존재하지 않는다.

정지 문제가 풀리지 않는 이유 — 귀류법

어느 쪽 가정을 해도 모순이 발생한다. 따라서 HALT 오라클 자체가 존재할 수 없다. 정지 문제는 결정 불가능(undecidable)하다.

직접 느껴보기 — 이 프로그램은 멈출까?

아래 예시들 중 어느 것이 멈추는지 컴퓨터는 일반적으로 판단할 수 없다. 물론 개별 케이스는 분석 가능하지만, 임의의 프로그램에 대한 일반적 알고리즘이 없다는 것이 핵심이다.

P vs NP — 100만 달러 짜리 미해결 문제

정지 문제는 "아예 풀 수 없는" 문제다. 그런데 "빠르게 풀 수 없는" 문제도 있다. P vs NP 문제는 이것을 다룬다.

P와 NP의 차이:

P (Polynomial): 다항 시간 내에 풀 수 있는 문제. 입력 크기 n이 커져도 $n^k$ 시간 이내 (느리지 않음).
NP (Non-deterministic Polynomial): 답이 주어지면 다항 시간에 검증할 수 있는 문제. 하지만 찾는 것은 지수 시간($2^n$)이 걸릴 수 있음.
예시: 스도쿠 — 완성된 답이 맞는지 확인: 쉬움(P). 빈 칸 채우기: 어려움(NP). 크기가 커지면 지수적으로 어려워짐.
질문: 검증이 쉬운 문제는 항상 풀기도 쉬운가? 즉 NP = P인가?

대부분의 전문가는 P ≠ NP라고 믿지만, 60년째 증명하지 못하고 있다. 클레이 밀레니엄 문제 중 하나로 상금 100만 달러.

왜 P ≠ NP가 중요한가

P = NP이면 (아마 거짓)

RSA 암호 즉시 붕괴 (소인수분해가 P에 속하게 됨)
신약 개발이 폭발적 가속 (단백질 접힘 등이 P에)
모든 창의적 문제가 기계적으로 풀림
수학의 증명 자동화 완성

P ≠ NP이면 (현재 믿음)

암호학이 안전한 이론적 기반 확보
많은 최적화 문제는 근사해로 만족해야 함
인간의 창의성과 기계의 계산은 근본적으로 다름
AI가 모든 것을 해결할 수는 없음

계산 가능성의 계층

1931

괴델 불완전성 정리 수학에는 참이지만 증명 불가능한 명제가 있다. 힐베르트의 꿈 붕괴.

1936

튜링/처치의 정지 문제 & λ-계산 컴퓨터가 원리적으로 풀 수 없는 문제 발견. 튜링 기계로 계산 가능성을 수학적으로 정의.

1971

쿡의 NP-완전성 SAT(논리 충족 가능성)가 NP-완전임을 증명. 이후 수천 개의 문제가 NP-완전으로 분류됨.

1994

쇼어 알고리즘 양자 컴퓨터는 소인수분해를 다항 시간에 풀 수 있다. 현재 암호학 위협. 단, 실용적 양자컴퓨터는 아직 없음.

현재

P vs NP 미해결 컴퓨터 과학 역사상 가장 중요한 미해결 문제. 클레이 밀레니엄 문제, 상금 100만 달러.

실용적 함의: 정지 문제의 결정 불가능성은 소프트웨어 자동 검증의 한계를 의미한다. "이 프로그램이 무한 루프에 빠지는 경우가 있는가?"를 항상 자동으로 검사하는 도구는 존재할 수 없다. 정적 분석 도구들이 보수적인 근사 분석에 그치는 이론적 이유다.