💻 computer science

A Constructive Proof of Rice's Theorem and the Halting Problem via Hilbert's Tenth Problem

이 논문은 배중률이나 대각선 논법 없이 힐베르트 제 10 문제의 비결정성을 가정하여 리스 정리와 정지 문제를 구성적 방식으로 증명하고, 이를 Rocq 증명 보조기를 통해 형식화한 내용을 담고 있습니다.

원저자: Jonathan Brossard

게시일 2026-04-21

📖 4 분 읽기☕ 가벼운 읽기

원저자: Jonathan Brossard

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

이 논문은 컴퓨터 과학의 두 가지 거대한 '불가능'을 증명하는 새로운 방법을 제시합니다. 바로 **리스 정리 (Rice's Theorem)**와 **정지 문제 (Halting Problem)**입니다.

기존의 증명들은 마치 "거울을 비추고, 스스로를 공격하는" 복잡한 논리 (자기 참조와 배중률) 를 사용했지만, 이 논문은 **힐베르트 10 번 문제 (Hilbert's Tenth Problem)**라는 수학적 난제를 이용해 훨씬 더 직관적이고 깔끔하게 증명합니다.

이 복잡한 내용을 일상적인 언어와 비유로 쉽게 설명해 드리겠습니다.

1. 핵심 질문: "프로그램의 성격을 알 수 있을까?"

컴퓨터 프로그램은 수많은 일을 합니다. 어떤 프로그램은 멈추고 (정지), 어떤 프로그램은 영원히 돌아갑니다 (무한 루프).
리스 정리는 이렇게 말합니다:

"프로그램이 어떤 '의미 있는 성질' (예: 멈추는가, 버그가 있는가, 특정 숫자를 계산하는가) 을 갖는지, 모든 프로그램에 대해 100% 정확하게 판단하는 기계는 존재할 수 없다."

기존의 증명들은 "만약 그런 기계가 있다면, 내가 그 기계에게 '네가 멈출지 말지'라고 물어보면 모순이 생긴다"는 식의 **자기 파괴적인 논리 (자기 참조)**를 썼습니다. 마치 "이 문장은 거짓이다"라고 말하며 스스로를 무너뜨리는 것과 비슷합니다.

하지만 이 논문은 그런 복잡한 함정을 피합니다.

2. 새로운 방법: "두 개의 쌍둥이 프로그램"

저자는 힐베르트 10 번 문제라는 '수학적 열쇠'를 사용합니다.

힐베르트 10 번 문제: "방정식 $x^2 + y^2 = z^2 + 1$ 같은 식에 정수 해가 있는지를 판단하는 기계는 존재하지 않는다"는 유명한 문제입니다.

저자는 이 문제를 이용해 다음과 같은 두 단계의 마술을 부립니다.

단계 1: 두 명의 '감시자'를 세우다

어떤 프로그램의 성질 (예: '멈추는가?') 을 판단하는 기계가 있다고 가정해 봅시다. 저자는 이 기계에게 속아넘어갈 수 있는 **두 개의 프로그램 ( $S_0$ 와 $S_1$ )**을 만듭니다.

이 두 프로그램은 **수학적 방정식 (Diophantine polynomial)**을 풀고 있습니다.

상황 A: 방정식에 해가 있을 때
- $S_0$ 는 "절대 멈추지 않는 프로그램"처럼 행동합니다.
- $S_1$ 는 "반드시 멈추는 프로그램"처럼 행동합니다.
- → 감시자 기계는 두 프로그램이 다르다는 것을 알 수 있습니다. ( $S_1$ 는 멈춤, $S_0$ 는 멈춤 안 함)
상황 B: 방정식에 해가 없을 때
- $S_0$ 와 $S_1$ 는 둘 다 영원히 멈추지 않는 프로그램이 됩니다.
- → 감시자 기계는 두 프로그램이 완전히 똑같다고 판단합니다. (어떤 성질을 갖든, 둘 다 '멈추지 않음'이니까요.)

단계 2: 감시자의 함정

이제 감시자 기계가 두 프로그램의 결과를 비교해 봅니다.

만약 방정식에 해가 있다면 $\rightarrow$ 감시자는 두 프로그램이 다르다고 말합니다.
만약 방정식에 해가 없다면 $\rightarrow$ 감시자는 두 프로그램이 같다고 말합니다.

여기가 핵심입니다!
감시자 기계가 두 프로그램의 차이를 알아내는 순간, 우리는 방정식에 해가 있는지 없는지를 알게 됩니다.
하지만 힐베르트 10 번 문제는 "방정식 해를 찾는 기계는 존재할 수 없다"고 이미 증명했습니다.
따라서, 방정식 해를 찾아내는 감시자 기계는 존재할 수 없습니다.
결국, 프로그램의 성질을 판단하는 기계도 존재할 수 없다는 결론이 나옵니다.

3. 왜 이 방법이 특별한가요? (구체적인 비유)

기존의 증명 (자기 참조) 은 다음과 같은 비유로 설명할 수 있습니다:

"나를 죽일 수 있는 총을 만들어라. 만약 네가 나를 죽인다면, 나는 살아있어야 하고, 살아있다면 너는 나를 죽일 수 없어야 한다."
(이건 너무 복잡하고, '죽음과 생명'을 동시에 가정하는 모순을 만들어냅니다.)

이 논문의 증명 (두 가지 증인) 은 다음과 같습니다:

"방정식 해가 있는지 없는지 알려주는 기계가 있다고 치자. 나는 그 기계에게 '이 두 개의 상자 중 하나가 해를 품고 있느냐'고 묻는다.
만약 해가 있다면, 상자는 다르게 변한다. 해가 없다면, 두 상자는 똑같이 비어있다.
기계가 상자를 구별할 수 있다면, 결국 방정식 해를 찾은 셈이다.
하지만 방정식 해를 찾는 기계는 불가능하다. 그러니 상자를 구별하는 기계도 불가능하다."

이 방법은 **자기 자신을 공격하는 것 (자기 참조)**을 전혀 쓰지 않습니다. 대신 **수학적인 문제 (방정식)**를 이용해 외부에서부터 논리를 밀어붙입니다.

4. 이 연구의 의미: "왜 중요한가?"

논리의 순수성: 이 증명 과정은 '거짓말'이나 '모순'을 가정하는 복잡한 논리 (배중률) 를 쓰지 않습니다. 순수한 논리 (직관적 논리) 만으로 증명했습니다. 이는 컴퓨터가 직접 검증할 수 있는 '신뢰할 수 있는 증명'입니다.
실용성: 이 증명 방식은 컴퓨터 프로그램이 실제로 어떻게 작동하는지 (단계별 실행) 를 더 잘 반영합니다.
정지 문제의 새로운 시각: 우리가 알고 있는 '프로그램이 멈출지 말지'를 판단할 수 없다는 사실 (정지 문제) 이, 사실은 더 근본적인 '수학적 방정식 풀기'의 불가능성에서 비롯된다는 것을 보여줍니다.

요약

이 논문은 **"프로그램의 성질을 판단하는 기계는 없다"**는 사실을 증명할 때, 복잡한 자기 파괴 논리 대신, '방정식 해 찾기'라는 수학적 난제를 이용했다는 점에 의의가 있습니다.

마치 **"어떤 문이 열려 있는지 알 수 있는 열쇠는 없다"**는 것을 증명하기 위해, **"그 문이 열려 있다면 이 두 개의 문이 다르게 보이고, 닫혀 있다면 똑같이 보인다"**는 사실을 이용해, 결국 그 문이 열려 있는지 닫혀 있는지 알 수 없는 수학적 사실로 증명해낸 것과 같습니다.

이것은 컴퓨터 과학의 한계를 수학적으로, 그리고 더 깔끔하게 규명한 멋진 업적입니다.

이 논문은 **리스의 정리 (Rice's Theorem)**와 **정지 문제 (Halting Problem)**에 대한 구현적 (Constructive) 증명을 제시하며, 기존의 고전적 증명 방식에서 필수적으로 사용되던 배중률 (Law of Excluded Middle, LEM) 과 자기 참조 (Self-reference) 를 배제했습니다. 저자는 힐베르트의 제 10 문제 (Hilbert's Tenth Problem, MRDP 정리) 의 결정 불가능성을 기반으로 한 새로운 증명을 제안했습니다.

주요 내용을 한국어로 상세히 요약하면 다음과 같습니다.

1. 문제 제기 (Problem)

리스의 정리: 프로그램의 비자명한 (non-trivial) 의미론적 속성 (semantic property) 은 결정 불가능하다.
기존 증명의 한계:
- 고전적 증명들은 주로 정지 문제로부터의 환원 (reduction) 을 사용하며, 이 과정에서 **배중률 (LEM)**을 두 번 사용합니다.
  1. 대각선 논법 (Diagonalization): 가상의 프로그램을 구성할 때, 그 프로그램이 멈추는지 멈추지 않는지 (halts or diverges) 를 가정합니다.
  2. 케이스 분할 (Case Split): 항상 발산하는 프로그램 $\bot$ 이 주어진 속성 $P$ 를 만족하는지 ( $P(\bot)$ ) 여부를 판단하기 위해 $P(\bot) \lor \neg P(\bot)$ 를 가정합니다.
- 이러한 논리 구조는 **직관주의 논리 (Intuitionistic Logic)**나 **형식적 검증 시스템 (Coq, Agda 등)**에서 직접 실행되거나 추출 (extraction) 될 수 없습니다.
목표: LEM, 대각선 논법, 자기 참조 없이, 그리고 $P(\bot)$ 의 값을 알지 못한 채 리스의 정리를 직관주의 논리 내에서 증명하는 것.

2. 방법론 (Methodology)

저자는 정지 문제가 아닌 **힐베르트의 제 10 문제 (Diophantine equations의 해 존재 여부)**로부터 직접 환원하는 이중 증관자 (Two-Witness) 구성을 제안했습니다.

핵심 아이디어: 이중 증관자 (Two-Witness Construction)
- 주어진 비자명한 속성 $P$ 에 대해, $P$ 를 만족하는 프로그램 $e_1$ 과 만족하지 않는 프로그램 $e_0$ 가 존재한다고 가정합니다.
- 임의의 디오판토스 다항식 $D$ $D$ 에 대해 두 개의 프로그램 $S^0_D$ $S_{D}^{0}$ 와 $S^1_D$ $S_{D}^{1}$ 를 구성합니다.
  - $D$ 가 해를 가질 경우: $S^0_D$ 는 $e_0$ 처럼 행동하고, $S^1_D$ 는 $e_1$ 처럼 행동합니다.
  - $D$ 가 해를 가지지 않을 경우: 두 프로그램 모두 모든 입력에서 발산 ( $\bot$ ) 하여 서로 관찰적으로 동등해집니다 ( $S^0_D \simeq S^1_D \simeq \bot$ ).
- 결정기 (Decider) 의 모순 유도:
  - 만약 $P$ 를 결정하는 프로그램 $Decide_P$ 가 존재한다고 가정하면, $D$ 의 해 존재 여부를 $S^0_D$ 와 $S^1_D$ 에 대한 $Decide_P$ 의 결과 차이 $\delta_D = Decide_P(S^1_D) - Decide_P(S^0_D)$ 로 판단할 수 있습니다.
  - $D$ 가 해를 가지면 $\delta_D = 1$ , 해를 가지지 않으면 $\delta_D = 0$ 이 됩니다.
  - 이는 디오판토스 방정식의 해 존재 여부를 결정하는 알고리즘이 존재함을 의미하며, 이는 **MRDP 정리 (힐베르트 제 10 문제의 결정 불가능성)**와 모순입니다.
구현적 특징:
- LEM 배제: "해가 있다 또는 없다"는 이분법적 진술 대신, "해가 있으면 $\delta_D=1$ "과 "해가 없으면 $\delta_D=0$ "이라는 두 개의 분리된 함의 (implication) 로 구성됩니다.
- $P(\bot)$ 불필요: $D$ 가 해를 가지지 않을 때 두 프로그램이 모두 발산하므로, $P(\bot)$ 의 진리값을 알지 못해도 $P(S^0_D) \iff P(S^1_D)$ 가 성립함을 관찰적 동등성 (observational equivalence) 으로 증명할 수 있습니다.
- 자기 참조 부재: 고정점 정리 (Recursion Theorem) 나 $s-1-1$ 정리를 사용하지 않고, 다항식 $D$ 와 비트 $b$ 만으로 프로그램을 명시적으로 구성합니다.

3. 주요 기여 (Key Contributions)

구현적 리스 정리 증명: 직관주의 논리에서 유효하며, MRDP 정리의 결정 불가능성 가정을 제외하고는 고전적 논리를 전혀 사용하지 않는 최초의 증명 중 하나입니다.
대각선 논법 및 자기 참조 제거: 정지 문제의 고전적 증명에 필수적이었던 자기 참조와 대각선 논법을 완전히 제거했습니다.
Rocq (Coq) 형식화: 논문의 모든 증명을 Rocq (Coq) 증명 보조기를 사용하여 형식화했습니다.
- **단계 인덱싱 모델 (Step-indexed model)**을 사용하여 부분 함수의 동등성을 정의했습니다.
- 외부 공리 (Axiom) 는 힐베르트 제 10 문제의 결정 불가능성 (H10C_SAT_undec) 하나만 사용하며, 이는 Larchey-Wendling과 Forster의 기존 형식화에서 가져온 것입니다.
- Print Assumptions 명령어로 확인했을 때, 리스 정리와 정지 문제 정리는 전역 문맥 하에 닫혀 있어 (Closed under global context) 추가적인 고전적 공리가 필요 없음을 입증했습니다.
정지 문제의 유도: 리스 정리의 정지 문제 (Terminates) 에 대한 인스턴스화를 통해 정지 문제의 결정 불가능성을 한 줄의 코드로 유도했습니다. 이는 기존에 정지 문제를 공리로 두고 다른 정리를 유도하던 방식과 반대로, MRDP $\to$ 리스 $\to$ 정지 문제 순서로 유도됩니다.

4. 결과 (Results)

정리 5.1 (리스의 정리, 구현적 버전): 비자명한 의미론적 속성 $P$ 를 결정하는 프로그램은 존재하지 않습니다.
부록 A (정리 6.4, 정지 문제): 프로그램이 입력 0 에서 멈추는지 여부를 결정하는 알고리즘은 존재하지 않습니다.
형식화 검증: 1,919 줄의 Rocq 코드가 0 개의 허용된 목표 (admitted goals) 와 0 개의 고전적 공리로 성공적으로 컴파일되었습니다.
실용적 예시: 논문의 부록에는 이 구성을 C 언어로 구현한 undecidable.c가 포함되어 있으며, 이는 정수론의 미해결 문제 (세 개의 세제곱수의 합) 와 관련된 프로그램의 종료 여부를 결정할 수 없음을 보여줍니다.

5. 의의 (Significance)

계산적 내용 (Computational Content): 고전적 증명은 계산적 내용을 담지 못하지만, 이 구현적 증명은 프로그램 추출 (program extraction) 이 가능한 형태로 undecidability 논증을 제공합니다. 이는 형식적 검증 시스템 내에서 결정 불가능성을 내부화하는 데 기여합니다.
구현적 역수학 (Constructive Reverse Mathematics): 각 정리가 어떤 비구현적 원리 (LEM 등) 에 의존하는지를 정확히 규명하는 데 기여합니다.
구조적 통찰: 단일 프로그램의 케이스 분할이 아닌, 두 프로그램 간의 관계적 차이 ( $\delta_D$ ) 를 통해 정보를 인코딩하는 비분기 환원 (non-branching reduction) 구조를 제시했습니다.
학술적 영향: 기존 Coq 라이브러리 (coq-library-undecidability) 와의 호환성을 유지하면서, 고전적 논리 없이도 강력한 정지 불가능성 결과를 도출할 수 있음을 보여주었습니다.

요약하자면, 이 논문은 힐베르트 제 10 문제를 새로운 기저로 삼아, LEM 과 자기 참조 없이 리스 정리와 정지 문제를 구현적으로 증명하고 이를 형식적으로 검증했다는 점에서 계산 이론과 형식적 방법론 분야에서 중요한 이정표가 됩니다.