재귀 열거 집합

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

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

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

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

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

함께 보기[편집]