재귀 집합 문서 원본 보기

{{위키데이터 속성 추적}}
[[계산 가능성 이론]]에서 '''재귀 집합'''({{llang|en|recursive set}}) 또는 '''계산 가능 집합'''({{llang|en|computable set}})은 어떤 자연수가 그 집합에 속하는지 아닌지를 유한한 시간 안에 판별하는 [[알고리즘]]이 존재하는 자연수 집합이다.

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

== 정의 ==
[[자연수]] 집합의 부분집합 <math>S</math>가 다음을 만족하면 '''재귀적'''({{llang|en|recursive}}) 또는 '''계산가능'''({{llang|en|computable}})이라 한다.
*다음과 같은 전역 [[계산 가능 함수]] <math>f</math>가 존재한다: <math>f(x) = \begin{cases} 1 & \mbox{if } x \in S \\ 0 & \mbox{if } x \not \in S \end{cases}</math>

다르게 말하면, [[지시함수]] <math>1_S</math>가 [[계산 가능 함수]]인 경우이다.

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

== 성질 ==
집합 <math>A</math>와 <math>B</math>가 재귀 집합이면, <math>A \cap B</math>, <math>A \cup B</math> 등도 재귀 집합이다. 또한 집합 A가 재귀 집합일 [[필요충분조건]]은 A와 A의 [[여집합]]이 모두 [[재귀 열거 집합]]이라는 것이다.

재귀 집합의 전역 계산가능 함수에 대한 [[상 (수학)|원상]]은 재귀 집합이다.

집합이 재귀 집합일 필요충분조건은 [[산술 위계]] <math>\Delta^0_1</math>에 속하는 것이다.

== 각주 ==
*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}}

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

{{수리논리학}}

[[분류:계산 가능성 이론]]