재귀 열거 집합

위키백과, 우리 모두의 백과사전.
(열거 집합에서 넘어옴)
둘러보기로 가기 검색하러 가기

계산 이론에서, 재귀적 열거 가능 집합(Recursively enumberable set), 귀납적 가산 집합(歸納的可算集合)은 다음 조건을 만족하는 집합 S를 말한다.

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

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

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

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

이외에 열거 가능 집합(Enumerable set), 계산 가능 집합(computable set), 준결정성 집합(semidecidable set), 튜링 인식 가능 집합(Turing-recognizable set) 등으로도 불린다.

함께 보기[편집]