알고리즘과 자료구조 5강. 컴퓨터가 절대 못 푸는 문제
컴퓨터가 발명되기도 전에, 컴퓨터가 영원히 못 하는 일이 무엇인지가 먼저 증명됐습니다.
풀고 시작
계산한다는 것이 무엇인지부터
1936년, 스물넷의 앨런 튜링은 힐베르트가 던진 결정 문제, 즉 어떤 명제가 공리에서 증명되는지를 기계적으로 판정하는 절차가 있는가라는 질문에 답하려 했습니다. 그런데 걸림돌이 있었습니다. "기계적 절차"가 정확히 무엇인지 아무도 정의한 적이 없었거든요. 튜링의 해법은 지금 봐도 대담합니다. 그는 종이 앞에 앉은 사람이 계산할 때 실제로 하는 일을 최소한으로 깎아 냈습니다. 무한히 긴 테이프 위에서 지금 칸의 기호를 읽고, 자기 상태와 그 기호에 따라 기호를 쓰고, 한 칸 좌우로 움직이고, 상태를 바꾼다. 이것이 튜링 기계의 전부입니다. 놀랍게도 이 초라한 장치가 오늘날 어떤 컴퓨터로 계산할 수 있는 것을 모두 계산합니다. 알론조 처치는 같은 시기에 람다 계산이라는 전혀 다른 형식에서 출발했는데 계산 가능한 범위가 정확히 일치했습니다. 여기서 처치-튜링 논제가 나옵니다. 직관적으로 계산 가능한 것은 튜링 기계로 계산 가능한 것과 같다는 주장이죠. 이것이 정리가 아니라 논제로 불리는 이유를 짚고 갑시다. 한쪽에 있는 "직관적 계산 가능성"은 수학적으로 정의된 개념이 아니라서 증명의 대상이 될 수 없습니다. 여러 독립적 정의가 모두 같은 곳에 도달했다는 압도적 증거가 뒷받침할 뿐입니다.
자기 자신을 먹는 프로그램
이제 튜링의 결정타입니다. 프로그램 P와 입력 x를 받아 P가 x에서 언젠가 멈추는지를 참거짓으로 답해 주는 판정기 H가 있다고 가정해 봅시다. 있으면 정말 좋을 도구죠. 이제 이 H를 부품으로 써서 심술궂은 프로그램 D를 만듭니다. D는 프로그램 하나를 입력으로 받아 H에게 "이 프로그램에 그 자신을 입력으로 넣으면 멈추는가"를 묻고, H가 "멈춘다"고 하면 일부러 무한 루프에 빠지고, H가 "안 멈춘다"고 하면 즉시 멈춥니다. 그럼 D에게 D 자신을 입력으로 넣어 보죠. D가 멈춘다면 H는 멈춘다고 답했을 테고, 그러면 D는 정의상 무한 루프에 빠져야 하니 멈추지 않습니다. 반대로 D가 멈추지 않는다면 H는 안 멈춘다고 답했을 테고, 그러면 D는 즉시 멈춥니다. 어느 쪽이든 모순입니다. 잘못된 것은 D가 아니라 H가 존재한다는 애초의 가정입니다. 이 논법의 뼈대는 칸토어가 실수를 셀 수 없음을 보인 대각선 논증 그대로입니다. 목록에 있는 모든 항목과 어긋나도록 만들어진 대각선의 존재가 목록의 완전성을 부수는 것이죠.
이 정리가 실무에 남긴 흔적
이것을 논리학자들의 실내 게임으로 여기면 곤란합니다. 정지 문제의 결정 불가능성은 소프트웨어를 만드는 사람의 일상에 매일 흔적을 남깁니다. 모든 프로그램의 무한 루프를 빠짐없이 잡아내는 완벽한 정적 분석기는 만들 수 없습니다. 있다면 그것이 곧 H일 테니까요. 그래서 현실의 분석 도구는 완벽함을 포기하고 한쪽으로 기웁니다. 안전한 코드까지 의심해 경고를 남발하거나(오탐 감수), 반대로 어떤 문제는 조용히 지나치거나(누락 감수) 둘 중 하나를 고르죠. 컴파일러 경고가 가끔 엉뚱한 곳을 짚는 이유가 게으름이 아니라 이 정리에 있습니다. 보안 쪽도 마찬가지입니다. 어떤 프로그램이든 입력으로 받아 악성인지 아닌지 완벽히 판정하는 검출기 역시 존재할 수 없습니다. 악성 여부는 그 프로그램이 결국 무슨 짓을 하는지에 관한 물음이고, 그런 물음은 정지 문제로 환원되기 때문입니다. 그래서 실제 보안 제품은 완벽한 판정을 포기하고 불완전한 방법을 여러 겹 쌓습니다. 알려진 악성 코드의 특징을 대조하고, 격리된 환경에서 행동을 관찰하고, 평소와 다른 통신 패턴을 통계로 잡아냅니다. 이용자 입장에서 실효가 큰 대비도 여기서 나옵니다. 검출을 믿기보다 소프트웨어를 최신 상태로 유지하고, 권한을 필요한 만큼만 주고, 백업을 따로 떼어 두는 쪽이 훨씬 낫습니다. 완벽한 문지기가 원리적으로 불가능하다면 문이 뚫린 뒤를 준비하는 것이 합리적이니까요.
예외가 아니라 규칙이었다
정지 문제만 유독 운이 없었던 것일까요. 1951년 헨리 고든 라이스가 훨씬 가혹한 답을 내놓았습니다. 라이스 정리에 따르면 프로그램이 계산하는 함수에 관한 성질 중 자명하지 않은 것은 전부 결정 불가능합니다. 여기서 자명하지 않다는 말은 어떤 프로그램은 그 성질을 가지고 어떤 프로그램은 갖지 않는다는 뜻입니다. 이 프로그램이 항상 멈추는가, 다른 프로그램과 똑같은 함수를 계산하는가처럼 우리가 정말 알고 싶은 질문들이 몽땅 이 그물에 걸립니다. 다만 경계는 분명합니다. 라이스 정리가 막는 것은 프로그램이 무엇을 계산하는가라는 의미론적 성질이지, 코드가 어떻게 생겼는가라는 구문적 성질이 아닙니다. 줄 수가 100줄을 넘는지, 특정 함수 이름이 등장하는지는 얼마든지 판정할 수 있습니다. 그래서 실무의 도구들은 의미를 직접 묻는 대신 구문과 근사에 기대는 것이죠.
괴델과 한 핏줄
이 이야기가 어딘가 익숙하다면 정확한 직감입니다. 1931년 쿠르트 괴델은 충분히 강한 형식 체계 안에 참이지만 증명할 수 없는 명제가 있음을 보였고, 그 증명의 심장에도 자기 지시와 대각선 논법이 있었습니다. 괴델이 명제로 한 일을 튜링은 기계로 다시 한 셈입니다. 실제로 튜링의 결과에서 괴델의 정리를 끌어낼 수도 있습니다. 두 사람이 함께 알려 준 것은 비관이 아니라 지도입니다. 형식 체계에도, 계산에도 넘을 수 없는 선이 있으며 그 선은 도구가 부실해서가 아니라 자기 자신을 다루는 능력에서 필연적으로 생겨납니다. 자세한 이야기는 수학기초론의 괴델 편에 있습니다. 알고리즘 다섯 강을 지나며 우리는 절차를 쓰는 법에서 시작해 비용을 재는 법을 배웠고, 마침내 절차라는 것 자체의 한계선까지 왔습니다. 이 선을 알고 나서야 그 안쪽에서 무엇을 할 수 있는지가 제대로 보입니다.
인출 문제
생각해볼 질문 (정답 없음)
- 완벽한 악성 코드 검출기가 원리적으로 불가능하다면, 안전하다는 표시를 붙여 판매되는 보안 제품의 약속은 정확히 무엇에 대한 약속이어야 할까요.
이전: 알고리즘과 자료구조 4강 · 다음: 프로그래밍의 세계 1강