재귀 열거 집합
재귀 열거 집합 (Recursively Enumerable Set, RE 집합)은 계산 가능성 이론에서 중요한 개념으로, 튜링 기계 또는 다른 계산 모델을 사용하여 정의할 수 있는 집합의 일종입니다. 집합 S가 재귀 열거 집합이라는 것은 다음 조건 중 하나를 만족한다는 의미입니다.
- S가 비어있는 집합이다.
- S에 속하는 모든 원소를 순서대로 생성해내는 알고리즘(튜링 기계)이 존재한다. 즉, 해당 알고리즘은 S의 원소를 차례대로 출력하며, S의 모든 원소는 언젠가는 출력된다. 이 때, 알고리즘이 유한 시간 안에 멈출 필요는 없다.
다른 말로 표현하면, 어떤 원소 x가 집합 S에 속하는지 확인할 수 있는 알고리즘이 존재하며, x가 S에 속하면 그 알고리즘은 언젠가 '참'을 반환하고, x가 S에 속하지 않으면 그 알고리즘은 영원히 멈추지 않거나 '거짓'을 반환한다. 이와 대조적으로, 재귀 집합은 어떤 원소가 집합에 속하는지 여부를 항상 결정할 수 있는 알고리즘이 존재하는 집합을 의미합니다. 즉, 재귀 집합은 원소가 집합에 속하면 '참'을, 속하지 않으면 '거짓'을 반환하는 알고리즘이 존재합니다.
모든 재귀 집합은 재귀 열거 집합이지만, 그 역은 성립하지 않습니다. 즉, 재귀 열거 집합 중에는 재귀 집합이 아닌 것들이 존재합니다. 이러한 집합의 예로는 정지 문제 (Halting Problem)가 있습니다. 정지 문제는 튜링 기계의 입력과 설명을 받았을 때, 그 튜링 기계가 유한 시간 안에 멈추는지 무한 루프에 빠지는지를 결정하는 문제입니다. 정지 문제에 대한 입력들의 집합은 재귀 열거 집합이지만, 재귀 집합은 아닙니다.
재귀 열거 집합은 이론 컴퓨터 과학에서 다양한 문제의 계산 복잡성을 분석하고, 알고리즘의 한계를 이해하는 데 중요한 역할을 합니다.