풀 수 없는 문제도 계산의 경계를 알려준다

기다리면 끝날까

프로그램이 실행 중인데 결과가 나오지 않는다. 계산량이 많을 수도 있고, 계속 같은 일을 하도록 작성됐을 수도 있다. 한 시간 더 기다린 뒤에도 멈추지 않았다면 둘을 구분할 증거가 조금 늘었을까. 여전히 더 늦게 끝나는 프로그램이 있을 수 있다. 오래 관찰했다는 사실만으로 영원히 끝나지 않을 것이라고 결론 내릴 수는 없다.

그렇다면 프로그램을 실행해서 기다리는 대신, 그 프로그램의 내용과 입력을 읽고 종료 여부를 미리 판정하는 프로그램을 만들면 될까. 특정한 경우에는 가능하다. 정해진 횟수만 반복하고 끝나는 절차는 분석하기 쉽다. 어려운 질문은 어떤 프로그램과 입력을 주어도 반드시 끝나며 올바르게 판정하는 하나의 방법이 있는가다.

이 질문을 계산 모델 안에서 다루면 그런 보편적 판정 방법은 존재하지 않는다. 이것은 컴퓨터가 아직 느려서 연구자가 답을 못 찾았다는 말과 다르다. 더 많은 시간을 주는 것으로 해소되지 않는 계산의 한계를 말한다. 다만 그 결론의 범위는 분명하다. 특정 프로그램의 종료는 규칙을 분석해 증명할 수 있다. 한계가 생기는 것은 가능한 모든 프로그램과 입력을 빠짐없이 맡아, 항상 종료하면서 맞는 답을 내는 하나의 계산법을 요구할 때다. 현대 판정·정지 문제의 정의 (새 창)

계산하는 일을 작은 동작으로 적기

튜링은 「계산 가능한 수에 관하여」에서 기호가 적힌 테이프와 그것을 읽는 기계의 모형을 제시했다. 기계의 현재 상태와 읽은 기호에 따라 다음 동작이 정해진다. 기호를 쓰거나 지우고, 읽는 위치를 옮기고, 상태를 바꾸는 작은 동작을 이어 간다. 상태는 현재 어떤 동작 규칙을 적용할지 구별하는 표시다. 같은 기호를 읽더라도 상태가 다르면 다음 동작이 달라질 수 있다. 원 논문 1–2절의 기계 설명 (새 창)

이 모형은 규칙을 따라 계산한다는 활동을 분명하게 적는 데 초점을 둔다. 읽기와 쓰기, 위치 이동 같은 작은 동작과 유한한 규칙으로 절차를 표현한다. 종이 위 모형의 단순함 덕분에 어느 계산이 가능한지에 대한 질문도 정확하게 표현할 수 있다.

기계의 규칙 자체를 기호로 기록할 수 있다는 점도 필요하다. 그러면 그 기록을 다른 기계의 입력으로 줄 수 있다. 계산을 수행하는 기계와 그 기계에 대한 설명을 처리하는 기계가 완전히 별개의 세계에 있지 않게 된다. 원 논문은 기계 설명을 부호로 나타내는 방식을 다룬다. 기계의 규칙을 일정한 기호의 순서로 나타내면, 다른 기계가 그 설명을 읽으며 해당 동작을 모사할 수 있다.

통상 이 논문을 ‘1936년 논문’이라고 부른다. 원 논문에는 그해의 접수·낭독 기록이 있고, 학술지의 현재 서지 페이지는 1937년으로 표기한다. 날짜를 단순화할 때 어느 기록을 가리키는지 남겨 두는 편이 정확하다. 이 차이는 기계 모형의 내용을 바꾸지는 않지만, 인용을 확인할 독자를 돕는다. 학술지 서지 표기 (새 창)

완벽한 판정기가 있다고 가정하기

정지 문제의 한계를 짧은 논증으로 보자. 다음은 현대의 표현으로 정리한 설명이며 튜링의 1936년 원문 증명을 그대로 옮긴 것이 아니다. 모든 프로그램의 종료 여부를 반드시 맞히는 판정기 H가 있다고 가정한다. H는 프로그램과 입력을 받고 ‘끝남’이나 ‘끝나지 않음’ 가운데 하나를 답한다.

H를 이용해 새 프로그램 D를 만든다. D는 입력으로 받은 프로그램 설명을 H에게 보내되, 그 프로그램이 자기 자신의 설명을 입력받았을 때 끝나는지 묻는다. H가 끝난다고 답하면 D는 끝없이 반복한다. H가 끝나지 않는다고 답하면 D는 곧바로 끝난다. 이 구성은 H의 답과 반대로 동작하도록 정한 규칙이다.

