재귀 집합

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

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

정의

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

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

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

예시

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

성질

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

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

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

각주

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

같이 보기

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