# [08-07] 계산 불가능성 (Undecidability)

계산 불가능성은 컴퓨터로 절대 풀 수 없는 문제들이 존재한다는 놀라운 사실을 다룹니다.

---

🎯 계산 불가능성이란 무엇인가

계산 불가능성의 정의

계산 불가능(Undecidable)한 문제는 어떤 알고리즘으로도 모든 입력에 대해 올바르게 판단할 수 없는 문제입니다.

쉬운 비유:

마법의 수정구슬로 비유:

가능한 질문: "내일 비가 올까?" → 일기예보로 예측 가능 (완벽하지 않지만)

불가능한 질문: "이 프로그램은 언제까지 실행될까?" → 절대 정확히 알 수 없음! → 수정구슬도 못 봄 → 컴퓨터도 못 봄

중요한 구분:

어려운 문제 (NP-완전):
- 시간이 오래 걸림
- 하지만 원칙적으로는 풀 수 있음
- 예: 외판원 문제 (느리지만 정확한 답 가능)

불가능한 문제 (계산 불가능):
- 아무리 시간을 줘도 풀지 못함
- 원칙적으로 풀 수 없음
- 예: 정지 문제 (어떤 방법으로도 불가능)

차이:
NP-완전 = 느림
계산 불가능 = 절대 불가능

---

🚫 왜 불가능한 문제가 존재하는가?

컴퓨터의 근본적 한계

핵심 이유:

프로그램은 자기 자신에 대해 완벽히 분석할 수 없습니다. 이것이 튜링이 발견한 컴퓨터의 근본적 한계입니다.

거울 비유:

상황: 거울로 자기 눈을 보려고 함

문제:
- 왼쪽 눈으로 왼쪽 눈을 볼 수 없음
- 거울에 비친 눈을 보지만, 그건 "직접" 보는 게 아님

프로그램도 마찬가지:
- 프로그램 A가 프로그램 B를 분석: 가능
- 프로그램 A가 자기 자신을 완벽히 분석: 불가능

간단한 예시: 출력 예측 문제

def predict_output_problem():
    """
    출력 예측 문제
    
    문제: 프로그램과 입력이 주어졌을 때, "이 프로그램이 'Hello'를 출력할까?"
    
    왜 불가능한가?
    프로그램이 자기 자신을 분석하려 하면 무한 재귀에 빠짐
    """
    
    # 가상의 예측기가 있다고 가정
    def will_print_hello(program, input_data):
        """
        program이 input_data에 대해 "Hello"를 출력하는지 예측
        
        이런 함수가 존재한다면?
        """
        # 마법처럼 예측한다고 가정
        pass
    
    # 역설 만들기
    def paradox_program(x):
        """
        역설을 만드는 프로그램
        
        논리:
        1. will_print_hello가 "출력한다"고 예측하면 → 출력하지 않음
        2. will_print_hello가 "출력 안 한다"고 예측하면 → 출력함
        
        결과: will_print_hello는 항상 틀림!
        """
        if will_print_hello(paradox_program, x):
            # 예측이 "출력한다"면 출력하지 않기
            return  # 아무것도 출력 안함
        else:
            # 예측이 "출력 안 한다"면 출력하기
            print("Hello")
    
    # will_print_hello(paradox_program, None)을 실행하면?
    # - Yes 답하면: 실제로는 출력 안 함 → 틀림
    # - No 답하면: 실제로는 출력함 → 틀림
    # 
    # 결론: will_print_hello는 존재할 수 없음!

# 이것이 계산 불가능성의 핵심!
# 프로그램이 자기 자신에 대해 완벽히 예측할 수 없음

왜 이런 일이 발생하는가?

프로그램이 자기 자신을 입력으로 받을 수 있기 때문입니다. 이것이 "자기 참조(self-reference)"를 만들고, 자기 참조는 역설을 만듭니다.

유명한 역설: "이 문장은 거짓이다" → 참이면 거짓, 거짓이면 참 → 모순!

