Recursively enumerable
숙어C2formal알고리즘으로 원소를 차례로 나열할 수 있는
phrase
- 1
집합이나 형식 언어의 모든 원소를 어떤 알고리즘 또는 튜링 기계가 유한한 시간 안에 하나씩 출력할 수 있는 성질을 가진.C2
having the property that all members of a set or formal language can be generated or listed by some algorithm or Turing machine.
The set of all valid proofs in this formal system is recursively enumerable.
이 형식 체계에서 모든 유효한 증명의 집합은 재귀적으로 열거 가능하다.
A recursively enumerable language may not be decidable, because the machine can run forever on inputs outside the language.
재귀적으로 열거 가능한 언어는 그 언어에 속하지 않는 입력에서 기계가 영원히 실행될 수 있으므로 결정 가능하지 않을 수도 있다.
뉘앙스 · 쓰임
‘recursive’는 보통 멈추는 결정 절차가 있어 소속 여부를 항상 판정할 수 있다는 뜻이고, ‘recursively enumerable’은 원소를 나열하거나 긍정 사례를 언젠가 확인할 수 있다는 더 약한 뜻입니다. ‘computably enumerable’은 거의 같은 의미의 현대적 표현이며, ‘semidecidable’은 판정 문제 관점에서 본 같은 개념에 가깝습니다.
일상 영어의 관용구가 아니라 수학·이론 컴퓨터 과학의 고정된 전문 표현입니다. 일반 글에서는 독자가 이 분야 배경지식이 없으면 설명을 붙이는 것이 좋습니다. 현대 문헌에서는 ‘recursively enumerable’ 대신 ‘computably enumerable’을 쓰는 경우가 많지만, 약어 ‘r.e.’는 여전히 널리 보입니다.
유의어 뉘앙스 비교
- computably enumerable
- 거의 같은 뜻의 현대적 표현으로, 최근 문헌에서 더 선호되는 경우가 많습니다.
- semidecidable
- 열거 가능성보다 판정 절차의 관점, 즉 속하는 경우에는 언젠가 받아들이지만 속하지 않는 경우에는 멈추지 않을 수 있다는 점을 강조합니다.
- Turing-recognizable
- 특히 형식 언어에 대해 튜링 기계가 인식할 수 있다는 관점을 강조합니다.
반의어
- decidable
- 모든 입력에 대해 유한 시간 안에 예/아니요를 판정할 수 있다는 더 강한 성질입니다. 엄밀한 반의어라기보다 대비되는 개념입니다.
- not recursively enumerable
- 알고리즘으로 원소를 모두 나열할 수 없는 경우를 직접적으로 가리키는 부정 표현입니다.
어원 · 암기 팁
[English]‘recursive’는 계산 이론에서 ‘효과적으로 계산 가능한’ 절차를 가리키던 전통적 용어에서 왔고, ‘enumerable’은 ‘하나씩 세거나 나열할 수 있는’이라는 뜻입니다. 따라서 ‘recursively enumerable’은 원래 ‘재귀적/계산 가능한 절차로 나열할 수 있는’이라는 의미로 형성된 전문 표현입니다.
💡 ‘enumerate’가 ‘열거하다’라는 뜻이므로, recursively enumerable은 ‘컴퓨터가 규칙적으로 하나씩 출력할 수 있다’고 기억하면 됩니다. 단, ‘항상 멈춰서 판정한다’가 아니라 ‘속하는 것은 언젠가 나온다’는 점을 함께 기억하세요.