https://namu.wiki/w/%EC%A0%95%EC%A7%80%20%EB%AC%B8%EC%A0%9C

정지 문제, 또는 Halting Problem으로 불리는 판정 문제의 한 갈래로 "유한한 수의 단계 후에 주어진 프로그램이 해결하고자 하는 문제가 해결되는지 우리에게 미리 말해줄 수 있는 어떠한 알고리즘이 존재하는가?" 라는 질문이다. 다르게 말하자면 튜링머신에 1개의 프로그램과 Input자료 1개를 넣으면서 "야 너 이게 유한한 단계 후에 답이 나올지 나에게 풀어보기 전에 미리 알려줄 수 있어?" 라는 질문을 할 때 이를 해결해줄 수 있는 특정한 단일 프로그램이 있는가가 정지 문제이다. (나무위키 중)

정지문제(halting problem)라는 이름이 좀 요상해서, 저도 이게 뭘 의미하는지 크게 관심이 없었다가, 마흐의 물통을 설명하려는 시도와 튜링의 정지문제가 정확히 같은 문제라는 점에 착안해서 설명을 좀 해보고자 합니다. 

정지한다는 표현이 동사이므로 동사에 관심을 둔 튜링도 이 문제의 본질에 다가가지 못했다고 할 수 있습니다. 대신 괴델의 불완전성 정리라는 표현이 낫습니다. 그가 관찰한 것이 동사라면 계 내부를 본 것이고, 계 내부에서 인자간 상호작용의 유한성을 확인하려 하므로 실패합니다. 

무슨 말이냐, 어떤 둘의 상호작용이 유한한지를 결정하는 것은 그 둘로는 설명 불가능하다는 거죠. 이는 게임이론으로도 설명할 수 있습니다. 게임이론에서 두 죄수만으로 최적의 전략을 설명하려고 한다면 두 죄수의 상호작용 혹은 연산은 끝이 나지 않습니다. 니가 그렇게 하면 나는 이렇게 한다가 서로에게 적용되는 거죠. 

부동산 시장에서의 전략도 같습니다. 정부가 민간 업자들과 같은 링에서 서로 멱살잡이 하고 있으면 답이 안 나옵니다. 이 경우엔 정부가 자기 포지션을 망각한 거죠. 심판이 될 수 있는 자가 선수로 뛰면 망하는 겁니다. 링 안에서는 답이 안나옵니다. 서로 자기가 맞다고 우기다가 밤샙니다. 서로 꼬리물기 하다가 빙글빙글. TV토론을 보면 자주 관찰하는 겁니다. 서로 인정을 안 하죠. 

문제를 풀기 전에 그 문제에 답이 있다는 사실을 알 수 있을까요?

당연히 알 수 있습니다. 모든 문제엔 답이 있다고 하잖아요. 문제에 답이 있는 이유는 문제와 답이 규칙에 의해 짝지어져있기 때문입니다. 이런식의 사고는 제논의 역설과도 닿아있죠. 이때 규칙은 외부에 있습니다. 반면 내부에는 선수만 있죠. 문제는 우리의 관심이 내부에 꽂혀있다는 겁니다. 내부만으로 완전하길 바라므로 답이 안 나옵니다. 그게 아니라니깐.

정지하냐는 말은 유한하냐로 바꿔쓸 수 있습니다. 유한하다는 것은 디지털이냐를 묻는 거고, 디지털이냐는 말은 외부가 있냐는 겁니다. 외부가 없으면 디지털이 될 수 없습니다. 지들끼리는 무한합니다. 컴퓨터이론에서 무한은 무서운 존재입니다. 왜냐하면 연산이 끝이 안 나면 컴퓨터가 퍼지거든요. 재귀문제로도 설명하곤 합니다.

끝이 없는 재귀문제를 멈추려면 규칙을 정해야 합니다. 실제로 프로그래밍에서 규칙을 정하기는 합니다. 그러면 문제 없는 거 아냐? 라고 생각하지만, 문제가 여전합니다. 정지 규칙을 정하는 그것을 분명하게 규정하지 않았거든요. 그것이 외부인지 내부인지를 말하지 않았다는 거죠. 절차지향과 객체지향 모두 내부만을 바라보는 한계가 있습니다. 주체지향이라는 것은 상대적인 외부를 정의하여 프로그래밍의 존재를 인간과 연결합니다.

for문에 대해 의심한 적이 있나요? 보통 반복문으로 이해하고 설명하는데, 망하는 설명이죠. 프로그래밍은 기본적으로 정지하지 않는 엔진입니다. 문제를 주면 끝없이 쪼개고 반복합니다. 그러므로 정지 규칙을 정해줘야 하는데, 그게 for입니다. 왜냐하면 for는 범위 또는 한계를 나타내기 때문입니다. 

범위를 정해주는게 곧 규칙이 되는 거죠. 프로그래밍 자체를 방정식으로 표현해야 하며, 내부와 외부를 상대적으로, 또 연쇄적으로 표현해야 합니다. https://private.tistory.com/43 AOP라고 해서 관점지향 프로그래밍이 있긴 한데, 정작 이걸 만든 사람도 본질을 때리지 못하고 기능적인 구현에만 머무르고 있습니다.