멈출지 알 수 없다
프로그램의 멈춤을 미리 알 수 있나
컴퓨터 프로그램이 무한 루프에 빠져 영원히 멈추지 않을지, 아니면 언젠가 계산을 끝내고 정상적으로 종료할지를 100% 미리 검사해 주는 만능 판별 프로그램을 만들어 보세요.
앨런 튜링은 그런 만능 검사기는 절대로 만들 수 없음을 증명했습니다. 모든 것을 계산할 수 있을 것 같은 컴퓨터에게 왜 스스로 멈출지조차 미리 알 수 없는 영원한 사각지대가 있을까요?
이야기
Unknown photographer
Public domain · 위키미디어 공용
1936년, 스물넷의 앨런 튜링이 이 증명을 발표했을 때 세상에는 컴퓨터가 없었습니다. 그는 종이 위에서 기계를 하나 상상해 놓고, 아직 만들어지지도 않은 기계의 한계를 먼저 증명한 것입니다.
그런데 이 증명이 뜻밖의 선물을 남겼습니다. 한계를 말하려고 상상한 그 기계 — 「튜링 기계」가 컴퓨터라는 것의 정의가 되었습니다. 「할 수 없다」를 보이려다 「무엇이 컴퓨터인가」를 정한 셈입니다.
증명은 이렇습니다. 멈출지 알려 주는 판별기 H가 있다고 해 봅시다. 이제 심술궂은 프로그램 D를 만듭니다. D는 자기 자신을 H에 넣어 보고, 「멈춘다」고 하면 일부러 영원히 돌고, 「안 멈춘다」고 하면 바로 멈춥니다.
그러면 D는 멈출까요. 멈춘다면 H가 그렇게 말했다는 뜻이고, 그러면 D는 영원히 돌게 되어 있습니다. 안 멈춘다면 H가 그렇게 말한 것이고, 그러면 D는 바로 멈추게 되어 있습니다.
어느 쪽도 안 됩니다. 그러니 H가 애초에 있을 수 없습니다. 영리하지 못해서가 아니라 원리적으로 불가능한 것입니다.
이 증명이 통하는 까닭은 프로그램이 자기 자신을 입력으로 받을 수 있기 때문입니다. 글이 자기를 가리켜 「이 문장은 거짓이다」가 되듯, 프로그램도 자기를 가리킬 수 있습니다. 그 순간 판별기는 갈 곳이 없어집니다.
이 한계 때문에 어떤 검사 도구도 모든 무한루프를 잡아내지 못합니다. 프로그램이 멈출지 미리 아는 완전한 방법은 원리적으로 없습니다.
그리고 이 답을 내려고 튜링이 정의한 「계산이란 무엇인가」가 지금 우리가 쓰는 컴퓨터의 설계도가 되었습니다.
계단 넷 — 같은 사실을 네 깊이로
청개구리 프로그램을 상상해 본다
어떤 프로그램은 버튼을 누르면 1초 만에 끝나고, 어떤 프로그램은 뱅글뱅글 돌며 먹통이 됩니다. 실행하기 전에 미리 오류를 잡아 주는 마법의 탐지기를 꿈꿔 봅니다.
하지만 자기 자신의 미래를 미리 보고 거꾸로 행동하는 영리한 청개구리 프로그램을 만들면 그 어떤 슈퍼컴퓨터 탐지기도 무조건 고장 납니다.
멈출까요 안 멈출까요
안 멈추면 영원히 기다려야 하기 때문입니다.
판별기 H 와 청개구리 T
만약 어떤 프로그램의 소스코드를 읽고 멈출지 무한 루프에 빠질지 100% 알아맞히는 만능 판별기 H가 있다고 가정해 봅시다.
이제 청개구리 프로그램 T를 만듭니다. T는 H에게 자기 자신을 검사하게 한 뒤, H가 "너는 멈춘다"고 판정하면 일부러 무한 루프를 돌고, H가 "너는 멈추지 않는다"고 판정하면 즉시 종료해 버립니다. H는 T 앞에서 반드시 틀릴 수밖에 없습니다.
왜 불가능한가
거짓말쟁이 역설과 똑같은 짜임입니다.
모순으로 보이기
튜링의 정지 문제(Halting Problem) 증명은 귀류법과 칸토어의 대각선 논법을 튜링 기계(Turing Machine)에 투영한 결과입니다.
프로그램과 입력의 쌍 에 대해 정지 여부를 판정하는 튜링 기계 가 존재한다고 가정하면, 은 이 '정지'면 무한루프, '루프'면 정지하도록 정의됩니다. 을 실행하면 모순이 발생하여 는 존재할 수 없습니다.
바쁜 비버
계산할 수 없을 만큼 빨리 커지는 함수입니다.
계산가능성
정지 문제의 결정 불가능성(Undecidability)은 라이스 정리(Rice's Theorem)로 확장되어 프로그램의 비자명한 모든 의미론적 성질(버그 유무, 정확성)을 기계적으로 자동 판별할 수 없음을 규명했습니다.
현대 소프트웨어 공학의 정적 분석기, 컴파일러 최적화 한계 및 사이버 보안의 악성코드 탐지 이론에서 근본적인 한계선이자 핵심 이론적 나침반으로 작용합니다.
결정 불가능한 문제들
모두 정지 문제로 환원됩니다 — 뿌리가 하나입니다.
풀어 보기
튜링의 정지 문제와 결정 불가능성. 다음 물음에 답하시오.
(1) 튜링의 정지 문제 증명에 사용된 수학적 증명 방법(논리 구조)의 이름을 쓰시오.
(2) 프로그램 P가 입력 x에 대해 정지하는지 여부를 판정하는 만능 알고리즘이 존재하지 않음을 청개구리 프로그램 D의 동작을 들어 설명하시오.
(3) 프로그램이 생성하는 언어의 비자명한 모든 성질이 튜링 결정 불가능하다는 일반화된 정리의 이름을 쓰시오.
(1) 귀류법 및 대각선 논법입니다. (2) 판별기가 '정지'라 하면 무한루프를 돌고 '루프'라 하면 멈추도록 구성하여 모순을 만듭니다. (3) 라이스 정리입니다.
답과 풀이 보기
(1) 귀류법과 대각선 논법입니다.
「있다고 치자 → 모순이 나온다 → 그러므로 없다」가 귀류법이고, 자기 자신을 입력으로 넣어 어긋나게 만드는 것이 대각선 논법입니다.
⭐ 칸토어가 실수를 셀 수 없음을 보인 그 방법과 뼈대가 같습니다.
(2) 판별기 가 있다고 가정합니다 — 프로그램 와 입력 를 주면 멈춘다/안 멈춘다를 언제나 맞힌다고 합시다.
이제 청개구리 프로그램 를 만듭니다 — 는 자기에게 들어온 프로그램 에 대해
· 가 「멈춘다」고 하면 → 는 영원히 돕니다
· 가 「안 멈춘다」고 하면 → 는 바로 멈춥니다
이제 자신을 에게 넣어 봅니다.
· 가 멈춘다면 → 규칙에 따라 영원히 돌아야 합니다
· 가 안 멈춘다면 → 규칙에 따라 멈춰야 합니다
둘 다 모순입니다. 그러므로 는 없습니다.
(3) 라이스 정리입니다.
「프로그램이 무엇을 하는지에 관한 성질 가운데 자명하지 않은 것은 모두 판정할 수 없다」
⛔ 그러니 「이 프로그램에 버그가 있는가」를 언제나 맞히는 프로그램은 만들 수 없습니다.
1936 년, 스물세 살 튜링이 이것을 증명했습니다. 컴퓨터가 세상에 하나도 없던 때입니다.
⭐ 그는 이 증명을 하려고 「기계로 셈한다」는 것이 무엇인지 먼저 정의해야 했습니다. 그렇게 만든 것이 튜링 기계 — 곧 컴퓨터의 설계도입니다.
컴퓨터로 할 수 없는 일을 증명하려다 컴퓨터를 발명했습니다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
컴퓨터가 태어나기 전에 그 한계가 먼저 밝혀졌습니다.
- 대각선 논법 — 칸토어와 괴델이 쓴 그 방법입니다
- 실무에서 — 그래서 어떤 검사 도구도 모든 무한루프를 잡아내지 못합니다
- 라이스 정리 — 프로그램의 「의미」에 관한 물음은 거의 다 판정 불가능합니다
이어지는 장
수학 체계 안에 증명할 수 없는 참인 명제가 있듯 컴퓨터 프로그램에도 끝날지 미리 알 수 없는 문제가 있습니다 — 제149장 의 불완전성 정리가 현대 컴퓨터 과학과 기계 계산의 한계로 고스란히 이어집니다.
영감을 받은 곳
앨런 튜링(Alan Turing)이 1936년 런던수학회보(Proceedings of the London Mathematical Society)에 발표한 논문 「계산 가능한 수와 결정 문제에의 응용에 관하여」에서 정지 불가능성을 증명했습니다.