프로그램도 마찬가지:
프로그램이 자기 자신에 대해 예측하면
→ 예측에 따라 행동을 바꿀 수 있음
→ 예측이 항상 틀리게 만들 수 있음
→ 완벽한 예측 불가능!

---

📋 계산 불가능한 문제들

예시 1: 프로그램 동치 문제 (Program Equivalence Problem)

• 프로그램 동치 문제 : 두 개의 서로 다른 프로그램(또는 알고리즘)이 모든 가능한 입력에 대해 동일한 출력(결과)을 내놓는지 판별하는 문제

문제:

두 프로그램이 주어졌을 때, "이 두 프로그램은 같은 일을 하는가?"

예:
프로그램 A:
def sum_array_A(arr):
    total = 0
    for x in arr:
        total += x
    return total

프로그램 B:
def sum_array_B(arr):
    return sum(arr)

질문: A와 B는 동치인가?
→ 사람은 "같다"고 알 수 있음
→ 하지만 일반적으로 컴퓨터는 판단 못함!

왜 불가능한가?

def program_equivalence_impossible():
    """
    프로그램 동치 문제가 왜 불가능한가?
    
    이유:
    두 프로그램이 "같다"는 것을 증명하려면 모든 가능한 입력에 대해 결과가 같아야 함
    
    문제:
    1. 입력이 무한할 수 있음
    2. 프로그램이 무한 루프일 수 있음
    3. 프로그램의 행동이 복잡할 수 있음
    
    결과:
    모든 경우를 확인할 수 없음!
    """
    
    # 예: 이 두 프로그램이 같은가?
    def program1(n):
        """
        콜라츠 추측 검증
        모든 n에 대해 1에 도달하면 True
        """
        while n != 1:
            if n % 2 == 0:
                n = n // 2
            else:
                n = 3 * n + 1
        return True
    
    def program2(n):
        """
        항상 True 반환
        """
        return True
    
    # 질문: program1과 program2는 동치인가?
    # 
    # 만약 모든 n에 대해 콜라츠 추측이 참이면: 동치
    # 하지만 콜라츠 추측은 아직 증명 안됨!
    # 
    # 따라서 동치 여부를 판단할 수 없음

예시 2: 프로그램 특성 문제

Rice의 정리:

프로그램의 의미론적 특성은 계산 불가능하다

의미론적 특성이란?
- "이 프로그램이 짝수만 출력하는가?"
- "이 프로그램이 항상 종료하는가?"
- "이 프로그램이 'Hello'를 출력하는가?"

Rice의 정리:
이런 질문들에 대해 모든 프로그램을 정확히 분류하는 알고리즘은 존재하지 않는다!

실용적 예시:

def rice_theorem_example():
    """
    Rice의 정리 예시
    
    불가능한 질문들:
    """
    
    # 질문 1: 이 프로그램이 항상 양수를 반환하는가?
    def always_positive(program):
        """
        계산 불가능!
        
        이유:
        모든 입력에 대해 확인해야 하는데 입력이 무한할 수 있음
        """
        pass
    
    # 질문 2: 이 프로그램이 배열을 정렬하는가?
    def is_sorting_program(program):
        """
        계산 불가능!
        
        이유:
        프로그램이 "의도적으로" 정렬하는지, 아니면 우연히 정렬된 결과를 내는지 판단할 수 없음
        """
        pass
    
    # 질문 3: 이 프로그램이 변수 x를 사용하는가?
    def uses_variable_x(program):
        """
        이건 가능!
        
        이유:
        프로그램 코드를 분석하면 됨 (구문론적)
        실행 결과를 볼 필요 없음
        
        Rice의 정리는 의미론적 특성에만 적용됨
        """
        # 코드 텍스트에서 'x' 찾기
        return 'x' in program

핵심:

가능 (구문론적 특성):
- 코드에 'x'가 있는가?
- 줄 수가 100줄 이상인가?
- for 루프를 사용하는가?

