재귀 열거 집합

계산 이론에서 재귀적 열거 가능 집합(Recursively enumberable set), 귀납적 가산 집합(歸納的可算集合)은 다음 조건을 만족하는 집합 S를 말한다.

• 집합 S의 모든 원소에 대해서만 진리값 참을 내놓는 알고리즘이 존재한다. (r.e.)

이 정의는 다음과 동치이다.

• 어떤 알고리즘을 이용해 집합 S의 원소를 처음부터 하나씩 열거(자연수로의 단사 함수)해 모두 세어 나갈 수 있다. 곧 출력이 s1, s2, s3... 와 같은 식으로 S의 원소의 목록이다. 이 알고리즘은 필요하다면 무한한 시간 동안 작동할 수도 있다.

계산 복잡도 이론에서 이와 같은 집합을 모임 RE (복잡도)로 분류한다. (c.e.)

이외에 열거 가능 집합(enumerable set), 계산 열거 가능 집합(computably enumerable set), 준결정성 집합(semidecidable set), 튜링 인식 가능 집합(Turing-recognizable set) 등으로도 불린다. 줄여서 r.e. 또는 c.e.라고 쓰이기도 한다.

형식적 정의

자연수로 구성된 한 집합 S에 대하여, 정의역이 정확히 S인 부분 재귀 함수 f가 존재할 때 S를 재귀적으로 열거가능하다고 한다. 이는 f가 정의된다는 것과 f의 입력이 S의 원소라는 것이 동치임을 의미한다.

다른 표현

다음은 자연수의 집합 S에 관하여 재귀적 열거가능성과 동치인 성질들이다.

준결정가능성(semidecidability):

• 집합 S는 재귀적으로 열거가능하다. 즉, S는 부분 재귀 함수의 정의역이다.
• 다음의 성질을 만족시키는 부분 재귀함수 f가 존재한다:

$f(x)=\left\{{\begin{matrix}1&{\mbox{if}}\ x\in S\\{\mbox{undefined/does not halt}}\ &{\mbox{if}}\ x\notin S\end{matrix}}\right.$

열거가능성:

• 집합 S는 부분 재귀함수의 치역이다.
• 집합 S는 전체 재귀함수의 치역이거나 공집합이다. 만약 S가 무한집합이라면 함수는 단사함수일 수도 있다.
• 집합 S는 원시 재귀함수의 치역이거나 공집합이다. 만약 S가 무한집합이라도 단사는 되지 않는다.

디오판토스 방정식:

• 다음과 같은 다항식 p가 존재한다: 정수의 계수를 가지며 변수 x, a, b, c, d, e, f, g, h, i 의 치역이 자연수 전체에 해당함.

$x\in S\Leftrightarrow \exists a,b,c,d,e,f,g,h,i\ (p(x,a,b,c,d,e,f,g,h,i)=0).$

(종속 변수의 개수가 꼭 이 정도로 많을 필요는 없다)

• 다음과 같은 정수에서 정수로의 다항식이 존재한다: 집합 S가 치역에서 정확히 음수 아닌 수만을 포함함.

예시

• 모든 재귀 집합은 재귀적으로 열거가능이지만 그 역은 항상 성립하지는 않는다. (재귀 집합에서 알고리즘은 입력이 집합에 포함되지 않는지도 진술해야 하지만, 재귀열거집합에서는 그럴 필요가 없다.)
• 재귀적으로 열거가능한 언어는 형식 언어의 재귀적으로 열거가능한 부분집합이다.
• 재귀적으로 열거가능하게 주어진 공리계에서 증명가능한 모든 식의 집합은 재귀적으로 열거가능하다.

특성

집합 A와 B가 재귀적 열거가능이면 둘의 교집합, 합집합, 곱집합도 재귀적 열거가능이다. 부분 재귀함수에 대하여 어떠한 재귀 열거가능 집합의 역상은 재귀 열거가능 집합이다.

어떠한 집합 A가 재귀적(계산가능)일 필요충분조건은 A와 A의 여집합이 모두 재귀적으로 열거가능하다는 것이다.

산술 위계로 표현하면 집합이 재귀 열거가능이라는 것은 집합이 위계 $\Sigma _{1}^{0}$ 에 속한다는 것과 동치이다.

처치-튜링 논제에 의하면 모든 효율적으로 계산가능한 함수는 튜링 기계로 계산가능하며, 고로 집합 S가 재귀 열거가능이라는 것은 S의 열거를 출력하는 알고리즘이 존재한다는 것과 동치이다. 그러나 이는 형식적인 정의로 표현되지 않는데, 처치-튜링 논제 자체가 형식적 공리 같은 것이 아닌 비형식적인 추측이기 때문이다.

같이 보기

• 재귀 열거 언어
• 재귀 집합
• 결정 문제