이제 D에게 D 자신의 설명을 입력한다. H가 D는 끝난다고 예측하면 D의 규칙에 따라 끝나지 않는다. 끝나지 않는다고 예측하면 D는 끝난다. 어느 답도 맞지 않는다. 따라서 처음 가정했던 완벽한 H는 존재할 수 없다. 모순을 만든 출발점은 D의 간단한 반대 동작이 아니라, H가 모든 경우에 올바르게 답한다는 가정이다. 현대 논증과 역사적 표현의 구분 (새 창)

D의 설명 역시 부호로 적을 수 있다. D를 실행하는 데 쓰인 규칙의 문자열을 다시 D의 입력으로 주는 것이 자기 참조의 구체적인 내용이다. 프로그램 설명을 처리한다는 같은 방식이 모든 입력에 적용되기 때문에, D 자신의 설명도 예외로 빼놓을 수 없다.

원 논문과 오늘의 교과서가 묻는 것

튜링의 원 논문은 이진 숫자를 계속 출력하는 기계 등의 판정 문제와 논리의 결정 문제를 다룬다. 오늘 익숙한 ‘정지 문제’라는 이름과 위의 자기 참조 논증이 그 논문에 같은 형태로 등장한 것은 아니다. 햄킨스와 네누의 연구는 이 차이를 자세히 검토하면서, 원 논문이 현대 정지 문제 분석에 필요한 큰 틀을 제공했다는 점도 함께 설명한다. 원 논문에 대한 연구자의 대조 (새 창)

원 논문의 기계 설명과 현대의 프로그램 설명을 대조하면, 이어진 발상과 달라진 표현을 함께 볼 수 있다. 당시에는 어떤 출력이 계속 가능한지를 물었고, 현대 정지 문제에서는 실행이 끝나는지를 묻는다. 계산 절차를 기호로 적고 그 설명 자체를 처리한다는 틀은 이 질문들을 연결한다.

‘범용’이라는 말도 모든 질문에 정답을 준다는 뜻으로 읽으면 안 된다. 다른 기계의 계산 절차를 모사할 수 있어도, 모사 중인 계산이 영원히 계속되는 경우에는 그 과정도 계속될 수 있다. 여러 일을 수행할 수 있다는 능력과 모든 과정의 결과를 미리 판정하는 능력은 다르다. 범용 기계의 폭넓음과 계산의 한계는 서로 모순되지 않는다.

실용적인 설계에서는 이 한계를 알아도 할 수 있는 일이 많다. 입력의 범위를 제한하거나, 명확한 종료 조건을 증명하거나, 제한 시간을 두고 중단할 수 있다. 하지만 제한 시간에 멈췄다는 것은 원래 프로그램이 영원히 끝나지 않는다고 증명한 것과 다르다. 운영상의 결정을 수학적 판정으로 표현하지 않아야 한다.

진행 기록을 남기면 특정 실행이 어디까지 갔는지는 확인할 수 있다. 다만 그 기록이 아무리 길어도 앞으로의 모든 단계를 직접 관찰한 것은 아니다. 실행을 본 증거와 규칙 전체에 대해 증명한 결과를 구분하면, 프로그램 점검의 성과도 한계도 더 분명하게 보고할 수 있다.

1950년에는 다른 질문을 꺼냈다

튜링의 **1950년 「계산 기계와 지능」**은 기계가 생각할 수 있는지라는 질문을 더 분명한 방식으로 다루기 위해 모방 게임을 제안한다. 계산가능성의 경계를 따진 논문과 시기와 목적이 다르다. 둘 모두 튜링의 작업이라는 이유로 하나의 실험처럼 합쳐서는 안 된다. 1950년 논문 서론 (새 창)

정지 문제를 일반적으로 판정할 수 없다는 결론은 기계의 모든 지적 활동이 불가능하다는 뜻이 아니다. 반대로 어떤 기계가 대화를 그럴듯하게 한다는 사실도 계산 불가능한 문제를 해결했다는 증거가 아니다. 지능의 평가, 계산 모델의 능력, 실제 장치의 시간과 메모리 비용은 나눠서 따져야 한다.

수학적으로 계산 가능한 절차라도 자원이 부족하면 실용적으로 실행하기 어렵다. 어려운 계산이 모두 불가능한 것은 아니고, 불가능성 정리가 있는 문제를 더 빠른 장치만으로 해결할 수 있는 것도 아니다. 이 둘을 구별하면 기술의 한계를 막연한 비관으로 말하지 않고, 어느 주장에 어떤 종류의 근거가 필요한지 요구할 수 있다.

프로그램이 답을 내놓지 않을 때 우리는 기다리거나, 범위를 바꾸거나, 다른 확인 방법을 선택할 수 있다. 그 선택을 설명할 언어가 있다는 것이 계산의 경계를 아는 데서 얻는 실용적인 성과다. 어떤 질문에 답하지 못했다는 사실과, 그런 질문 모두에 답할 계산법이 없다는 증명은 끝까지 별개의 기록으로 남겨야 한다.