Primitive recursive
숙어C2formal수학·컴퓨터 과학에서 기본 함수와 제한된 재귀로 정의될 수 있는
phrase
- 1
초기 함수, 합성, 원시 재귀만을 사용하여 정의할 수 있는 함수나 술어를 나타내는 말C2
Used of a function or predicate that can be defined from initial functions by composition and primitive recursion only.
Addition and multiplication are primitive recursive functions.
덧셈과 곱셈은 primitive recursive 함수이다.
The Ackermann function is computable but not primitive recursive.
아커만 함수는 계산 가능하지만 primitive recursive는 아니다.
뉘앙스 · 쓰임
recursive는 단순히 자기 자신을 다시 호출하거나 반복적으로 정의되는 것을 넓게 가리키지만, primitive recursive는 허용된 구성 규칙이 엄격히 제한된 전문 용어입니다. computable은 계산 가능한 함수를 더 넓게 말하며, primitive recursive보다 범위가 큽니다. total recursive는 항상 값이 정의되는 계산 가능 함수를 뜻하지만, primitive recursive보다 더 넓은 개념입니다.
일상 대화에서는 거의 쓰지 않으며, 논문·강의·교재 등에서 사용합니다. 하이픈을 넣어 primitive-recursive라고 쓰기도 하며, 명사 앞에서는 primitive recursive function처럼 씁니다. '원시적'이라는 한국어 직역 때문에 미개하거나 낡았다는 뜻으로 오해하면 안 됩니다.
유의어 뉘앙스 비교
- PR
- primitive recursive의 약어로, 논문이나 강의 노트에서 자주 쓰이지만 처음에는 풀어 쓰는 것이 좋습니다.
- primitive-recursive
- 하이픈을 넣은 철자로, 특히 명사 앞에서 형용사처럼 쓸 때 보입니다. 의미 차이는 거의 없습니다.
반의어
- not primitive recursive
- 가장 직접적인 반의 표현으로, 계산 가능하더라도 원시 재귀의 범위를 넘어서는 경우에 씁니다.
- non-primitive-recursive
- 더 전문적이고 압축적인 표현으로, 학술 문체에서 쓰입니다.
어원 · 암기 팁
[English]primitive는 라틴어 primitivus에서 온 말로 '초기의, 기본적인'이라는 뜻이고, recursive는 '되돌아가다'라는 뜻의 라틴어 recurrere와 관련됩니다. 수리논리학에서 기본 함수와 제한된 재귀 규칙으로 정의되는 함수의 부류를 가리키는 용어로 자리 잡았습니다.
💡 primitive를 '기본 블록', recursive를 '이전 값으로 다음 값을 만드는 규칙'으로 기억하면 좋습니다. 즉 primitive recursive는 '기본 블록에서 출발해 제한된 재귀로 쌓아 올린 함수'라고 이해하면 됩니다.