튜링의 펜은 망설임 없이 움직였다. 그의 노트 위에, 논리적 함정의 설계도가 그려지고 있었다.
첫 번째 부품은 그가 방금 가정한 만능 ‘정지 문제 판별기(H)’였다.
H는 일종의 블랙박스다. 이 상자에는 두 개의 투입구가 있다. 첫 번째 투입구에는 프로그램의 설계도(P)를, 두 번째 투입구에는 그 프로그램에 전달할 입력값(I)을 넣는다. 그러면 잠시 후, 상자에서는 둘 중 하나의 팻말이 나온다.
- ‘HALTS’ (이 프로그램은 정지합니다)
- ‘LOOPS’ (이 프로그램은 영원히 돕니다)
H는 예언가와 같았다. 어떤 프로그램이든, 어떤 입력값이든 그 운명을 미리 알려주는 완벽한 기계.
튜링은 이 완벽한 예언가를 그대로 사용하지 않았다. 그는 H를 심장부에 장착한, 훨씬 더 뒤틀리고 심술궂은 새로운 기계를 구상했다. 그는 이 기계를 ‘모순 기계(C, Contradiction Machine)’라고 이름 붙였다.
모순 기계 C의 작동 원리는 악의적일 정도로 단순했다.
-
입력:
모순 기계 C는 입력값을 단 하나만 받는다. 바로 다른 프로그램의 설계도(P)다. -
내부 작동:
- 복제: C는 입력받은 설계도 P를 내부에서 복제한다. 이제 똑같은 P가 두 개가 된다.
- 질문: C는 이 두 개의 복제본 P를, 자신의 심장부에 있는 H의 두 투입구에 각각 집어넣는다. 즉, H에게 이런 질문을 던지는 것이다. “프로그램 P에게, 자기 자신의 설계도 P를 입력값으로 주면, 정지할까?”
[H(P, P) ?] - 반항: H는 잠시 후 ‘HALTS’ 또는 ‘LOOPS’라는 예언을 내놓는다. 바로 이 순간, C의 청개구리 같은 본성이 발동한다.
- 만약 H의 예언이 ‘HALTS’라면, C는 그 예언을 배신하고 즉시 무한 루프에 빠진다. (예: “10: GOTO 10” 같은 무의미한 명령을 영원히 반복한다.)
- 만약 H의 예언이 ‘LOOPS’라면, C는 그 말을 비웃기라도 하듯 그 자리에서 즉시 작동을 멈춘다(HALT).
튜링은 펜을 놓고 자신이 설계한 C의 도표를 내려다보았다.
이 기계 C는 H의 예언을 정면으로 거스르도록 프로그래밍된, 완벽한 반항아였다. H가 멈춘다고 하면 영원히 달리고, H가 영원히 달린다고 하면 그 즉시 멈춰버리는 기계.
그의 눈빛은 차갑게 빛났다.
논리적 시한폭탄이 만들어졌다. 모든 부품은 완벽하게 제자리에 놓였다.
H라는 완벽한 예언가가 존재한다고 가정했더니, 그 예언을 무조건 거꾸로 행동하는 C라는 반항아가 태어났다.
이제 마지막 단계만이 남았다.
이 모순 덩어리 기계, 이 자기 자신을 부정하기 위해 태어난 뱀에게, 먹이를 줄 시간이었다.
그 먹이는 바로, 자기 자신의 꼬리였다.
튜링은 노트의 다음 페이지에 단 한 줄의 질문을 적었다.
“이 모순 기계 C에게, 입력값으로 자기 자신의 설계도 C를 주면, 무슨 일이 벌어지는가?”
그 질문이 쓰이는 순간, 힐베르트의 결정 문제는 돌이킬 수 없는 운명에 처했다. 논리의 붕괴는 이제 시간문제였다.
