재귀 열거 집합

1. 개요

재귀 열거 집합은 자연수의 집합 S에 대해, S가 부분 재귀 함수의 정의역이 되는 경우를 의미한다. 이는 S의 원소인 입력에 대해서만 함수가 정의됨을 뜻하며, 계산 가능 열거 집합이라고도 불린다. 재귀 열거 가능성은 준결정가능성, 열거가능성, 디오판토스 방정식과 같은 다양한 방식으로 표현될 수 있다. 모든 재귀 집합은 재귀적으로 열거 가능하지만 그 역은 성립하지 않으며, 재귀 열거 집합의 교집합, 합집합, 곱집합은 모두 재귀적으로 열거 가능하다. 집합과 그 여집합이 모두 재귀적으로 열거 가능하면 해당 집합은 재귀 집합이 된다.

2. 형식적 정의

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

이 정의는 임의의 가산 집합 A로 확장할 수 있다. 이를 위해서는, A의 원소를 괴델 수로 나타내고, 만약 대응하는 괴델 수의 집합이 귀납적 가산이라면 A의 어떤 부분 집합이 귀납적 가산이 되는지를 말하면 된다.

다음은 자연수 집합 S에 대해 동일한 특성을 표현한 것이다.

3. 다른 표현

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

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

반결정가능성과 열거 가능성의 동치는 도브테일링 기술을 통해 얻을 수 있다.

계산 가능 열거 가능 집합의 디오판토스 특성은 유리 마티야세비치가 힐베르트의 열 번째 문제에 대한 부정적인 해의 일부로 발견했다. 디오판토스 집합은 재귀 이론보다 먼저 존재하므로 역사적으로 이러한 집합을 설명하는 첫 번째 방법이었다.

3.1. 준결정가능성 (Semidecidability)

* 집합 S는 부분 재귀 함수의 정의역으로, 재귀적으로 열거 가능하다.
* 다음 성질을 만족시키는 부분 재귀 함수 f가 존재한다:
::$f(x)\; =$
\left\{\begin{matrix}
1 &\mbox{if}\ x \in S \\
\mbox{정의되지 않음/멈추지 않음}\ &\mbox{if}\ x \notin S
\end{matrix}\right.

3.2. 열거가능성 (Enumerability)

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

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

다음은 정수 계수를 가지며 변수 x, a, b, c, d, e, f, g, h, i의 치역이 자연수 전체에 해당하는 다항식 p가 존재함을 나타낸다.

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

또한, 집합 S가 치역에서 정확히 음수가 아닌 수만을 포함하는 정수에서 정수로의 다항식이 존재한다.

이러한 디오판토스 방정식의 성질은 유리 마티야세비치가 힐베르트의 열 번째 문제에 대한 부정적인 해를 제시하는 과정에서 발견되었다. 디오판토스 집합은 재귀 이론보다 먼저 존재했기 때문에, 역사적으로 이러한 집합을 설명하는 첫 번째 방법이었다. 그러나 이 동치 관계는 계산 가능 열거 가능 집합이 도입된 지 30년이 지나서야 언급되었다.

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의 열거를 출력하는 알고리즘이 존재한다는 것과 동치이다. 그러나 이는 형식적인 정의로 표현되지 않는데, 처치-튜링 논제 자체가 형식적 공리 같은 것이 아닌 비형식적인 추측이기 때문이다.

만약 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로 표기된다.

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