Co-recursively enumerable
숙어C2formal여집합이 재귀적으로 열거 가능한, 즉 ‘아님’을 반결정할 수 있는
phrase
- 1
어떤 집합, 언어, 문제의 여집합이 재귀적으로 열거 가능한 성질; 즉 비소속 여부를 튜링 기계가 언젠가 받아들여 확인할 수 있는 성질.C2
A property of a set, language, or problem whose complement is recursively enumerable; equivalently, non-membership can be semidecided by a Turing machine.
The complement of the halting set is co-recursively enumerable but not recursively enumerable.
정지 집합의 여집합은 co-recursively enumerable이지만 recursively enumerable은 아니다.
If a language is both recursively enumerable and co-recursively enumerable, then it is decidable.
어떤 언어가 recursively enumerable이면서 co-recursively enumerable이면, 그 언어는 판정 가능하다.
뉘앙스 · 쓰임
‘recursively enumerable’은 어떤 집합의 원소임을 반결정할 수 있다는 뜻이고, ‘co-recursively enumerable’은 원소가 아님을 반결정할 수 있다는 뜻입니다. ‘decidable’ 또는 ‘recursive’는 원소인지 아닌지를 모두 유한 시간 안에 판정할 수 있다는 더 강한 의미입니다. 따라서 한 집합이 recursively enumerable이면서 co-recursively enumerable이면 decidable입니다.
일상 영어 표현이나 속담이 아니라 수학·컴퓨터 과학의 고정 전문 용어입니다. ‘co-’는 ‘함께’라는 일반적 뜻이 아니라 보통 ‘여집합/complement’과 관련된 뜻으로 이해해야 합니다. 문맥에 따라 ‘set’, ‘language’, ‘problem’과 함께 쓰이며, 하이픈을 넣어 ‘co-recursively enumerable’로 쓰는 것이 표준적입니다.
유의어 뉘앙스 비교
- co-r.e.
- 같은 뜻의 축약형으로, 논문이나 강의 노트에서 자주 쓰입니다.
- co-RE
- 같은 뜻의 대문자 약어로, theoretical computer science 문맥에서 흔합니다.
- complement recursively enumerable
- 의미를 더 풀어서 설명하는 표현으로, ‘여집합이 재귀적으로 열거 가능하다’는 점을 직접 드러냅니다.
- Π₁⁰
- 산술 계층에서의 관련 표기입니다. 모든 문맥에서 완전히 같은 말처럼 쓰기보다는 형식 논리학적 분류로 이해해야 합니다.
반의어
- recursively enumerable
- 원소임을 반결정할 수 있다는 뜻입니다. 엄밀한 논리적 반의어라기보다 대비되는 개념이며, 어떤 집합은 둘 다일 수 있습니다.
- not co-recursively enumerable
- 여집합이 재귀적으로 열거 가능하지 않다는 직접적인 부정 표현입니다.
어원 · 암기 팁
[English]‘recursively enumerable’은 계산 가능성 이론에서 튜링 기계나 재귀 함수로 원소들을 열거할 수 있는 집합을 가리키는 용어로 자리 잡았습니다. 앞의 ‘co-’는 ‘complement’의 뜻을 나타내며, 따라서 ‘co-recursively enumerable’은 ‘그 자체가 아니라 여집합이 recursively enumerable인’ 경우를 뜻합니다.
💡 ‘co-’를 ‘complement’로 기억하세요. 즉 co-RE는 ‘RE of the complement’, 곧 ‘여집합이 RE’라고 외우면 됩니다.