정지 문제, 컴퓨터가 끝내 풀 수 없는 질문

정지 문제는 어떤 프로그램과 입력이 주어졌을 때, 그 프로그램이 언젠가 멈출지 아니면 영원히 돌아갈지를 판정하는 문제다. 1936년 앨런 튜링은 모든 프로그램에 대해 이 질문에 답해 주는 일반적인 방법은 존재할 수 없음을 증명했다. 컴퓨터의 성능이 아무리 좋아져도 넘을 수 없는, 계산 자체의 한계다.

왜 그냥 돌려 보면 안 되나

프로그램이 멈추는지 알고 싶으면 실행해 보면 될 것 같다. 멈추면 멈춘다는 답을 얻는다. 문제는 멈추지 않을 때다. 한 시간을 돌려도 끝나지 않는 프로그램이 앞으로 영원히 안 끝날지, 아니면 하루 뒤에 끝날지는 기다리는 것만으로 알 수 없다. 기다림에는 끝이 없고, 언제 포기해야 할지 알려 주는 기준도 없다.

그래서 필요한 것은 실행하지 않고 코드를 읽어서 판정하는 검사기다. 간단한 프로그램이라면 사람도 읽고 판단할 수 있다. 숫자를 하나씩 늘리다 10에서 멈추는 반복문은 분명히 끝난다. 조건이 늘 참인 반복문은 영원히 돈다. 튜링이 던진 질문은 이런 판단을 모든 프로그램에 대해 빠짐없이 해내는 단 하나의 방법이 있느냐는 것이었다.

튜링은 어떻게 불가능을 증명했나

증명은 귀류법을 쓴다. 만능 검사기가 있다고 가정하고, 거기서 모순을 끌어내는 방식이다. 만능 검사기 H가 있다고 하자. H는 프로그램과 입력을 받아, 멈추면 '멈춘다', 영원히 돌면 '안 멈춘다'고 반드시 답한다.

이제 H를 이용해 심술궂은 프로그램 D를 만든다. D는 프로그램 하나를 입력으로 받아, 그 프로그램에 자기 자신을 입력했을 때 어떻게 되는지를 H에게 묻는다. H가 '멈춘다'고 답하면 D는 일부러 영원히 돈다. H가 '안 멈춘다'고 답하면 D는 곧바로 멈춘다. H의 답과 반대로만 움직이는 프로그램이다.

마지막으로 D에게 D 자신을 입력한다. H가 'D는 멈춘다'고 답하면 D는 영원히 돌고, 'D는 안 멈춘다'고 답하면 D는 멈춘다. 어느 쪽이든 H의 답은 틀린다. 반드시 맞는 답을 내는 H가 있다는 가정 자체가 모순을 낳았으니, 그런 H는 존재할 수 없다.

이 논증은 '이 문장은 거짓이다' 같은 자기 지시의 역설과 닮았다. 자기 자신에 대한 질문을 스스로 품을 수 있을 만큼 강력한 체계는 바로 그 강력함 때문에 모든 질문에 답할 수 없게 된다.

이 증명은 컴퓨터보다 먼저 나왔나

튜링이 이 논문을 쓴 1936년에는 오늘날 같은 전자식 컴퓨터가 없었다. 그는 계산을 아주 단순한 기계로 정의했다. 칸이 이어진 긴 테이프 위에 기호를 읽고 쓰며, 정해진 규칙에 따라 한 칸씩 움직이는 상상 속의 기계다. 이것이 튜링 기계다.

놀라운 점은 이 단순한 기계가 오늘날의 어떤 컴퓨터가 할 수 있는 계산도 원리상 모두 해낼 수 있다는 것이다. 속도는 비교할 수 없이 느리지만, 계산할 수 있는 것의 범위는 같다. 그래서 튜링 기계에 대해 증명한 한계는 모든 컴퓨터에 그대로 적용된다. 계산이 무엇인지를 정의하는 일과 계산의 한계를 보이는 일이 같은 논문에서 함께 이루어졌다.

질문	일반적으로 답할 수 있나
이 프로그램은 특정 입력에서 멈추는가	할 수 없다
이 프로그램은 어떤 입력에서든 멈추는가	할 수 없다
두 프로그램은 늘 같은 결과를 내는가	할 수 없다
이 짧은 반복문은 끝나는가	개별적으로는 가능

그렇다면 실제 소프트웨어 검사는 어떻게 하나

정지 문제가 풀 수 없다고 해서 프로그램을 검사하는 일이 무의미한 것은 아니다. 증명이 말하는 것은 '모든' 프로그램에 대해 '언제나' 맞는 답을 내는 방법이 없다는 것뿐이다. 실제 검사 도구는 이 한계를 피해 간다. 확실히 멈추는 경우와 확실히 위험한 경우는 찾아내고, 판단할 수 없는 경우에는 '모르겠다'고 답하는 식이다. 반복 횟수에 상한을 두는 언어를 쓰거나, 프로그램을 판정하기 쉬운 형태로 제한하는 방법도 있다.

남은 질문

정지 문제는 풀 수 없는 문제의 첫 번째 예일 뿐이다. 이후 프로그램의 거의 모든 '의미'에 관한 질문, 예컨대 이 프로그램이 특정 값을 출력하는지 같은 질문도 일반적으로는 판정할 수 없다는 사실이 밝혀졌다. 풀 수는 있지만 시간이 지나치게 오래 걸리는 문제들, 곧 계산 복잡도의 세계는 또 다른 영역이다. 그 가운데 대표적인 질문인 'P와 NP는 같은가'는 아직 답이 나오지 않은 수학의 가장 큰 미해결 문제 가운데 하나로 남아 있다.