재귀 집합
계산 가능성 이론에서 재귀 집합(영어: recursive set) 또는 계산 가능 집합(영어: computable set)은 어떤 자연수가 그 집합에 속하는지 아닌지를 유한한 시간 안에 판별하는 알고리즘이 존재하는 자연수 집합이다.
조건을 일반화하여 재귀 열거 집합의 정의를 얻을 수 있다.
정의
편집자연수 집합의 부분집합 가 다음을 만족하면 재귀적(영어: recursive) 또는 계산가능(영어: computable)이라 한다.
- 다음과 같은 전역 계산 가능 함수 가 존재한다:
예시
편집성질
편집집합 와 가 재귀 집합이면, , 등도 재귀 집합이다. 또한 집합 A가 재귀 집합일 필요충분조건은 A와 A의 여집합이 모두 재귀 열거 집합이라는 것이다.
재귀 집합의 전역 계산가능 함수에 대한 원상은 재귀 집합이다.
집합이 재귀 집합일 필요충분조건은 산술 위계 에 속하는 것이다.
각주
편집- 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