재귀 집합

(재귀적 집합에서 넘어옴)

계산 가능성 이론에서 재귀 집합(영어: 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

같이 보기

편집