멈출까, 멈추지 않을까Will it stop, or run forever?
모든 프로그램은 둘 중 하나입니다. 언젠가 멈추거나(halt), 아니면 영원히 도는(loop) 것이죠. 간단해 보입니다. 그냥 실행해서 지켜보면 되지 않을까요? 문제는, 아직 안 멈춘 프로그램이 "곧 멈출 것"인지 "영원히 안 멈출 것"인지 구분할 방법이 없다는 겁니다. 1억 번째 단계에서 멈출지도 모르니까요. 영원히 기다려 볼 수는 없습니다.
Every program does one of two things: it eventually halts, or it loops forever. Sounds simple. Why not just run it and watch? The trouble is that a program which hasn't stopped yet gives no clue whether it is "about to stop" or "never going to stop." It might halt on step one billion. And you cannot wait forever.
그래서 우리는 더 똑똑한 걸 원합니다. 실행해 보지 않고도 코드만 분석해서 답을 주는 판정기 H. 프로그램 P와 입력을 넣으면, H는 절대 멈추지 않고 "멈춤" 또는 "무한 루프"를 정확히 답합니다. 이런 게 있으면 세상이 편해지겠죠. 무한 루프 버그를 미리 잡고, 완벽한 백신을 만들 수 있을 테니까요. 튜링은 이 꿈의 기계가 논리적으로 불가능함을 보였습니다.
So we want something cleverer: a decider H that analyzes the code alone, without running it. Feed it a program P and an input, and H always halts and correctly answers "halts" or "loops forever." Such a machine would be a gift: it would catch every infinite-loop bug and build a perfect antivirus. Turing showed this dream machine is logically impossible.
불가능을 증명하는 법: 청개구리 기계How to prove impossibility: the contrarian machine
직접 못 만든다는 걸 어떻게 증명할까요? "만들 수 있다"고 가정한 뒤, 그 가정이 스스로 무너지게 만드는 겁니다(귀류법). 완벽한 판정기 H가 있다고 칩시다. 정의는 이렇습니다.
How do you prove something can't be built? You assume it can, then let that assumption destroy itself (proof by contradiction). Suppose a perfect decider H exists. Here is its definition:
이제 이 H를 부품으로 써서 청개구리 기계 C를 만듭니다. C는 프로그램 P 하나를 받아, H에게 "P가 자기 자신 P를 입력받으면 멈추냐?"고 물어봅니다. 그리고 정확히 그 반대로 행동합니다.
Now use H as a component to build a contrarian machine C. C takes a single program P, asks H "does P halt when fed its own code P?", and then does exactly the opposite:
H가 "멈춘다"고 하면 C는 청개구리처럼 일부러 무한 루프에 빠지고, "무한 루프"라 하면 일부러 멈춥니다. 여기까지는 아무 문제 없습니다. 그런데 결정적인 한 방이 남았습니다. C에게 다른 프로그램이 아니라 자기 자신 C를 입력하는 것. 그게 무슨 뜻인지 예시로 차근차근 따라가 봅시다.
If H says "halts," C stubbornly loops forever; if H says "loops," C halts. No problem so far. But one fatal move remains: feeding C not some other program but its own code C. Let us walk through what that means, step by step, with an example.
예시로 따라가기: "C에 C를 넣는다"는 것Walking it through: feeding C to itself
프로그램이 자기 자신을 입력으로 받는 건 이상한 일이 아닙니다. 메모장으로 메모장의 소스코드 파일을 열 수 있고, 압축 프로그램으로 그 압축 프로그램의 설치파일을 압축할 수 있죠. C도 "프로그램 하나를 입력받는" 기계니까, 그 입력 자리에 C 자신의 코드를 넣을 수 있습니다. 먼저 C를 코드로 써보면 이렇습니다.
A program taking itself as input is nothing strange. You can open a text editor's own source file in that text editor, or compress a zip tool's own installer with that zip tool. C is a machine that "takes one program as input," so we can put C's own code into that input slot. First, here is C written out as code:
def C(프로그램):
답 = H(프로그램, 프로그램) # "이걸 자기 자신에게 돌리면 멈춰?"
if 답 == "멈춤":
while True: pass # 멈춘다길래 → 일부러 안 멈춘다
else: # 답 == "무한루프"
return # 안 멈춘다길래 → 일부러 멈춘다
def C(program):
ans = H(program, program) # "does this halt when run on itself?"
if ans == "HALT":
while True: pass # it says halt -> deliberately never halt
else: # ans == "LOOP"
return # it says loop -> deliberately halt
먼저 평범한 예시. 실행하면 곧바로 끝나는 프로그램 항상멈춤을 C에 넣어봅시다.
First, an ordinary example. Feed C a program called alwaysHalt that finishes immediately.
C(항상멈춤):
답 = H(항상멈춤, 항상멈춤) # 항상멈춤은 멈추니까 → 답 = "멈춤"
→ while True → C(항상멈춤)은 영원히 돈다
C(alwaysHalt):
ans = H(alwaysHalt, alwaysHalt) # alwaysHalt halts, so ans = "HALT"
→ while True → C(alwaysHalt) runs forever
여기서 H는 "항상멈춤은 멈춘다"고 참말을 했습니다. C가 그 말을 듣고 제멋대로 무한 루프에 빠진 것뿐이라, 아무 모순이 없어요. 그래서 지금까진 문제가 없는 겁니다. C는 좀 이상하지만 멀쩡한 프로그램입니다.
Here H told the truth: "alwaysHalt halts." C merely chose to loop after hearing that, so there is no contradiction. That is why nothing has broken yet. C is a strange but perfectly valid program.
이제 결정적 순간. 입력 자리에 C 자신을 넣습니다. 위 코드의 '프로그램' 자리에 전부 C를 대입해 보세요.
Now the decisive moment. Put C itself into the input slot: substitute C everywhere 'program' appears above.
C(C):
답 = H(C, C) # "C를 C에 돌리면(=C(C)) 멈춰?" ← 지금 돌리는 바로 그것!
if 답 == "멈춤": while True: pass # → C(C)는 영원히 돈다
else: return # → C(C)는 멈춘다
C(C):
ans = H(C, C) # "does C(C) halt?" ← the very thing now running!
if ans == "HALT": while True: pass # → C(C) runs forever
else: return # → C(C) halts
H(C, C)는 "C(C)가 멈추냐?"를 묻는 건데, 그 C(C)가 지금 실행 중인 바로 이 프로그램입니다. 이제 H가 뭐라 답하든 확인해 보세요.
H(C, C) asks "does C(C) halt?", and that C(C) is the very program running right now. Whatever H answers, check what happens:
| H의 답 | 코드가 실제로 하는 일 | 결과 |
|---|---|---|
| "멈춘다" | while True → 안 멈춤 | H 틀림 |
| "무한루프" | return → 멈춤 | H 틀림 |
| H's answer | what the code actually does | result |
|---|---|---|
| "halts" | while True → never halts | H is wrong |
| "loops" | return → halts | H is wrong |
어느 쪽이든 H가 틀립니다. C(C)는 "내가 멈출지"를 H에게 미리 물어보고 그 예언과 정확히 엇나가는 프로그램이라, H의 답은 반드시 빗나갑니다. 점쟁이가 "너 앉는다" 하면 안 앉고 "안 앉는다" 하면 앉아버리는 청개구리 앞에서 점쟁이가 무력해지는 것과 똑같죠.
Either way, H is wrong. C(C) asks H in advance "will I halt?" and then defies the prediction exactly, so H's answer must miss. It is like a contrarian who sits when the fortune-teller says "you won't" and stands when it says "you will": the fortune-teller is helpless against that one person.
이제 아래에서 H의 두 대답을 직접 눌러, 어느 쪽을 골라도 모순이 터지는 걸 확인해 보세요.
Now press each of H's two answers below, and see the contradiction detonate no matter which one you choose.
⚙ 청개구리 기계에 자기 자신을 넣기⚙ Feed the contrarian machine itself
양쪽 다 막다른 골목Both roads are dead ends
C(C)를 실행하면 두 갈래뿐인데, 둘 다 자기모순입니다.
Running C(C) leaves only two branches, and both contradict themselves:
- H가 “C(C)는 멈춘다”고 판정하면 → C는 청개구리라 무한 루프에 빠집니다. 그런데 그럼 실제로는 안 멈췄죠. H가 틀렸습니다.
- If H says “C(C) halts” → C, being contrarian, loops forever. But then it did not halt. So H was wrong.
- H가 “C(C)는 무한 루프”라 판정하면 → C는 반대로 멈춥니다. 그런데 그럼 실제로는 멈췄죠. 역시 H가 틀렸습니다.
- If H says “C(C) loops forever” → C does the opposite and halts. But then it did halt. Again H was wrong.
즉 C(C)는 멈추는 동시에 안 멈추는 프로그램이어야 합니다. 이건 불가능한 문장이죠.
In other words C(C) would have to be a program that halts and does not halt at the same time. That is an impossible statement:
우리가 한 가정은 딱 하나, "완벽한 판정기 H가 존재한다"였습니다. 그 가정에서 모순이 나왔으니, 잘못된 것은 가정입니다. 따라서 H는 존재할 수 없습니다. 정지 문제는 결정 불가능(undecidable)합니다. 어렵다는 게 아니라, 원리적으로 불가능하다는 뜻입니다.
We made exactly one assumption: that a perfect decider H exists. It led to a contradiction, so the assumption is what fails. Therefore H cannot exist. The halting problem is undecidable, not merely hard, but provably impossible.
야생의 정지 문제The halting problem in the wild
추상적인 이야기 같지만, 이 벽은 아주 현실적입니다. 이미 콜라츠 추측을 아신다면, 그게 바로 야생의 정지 문제입니다. "짝수는 반, 홀수는 3배+1" 규칙을 도는 이 짧은 프로그램이 모든 수에서 결국 멈추는가? 수학자들이 80년 넘게 매달렸지만 아무도 모릅니다. 단 몇 줄짜리 프로그램의 정지 여부조차 이렇게 어렵습니다.
It sounds abstract, but this wall is very real. If you already know the Collatz conjecture, that is the halting problem in the wild. Does this tiny program ("halve if even, 3n+1 if odd") eventually stop for every starting number? Mathematicians have chased it for over eighty years and nobody knows. Even a few lines of code can hide an unanswerable halting question.
정지 문제의 그림자는 더 넓게 퍼집니다. 라이스 정리는 한 걸음 더 나아가, 프로그램이 무엇을 하는지에 관한 흥미로운 성질은 무엇이든 일반적으로 판정할 수 없다고 말합니다. 그래서 모든 악성코드를 완벽히 걸러내는 백신도, 모든 버그를 빠짐없이 찾는 검사기도, 모든 프로그램을 최적으로 만드는 컴파일러도 원리적으로 불가능합니다. 현실의 도구들은 이 한계를 알기에, "완벽" 대신 근사와 어림으로 우회합니다.
The shadow spreads wider. Rice's theorem goes further: any interesting property of what a program does is, in general, undecidable. So a virus scanner that catches all malware, a bug checker that finds every bug, and a compiler that optimizes every program perfectly are all impossible in principle. Real tools know this limit, so instead of "perfect" they settle for approximations and good-enough heuristics.