재귀 집합

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

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

정의

자연수 집합의 부분집합 $S$가 다음을 만족하면 재귀적(영어: recursive) 또는 계산가능(영어: computable)이라 한다.

• 다음과 같은 전역 계산 가능 함수 $f$가 존재한다: $f(x)={\begin{cases}1&{\mbox{if }}x\in S\\0&{\mbox{if }}x\not \in S\end{cases}}$

다르게 말하면, 지시함수 $1_{S}$가 계산 가능 함수인 경우이다.

예시

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

성질

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

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

집합이 재귀 집합일 필요충분조건은 산술 위계 $\Delta _{1}^{0}$에 속하는 것이다.

각주

• Cutland, N. Computability. Cambridge University Press, Cambridge-New York, 1980. ISBN 0-521-22384-9; ISBN 0-521-29465-7
• Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1
• Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7

같이 보기

• 재귀 언어
• 계산 가능 함수
• 산술 위계