정의
계산 가능성 이론(Computability Theory)은 알고리즘이나 계산 절차에 의해 해결될 수 있는 문제와 그렇지 않은 문제를 구분하고, 계산 가능한 함수와 언어의 구조를 연구하는 이론적 컴퓨터 과학의 한 분야이다. 한국어에서 “계산 가능성”은 영어 “computability”를 직역한 표현이며, “이론”은 학문적 체계를 의미한다.
역사 및 주요 발전
- 1930년대 초, 알론조 처치(Alonzo Church)와 알란 튜링(Alan Turing)은 각각 람다 계산법과 튜링 기계를 독립적으로 제시하면서 계산 가능성의 형식적 정의를 확립하였다.
- 1936년 튜링은 “튜링 기계” 모델을 통해 어떤 함수가 기계적으로 계산 가능한지를 명확히 하였으며, 이는 현대 컴퓨터 과학의 기초가 된다.
- 동일 시기에 쿠르트 괴델(Kurt Gödel)의 불완전성 정리와 연결된 “결정 가능성”(decidability) 개념이 등장하였다.
- 1950년대와 1960년대에 마틴 다이어(Martin Davis), 리차드 해밀턴(Richard M. Karp), 스티븐 쿠크(Steven Cook) 등은 복잡도 이론과의 연계 연구를 진행하였다.
핵심 개념
- 계산 가능 함수: 튜링 기계, 람다 계산법, 재귀 함수 등 형식 모델에 의해 계산될 수 있는 함수.
- 결정 가능 언어(Decidable Language): 주어진 입력에 대해 언제나 정답을 반환하는 알고리즘(튜링 기계)이 존재하는 언어.
- 반결정 가능 언어(Semi-decidable/Recursively Enumerable Language): 올바른 입력에 대해서는 알고리즘이 멈추지만, 잘못된 입력에 대해서는 무한히 실행될 수 있는 언어.
- 불가능 문제(Undecidable Problem): 대표적으로 튜링 기계의 정지 문제(Halting Problem)와 같이 어떤 알고리즘도 모든 경우에 정답을 보장하지 못하는 문제.
주요 정리 및 정리
- 튜링의 정지 문제 불가능성: 모든 일반적인 프로그래밍 언어나 튜링 기계에 대해, 프로그램이 주어진 입력에 대해 멈출지 여부를 판정하는 보편적인 알고리즘은 존재하지 않는다.
- 교환 가능성 정리(Church–Turing Thesis): 직관적으로 “효율적인 계산”이라고 생각되는 모든 모델은 튜링 기계와 계산 가능성 측면에서 동등하다고 가정한다. 이 정리는 증명된 정리가 아니라 경험적·철학적 가설이다.
- 재귀적 가산성: 모든 재귀적으로 열거 가능한 언어는 튜링 기계에 의해 반결정 가능하며, 그 반대도 성립한다.
연관 분야
- 복잡도 이론: 계산 가능성 위에 시간·공간 자원 제한을 두어 문제의 실용적 난이도를 분석한다.
- 형식 언어 이론: 자동기관, 문법과 연결되어 언어의 구조적 특성을 조사한다.
- 프로그램 검증: 프로그램이 특정 속성을 만족하는지 여부를 계산 가능성 관점에서 검토한다.
어원 및 용어 사용
- “계산”(計算, calculation) + “가능성”(可能性, possibility) + “이론”(理論, theory)이라는 구성은 영어 “computability theory”를 직역한 형태이다.
- 학술 논문, 교재, 대학 강의 등에서 “계산 가능성 이론”이라는 용어는 주로 이론 컴퓨터 과학, 수학적 논리학, 인공지능 이론 분야에서 사용된다.
참고문헌
- A. Church, An Unsolvable Problem of Elementary Number Theory, American Journal of Mathematics, 1936.
- A. M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, 1936.
- M. Davis, Computability and Unsolvability, McGraw‑Hill, 1958.
- S. Cook, The Complexity of Theorem-Proving Procedures, Proceedings of the 3rd ACM Symposium on Theory of Computing, 1971.
※ 위 내용은 현재까지 널리 인정받는 학술 자료와 교과서에 기반한 객관적인 서술이다.
