논리의 붕괴

튜링의 펜 끝이 노트 위에 떠 있었다. 모든 준비는 끝났다. 이제 그가 설계한 논리적 시한폭탄의 스위치를 누를 시간이었다.

질문은 단 하나였다.
“모순 기계 C는, 자기 자신의 설계도 C를 입력받았을 때, 정지하는가?”

논리적으로 가능한 답은 두 가지뿐이다. 정지하거나, 정지하지 않거나. 튜링은 첫 번째 가능성부터 차례대로 검증해 나갔다.

[가정 1] C(C)는 언젠가 정지(HALT)한다.

1. 이 가정이 사실이라면, C의 심장부에 있는 완벽한 예언가, 정지 문제 판별기 H는 C(C)의 운명을 정확히 예측해야 한다. 따라서 H는 ‘HALTS’라는 팻말을 내놓을 것이다.

2. 모순 기계 C는 H로부터 ‘HALTS’라는 답을 전달받는다.

3. C의 설계도를 기억해보자. C는 H의 예언을 정면으로 거스르도록 만들어졌다. H가 ‘HALTS’라고 말하면, C는 그 즉시 무한 루프(LOOP)에 빠져 영원히 달려야 한다.

결과를 보라.
우리는 “C(C)는 정지한다”고 가정했는데, 그 가정에 따른 논리적 귀결은 “C(C)는 영원히 돈다”는 것이다.

명백한 모순이다.
따라서, [가정 1]은 거짓이다. C(C)는 절대로 정지할 수 없다.

튜링의 입가에 희미한 미소가 걸렸다. 함정의 첫 번째 부분이 완벽하게 작동했다. 이제 남은 가능성은 단 하나뿐이었다.

[가정 2] C(C)는 정지하지 않고 영원히 돈다(LOOP).

1. 이 가정이 사실이라면, 예언가 H는 이번에도 정확하게 예측하여 ‘LOOPS’라는 팻말을 내놓을 것이다.

2. 모순 기계 C는 H로부터 ‘LOOPS’라는 답을 전달받는다.

3. 다시 C의 설계도를 떠올려보자. 청개구리 같은 C는, H가 ‘LOOPS’라고 말하면, 그 말을 비웃으며 그 즉시 모든 작동을 멈추어야(HALT) 한다.

또다시 결과를 보라.
우리는 “C(C)는 영원히 돈다”고 가정했는데, 그 논리적 귀결은 “C(C)는 즉시 정지한다”는 것이다.

이것 또한 완벽한 모순이다.
따라서, [가정 2] 역시 거짓이다.

튜링은 펜을 내려놓았다.
그의 눈앞에서, 논리라는 이름의 건축물이 완전히 붕괴했다.

C(C)는 정지할 수도 없고, 그렇다고 영원히 돌 수도 없다.
이것은 수학의 세계에서는 있을 수 없는 일이다. 어떤 기계든 그 운명은 둘 중 하나여야만 한다.

그렇다면 무엇이 잘못된 것인가?
튜링의 논증 과정에는 단 하나의 흠결도 없었다. 모든 단계는 필연적이었다.

이 모든 논리적 붕괴의 근원은 단 하나.
우리가 맨 처음에 세웠던, 단 하나의 증명되지 않은 가정에서 비롯된다.

“모든 프로그램의 정지 여부를 미리 판별해 줄 수 있는 만능 프로그램, 즉 ‘정지 문제 판별기(H)’가 존재한다.”

바로 이 가정이, 이 모든 모순의 씨앗이었다. 이 가정이 있었기에 모순 기계 C를 만들 수 있었고, 그 C가 시스템 전체를 무너뜨렸다. 따라서 최초의 가정 자체가 틀렸음이 증명된 것이다.

튜링은 노트의 마지막에 결론을 적었다. 그의 필체는 그 어느 때보다 단호했다.

“정지 문제 판별기 H는 존재할 수 없다. 절대로.”

귀류법(Reductio ad absurdum).
상대방의 주장을 참이라 가정하고, 그 가정으로부터 모순을 이끌어내어 원래의 주장이 거짓임을 증명하는 가장 강력한 논리의 칼.

튜링은 그 칼로 ‘정지 문제’라는 심장을 정확히 꿰뚫었다.
이제 남은 것은 쓰러진 거인의 시체를 밟고, 최종 목표인 ‘결정 문제’의 성문 앞에 서는 것뿐이었다.