개념
"일정한 절차로 풀 수 있는 문제는 무엇인가?"에 대한 수학적 연구. 계산 기계가 이미 존재하던 1936년, 처치와 튜링은 서로 다른 형식 모형으로 알고리즘의 능력과 한계를 선명하게 했다.
한 호흡으로 이해하기
"어떤 함수를 알고리즘으로 계산할 수 있는가." 1936년 튜링은 종이와 연필로 하는 계산을 이상화한 기계를 제시하고 결정 문제의 한계를 보였다. 오늘날의 정지 문제 표현으로 말하면 임의의 프로그램이 멈출지 판정하는 일반 알고리즘은 없다. 당시에도 계산 기계는 있었지만, 이 논문은 보편 계산의 추상 모형을 선명하게 했다.
한눈에 보기
문제 | 결정 가능? | 비고 |
|---|---|---|
소수 판별 | ✓ | 에라토스테네스의 체 |
정렬·검색 | ✓ | 효율 차이만 있을 뿐 |
정수해 다항식 (디오판투스 #10) | ✗ | 힐베르트 10번 — 1970 마티야세비치 |
정지 문제 (Halting Problem) | ✗ | 튜링 1936 — 대각화 논법 |
두 프로그램이 같은 일을 하는가 | ✗ | 라이스 정리 (모든 비자명 의미적 속성) |
단어 문제 (군론) | ✗ | Novikov 1955 |
결정 불가능한 문제들이 예외가 아니라 압도적 다수. 결정 가능한 게 희귀한 보석.
핵심 식
계산 가능 ⟺ 튜링 기계로 풀림
핵심 순간
힐베르트 — 결정 문제(Entscheidungsproblem)
"모든 수학 명제의 참·거짓을 기계적으로 결정하는 알고리즘이 있는가?" 힐베르트의 마지막 큰 질문.
처치·튜링 — NO (독립 증명)
같은 해 알론조 처치(람다 계산법)와 알란 튜링(튜링 기계)이 독립적으로 "그런 알고리즘은 없다"를 증명.
튜링 — 튜링 기계의 정의
종이와 연필로 따르는 계산 절차를 이상화한 추상 기계를 제시했다. “효과적으로 계산 가능하다”는 직관과의 일치는 Church–Turing 명제로 구분한다.
P vs NP — 새로운 미해결 문제
쿡-카프 등이 효율적으로 풀 수 있는 문제와 효율적으로 검증 가능한 문제가 같은가의 질문 제기. 100만 달러 밀레니엄 문제.
오늘날의 응용
컴파일러 설계의 한계, 자동 정리 증명 시스템, AI의 이론적 한계, 프로그래밍 언어의 표현력 분석.
MathVoyage 너머로
불러오는 중…