오늘은 컴퓨터가 탄생하는 데 수학이 어떤 역할을 했는지 알아볼 거예요. 영국의 수학자이자 현대 컴퓨터의 창시자인 앨런 튜링은 일종의 판정 문제인 ‘정지 문제’를 ‘튜링 기계’를 이용해 풀 수 없다는 사실을 증명했는데요. 어떤 증명 과정을 거쳤는지 살펴봅시다.
♥ 정지 문제가 가능하다면
정지 문제란 현재 실행 중인 프로그램이 계산을 끝내고 언젠가 종료하는지 아니면 영원히 계산을 반복하는지 판별하는 기계가 존재할 수 있는지를 묻는 문제입니다. 튜링은 정지 문제를 풀 수 없다는 사실을 증명하기 위해 튜링 기계라는 개념을 사용했는데요. 튜링 기계는 튜링이 만들어낸 가상의 연산 기계로, 수학 원리로 구성돼 있습니다.
실제 증명 과정은 더 복잡하지만, 여기서는 그 과정을 단순화시켜 알아볼게요. 다음과 같이 행동하는 프로그램 P와 데이터 x를 튜링 기계에 입력한다고 가정할게요.
P는 입력값에 따라서 정상적으로 종료할 수도 있고, 무한반복의 덫에 걸려 영원히 종료하지 않을 수도 있습니다. 예를 들어 볼게요.
만약 정지 문제가 가능하다면, 우리는 임의의 프로그램 Q와 데이터 y가 주어졌을 때, Q(y)가 정상 종료한다면 ‘참’을 출력하고, 그렇지 않다면 ‘거짓’을 출력하는 프로그램 Halt(Q, y)를 튜링 기계에서 만들 수 있습니다.
여기까지는 그럭저럭 따라갈 만합니다. 그런데 이 다음 내용이 조금 헷갈리니 주의해 주세요.
♠ 모순의 씨앗
‘컴퓨터의 모든 데이터는 0과 1의 나열로 표현한다’고 하지요. 실제로 자연수 3은 11로, 자연수 27은 11011으로 나타내요. 프로그램도 마찬가지입니다. 예를 들어 두 변수의 값을 더해 저장하는 프로그램은 컴퓨터 내부에서 다음과 같이 나타납니다.
앞서 예시로 든 프로그램 P 또한 컴퓨터 내부에서는 0과 1의 나열로 나타날 거예요. 실제 나열은 훨씬 길겠지만 설명의 편의를 위해 P는 110001로 표현한다고 합시다. 자연수 3은 11이므로, Halt(P, 3)은 다음과 같이 처리됩니다.
이렇게 쓰고 보니 쉼표 앞뒤로 들어오는 값 사이에는 본질적인 차이가 없습니다. 둘 다 0과 1의 나열에 지나지 않습니다. 따라서 Halt 프로그램의 두 입력값이 동일한 경우도 고려할 수 있겠어요.
그러나 이곳에 모순의 씨앗이 숨어 있습니다. 아래의 프로그램 G를 살펴봅시다. G는 임의의 프로그램 z를 입력값으로 받습니다.
◆ 가정이 틀렸다?
여기서 질문을 하나 드려 볼게요. G에 G를 입력값으로 주면 어떤 일이 일어날까요? 즉, G(G)는 정상 종료할까요, 무한반복에 빠지고 말까요? 충분히 생각한 다음에 답을 확인해 보세요.
먼저 G(G)가 정상적으로 종료했다고 가정해 봅시다. 이것은 Halt(G, G)가 거짓임을 시사합니다. 그러나 Halt(G, G)가 거짓이려면 G(G)는 정상 종료해서는 안 됩니다. 이것은 모순입니다. 따라서 G(G)는 무한반복에 빠져야 합니다. 이는 Halt(G, G)가 참임을 시사합니다. Halt(G, G)가 참이려면 G(G)는 정상 종료해야 합니다. 이것도 모순이에요.
두 가지 가능성 모두 모순된 결과를 내놓는다면 가능한 결론은 하나뿐입니다. 맨 처음 가정, 즉 정지 문제가 가능하다는 가정이 틀렸던 것입니다!
튜링은 튜링 기계를 이용해 논문 ‘계산 가능한 수와 결정문제의 응용에 관하여’에서 이 내용을 증명했어요. 튜링 기계는 후대 학자들에 의해 컴퓨터라는 개념으로 발전하지요.
