정지 문제 (Halting Problem)

한 줄 정의: 임의의 프로그램이 언젠가 멈출지 영원히 계속될지를 모든 경우에 대해 판별해주는 알고리즘은 존재할 수 없다는 이론적 결론입니다.

쉽게 풀면

"이 프로그램 코드를 보기만 하고, 실행해보지 않고도 언젠가 멈추는지 아니면 무한히 반복하는지 미리 알려주는 만능 검사기를 만들 수 있을까?"라는 질문이 정지 문제입니다. 앨런 튜링은 1936년에 그런 만능 검사기는 절대로 만들 수 없다는 것을 수학적으로 증명했습니다. 간단한 프로그램 몇 개는 코드만 보고도 멈출지 알 수 있지만, "모든" 프로그램에 대해 항상 정확히 판별하는 방법은 근본적으로 존재하지 않는다는 뜻입니다. 이는 컴퓨터 성능이 부족해서가 아니라, 논리적으로 불가능하다는 한계를 보여주는 결과입니다.

왜 중요한가

정지 문제는 계산이론에서 "컴퓨터로 원리적으로 풀 수 없는 문제가 존재한다"는 사실을 보여준 최초의 사례이기 때문에, 결정 불가능성을 다루는 이후의 거의 모든 이론적 결과가 이 개념을 기준점으로 삼습니다. 소프트웨어 검증, 정적 분석, 컴파일러 최적화처럼 프로그램의 동작을 자동으로 판단하려는 실무 분야에서도, 완벽한 도구를 만들 수 없는 근본적인 이유를 설명할 때 정지 문제가 자주 인용됩니다.

논문에서는 이렇게 쓰입니다

"정적 분석 도구가 무한 루프를 완벽하게 탐지하지 못하는 것은 정지 문제(halting problem)의 결정 불가능성(undecidability)에서 비롯된 근본적 한계이다."

이 문장은 "코드 분석 도구가 아무리 정교해져도, 모든 무한 루프를 빠짐없이 찾아내는 것은 도구의 완성도 문제가 아니라 이론적으로 불가능한 일"이라는 뜻입니다.

"제안된 타입 시스템은 완전한 프로그램 종료성 판별이 정지 문제로 환원되어 결정 불가능함을 인지하고, 대신 보수적으로 종료를 보장하는 부분집합만을 허용하도록 설계되었다."

프로그래밍 언어 이론 논문에서는 완벽한 판별이 불가능하다는 사실을 인정한 뒤, 그 대신 안전하게 확인 가능한 더 좁은 범위만 다루도록 시스템을 설계했다는 뜻으로 쓰입니다.

"본 연구에서 다룬 스케줄링 문제의 결정 불가능성은 정지 문제로부터의 환원(reduction)을 통해 증명된다."

이론전산학 논문에서는 새로운 문제가 풀 수 없음을 보이기 위해, 그 문제를 풀 수 있다면 정지 문제도 풀 수 있게 된다는 논리로 환원 증명을 구성하는 경우가 흔합니다.

조금 더 깊게 보면

정지 문제가 풀릴 수 없다는 증명은 흔히 대각선 논법을 이용하는데, 만약 정지 여부를 항상 정확히 판별하는 프로그램이 존재한다고 가정하면 자기 자신에게 모순되는 동작을 하는 프로그램을 만들 수 있음을 보여 귀류법으로 결론을 이끌어냅니다. 이 개념은 이후 다른 문제가 풀 수 없음을 보이는 표준적인 방법인 "환원(reduction)"의 출발점이 되었으며, 많은 결정 불가능성 증명이 "이 문제를 풀 수 있다면 정지 문제도 풀 수 있다"는 논리 구조를 따릅니다. 다만 결정 불가능성은 "모든 프로그램에 대해 항상 정확한 하나의 알고리즘이 없다"는 뜻이지, 개별 프로그램 하나하나를 분석하는 것 자체가 불가능하다는 뜻은 아닙니다.

주의할 점

정지 문제가 "결정 불가능(undecidable)"하다는 것은 "특정 프로그램이 멈추는지 확인할 수 없다"는 뜻이 아닙니다. 개별 프로그램은 대부분 분석해서 답을 낼 수 있습니다. 불가능한 것은 "어떤 프로그램을 넣어도 항상 정확하게 답하는 하나의 범용 알고리즘"을 만드는 일입니다. 이 개념은 계산 모델의 한계를 정의하는 튜링 기계 이론과 함께 이해하면 좋습니다.