재귀 열거 집합 문서 원본 보기

{{위키데이터 속성 추적}}
[[계산 이론]]에서 '''재귀적 열거 가능 집합'''(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가 존재한다:
::<math>f(x) = 
\left\{\begin{matrix}
1 &\mbox{if}\ x \in S \\
\mbox{undefined/does not halt}\ &\mbox{if}\ x \notin S
\end{matrix}\right.
</math>
:열거가능성:
:* 집합 S는 부분 재귀함수의 치역이다.
:* 집합 S는 전체 재귀함수의 치역이거나 공집합이다. 만약 S가 무한집합이라면 함수는 [[단사함수]]일 수도 있다.
:* 집합 S는 [[원시 재귀함수]]의 치역이거나 공집합이다. 만약 S가 무한집합이라도 단사는 되지 않는다.
:[[디오판토스 방정식]]:
:* 다음과 같은 다항식 p가 존재한다: 정수의 계수를 가지며 변수 ''x'', ''a'', ''b'', ''c'', ''d'', ''e'', ''f'', ''g'', ''h'', ''i'' 의 치역이 자연수 전체에 해당함.
::<math>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).</math>
::(종속 변수의 개수가 꼭 이 정도로 많을 필요는 없다)
:* 다음과 같은 정수에서 정수로의 다항식이 존재한다: 집합 S가 치역에서 정확히 음수 아닌 수만을 포함함.

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

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

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

[[산술 위계]]로 표현하면 집합이 재귀 열거가능이라는 것은 집합이 위계 <math>\Sigma^0_1</math> 에 속한다는 것과 동치이다.

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

== 같이 보기 ==
* [[재귀 열거 언어]]
* [[재귀 집합]]
* [[결정 문제]]

{{집합론}}
{{계산 이론}}
{{토막글|컴퓨터}}

[[분류:계산 이론]]
[[분류:계산 가능성 이론]]