1936
계산을 수학적으로 정의하다
튜링의 논문이 런던수학회에 접수되었고, 처치의 독립적인 연구와 함께 계산 가능성의 개념이 정밀하게 정리되었습니다.
01 · THE QUESTION AND THE PERSON
끝나는 계산과
끝나지 않는 계산
동아리에서 만든 간단한 프로그램부터 튜링의 실제 연구 배경과 기계 모델까지 읽습니다. 먼저 프로그램, 입력, 종료의 뜻을 정확히 구별합니다.
01 · 읽어 보기
1. 컴퓨터가 오래 계산하는 것과 영원히 계산하는 것은 어떻게 다를까요?
동아리 학생이 학교 축제의 참가 신청을 정리하는 프로그램을 만든다고 생각합시다. 첫 번째 프로그램은 참가자가 제출한 신청서 500장의 이름을 한 번씩 읽고 중복을 제거합니다. 파일을 정상적으로 읽을 수 있고 처리 규칙이 정해져 있다면 이 프로그램은 500장을 처리하고 종료합니다. 데이터가 많아 오래 걸릴 수는 있어도 끝나는 지점이 분명합니다.
두 번째 프로그램은 자연수 n을 입력받아 n이 0이 될 때까지 1씩 줄이는 단순한 계산을 합니다. 입력이 5라면 n의 값은 5, 4, 3, 2, 1, 0 순서로 변하고, 여섯 번째 상태를 확인한 뒤 종료합니다. 입력이 100만이면 더 오래 걸리지만 여전히 끝납니다. 이 사례에서는 매 반복마다 n이 감소하며 0 아래로 내려가지 않는다는 사실을 이용해 종료를 증명할 수 있습니다.
세 번째 프로그램은 0보다 큰 정수 x를 입력받아 x = x + 1이라는 명령을 끝없이 반복합니다. 정수를 무한히 크게 표현할 수 있다는 수학적 계산 모델에서 이 프로그램에는 종료 명령이 없습니다. 실제 컴퓨터에서는 메모리 부족이나 시스템 종료 같은 외부 요인으로 실행이 중단될 수 있습니다. 하지만 우리가 묻는 것은 운영체제가 프로그램을 강제로 닫을 수 있는지가 아니라, 그 프로그램이 규정된 계산 절차에 따라 스스로 종료 상태에 도달하는가입니다.
네 번째 프로그램은 주어진 자연수 n에 대해 k = 0부터 시작하여 k² = n을 만족하는 자연수 k를 찾을 때까지 k를 하나씩 증가시킵니다. n이 16이면 k = 4에서 끝나고, n이 2이면 끝나지 않습니다. 이 프로그램을 수학적으로 살펴보면 입력값에 따른 결과를 알아낼 수 있습니다. 특히 n = 2의 경우 자연수의 제곱이 2가 될 수 없음을 증명하면 무한 반복이라는 결론을 얻습니다. 반대로 n = 16의 경우 k = 4라는 실제 증거가 있습니다.
여기까지의 사례에서는 우리가 프로그램을 충분히 이해했기 때문에 답을 냈습니다. 정지 문제는 이해하기 쉬운 네 프로그램의 종료 여부를 판별할 수 있는가에서 출발하지만, 곧 질문의 범위를 규칙에 맞게 작성할 수 있는 모든 프로그램으로 넓힙니다. 프로그램 길이나 실행 시간에 상한을 두지 않고, 입력값도 임의로 허용한다는 조건이 뒤에 나올 증명에서 중요합니다.
02 · 읽어 보기
2. 천만 번 실행했는데 멈추지 않았다면 앞으로도 멈추지 않을까요?
프로그램을 1초 동안 돌렸는데 결과가 없었다고 합시다. 1시간, 하루, 한 달을 기다려도 결과가 나오지 않을 수 있습니다. 여기서 확인된 사실은 그 기간에 실행이 끝나지 않았다는 것뿐입니다. 처음 백만 번째 단계까지 반복하다가 백만한 번째 단계에 종료하는 프로그램도 어렵지 않게 만들 수 있습니다. 따라서 유한한 시간 동안 멈추지 않았다는 관찰만으로 영원히 멈추지 않는다고 결론 내릴 수는 없습니다.
모든 프로그램에 실행 횟수 제한을 정하는 검사를 생각해 봅시다. 예를 들어 1억 번의 계산 단계 안에 종료하면 종료, 그렇지 않으면 시간 초과라고 답합니다. 이 검사는 입력된 프로그램을 정해진 단계만큼 실행해 보면 되므로 절차 자체는 언제나 끝납니다. 다만 시간 초과라는 결과는 영원히 종료하지 않음과 다릅니다. 1억 1번째 단계에 끝나는 프로그램도 같은 판정을 받기 때문입니다.
한 가지 가능성은 검사 시간을 계속 늘리는 방법입니다. 먼저 천 번, 다음에는 만 번, 다시 십만 번을 실행해 봅니다. 언젠가 종료하는 프로그램은 충분히 오래 기다리면 종료하는 순간을 확인할 수 있습니다. 하지만 끝나지 않는 프로그램에서는 어디까지 더 검사할 것인가라는 질문이 계속 남습니다. 이 차이는 정지 문제를 설명할 때 중요한 단서가 됩니다. 종료했다는 사실에는 실제로 종료한 계산 이력이 증거가 되지만, 모든 프로그램이 종료하지 않는다는 판단을 동일한 방식의 단순 실행으로 확인할 수는 없습니다.
여기서 컴퓨터의 성능이나 계산 속도는 부차적입니다. 초당 백만 단계를 실행하든 백조 단계를 실행하든, 미리 정한 유한한 검사 시간 밖에서 끝나는 프로그램을 만들 수 있습니다. 우리가 알아보려는 것은 성능 개선의 여지가 있는가가 아니라, 시간제한 없이 모든 입력의 종료 여부를 정확히 결정하는 알고리즘이 이론적으로 가능한가입니다.
03 · 읽어 보기
3. 앨런 튜링은 어떤 연구에서 이 문제를 다루게 되었을까요?
앨런 매시슨 튜링(Alan Mathison Turing, 1912–1954)은 영국 런던에서 태어난 수학자이자 논리학자입니다. 케임브리지대학교 킹스칼리지에서 수학을 공부했고, 이후 미국 프린스턴대학교에서 연구했습니다. 제2차 세계대전에는 영국의 암호 분석에 참여했으며, 전후에는 계산 기계와 프로그램에 관한 연구를 이어 갔습니다. 정지 문제를 이해할 때 중요한 업적은 전쟁기의 암호 해독보다 앞선 1936년의 계산 가능성 연구입니다.
그가 연구하던 시기에는 다비트 힐베르트와 빌헬름 아커만이 제기한 판정 문제(Entscheidungsproblem, 어떤 논리식이 모든 해석에서 성립하는지를 일반적인 절차로 판정하는 문제)가 중요한 과제였습니다. 제09회에서 살핀 괴델의 1차 논리 완전성 정리에 따르면, 모든 모형에서 성립하는 1차 논리식에는 형식적 증명이 존재합니다. 그러나 증명이 존재한다는 사실과, 임의의 논리식을 받았을 때 언제나 유한한 시간 안에 증명 가능 여부를 판정하는 절차가 있다는 사실은 서로 다릅니다.
튜링은 계산한다는 행위를 작은 단계의 규칙으로 분해했습니다. 기계가 읽는 기호, 기계가 기억하는 상태, 다음 행동을 정하는 규칙을 명시하면 계산 절차를 수학의 대상으로 다룰 수 있습니다. 그는 기계가 끝없이 기호를 출력할 수 있는가와 관련한 판정 불가능성을 연구하여, 이를 판정 문제의 부정적인 해답으로 연결했습니다.
출판 연혁은 분명히 구분해야 합니다. 튜링의 논문 「계산 가능한 수와 판정 문제에 대한 응용」(On Computable Numbers, with an Application to the Entscheidungsproblem)은 1936년 5월 28일 접수되었고, Proceedings of the London Mathematical Society 제42권 230–265쪽의 1937년 발행 기록이 있습니다. 학술 문헌에서 튜링 1936–1937년 논문이라고 쓰는 이유입니다. 독립적으로 유사한 결론에 이른 알론조 처치(Alonzo Church)의 1936년 연구 역시 이 역사에서 중요합니다. 어느 한 사람의 성과로 계산 가능성 이론 전체를 환원해서는 안 됩니다.
또 한 가지 주의할 부분이 있습니다. 오늘날 교과서에 널리 실리는 주어진 프로그램과 입력이 정지할지 판정하는 문제의 두 갈래 증명은 튜링의 1936년 원논문에 수록된 설명을 한 문장도 바꾸지 않고 옮긴 것이 아닙니다. 튜링의 원논문은 무한히 숫자를 출력하는 기계의 성질, 원형 기계(circular machine), 만족스러운 기술 번호(satisfactory description number) 등을 통해 논증을 진행합니다. 이번 글은 원논문의 역사적 질문과 현대적인 정지 문제 증명을 구별해서 설명합니다.
04 · 읽어 보기
4. 튜링 기계는 어떤 장치이고, 왜 프로그램을 대신할 수 있을까요?
튜링 기계(Turing machine)는 여러 종류의 계산 장치를 비교할 수 있도록 규칙을 단순하게 만든 수학적 기계입니다. 길게 이어진 칸에 기호를 적는 테이프가 있고, 어느 한 칸을 읽는 머리와 현재 상태를 기억하는 장치가 있습니다. 한 번의 계산 단계에서 기계는 지금 읽는 기호와 자신의 상태를 확인한 뒤, 새 기호를 쓰고, 머리를 왼쪽이나 오른쪽으로 움직이고, 다음 상태로 바꿀 수 있습니다. 실제 컴퓨터의 회로를 재현하는 장치는 아닙니다. 규칙으로 수행되는 계산을 분석하기 위한 모형입니다.
이 기계에는 유한한 개수의 상태와 유한한 종류의 테이프 기호를 부여합니다. 프로그램으로 볼 수 있는 전이 규칙표도 유한합니다. 반면 필요에 따라 사용할 수 있는 테이프 칸의 개수에는 미리 정한 상한을 두지 않습니다. 어떤 한 시점에 실제로 사용한 칸은 유한하더라도 계산을 계속하면서 새로운 칸을 사용할 수 있습니다. 이러한 구분 덕분에 입력은 유한하고 명령도 유한하지만 계산은 끝없이 이어질 수 있다는 상황을 다룰 수 있습니다.
아주 단순한 규칙표를 생각해 봅시다. 상태가 읽는 중일 때 기호 1을 만나면 0으로 바꾸고 오른쪽으로 이동한 뒤 계속 읽습니다. 빈칸을 만나면 종료 상태로 바꿉니다. 오른쪽에 유한한 개수의 1이 있다면 이 기계는 마지막 1을 지나 빈칸을 읽고 끝납니다. 이 사례에서 실제 프로그램과 튜링 기계의 공통점은 현재 상태와 읽은 자료를 토대로 다음 동작이 결정된다는 점입니다.
튜링이 제시한 중요한 발상 가운데 하나는 범용 기계(universal machine)입니다. 서로 다른 계산 기계마다 물리적 장치를 하나씩 새로 만들지 않아도, 기계의 규칙표 자체를 부호로 나타내면 하나의 범용 기계가 다른 기계의 계산을 따라 할 수 있습니다. 현대적인 기호로 쓰면 U(⌜P⌝, x)입니다. 여기서 ⌜P⌝는 프로그램 P의 규칙을 나타내는 유한한 부호, x는 그 프로그램에 넣을 입력입니다. 범용 기계 U는 P를 묘사한 부호를 읽어 P가 입력 x에서 하는 계산을 단계별로 모사합니다.
이렇게 프로그램을 자료로 바꿀 수 있어야 뒤의 논증이 가능합니다. 프로그램을 읽는 검사는 프로그램의 규칙을 입력받아야 합니다. 그 프로그램 자체의 부호도 다시 입력 자료로 사용할 수 있습니다. 이는 컴퓨터가 코드를 파일로 저장하거나 다른 프로그램이 그 파일을 읽는 일과 같은 형식적 성질입니다. 다만 이 설명에서 프로그램은 무작위의 자연어 지시가 아니라, 문법과 실행 의미가 정확히 정해진 계산 절차를 뜻합니다.
1937
판정 문제의 한계를 발표하다
『계산 가능한 수와 판정 문제에 대한 응용』이 학회지 제42권 230–265쪽에 실렸습니다.
