계산 가능성 이론
From Wikipedia, the free encyclopedia
계산 가능성 이론(計算可能性理論, 영어: computability theory) 또는 재귀 이론(再歸理論, 영어: recursion theory)은 수학기초론의 중요한 분야이자 컴퓨터 과학에서는 계산 이론의 한 갈래이다.
계산 가능성 이론의 기초는 가산 집합 상에서 함수의 해를 찾는 문제와 관련이 있다. 1930년대 불완전성 정리와 함께 람다 대수와 튜링 기계라는 계산 모형이 만들어지면서, 어떤 집합이 효율적으로 계산 가능한지의 문제는 실질적으로 그 집합을 효율적으로 계산해 내는 함수를 만들어 내는 것과 같은 일이 되었다. 계산 가능성 이론의 초기 성과는 이들 집합을 계산적으로 동치인 것들로 묶어 위계로 분류한 것이다. 수학적으로 유한히 정의된 함수를 계산 가능성에 따라 분류했을 때 어떤 함수의 계산 가능성 문제를 다른 함수(다른 함수들)의 문제로 환원할 수 있다는 것을 보임으로써, 굳이 알고리즘 자체를 증명에 끌어들이지 않고도 계산 가능성을 증명할 수 있는 것이다. 이에 따라 대안적인 공리계를 모색하기 위한 이론적 토대가 마련되었고, 수리논리학과 증명론에서 직관주의가 입지를 공고히 했으며, 유형 이론과 고차 논리, 자연 연역, 헤이팅 대수의 비약적 발전에 영향을 주었다.
계산 복잡도 이론에서는 계산 가능한 집합을 그 함수의 해를 찾는 효율적인 알고리즘에 의해 소모되는 시공간적 자원의 추세를 토대로 분류한다. 이에 따라 계산 복잡도 이론과 계산 가능성 이론 중 어느 쪽이 상위의 개념인지에 관해 다소 논쟁이 있다.