불가능 (의미론적 특성):
- 실행하면 'x'를 사용하는가?
- 100번 이상 반복하는가?
- 결과가 정렬되는가?

차이:
구문론적 = 코드만 봐도 알 수 있음
의미론적 = 실행해봐야 알 수 있음

---

🔧 환원으로 불가능성 증명하기

환원의 활용

불가능한 문제가 하나 있으면, 환원으로 다른 문제도 불가능함을 증명할 수 있습니다.

방법:

1. 알려진 불가능 문제: A (예: 정지 문제)
2. 증명하고 싶은 문제: B

3. A ≤ B 환원 만들기 (A를 B로 변환)

4. 결론:
   만약 B를 풀 수 있다면
   → A도 풀 수 있다 (환원으로)
   → 하지만 A는 불가능
   → 모순!
   → 따라서 B도 불가능!

예시: 정지 문제 → 출력 예측 문제

def halting_to_output_reduction():
    """
    정지 문제를 출력 예측 문제로 환원
    
    목표:
    출력 예측 문제도 불가능함을 증명
    
    방법:
    정지 문제를 풀 수 있다면 출력 예측 문제로 변환해서 풀 수 있음을 보임
    """
    
    # 가정: 출력 예측기가 있다고 가정
    def will_output_yes(program, input_data):
        """
        program(input_data)가 "YES"를 출력하는가?
        
        이게 가능하다고 가정
        """
        pass
    
    # 정지 문제 풀기
    def solve_halting(program, input_data):
        """
        정지 문제를 출력 예측으로 풀기
        
        아이디어:
        1. 원래 program을 변형
        2. 정지하면 "YES" 출력하는 새 프로그램 만들기
        3. 새 프로그램이 "YES" 출력하는지 확인
        """
        
        # 1단계: 변환 - 새 프로그램 만들기
        def modified_program(x):
            """
            원래 프로그램을 감싼 프로그램
            
            행동:
            - program(input_data) 실행
            - 정지하면 "YES" 출력
            - 무한 루프면 출력 안함
            """
            program(input_data)  # 원래 프로그램 실행
            print("YES")  # 정지했으면 여기 도달
        
        # 2단계: 출력 예측기로 확인
        # modified_program이 "YES" 출력하는가?
        # = program이 정지하는가?
        return will_output_yes(modified_program, input_data)
    
    # 결론:
    # will_output_yes가 존재하면
    # → solve_halting으로 정지 문제 풀 수 있음
    # → 하지만 정지 문제는 불가능
    # → 모순!
    # → will_output_yes도 존재할 수 없음!

환원 그림:

정지 문제 (불가능)
    ↓ 환원
출력 예측 문제
    ↓
만약 풀 수 있다면
    ↓
정지 문제도 풀 수 있음
    ↓
모순! (정지 문제는 불가능)
    ↓
따라서 출력 예측도 불가능

---

🎨 실생활 비유

비유 1: 거짓말쟁이 역설

크레타 사람:
"모든 크레타 사람은 거짓말쟁이다"

분석:
- 이 말이 참이면: 크레타 사람이  → 이 말도 거짓  → 모순!

- 이 말이 거짓이면: 크레타 사람이 정직  → 이 말이 참  → 모순!

결론: 자기 참조는 역설을 만듦

프로그램:
프로그램이 자기 자신에 대해 판단하면 → 비슷한 역설 발생 → 완벽한 판단 불가능

비유 2: 이발사 역설

마을 규칙:
"이발사는 자기 자신을 면도하지 않는 모든 사람을 면도한다"

질문: 이발사는 자기를 면도하는가?

- 면도한다면:
  → "자기를 면도하지 않는 사람"이 아님  → 면도하면 안됨  → 모순!

- 면도하지 않는다면:
  → "자기를 면도하지 않는 사람"임  → 면도해야 함  → 모순!

결론: 이런 이발사는 존재할 수 없음

프로그램:
"자기를 분석하는 프로그램"도 비슷한 이유로 존재할 수 없음

---

