정지 문제
고친 사람 github-actions[bot]
정지 문제는 프로그램이 언젠가 끝나는지를 끝까지 기다리지 않고 알아내라는 물음입니다. 어떤 프로그램을 넣어도 이 물음에 맞게 답하는 판정기는 만들 수 없다고 증명되어 있습니다. 그래서 무한 루프를 빠짐없이 잡아내는 검사 도구는 없습니다. 실무 도구는 이 한계를 비켜 가는 쪽으로 만들어집니다.
쉽고 빠른 이해
무엇을 말하나 — 정지 문제는 프로그램이 끝날지 영원히 돌지를 묻습니다. 이 물음에 늘 맞게 답하는 판정기는 만들 수 없다는 것이 증명되어 있습니다. 반복문 하나짜리 짧은 코드 가운데도 모든 입력에서 끝나는지 아무도 모르는 것이 있습니다.
왜 알아야 하나 — 코드 검사 도구가 엉뚱한 경고를 내거나 버그를 놓치는 까닭이 여기서 나옵니다. 이 사실을 모르면 모든 코드를 맞게 가르는 판정기를 만들려다 헛수고를 합니다.
어떻게 증명하나
- 판정기가 있다고 놓습니다
- 판정기의 답과 반대로 움직이는 프로그램을 짭니다
- 그 프로그램을 자기 자신에게 판정시키면 판정기가 어느 답을 내도 틀립니다
무엇을 내주나 — 실무 도구는 모르면 경고 쪽이나 통과 쪽 중 하나로 정해 버리거나, 시간을 정해 두고 끊거나, 끝나는 것이 보장된 코드만 쓰게 합니다.
상세
이 절은 정지 문제가 무엇을 묻는지, 왜 답할 수 없는지, 실무가 이 한계를 어떻게 비켜 가는지를 다룹니다. 짧은 파이썬 함수 몇 개를 가지고 봅니다.
정지 문제는 결정 문제입니다. 결정 문제는 답이 「예」나 「아니요」 둘 중 하나인 물음입니다. 「이 수가 소수인가」가 결정 문제입니다.
정지 문제가 받는 입력은 둘입니다. 프로그램의 코드 한 벌과, 그 프로그램에 넣을 입력 하나입니다. 물음은 「이 프로그램에 이 입력을 넣으면 언젠가 끝나나」입니다.
판정기가 지켜야 하는 약속
이 물음에 답하는 프로그램을 판정기라고 부르겠습니다. 판정기는 아래 약속 셋을 지켜야 합니다.
- 어떤 코드든 받는다 — 코드와 입력이 무엇이든 받아 줍니다
- 늘 맞게 답한다 — 받은 것마다 「끝난다」나 「안 끝난다」 가운데 맞는 쪽을 냅니다
- 판정기 자신도 끝난다 — 답을 내고 반드시 멈춥니다
답을 영영 안 주는 판정기는 아무것도 판정하지 않은 것과 같습니다. 그래서 셋째 약속이 붙습니다.
돌려 보면 되지 않나
가장 먼저 떠오르는 방법은 그냥 돌려 보는 것입니다. 프로그램이 끝나면 「끝난다」를 바로 알 수 있습니다.
문제는 안 끝날 때입니다. 100초를 기다려도 안 끝났다고 해서 101초째에 안 끝난다는 보장이 없습니다. 돌려 보는 방법으로는 「끝난다」만 답할 수 있습니다. 「안 끝난다」를 답하려고 기다리면 판정기 자신이 끝나지 않아 셋째 약속이 깨집니다.
코드를 읽어서 판단하는 것도 쉽지 않습니다. 아래 함수는 세 줄짜리 반복문입니다.
n 이 짝수면 반으로 나눕니다. 홀수면 세 배에 1 을 더합니다. 1 이 될 때까지 이것을 되풀이합니다.
def collatz(n):
steps = 0
while n != 1:
n = n // 2 if n % 2 == 0 else 3 * n + 1
steps += 1
return steps
collatz(6) # 8
collatz(27) # 111
주석의 값은 1 에 닿을 때까지 돈 횟수입니다. 6 은 여덟 번 만에 끝납니다. 27 은 백열한 번을 돌고서야 끝납니다.
이 함수가 모든 양의 정수에서 끝나는지는 아직 아무도 증명하지 못했습니다. 이 물음을 콜라츠 추측이라고 부릅니다. 세 줄짜리 코드도 끝나는지 모를 수 있다는 예입니다.
판정기가 있다고 놓고 모순을 끌어낸다
판정기를 만들 수 없다는 증명은 귀류법으로 갑니다. 귀류법은 반대 주장이 참이라고 놓고, 거기서 모순을 끌어내 반대 주장을 무너뜨리는 증명 방법입니다.
그래서 판정기가 있다고 놓습니다. 이름을 halts 라고 붙입니다. 코드 p 와 입력 x 를 받아 끝나면 True, 안 끝나면 False 를 돌려줍니다.
halts(p, x) # True 또는 False
증명은 코드도 입력이 될 수 있다는 점을 씁니다. 코드는 결국 글자를 늘어놓은 텍스트입니다. 컴파일러가 소스 코드를 입력으로 받듯이, 어떤 프로그램이든 다른 프로그램의 코드를 입력으로 받을 수 있습니다. 자기 자신의 코드도 받을 수 있습니다.
이제 halts 를 써서 일부러 반대로 움직이는 함수를 하나 짭니다. 이름은 contrary 입니다.
def contrary(p):
if halts(p, p): # 끝난다는 답이면
while True: # 영원히 돈다
pass
return # 아니면 바로 끝낸다
contrary 는 코드 p 를 받습니다. 그리고 「p 에 p 자신의 코드를 넣으면 끝나나」를 halts 에게 묻습니다. 답을 받으면 그와 반대로 움직입니다.
마지막 한 수는 contrary 에 contrary 자신의 코드를 넣는 것입니다. 그러면 안에서 부르는 halts(contrary, contrary) 가 받는 물음은 「지금 돌고 있는 바로 이 contrary(contrary) 가 끝나나」가 됩니다. 아래 그림이 이 겹침을 보입니다.
sequenceDiagram
participant contrary
participant halts
contrary->>halts: halts(contrary, contrary) · 이 실행이 끝나나?
Note over contrary,halts: 묻는 대상이 지금 돌고 있는 바로 이 실행이다
halts-->>contrary: 끝난다 또는 안 끝난다
Note over contrary: 받은 답과 반대로 움직인다
halts 가 내놓을 수 있는 답은 둘뿐입니다. 아래 그림처럼 어느 쪽이든 틀립니다.
flowchart TD
A["contrary 에 자기 코드를 넣는다"] --> B{"halts(contrary, contrary): 이 실행이 끝나나?"}
B -->|끝난다| C["contrary 는 영원히 돈다"]
B -->|안 끝난다| D["contrary 는 바로 끝난다"]
C --> E["끝난다는 답이 틀렸다"]
D --> F["안 끝난다는 답이 틀렸다"]
E --> G["halts 는 이 입력에서 반드시 틀린다"]
F --> G
halts 를 어떻게 짜든 이 입력 하나에서는 틀립니다. 그러니 모든 입력에 맞게 답하는 판정기는 처음부터 없었던 것입니다.
한계가 생기는 원인
판정기를 만들 수 없다는 결론은 수학 증명에서 나옵니다. 컴퓨터가 빨라지거나 더 똑똑한 분석 기법이 나와도 바뀌지 않습니다.
뿌리는 자기 참조입니다. 판정기가 받는 입력 가운데 판정기 자신을 품은 코드가 섞일 수 있습니다. 그 코드가 판정기의 답을 뒤집도록 짜이면 판정기는 피할 길이 없습니다.
이것은 특정 언어의 약점이 아닙니다. 조건문과 끝을 미리 정하지 않는 반복문이 있으면 앞의 contrary 를 짤 수 있습니다. 이렇게 어떤 계산이든 표현할 수 있는 언어를 튜링 완전하다고 부릅니다. 파이썬·자바·C 같은 범용 언어는 거의 다 튜링 완전합니다.
어떤 결정 문제에 모든 입력에서 맞게 답하는 알고리즘이 없을 때, 그 문제를 결정 불가능하다고 합니다. 정지 문제는 결정 불가능한 문제의 대표입니다. 이 증명을 처음 보인 사람은 앨런 튜링입니다.
불가능하다는 말이 막는 범위
증명이 막는 것은 「모든 프로그램에 대해 늘 맞게 답하는 판정기 하나」입니다. 특정 프로그램이 끝나는지를 아는 것까지 막지는 않습니다.
for i in range(10) 하나만 도는 코드는 열 번 돌고 끝난다고 바로 압니다. 반복문이 아예 없는 코드도 끝난다고 압니다. 많은 프로그램은 이렇게 판정할 수 있습니다. 판정이 안 서는 프로그램이 반드시 남는다는 것이 증명의 내용입니다.
실제 컴퓨터는 메모리가 유한합니다. 여기서 상태란 어느 순간 메모리에 든 값 전체를 말합니다. 메모리가 유한하니 상태의 가짓수도 유한합니다.
프로그램은 같은 상태에서 늘 같은 다음 상태로 넘어갑니다. 그래서 같은 상태가 한 번 다시 나오면 그 뒤로는 같은 길을 끝없이 되풀이합니다. 상태가 되풀이되는지 지켜보면 끝나는지 가릴 수 있습니다.
stateDiagram-v2
state "상태 A" as s1
state "상태 B" as s2
state "상태 C" as s3
s1 --> s2
s2 --> s3
s3 --> s1
note right of s1 : 같은 상태 다음에는 늘 같은 상태가 온다
하지만 상태의 가짓수가 메모리 비트 수만큼 2 를 거듭 곱한 수라서 이 방법은 쓸모가 없습니다. 메모리가 1 킬로바이트만 돼도 2 를 팔천 번 넘게 곱한 수입니다.
오래 걸리는 문제와 못 푸는 문제
정지 문제는 오래 걸리는 문제와 다릅니다. 오래 걸리는 쪽의 대표가 NP-완전(이름의 NP 는 Nondeterministic Polynomial time 의 줄임말) 문제입니다.
NP-완전 문제는 답을 내는 알고리즘이 있습니다. 다만 입력이 커지면 걸리는 시간이 빠르게 불어나, 기다릴 수 없을 만큼 오래 걸릴 수 있습니다. 모든 도시를 한 번씩 도는 가장 짧은 길을 찾는 외판원 순회가 이런 문제입니다.
정지 문제는 시간을 아무리 줘도 모든 입력에 답하는 알고리즘이 없습니다. NP-완전 문제는 얼마나 빨리 풀리나를 따집니다. 정지 문제는 풀리기는 하나를 따집니다. 이 둘을 가르는 분야가 계산가능성 이론입니다.
같은 벽에 부딪히는 다른 물음
코드가 무엇을 하는지 묻는 물음은 대개 정지 문제만큼 어렵습니다. 정지 문제를 그 물음으로 바꿀 수 있기 때문입니다. 「이 함수가 None 을 돌려줄 수 있나」를 예로 봅니다.
아무 프로그램 p 와 입력 x 를 골라 아래 함수를 만듭니다.
def f():
p(x) # p 가 끝나야
return None # 이 줄에 닿는다
f 가 None 을 돌려주는 때는 p(x) 가 끝날 때뿐입니다. 「f 가 None 을 돌려줄 수 있나」에 늘 맞게 답하는 도구를 None 도구라고 부르겠습니다. 이 도구가 있으면 아래 그림처럼 그것을 부품으로 써서 정지 문제의 판정기를 짤 수 있습니다.
flowchart TD
A["프로그램 p 와 입력 x"] --> B["f 를 짠다 · p(x) 를 돌린 뒤 None 을 돌려준다"]
B --> C{"None 도구에 f 를 넣는다"}
C -->|돌려줄 수 있다| D["p(x) 는 끝난다"]
C -->|돌려줄 수 없다| E["p(x) 는 안 끝난다"]
D --> F["정지 문제가 풀렸다 · 그런데 정지 문제는 못 푼다"]
E --> F
F --> G["그러니 None 도구는 없다"]
어떤 p 와 x 를 넣어도 이 조립은 정지 문제에 답합니다. 정지 문제는 못 푸니 None 도구도 없습니다.
이렇게 한 물음을 다른 물음으로 바꾸는 일을 환원이라고 부릅니다. 환원은 물음을 풀 때 씁니다. 여기서처럼 못 푼다는 사실을 다른 물음으로 옮겨 보일 때도 씁니다.
같은 방법으로 아래 물음들도 모든 코드에 대해 맞게 답할 수 없습니다. 표의 오른쪽은 그 답을 원하는 도구입니다.
| 묻는 것 | 그 답을 원하는 도구 |
|---|---|
| 이 줄에 실행이 닿을 수 있나 | 죽은 코드를 찾는 검사 |
| 이 변수가 비어 있는 채로 쓰일 수 있나 | 널 참조 경고 |
| 두 함수가 모든 입력에서 같은 값을 내나 | 리팩터링 검증 · 최적화 |
| 이 반복문이 끝나나 | 무한 루프 경고 |
이것을 한 문장으로 묶은 것이 라이스 정리입니다. 프로그램이 내는 결과에 관한 성질은, 늘 참이거나 늘 거짓인 시시한 성질이 아니면 전부 결정 불가능하다는 정리입니다.
한계를 비켜 가는 방법
판정기를 만들 수 없다는 결론은 못 넘습니다. 할 수 있는 것은 판정기의 약속 셋 가운데 하나를 풀어, 그 결론에 부딪히지 않게 일을 바꾸는 것입니다. 실무에서 쓰는 방법은 셋입니다.
| 방법 | 푸는 약속 | 내주는 것 |
|---|---|---|
| 넘겨짚기 | 늘 맞게 답한다 · 「모르겠다」도 답으로 낸다 | 틀린 경고나 놓친 버그 |
| 시간 제한 | 늘 맞게 답한다 · 시간 안에 안 끝나면 실패로 친다 | 조금 더 기다렸으면 끝났을 작업도 끊긴다 |
| 언어 좁히기 | 어떤 코드든 받는다 | 표현할 수 있는 계산이 줄어든다 |
첫째는 넘겨짚기입니다. 판정이 서는 코드에는 답합니다. 안 서는 코드는 「모르겠다」로 돌려보냅니다. 그 「모르겠다」를 경고 쪽이나 통과 쪽 가운데 하나로 정해 버리는 것이 넘겨짚기입니다.
어느 쪽으로 넘겨짚느냐가 정적 분석 도구의 성격을 가릅니다. 모르면 일단 경고하는 도구는 문제가 없는 곳에도 경고를 냅니다. 이것을 오탐이라고 합니다.
모르면 조용히 넘어가는 도구는 진짜 버그를 지나칩니다. 이것을 미탐이라고 합니다. 아래 그림이 두 갈래를 보입니다.
flowchart TD
A{"판정이 서나"} -->|선다| B["판정대로 답한다"]
A -->|안 선다| C{"모르겠다를 어느 쪽으로 정하나"}
C -->|일단 경고| D["오탐 · 문제 없는 곳에 경고"]
C -->|조용히 넘어감| E["미탐 · 진짜 버그를 지나침"]
둘째는 시간 제한입니다. 정해 둔 시간이 지나면 작업을 끊고 실패로 칩니다. 요청마다 거는 타임아웃, 빌드 작업에 거는 실행 시간 상한, 멈춘 장치를 다시 켜는 워치독이 이 방법입니다.
시간 제한은 끝나는지를 판정한 것이 아닙니다. 끝나지 않을지도 모르는 작업을 끝까지 안 기다리기로 한 것입니다. 그래서 조금만 더 기다렸으면 끝났을 작업도 같이 끊깁니다.
셋째는 언어를 좁히는 것입니다. 반복 횟수가 실행 전에 정해지는 반복문만 허락합니다. 끝을 정하지 않는 반복과 재귀는 막습니다. 그러면 모든 프로그램이 끝납니다.
반복을 막는 대신 끝난다는 증명을 코드와 함께 내라고 하는 언어도 있습니다. 이 증명을 종료 증명이라고 부릅니다.
대가는 튜링 완전성을 잃는 것입니다. 끝나는 것이 보장된 대신, 그 언어로는 짤 수 없는 계산이 생깁니다. 그래서 이 방법은 Bazel 빌드 파일을 적는 언어 Starlark 나 설정 언어 Dhall 처럼 할 일이 좁은 언어에서 주로 씁니다.
관련 항목
정지 문제가 속하는 상위 분류
계산가능성 · 계산 이론 · 결정 문제 · 알고리즘
증명을 이루는 모형과 논법
튜링 기계 · 범용 튜링 기계 · 튜링 완전성 · 귀류법 · 대각선 논법 · 자기 참조 · 환원
정지 문제와 같은 뿌리의 불가능성 결과
라이스 정리 · 우편 대응 문제 · 괴델의 불완전성 정리 · 결정 불가능성
정지 문제와 맞세워지는 복잡도 등급
P 클래스 · NP 클래스 · NP-완전 · NP-난해 · P 대 NP 문제 · 외판원 순회
이 한계 탓에 넘겨짚는 분석 도구
정적 분석 · 린터 · 타입 검사 · 추상 해석 · 심볼릭 실행 · 모델 검사
넘겨짚는 방향을 가리키는 이름
오탐 · 미탐 · 건전성 · 완전성
정지 문제로 바뀌는 구체적 물음
무한 루프 · 죽은 코드 · 널 포인터 역참조 · 데드락 · 콜라츠 추측
이 한계를 비켜 가는 수단
타임아웃 · 워치독 · 종료 증명 · 전체 함수형 프로그래밍
이 물음을 처음 다룬 사람과 명제
앨런 튜링 · 알론조 처치 · 처치-튜링 논제 · 힐베르트의 결정 문제
다른 이름: halting problem · 멈춤 문제 · 정지성 문제