재귀 집합

1. 개요

재귀 집합은 자연수 집합의 부분집합 S에 대해, S의 원소 여부를 유한한 단계 내에 판별할 수 있는 계산 가능 함수가 존재하는 집합을 의미한다. 이는 지시 함수가 계산 가능한 경우와 동치이며, 계산 가능한 집합이라고도 불린다. 재귀 집합의 예시로는 유한 집합, 공집합, 자연수 전체 집합, 소수의 집합 등이 있으며, 정지 문제와 같은 결정 불가능한 문제들은 재귀 집합이 아니다. 재귀 집합은 교집합, 합집합 등의 연산에 닫혀 있으며, 전역 계산 가능 함수의 상과 원상도 재귀 집합이다.

2. 정의

자연수 집합의 부분집합 $S$에 대해, 어떤 원소가 $S$에 속하는지 여부를 유한한 단계 내에 판별할 수 있는 계산 가능 함수 $f$가 존재하면, $S$를 재귀적(recursive^영어) 또는 계산가능(computable^영어)이라고 정의한다.

이는 지시함수 $1\_S$가 계산 가능 함수인 경우와 동치이다. 즉, 집합 $S$는 지시 함수 $\backslash mathbb\{1\}\_\{S\}$가 계산 가능일 때와 경우에만 계산 가능하다.

3. 예시

다음은 재귀적 집합의 예시이다.

* 자연수의 유한 부분집합 또는 쌍대 유한 부분집합
* 공집합
* 자연수 전체
* 각 자연수
* 소수
* 재귀 언어
* 괴델 수

3.1. 기본적인 예시

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

3.2. 형식 언어 및 수론 관련 예시

* 재귀 언어는 형식 언어 집합의 재귀 부분집합이다.
* 괴델의 불완전성 정리에서 사용된 산술 증명의 괴델 수 집합은 재귀 집합이다.

3.3. 계산 불가능한 집합 (비예시)

* 정지하는 튜링 기계의 집합은 계산 가능하지 않다.
* 두 유한 단체 복합체의 동형 사상류는 계산 가능하지 않다.
* 바쁜 비버 챔피언의 집합은 계산 가능하지 않다.
* 힐베르트의 열 번째 문제는 계산 가능하지 않다.

4. 성질

집합 $A$와 $B$가 재귀 집합이면, $A\; \backslash cap\; B$ (교집합), $A\; \backslash cup\; B$ (합집합), $A\; \backslash times\; B$의 칸토어 쌍 함수에 의한 상 등도 재귀 집합이다. 집합 $A$가 재귀 집합일 필요충분조건은 $A$와 $A$의 여집합이 모두 재귀 열거 집합이라는 것이다. 재귀 집합의 전역 계산가능 함수에 대한 원상은 재귀 집합이다.

집합이 재귀 집합일 필요충분조건은 산술 위계 $\backslash Delta^0\_1$에 속하는 것이다. 만약 A가 계산 가능한 집합이라면, A의 여집합 또한 계산 가능한 집합이다. A와 B가 계산 가능한 집합이라면, A ∩ B, A ∪ B, 그리고 A × B의 칸토어 쌍 함수에 의한 상은 계산 가능한 집합이다.

A는 A와 A의 여집합이 모두 계산가능한 열거 집합 (c.e.)일 필요충분조건이다. 전체 계산 가능한 함수 하에서 계산 가능한 집합의 역상은 계산 가능한 집합이다. 전체 계산 가능한 전단사 함수 하에서 계산 가능한 집합의 상은 계산 가능하다. (일반적으로 계산 가능한 함수 하에서 계산 가능한 집합의 상은 c.e.이지만 계산 가능하지 않을 수 있다.)

A는 산술적 위계의 $\backslash Delta^0\_1$ 레벨에 있다면 계산 가능한 집합이다. A는 증가하지 않는 전체 계산 가능한 함수의 범위이거나 공집합일 때 계산 가능한 집합이다. 증가하지 않는 전체 계산 가능한 함수 하에서 계산 가능한 집합의 상은 계산 가능하다.