재귀 열거 집합

재귀 열거 집합(Recursively enumberable set, 귀납 가산 집합), 가산 집합(computable set), 준결정성 집합(semidecidable set), 튜링 인식 가능 집합(Turing-recognizable set)은 다음 조건을 만족하는 집합 S를 말한다.

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

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

• 어떤 알고리듬을 이용해 집합 S의 원소를 처음부터 하나씩 나열해 모두 세어 나갈 수 있다.

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

함께 보기

• 가산 집합
• 재귀 열거 언어