💡 실무 의미

계산 불가능성의 영향

1. 완벽한 도구는 불가능

불가능한 도구들:
- 완벽한 바이러스 검사기  → 모든 바이러스를 찾는 건 불가능
  
- 완벽한 버그 찾기  → 모든 버그를 자동으로 찾는 건 불가능
  
- 완벽한 최적화 컴파일러  → 항상 최적 코드 생성은 불가능

이유:
이런 도구들은 프로그램의 의미론적 특성을 완벽히 분석해야 하는데, Rice의 정리에 의해 불가능

2. 근사 (Approximation)와 휴리스틱 (Heuristic) 필요

• 근사와 휴리스틱: 복잡한 문제나 정보가 부족한 상황에서 완벽한 정답 대신 '충분히 좋은' 해를 빠르게 찾기 위한 실용적인 접근 방식
  • 근사: 최적해(Optimal solution)에 가까운 해(근사해)를 찾기 위해 논리적/수학적 기법을 사용
  • 휴리스틱: '발견법' 또는 '경험 법칙'이라고도 하며, 경험에 기반하여 문제를 대략적으로 해결하는 간편한 방법

def practical_approach():
    """
    실무에서의 접근
    
    완벽은 불가능하지만, "대부분의 경우"에 작동하는 도구는 가능!
    """
    
    # 바이러스 검사
    def virus_scanner_practical(program):
        """
        완벽하진 않지만 실용적
        
        접근:
        1. 알려진 바이러스 패턴 확인
        2. 의심스러운 행동 탐지
        3. 샌드박스에서 실행
        
        한계:
        - 새로운 바이러스는 못 찾을 수 있음
        - 교묘한 바이러스는 놓칠 수 있음
        
        하지만:
        - 대부분의 바이러스는 찾음
        - 실무에서 충분히 유용
        """
        pass
    
    # 버그 찾기
    def bug_finder_practical(program):
        """
        완벽하진 않지만 도움됨
        
        접근:
        1. 정적 분석 (코드만 봄)
        2. 동적 분석 (테스트 실행)
        3. 알려진 패턴 확인
        
        한계:
        - 모든 버그를 못 찾음
        - 거짓 양성 가능
        
        하지만:
        - 많은 버그를 찾아줌
        - 코드 품질 향상
        """
        pass

---

🎯 핵심 정리

계산 불가능성

정의:
어떤 알고리즘으로도 모든 입력에 대해 올바르게 판단할 수 없는 문제

특징:
- 시간 문제가 아님 (아무리 기다려도 안 됨)
- 컴퓨터의 근본적 한계
- 자기 참조로 인한 역설

왜 불가능한가?

핵심 이유:
프로그램이 자기 자신에 대해 완벽히 분석할 수 없음

역설:
- 예측기가 예측하면
- 프로그램이 예측 반대로 행동
- 예측이 항상 틀림
- 완벽한 예측 불가능

대표 예시

- 정지 문제
- 프로그램 동치 문제
- 출력 예측 문제
- Rice의 정리 (의미론적 특성)

실무 의미

불가능:
- 완벽한 바이러스 검사
- 완벽한 버그 찾기
- 완벽한 최적화

가능:
- 대부분의 경우 작동
- 휴리스틱과 근사
- 실용적 도구

환원 활용

불가능성 증명:
1. 알려진 불가능 문제 A
2. A ≤ B 환원
3. B도 불가능 증명

예: 정지 문제 → 출력 예측 → 불가능

---

🔗 다음 글에서는

[08-08] 정지 문제 (Halting Problem)

• 정지 문제의 정의: 프로그램이 멈추는지 판단하기
• 튜링의 증명: 귀류법으로 불가능성 증명
• 콜라츠 추측: 여전히 풀리지 않은 정지 문제
• 실무 영향: 완벽한 디버거가 불가능한 이유

---

이전 글: [08-06] 다항 시간 환원
다음 글: [08-08] 정지 문제
시리즈: P1. Computer Science