# 정지 문제(Halting Problem)의 증명

## 1. 정지 문제란 무엇인가?
정지 문제(Halting Problem)는 앨런 튜링이 1936년 증명한 것으로, 다음과 같은 질문입니다.

> **"어떤 컴퓨터 프로그램과 그 프로그램에 줄 입력값이 주어졌을 때, 이 프로그램이 영원히 실행될지 아니면 언젠가 멈출지를 판별할 수 있는 만능 알고리즘이 존재하는가?"**

튜링은 **"그런 알고리즘은 존재할 수 없다"**는 것을 귀류법(Proof by Contradiction)을 통해 증명했습니다.

## 2. 증명 과정 (귀류법)

### 가정도입
우선, 정지 문제를 완벽하게 해결할 수 있는 가상의 기계(함수)가 **존재한다고 가정**해 봅시다. 이 기계를 `H`라고 부르겠습니다.

기계 `H`는 두 개의 입력을 받습니다:
1.  프로그램 코드 `P`
2.  그 프로그램에 넣을 입력값 `I`

`H(P, I)`의 작동 방식:
*   만약 `P`가 입력 `I`에 대해 실행되다가 멈춘다면(Halt) -> "멈춤(True)"을 출력.
*   만약 `P`가 입력 `I`에 대해 영원히 실행된다면(Infinite Loop) -> "안 멈춤(False)"을 출력.

즉, `H`는 어떤 프로그램이든 멈추는지 안 멈추는지 정확히 판별합니다.

### 모순을 일으키는 기계 'D' 제작
이제 `H`를 이용해서, 자신을 입력으로 받아 기괴하게 행동하는 새로운 기계(프로그램) `D`를 만듭니다.

기계 `D`는 하나의 입력(프로그램 코드 `P`)만 받습니다. 그리고 내부적으로 `H(P, P)`를 실행하여 결과를 확인합니다.

`D(P)`의 작동 알고리즘:
1.  `H(P, P)`를 실행합니다. (즉, 프로그램 `P`에 자기 자신인 `P`를 입력으로 줬을 때 멈추는지 확인합니다.)
2.  만약 `H(P, P)`가 "멈춤"이라고 답하면 -> `D`는 무한 루프에 빠집니다 (영원히 실행).
3.  만약 `H(P, P)`가 "안 멈춤"이라고 답하면 -> `D`는 바로 멈춥니다.

즉, `D`는 `H`의 예측과 반대로 행동하도록 설계되었습니다.

### 결정적 모순 (The Paradox)
이제 결정적인 질문을 던집니다.

> **"기계 `D`에 자기 자신인 `D`를 입력으로 주면 (`D(D)`를 실행하면) 어떻게 될까?"**

이 경우 `H(D, D)`가 판별을 시도합니다.

**경우 1: `H(D, D)`가 "멈춤"이라고 판별한다면?**
*   `H`는 `D`가 멈출 것이라고 예측했습니다.
*   하지만 `D`의 설계(알고리즘 2번)에 따라, `H`가 "멈춤"이라고 하면 `D`는 **무한 루프(안 멈춤)**에 빠집니다.
*   모순 발생: `H`는 멈춘다고 했지만, 실제 `D`는 안 멈춥니다. (`H`가 틀림)

**경우 2: `H(D, D)`가 "안 멈춤"이라고 판별한다면?**
*   `H`는 `D`가 안 멈출 것이라고 예측했습니다.
*   하지만 `D`의 설계(알고리즘 3번)에 따라, `H`가 "안 멈춤"이라고 하면 `D`는 **바로 멈춥니다.**
*   모순 발생: `H`는 안 멈춘다고 했지만, 실제 `D`는 멈춥니다. (`H`가 틀림)

## 3. 코드 예시 (Pseudo-code)
증명 과정을 이해하기 쉽도록 파이썬 스타일의 의사 코드로 표현해 보겠습니다.

```python
# 가상의 만능 판별 함수 H
def H(program, input_data):
    if program(input_data) stops:
        return True  # 멈춤
    else:
        return False # 안 멈춤 (무한 루프)

# 모순을 만들기 위해 설계된 기계 D
def D(P):
    # 1. 프로그램 P를 자기 자신(P)에게 입력으로 줬을 때의 결과를 H에게 물어봄
    result = H(P, P) 
    
    # 2. H의 결과와 정반대로 행동함
    if result == True:  # H가 "P는 멈춘다"고 하면
        while True:     # D는 일부러 무한 루프를 돕니다.
            pass
    else:               # H가 "P는 안 멈춘다"고 하면
        return          # D는 바로 멈춥니다.
```

이제 `D(D)`를 실행하는 상황을 코드로 보면 모순이 명확해집니다.

```python
# D(D) 실행 시 벌어지는 일 (= Paradox)
def D(D):
    result = H(D, D) # H에게 D가 D를 입력받으면 멈추는지 물어봄
    
    if result == True: # H가 "멈출 거야"라고 예측했다면
        while True:    # 실제 D는 무한 루프에 빠짐 (H의 예측 틀림!)
            pass
    else:              # H가 "안 멈출 거야"라고 예측했다면
        return         # 실제 D는 바로 멈춤 (H의 예측 틀림!)
```

## 4. 결론
어떤 경우(멈춤 또는 안 멈춤)를 가정하더라도, 기계 `H`의 판별은 항상 틀리게 됩니다.

따라서 "모든 프로그램의 정지 여부를 판별할 수 있는 만능 기계 `H`는 존재할 수 없다"는 결론에 도달합니다. 이것이 정지 문제가 '결정 불가능(Undecidable)'하다는 튜링의 증명입니다.