재귀 열거 집합

3. 다른 표현

자연수의 집합 S에 대해 재귀적 열거 가능성과 동치인 성질들은 다음과 같다.

• 준결정가능성(semidecidability): 집합 S는 부분 재귀 함수의 정의역이다. 특정 조건을 만족하는 부분 재귀 함수 f가 존재한다.
• 열거가능성: 집합 S는 부분 재귀 함수의 치역이다. S는 전체 재귀 함수의 치역이거나 공집합이며, 무한집합이면 단사 함수일 수 있다. S는 원시 재귀 함수의 치역이거나 공집합이지만, 무한집합이라도 단사는 아니다.
• 디오판토스 방정식: 특정 조건을 만족하는 다항식 p가 존재한다. 집합 S가 치역에서 음이 아닌 정수만을 포함하는 정수 다항식이 존재한다.

3. 1. 준결정가능성 (Semidecidability)

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

3. 2. 열거가능성 (Enumerability)

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

3. 3. 디오판토스 방정식 (Diophantine Equation)

4. 예시

• 모든 재귀 집합은 재귀적으로 열거 가능하지만 그 역은 항상 성립하지 않는다. 재귀 집합은 입력이 집합에 포함되지 않는지 여부도 알고리즘으로 판별해야 하지만, 재귀 열거 집합에서는 그럴 필요가 없다.
• 재귀 열거 언어는 형식 언어의 재귀적으로 열거 가능한 부분집합이다.
• 재귀적으로 열거 가능하게 주어진 공리계에서 증명 가능한 모든 식의 집합은 재귀적으로 열거 가능하다.
• 마티야세비치 정리에 따르면, 모든 재귀적 열거 집합은 디오판토스 집합이다(역도 명백히 참이다).
• 단순 집합은 재귀적 열거 집합이지만 재귀적이지 않다.
• 창조적 집합은 재귀적 열거 집합이지만 재귀적이지 않다.
• 생산적 집합은 재귀적 열거 집합이 아니다.
• 계산 가능한 함수의 괴델 넘버링 $\backslash phi$가 주어졌을 때, 집합 $\backslash \{\backslash langle\; i,x\; \backslash rangle\; \backslash mid\; \backslash phi\_i(x)\; \backslash downarrow\; \backslash \}$(여기서 $\backslash langle\; i,x\; \backslash rangle$는 칸토어 페어링 함수이고, $\backslash phi\_i(x)\backslash downarrow$는 $\backslash phi\_i(x)$가 정의됨을 나타낸다)는 재귀적 열거 집합이다. 이 집합은 각 튜링 기계가 정지하는 입력 매개변수를 설명하므로 정지 문제를 인코딩한다.
• 계산 가능한 함수의 괴델 넘버링 $\backslash phi$가 주어졌을 때, 집합 $\backslash \{\; \backslash left\; \backslash langle\; x,\; y,\; z\; \backslash right\; \backslash rangle\; \backslash mid\; \backslash phi\_x(y)\; =\; z\; \backslash \}$는 재귀적 열거 집합이다. 이 집합은 함수 값을 결정하는 문제를 인코딩한다.
• 자연수에서 자연수로의 부분 함수 ''f''가 주어졌을 때, ''f''의 그래프, 즉 ''f''(''x'')가 정의되는 모든 쌍 $\backslash langle\; x,f(x)\backslash rangle$의 집합이 재귀적 열거 집합인 경우에만 ''f''는 부분 계산 가능 함수이다.

5. 특성

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

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

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

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

만약 ''A''와 ''B''가 계산가능 열거 집합이면, ''A'' ∩ ''B'', ''A'' ∪ ''B'', 그리고 ''A'' × ''B'' (자연수의 순서쌍이 칸토어 쌍 함수를 사용하여 단일 자연수로 매핑됨)는 계산가능 열거 집합이다. 부분 계산 가능 함수에 대한 계산가능 열거 집합의 원상은 계산가능 열거 집합이다.

집합 $T$는 그 여집합 $\backslash mathbb\{N\}\; \backslash setminus\; T$가 계산가능 열거 집합이면 '''공-계산가능-열거''' 또는 '''공-c.e.'''라고 불린다. 동등하게, 집합이 co-r.e.인 것은 그 집합이 산술적 위계의 $\backslash Pi^0\_1$ 수준에 있을 때이다. 공-계산가능-열거 집합의 복잡도 클래스는 co-RE로 표기된다.

일부 계산가능 열거 집합 쌍은 효과적으로 분리 가능하고, 일부는 그렇지 않다.

참조

_[1] 서적 Algorithmic Randomness and Complexity https://books.google[...] Springer Science & Business Media 2010-10-29
_[2] 논문 Three Theorems on Recursive Enumeration. I. Decomposition. II. Maximal Set. III. Enumeration Without Duplication 1958