재귀 열거 집합

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

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

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

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

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

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

함께 보기[편집]