재귀 열거 집합
From Wikipedia, the free encyclopedia
계산 이론에서 재귀적 열거 가능 집합(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.라고 쓰이기도 한다.