# [08-08] 정지 문제 (Halting Problem)
정지 문제는 컴퓨터로 풀 수 없는 가장 유명한 문제로, 컴퓨터 과학의 근본적 한계를 보여 줍니다.
🎯 정지 문제란 무엇인가
정지 문제 (Halting Problem)의 정의
정지 문제는 다음 질문에 답하는 것입니다:
주어진 프로그램과 입력에 대해, "이 프로그램이 정지할까? 무한 루프일까?"쉬운 비유:
영화 보기:
질문: "이 영화가 언제 끝날까?"
쉬운 경우:
- 90분짜리 영화 → 90분 후 끝남 (명확)
어려운 경우:
- 반복 재생 설정된 영화 → 영원히 안 끝남 → 하지만 처음엔 구분 어려움
정지 문제:
프로그램이 "끝나는 영화"인지 "무한 반복 영화"인지 판단하기명백한 경우들
일부 프로그램은 명백히 정지하거나 명백히 정지하지 않습니다.
# ===== 명백히 정지하는 프로그램 =====
def clearly_halts_1(n):
"""
간단한 계산만 하고 끝 → 명백히 정지함
"""
return n + 1
def clearly_halts_2(n):
"""
제한된 반복 후 종료 → 명백히 정지함
"""
total = 0
for i in range(n): # n번만 반복
total += i
return total
# ===== 명백히 정지하지 않는 프로그램 =====
def clearly_infinite_1(n):
"""
무한 루프 → 명백히 정지 안함
"""
while True:
pass # 영원히 반복
def clearly_infinite_2(n):
"""
끝나지 않는 카운트 → 명백히 정지 안함
"""
i = 0
while i >= 0: # i는 항상 양수
i += 1 # 계속 증가이런 간단한 경우는 사람이 쉽게 판단할 수 있습니다.
어려운 경우
문제는 복잡한 프로그램입니다.
def collatz(n):
"""
콜라츠 추측 (Collatz Conjecture)
규칙:
- 짝수면: n을 2로 나누기
- 홀수면: 3n + 1
- 1이 되면 종료
질문: 모든 양수 n에 대해 정지하는가?
"""
while n != 1:
if n % 2 == 0: # 짝수
n = n // 2
else: # 홀수
n = 3 * n + 1
return True
# 예시들
def test_collatz():
"""
콜라츠 추측 테스트
"""
# n = 5
# 5 → 16 → 8 → 4 → 2 → 1 (정지!)
# n = 6
# 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 (정지!)
# n = 27
# 27 → 82 → 41 → 124 → 62 → 31 → 94 → 47 → ...
# ... → 1 (111단계 후 정지!)
# 질문: 모든 n에 대해 정지하는가?
# 답: 아무도 모름!
# → 1,000,000,000,000,000,000까지 확인됨
# → 하지만 모든 n에 대해서는 증명 안됨
# → 90년 넘게 미해결!왜 어려운가?
간단해 보이는 규칙이지만:
- 어떤 숫자는 금방 1에 도달
- 어떤 숫자는 오래 걸림
- 패턴을 예측할 수 없음
인간도 판단 못 하는데, 컴퓨터가 자동으로 판단할 수 있을까?
→ 튜링이 증명: 불가능!🚫 튜링의 증명: 정지 문제는 불가능하다
귀류법 증명
튜링은 귀류법(proof by contradiction)으로 정지 문제가 불가능함을 증명했습니다.
귀류법이란?
1. 가정: "A가 참이다"
2. 논리 전개: A가 참이면...
3. 결과: 모순 발생!
4. 결론: A는 거짓이다
예:
가정: "가장 큰 소수가 존재한다"
→ 그보다 큰 소수를 만들 수 있음
→ 모순!
→ 결론: 가장 큰 소수는 없다튜링의 증명 (단계별)
1단계: 정지 판단기가 있다고 가정
# 가정: 이런 함수가 존재한다고 가정
def halts(program, input_data):
"""
정지 판단기 (가상)
program: 판단할 프로그램 (함수)
input_data: 프로그램의 입력
Returns: True if program(input_data)가 정지
False if program(input_data)가 무한 루프
특징:
- 항상 정확함
- 모든 프로그램에 대해 작동
- 스스로는 항상 정지함 (답을 냄)
이런 함수가 존재한다고 가정!
"""
# 마법처럼 판단한다고 가정
pass2단계: 역설 프로그램 만들기
def paradox(p):
"""
역설을 만드는 프로그램
p: 프로그램 (자기 자신을 받을 수도 있음!)
논리:
1. halts가 "정지한다"고 판단하면 → 무한 루프 실행 (정지 안 함!)
2. halts가 "정지 안 한다"고 판단하면 → 즉시 종료 (정지함!)
핵심:
halts의 판단과 반대로 행동! → halts가 항상 틀리게 만듦
"""
# p(p)가 정지하는지 판단 (프로그램에 자기 자신을 입력으로 줌)
if halts(p, p):
# halts가 "정지한다"고 했으면 → 반대로 무한 루프!
while True:
pass # 영원히 실행
else:
# halts가 "정지 안한다"고 했으면 → 반대로 즉시 종료!
return # 바로 끝3단계: 자기 자신에게 적용
# 질문: paradox(paradox)는 어떻게 되는가?
# 경우 1: halts(paradox, paradox) = True라고 가정
# → halts: "paradox(paradox)는 정지한다"
# → 하지만 paradox의 코드를 보면:
# if halts(p, p): # True
# while True: pass # 무한 루프!
# → 실제로는 정지 안함!
# → halts가 틀림!
# → 모순!
# 경우 2: halts(paradox, paradox) = False라고 가정
# → halts: "paradox(paradox)는 정지 안한다"
# → 하지만 paradox의 코드를 보면:
# if halts(p, p): # False
# pass
# else:
# return # 즉시 종료!
# → 실제로는 정지함!
# → halts가 틀림!
# → 모순!4단계: 결론
두 경우 모두 모순!
→ halts는 paradox(paradox)를 판단할 수 없음
→ halts는 존재할 수 없음!
∴ 정지 문제를 푸는 알고리즘은 존재하지 않는다!증명 정리
핵심 아이디어:
1. "정지 판단기"가 있다고 가정
2. 그 판단과 "반대로 행동"하는 프로그램 만들기
3. 그 프로그램에 "자기 자신"을 입력
4. 모순 발생!
5. 따라서 정지 판단기는 불가능
왜 이런 일이?
→ 자기 참조(self-reference) 때문
→ 프로그램이 자기 자신을 입력으로 받을 수 있음
→ 자기 자신에 대한 예측을 뒤집을 수 있음📊 정지 문제의 실제 예시
예시 1: 콜라츠 추측
def collatz_detailed(n):
"""
콜라츠 추측 상세
규칙:
- 짝수: n ÷ 2
- 홀수: 3n + 1
- 1이면 종료
주장: 모든 양수는 결국 1에 도달한다
상태: 미증명 (1937년~)
"""
steps = 0
original = n
sequence = [n]
while n != 1:
if n % 2 == 0:
n = n // 2
else:
n = 3 * n + 1
sequence.append(n)
steps += 1
# 너무 길면 중단 (무한 루프 방지)
if steps > 10000:
print(f"{original}: 10000단계 초과!")
return None
return steps, sequence
# 테스트
print("콜라츠 추측 테스트:")
print()
test_numbers = [5, 27, 97, 871]
for n in test_numbers:
result = collatz_detailed(n)
if result:
steps, seq = result
print(f"n = {n}:")
print(f" 단계: {steps}")
print(f" 경로: {seq[:5]}...{seq[-3:]}")
print()
# 출력 예시:
# n = 5:
# 단계: 5
# 경로: [5, 16, 8, 4, 2]...[4, 2, 1]
#
# n = 27:
# 단계: 111
# 경로: [27, 82, 41, 124, 62]...[4, 2, 1]
#
# n = 97:
# 단계: 118
# 경로: [97, 292, 146, 73, 220]...[4, 2, 1]왜 증명 못 하는가?
시도한 방법들:
1. 모든 수 확인: 불가능 (무한함)
2. 패턴 찾기: 아직 못 찾음
3. 수학적 증명: 너무 어려움
현재 상황:
- 2⁶⁸ (약 3×10²⁰)까지 확인됨
- 모두 1에 도달함
- 하지만 모든 수에 대한 증명은 없음
정지 문제와 관계:
"collatz(n)이 모든 n에 대해 정지하는가?"
→ 정지 문제의 특수한 경우
→ 일반적인 정지 문제가 불가능하므로 이런 특수한 경우도 어려울 수 있음예시 2: 비버 게임
def busy_beaver(n):
"""
비버 게임 (Busy Beaver)
문제:
n개 상태를 가진 튜링 기계 중 가장 많은 1을 쓰고 정지하는 기계는?
왜 어려운가?
- 정지하는 기계만 세야 함
- 정지 여부를 판단해야 함
- 정지 문제가 불가능하므로 일반적인 해법 없음
알려진 값:
BB(1) = 1
BB(2) = 6
BB(3) = 21
BB(4) = 107
BB(5) ≥ 47,176,870
BB(6) > 10¹⁵ (확실하지 않음)
특징:
계산 가능한 함수 중 가장 빠르게 증가!
"""
pass💡 실무 의미
완벽한 도구는 불가능
1. 완벽한 디버거
def why_perfect_debugger_impossible():
"""
완벽한 디버거가 불가능한 이유
원하는 기능:
- 모든 무한 루프 탐지
- 코드 실행 전에 경고
왜 불가능:
→ 무한 루프 탐지 = 정지 문제
→ 정지 문제는 불가능
→ 완벽한 디버거도 불가능
실제 디버거:
- 간단한 무한 루프는 탐지
- 복잡한 경우는 못 찾음
- 타임아웃 같은 휴리스틱 사용
"""
# 간단한 무한 루프: 탐지 가능
def simple_loop():
while True:
pass
# → 명백한 무한 루프, 정적 분석으로 탐지 가능
# 복잡한 경우: 탐지 어려움
def complex_case(n):
# 콜라츠 추측
while n != 1:
if n % 2 == 0:
n = n // 2
else:
n = 3 * n + 1
# → 정지 여부 불확실, 자동 탐지 불가능2. 완벽한 최적화 컴파일러
def why_perfect_optimizer_impossible():
"""
완벽한 최적화 컴파일러가 불가능한 이유
원하는 기능:
- 불필요한 코드 모두 제거
- 실행 결과는 그대로
예:
def compute(n):
x = expensive_calculation(n) # 오래 걸림
return 42 # x를 안 씀!
최적화:
def compute_optimized(n):
return 42 # expensive_calculation 제거!
왜 불가능:
- expensive_calculation이 정지하는지 확인 필요
- 정지 안 하면 원본과 최적화 버전이 다름 (원본: 무한 루프, 최적화: 즉시 42 반환)
- 정지 여부 판단 = 정지 문제
- 완벽한 최적화 불가능
실제 컴파일러:
- 안전한 최적화만 수행
- 보수적 접근 (확실한 것만)
"""
pass3. 완벽한 테스트 커버리지
def why_perfect_testing_impossible():
"""
완벽한 테스트가 불가능한 이유
목표:
"모든 실행 경로를 테스트"
문제:
def mystery_function(n):
if some_complex_condition(n): # 복잡한 조건
return True
else:
while complex_loop(n): # 복잡한 루프
n = transform(n)
return False
질문:
- if 분기를 테스트하려면?
→ some_complex_condition이 True인 입력 필요
→ 그런 입력이 존재하는가? (판단 어려움)
- else 분기를 테스트하려면?
→ 루프가 정지해야 함
→ 정지하는가? (정지 문제!)
결론:
- 모든 경로 테스트 불가능
- 대표적 경로만 테스트
- 100% 커버리지 != 100% 정확성
"""
pass실용적 접근
정지 문제가 불가능하지만, 실무에서는 여전히 유용한 도구들이 있습니다.
def practical_approaches():
"""
실무적 접근 방법들
"""
# 1. 타임아웃
import signal
def with_timeout(func, timeout_sec):
"""
제한 시간 내에 실행
완벽하지 않지만 실용적:
- timeout_sec 안에 안 끝나면 중단
- 진짜 무한 루프와 느린 프로그램 구분 못함
- 하지만 대부분의 경우 충분
"""
def timeout_handler(signum, frame):
raise TimeoutError("시간 초과!")
# 타임아웃 설정
signal.signal(signal.SIGALRM, timeout_handler)
signal.alarm(timeout_sec)
try:
result = func()
signal.alarm(0) # 타임아웃 해제
return result
except TimeoutError:
return None # 시간 내 안 끝남
# 2. 정적 분석
def static_analysis(code):
"""
코드 실행없이 분석
탐지 가능:
- 명백한 무한 루프 (while True)
- 도달 불가능 코드
- 간단한 패턴
탐지 불가능:
- 복잡한 조건의 무한 루프
- 데이터 의존적 루프
"""
pass
# 3. 휴리스틱
def heuristic_check(program):
"""
경험적 규칙
예:
- 루프 변수가 증가만 하는가?
- 종료 조건이 있는가?
- 재귀 깊이가 제한되는가?
완벽하지 않지만 도움됨
"""
pass🎯 핵심 정리
정지 문제
정의:
"프로그램이 정지할까? 무한 루프일까?"
특징:
- 가장 유명한 계산 불가능 문제
- 튜링이 1936년 증명
- 컴퓨터 과학의 근본적 한계튜링의 증명
방법: 귀류법
1. 가정: 정지 판단기 halts 존재
2. 역설 프로그램: halts와 반대로 행동
3. 자기 참조: paradox(paradox) 실행
4. 모순: 두 경우 모두 모순
5. 결론: halts는 존재 불가능실제 예시
- 콜라츠 추측: 90년째 미해결
- 비버 게임: 가장 빠른 성장 함수
- 복잡한 프로그램: 정지 여부 불확실실무 의미
불가능한 도구:
- 완벽한 디버거
- 완벽한 최적화 컴파일러
- 완벽한 테스트
가능한 접근:
- 타임아웃
- 정적 분석 (간단한 경우)
- 휴리스틱 (경험적 규칙)철학적 의미
컴퓨터의 한계:
- 모든 문제를 풀 수 없음
- 자기 자신에 대한 완벽한 분석 불가능
- 수학적으로 증명된 한계
하지만:
- 대부분의 실용적 문제는 해결 가능
- 근사와 휴리스틱으로 충분히 유용🔗 다음 글에서는
[08-09] 기타 복잡도 클래스
- co-NP: NP의 여집합, 반대 증명이 쉬운 문제들
- PSPACE: 다항 공간으로 해결 가능한 문제들
- EXPTIME: 지수 시간이 필요한 문제들
- 복잡도 클래스 계층: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME
이전 글: [08-07] 계산 불가능성
다음 글: [08-09] 기타 복잡도 클래스
시리즈: P1. Computer Science
AI 전문가를 꿈꾸는 도전자