재귀 집합

계산 가능성 이론에서 재귀 집합() 또는 계산 가능 집합()은 어떤 자연수가 그 집합에 속하는지 아닌지를 유한한 시간 안에 판별하는 알고리즘이 존재하는 자연수 집합이다.

조건을 일반화하여 재귀 열거 집합의 정의를 얻을 수 있다.

 정의 
자연수 집합의 부분집합 가 다음을 만족하면 재귀적() 또는 계산가능()이라 한다.
다음과 같은 전역 계산 가능 함수 가 존재한다: 

다르게 말하면, 지시함수 가 계산 가능 함수인 경우이다.

 예시 
자연수 집합의 유한 부분집합 또는 쌍대 유한 부분집합은 계산가능이다.
 공집합
자연수 전체: 공집합의 여집합이므로.
각 자연수들: 집합론적으로 정의된 경우를 이야기한다. 즉, 한 자연수에 대해서 그 자연수보다 작은 자연수의 집합이 계산가능하다는 것이다.
 소수의 집합
 재귀 언어는 형식 언어 집합의 재귀 부분집합이다.
 괴델 수의 집합

 성질 
집합 와 가 재귀 집합이면, ,  등도 재귀 집합이다. 또한 집합 A가 재귀 집합일 필요충분조건은 A와 A의 여집합이 모두 재귀 열거 집합이라는 것이다.

재귀 집합의 전역 계산가능 함수에 대한 원상은 재귀 집합이다.

집합이 재귀 집합일 필요충분조건은 산술 위계 에 속하는 것이다.

 각주 
Cutland, N. Computability. Cambridge University Press, Cambridge-New York, 1980. ; 
Rogers, H.   The Theory of Recursive Functions and Effective Computability, MIT Press. ;  
Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic.  Springer-Verlag, Berlin, 1987. 

 같이 보기 
 재귀 언어
 계산 가능 함수
 산술 위계

분류:계산 가능성 이론