원시 재귀 함수

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

원시 재귀 함수는 자연수에서 자연수로의 함수인 수론적 함수로, 기본적인 함수와 연산자를 유한 번 적용하여 얻을 수 있다. 기본적인 함수에는 상수 함수, 따름수 함수, 사영 함수가 있으며, 연산자로는 합성 함수와 원시 재귀가 있다. 덧셈, 곱셈, 지수, 팩토리얼과 같은 다양한 수론적 함수가 원시 재귀 함수로 정의될 수 있다. 원시 재귀 함수는 전재귀 함수이지만, 모든 전재귀 함수가 원시 재귀 함수는 아니며, 아커만 함수가 그 예시이다. 원시 재귀 함수는 LOOP 프로그래밍 언어로 프로그래밍할 수 있으며, 수학적 유한주의와 관련이 깊다. 리하르트 데데킨트가 1888년 원시 재귀의 구성을 제시했으며, 현재의 용어는 로자 페테르에 의해 만들어졌다.

더 읽어볼만한 페이지

재귀 - 무한 루프
무한 루프는 컴퓨터 프로그램에서 루프가 종료되지 않고 무한히 반복되는 현상으로, 프로그램 오류나 의도적인 경우에 발생하며 시스템 응답 불능을 초래하거나 특정 상황에서 사용되기도 한다.
재귀 - 점화식
점화식은 수열의 각 항을 이전 항들의 함수로 표현하는 방정식으로, 피보나치 수열, 로지스틱 맵, 이항 계수 등의 예시가 있으며, 선형대수학이나 Z변환 등을 이용하여 풀고 다양한 분야에 응용된다.
계산 이론 - 튜링 완전
튜링 완전은 계산 이론에서 시스템이 튜링 기계와 동등한 계산 능력을 갖춰 튜링 기계가 계산할 수 있는 모든 함수를 계산하고 범용 튜링 기계를 시뮬레이션할 수 있음을 의미하며, 튜링 동등이라고도 한다.
계산 이론 - 디지털 물리학
디지털 물리학은 우주를 거대한 디지털 컴퓨터로 보고 정보 이론, 통계 역학, 양자역학 등을 융합하여 우주의 작동 방식을 디지털 계산 과정으로 설명하려는 이론적 관점이다.
계산 가능성 이론 - 처치-튜링 논제
처치-튜링 논제는 모든 효과적인 계산 과정이 튜링 기계로 수행될 수 있다는 가설로, 알고리즘과 계산 가능성의 본질에 대한 논의를 촉발하며 컴퓨터 과학과 철학 분야에서 활발히 연구되고 있다.
계산 가능성 이론 - 튜링 기계
튜링 기계는 앨런 튜링이 제시한 계산 모델로, 테이프 위에서 기계적으로 작동하며, 유한한 상태, 테이프, 헤드, 명령 표를 통해 작동하고, 계산 가능성과 알고리즘의 한계를 연구하는 데 사용된다.

원시 재귀 함수

2. 정의

원시 재귀 함수는 자연수에서 자연수로 가는 함수, 즉 수론적 함수이다. n개의 변수를 받는 함수를 n항 함수라고 한다.

원시 재귀 함수는 몇 가지 기본 함수와 연산들로부터 정의된다. 기본적인 원시 재귀 함수는 다음 공리에 의해 주어진다.^[11]

'''상수 함수''': 0항 함수 0은 원시 재귀 함수이다.
'''따름수 함수''': 1항 함수 S는 인수의 따름수를 반환하는 함수로, 원시 재귀 함수이다. (S(k) = k + 1)
'''사영 함수''': n≥1 이고 1≤i≤n 일 때, n항 함수 $P^n_i$ 는 i번째 인수를 반환하는 함수로, 원시 재귀 함수이다.

더 복잡한 원시 재귀 함수는 다음 공리로 주어지는 연산을 적용하여 얻을 수 있다.

'''합성''': k항 원시 재귀 함수 f와 k개의 m항 원시 재귀 함수 $g_1,...,g_k$ 가 주어졌을 때, f와 $g_1,...,g_k$ 의 합성 함수, 즉 m항 함수 $h(x_1,\ldots,x_m) = f(g_1(x_1,\ldots,x_m),\ldots,g_k(x_1,\ldots,x_m))$ 는 원시 재귀 함수이다.
'''원시 재귀''': k항 원시 재귀 함수 f와 (k+2)항 원시 재귀 함수 g가 주어졌을 때, (k+1)항 함수 h는 f와 g의 원시 재귀로 정의된다. 즉, 다음이 성립하면 h는 원시 재귀 함수이다.
$h (0, x_1, \ldots, x_k) = f (x_1, \ldots, x_k)$
$h (S(y), x_1, \ldots, x_k) = g (y, h (y, x_1, \ldots, x_k), x_1, \ldots, x_k)$

위에 주어진 기본 함수들에 연산들을 유한 번 적용하여 얻을 수 있는 함수가 '''원시 재귀 함수'''이다.

2. 1. 기본 함수

원시 재귀 함수는 몇 가지 기본 함수로부터 시작하여 더 복잡한 함수를 만들어 나가는 방식이다. 기본 함수는 다음 세 가지가 있다.^[11]

상수 함수: 0항 함수 0
따름수 함수: 1항 함수 S(k) = k + 1
사영 함수: n≥1 이고 1≤i≤n 일 때, n항 함수 $P^n_i$ 는 i번째 인수를 반환.

이 기본 함수들은 자연수에서 자연수로 가는 함수, 즉 수론적 함수이며, n개의 변수를 받는 함수는 n항 함수라고 불린다.

2. 1. 1. 상수 함수

모든 자연수 n과 k에 대해, k항 상수 함수

C_n^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\  n

은 원시 재귀 함수이다.^[11] 특히, 0항 상수 함수 0은 원시 재귀 함수이다.^[11]

2. 1. 2. 따름수 함수

1항 따름수 함수 S(x)는 인수의 따름수를 반환하는 함수로, 원시 재귀 함수이다. S(x)는 x + 1로 정의된다.^[11] 이는 페아노 공리를 따른다.

2. 1. 3. 사영 함수

모든 자연수

n \ge 1

과

1 \le i \le n

에 대해,

n

항 사영 함수

P_i^n(x_1, \ldots, x_n) = x_i

는 원시 재귀 함수이다.^[11] 이 함수는

i

번째 인수를 반환한다.

사영 함수를 사용하면, 앞서 언급한 함수군에서 인수의 개수를 변경할 수 있다. 사영 함수의 합성을 통해 어떤 함수의 인수의 부분 집합을 다른 함수에 전달할 수 있다. 예를 들어, 2항 원시 재귀 함수 ''g''와 ''h''를 다음과 같이 합성할 수 있다.

:

f(a,b,c) = g(h(a,c),h(a,b)) \!

''f''도 원시 재귀적이다. 사영 함수에 의한 형식적 정의는 다음과 같다.

:

f(a,b,c) = g(h(P^3_1(a,b,c),P^3_3(a,b,c)),h(P^3_1(a,b,c),P^3_2(a,b,c))

.

2. 2. 연산

원시 재귀 함수는 기본적인 함수에 주어진 연산을 유한 번 적용하여 얻을 수 있다. 이러한 연산에는 합성 연산과 원시 재귀 연산이 있다.^[11]

합성 연산은 여러 함수를 결합하여 새로운 함수를 만드는 방법이며, 원시 재귀 연산은 초기 조건과 반복 규칙을 통해 함수를 정의하는 방식이다.

2. 2. 1. 합성

k항 원시 재귀 함수 ''f''와 k개의 m항 원시 재귀 함수 ''g''₁, ..., ''g''_''k''가 주어졌을 때, ''f''와 ''g''₁, ..., ''g''_''k''의 합성 함수, 즉 m항 함수 ''h''(''x''₁, ..., ''x''_''m'') = ''f''(''g''₁(''x''₁, ..., ''x''_''m''), ..., ''g''_''k''(''x''₁, ..., ''x''_''m''))는 원시 재귀 함수이다.^[11]

2. 2. 2. 원시 재귀

k항 원시 재귀 함수 f와 (k+2)항 원시 재귀 함수 g가 주어졌을 때, (k+1)항 함수 h는 다음과 같이 정의되며, 이는 원시 재귀 함수이다.^[11]

:

h (0, x_1, \ldots, x_k) = f (x_1, \ldots, x_k) \,

:

h (S(y), x_1, \ldots, x_k) = g (y, h (y, x_1, \ldots, x_k), x_1, \ldots, x_k) \,.

여기서,

`S(y)`는 y의 따름수를 나타낸다 (즉, `S(y) = y + 1`).
`h`는 `f`와 `g`의 원시 재귀로 정의된다.

함수

f

는 첫 번째 인수의 값까지

0

부터의 for-루프 역할을 한다. 여기서

x_1,\ldots,x_k

로 표시된

f

의 나머지 인수들은 계산 중에 사용될 수 있지만 변경할 수 없는 for-루프에 대한 초기 조건 집합이다. 방정식의 오른쪽에 있는 함수

g

와

h

는 계산을 수행하는 루프의 본체를 나타낸다. 함수

g

는 초기 계산을 수행하기 위해 한 번만 사용된다. 루프의 후속 단계에 대한 계산은

h

에 의해 수행된다.

h

의 첫 번째 매개변수는 for-루프의 "현재" 인덱스 값을 받는다.

h

의 두 번째 매개변수는 이전 단계의 for-루프의 이전 계산 결과를 받는다.

h

의 나머지 매개변수는 앞서 언급한 for-루프에 대한 변경할 수 없는 초기 조건이다.

3. 예시

다양한 수론적 함수들이 원시 재귀 함수로 정의될 수 있다. 인수가 하나인 많은 재귀적으로 정의된 수론적 함수는 원시 재귀적이다. 기본적인 예시로 덧셈, "제한된 뺄셈", 곱셈 함수가 있다.

기본 함수:
$C_0^1(x) = 0$ (모든 입력에 대해 0을 반환)
$C_1^1(x) = 1$ (모든 입력에 대해 1을 반환)
$C_3^0 = 3$ (상수)
$P_1^1(x) = x$ (항등 함수)
$P_1^2(x,y) = x$ , $P_2^2(x,y) = y$ (투영 함수)
$(S \circ S)(x) = x+2$ (입력에 2를 더함)
$(S \circ C_0^1)(x) = 1$ (모든 입력에 대해 1을 반환, $C_1^1$ 과 동일)
모든 $C_n^k$ 는 $S$ 와 $C_0^k$ 의 합성으로 표현 가능하며, $C_0^k = C_0^1 \circ P_1^k$

원시 재귀 함수 예시:
덧셈: a+b
곱셈: a*b
거듭제곱: a^b
계승 a! : 0! = 1, a'! = a!*a'
pred(a): 감소: a>0이면 a-1, 그렇지 않으면 0
뺄셈: a ∸ b (a ≥ b이면 a-b, 그렇지 않으면 0)
최소 (a₁, ... a_n)
최대 (a₁, ... a_n)
절댓값: | a-b | =_def a ∸ b + b ∸ a
~sg(a): NOT[signum(a}]: a=0이면 sg(a)=1, 그렇지 않고 a>0이면 sg(a)=0
sg(a): signum(a): a=0이면 sg(a)=0, 그렇지 않고 a>0이면 sg(a)=1
나머지 (a, b): a가 b로 나누어 떨어지지 않는 경우의 나머지
나눗셈 [ a | b ]: 나머지가 0인 경우
s = b: sg | a - b |
a < b: sg( a' ∸ b )
a | b: 나눗셈
Pr(a): a는 소수 Pr(a) =_def a>1 & NOT(Exists c)_{1 [ c|a ]}
P_i: i+1번째 소수
(a)_i : p_i =_def μx [ _{x [p_i^x|a & NOT(p_i ^x'|a ]의 지수 a_i . μx는 최소화 연산자.}
lh(a): a의 "길이" 또는 사라지지 않는 지수(non-vanishing exponents)의 개수
a*b: a와 b가 소인수일 때, a*b는 소인수의 곱셈 결과를 나타낸다.
lo(x, y): 밑 y에서의 x의 로그

원시 재귀적 함수/술어/결합자:
함수 Ψ와 상수 q₁, ... q_n에서 명시적으로 정의 가능한 함수는 Ψ에서 원시 재귀적이다.
총합 Σ_{y ψ('''x''', y)와 총곱 Π_{yψ('''x''', y)는 ψ에서 원시 재귀적이다.}}
술어 Q의 각 인수를 함수 χ₁ , ..., χ_m으로 대체한 술어는 χ₁, ..., χ_m, Q에서 원시 재귀적이다.
부정(NOT), 논리합(V), 논리곱(&), 함의(→), 동치(≡) 술어는 Q와 R에서 원시 재귀적이다.
(Ey)_{y R('''x''', y), (y)_{y R('''x''', y), μy_{y R('''x''', y) 술어는 술어 R에서 원시 재귀적이다.}}}
경우에 따른 정의는 상호 배타적인 술어와 함께 사용될 때 원시 재귀적이다.
φ(y, '''x''') = χ(y, NOT-φ(y; x₂, ... x_n ), x₂, ... x_n를 만족할 때 χ에서 φ는 원시 재귀적이다.

지수와 소수 판별법은 원시 재귀적이다.^[1]

3. 1. 덧셈

2항 함수

Add

는 인수의 합을 계산하며, 원시 재귀 연산자

\rho

를 사용하여 정의할 수 있다. 이를 위해 다음의 방정식을 고려한다.

:

\begin{array}{rcll}0+y & = & y & \text{ 및} \\S(x)+y & = & S(x+y) & . \\\end{array}

위 식은 "원시 재귀 함수 용어"로 다시 표현할 수 있다.

\rho(g,h)

의 정의에서 첫 번째 방정식은

Add(0,y) = g(y) = y

를 얻기 위해

g = P_1^1

을 선택하도록 한다. 두 번째 방정식은

Add(S(x),y) = h(x,Add(x,y),y) = (S \circ P_2^3)(x,Add(x,y),y) = S(Add(x,y))

를 얻기 위해

h = S \circ P_2^3

을 선택하도록 한다. 따라서 덧셈 함수는

Add = \rho(P_1^1,S \circ P_2^3)

로 정의할 수 있다.

계산 예시는 다음과 같다.

:

\begin{array}{lll}& Add(1,7) \\= & \rho(P_1^1,S \circ P_2^3) \; (S(0),7) & \text{ by Def. } Add, S \\= & (S \circ P_2^3)(0,Add(0,7),7) & \text{ by case } \rho(g,h) \; (S(...),...) \\= & S(Add(0,7)) & \text{ by Def. } \circ, P_2^3 \\= & S( \; \rho(P_1^1,S \circ P_2^3) \; (0,7) \; ) & \text{ by Def. } Add \\= & S(P_1^1(7)) & \text{ by case } \rho(g,h) \; (0,...) \\= & S(7) & \text{ by Def. } P_1^1 \\= & 8 & \text{ by Def. } S . \\\end{array}

주어진

Add

에 대해, 1항 함수

Add \circ (P_1^1,P_1^1)

는 인수를 두 배로 만든다. 즉,

(Add \circ (P_1^1,P_1^1))(x) = Add(x,x) = x+x

이다.

인수가 하나인 많은 재귀적으로 정의된 수론적 함수는 원시 재귀적이다. 기본적인 예시로 덧셈과 "제한된 뺄셈" 함수가 있다.

직관적으로 덧셈은 다음 규칙으로 재귀적으로 정의할 수 있다.

:add(0, ''x'') = ''x'',

:add(''n'' + 1, ''x'') = add(''n'', ''x'') + 1.

이를 엄밀한 원시 재귀 함수의 정의에 맞추기 위해 다음과 같이 정의한다.

:add(0, ''x'') = ''P''₁¹(''x''),

:add(S(''n''), ''x'') = ''S''(''P''₁³(add(''n'', ''x''), ''n'', ''x'')).

여기서 ''P''₁³은 3개의 인수를 취하고 첫 번째 인수를 반환하는 사영 함수이며, ''S''는 후자 함수이다.

''P''₁¹은 단순한 항등 함수이며, 이는 원시 재귀 함수의 정의에 맞추기 위해 도입되었다.

3. 2. 뺄셈

Predecessor function^영어 (전임자 함수)는 후임자 함수의 "반대" 역할을 하며,

Pred(0) = 0

및

Pred(S(n)) = n

에 의해 재귀적으로 정의된다. 제한된 뺄셈 함수("monus^영어"라고도 함)는 전임자 함수로부터 정의될 수 있다. 이 함수는 다음 방정식을 만족한다.

:

\begin{array}{rcll}y \stackrel{-}{} 0 & = & y & \text{그리고} \\y \stackrel{-}{} S(x) & = & Pred(y \stackrel{-}{} x) & . \\\end{array}

원시 재귀 함수는 정수가 아닌 자연수를 다루며, 뺄셈은 자연수의 범위에서 닫혀 있지 않기 때문에, 여기서는 제한된 뺄셈 함수를 다룬다. 제한된 뺄셈 함수 sub(''a'', ''b'')^영어는 ''b'' - ''a''가 음수가 아니면 그 값을 반환하고, 음수인 경우에는 ''0''을 반환한다.

전임자 함수를 사용하여 덧셈이 정의되는 것과 비슷하게, 제한된 뺄셈 함수는 다음과 같이 정의된다.

:sub(0, ''x'') = ''P''₁¹(''x''),

:sub(S(''n''), ''x'') = pred(''P''₁³(sub(''n'', ''x''), ''n'', ''x'')).

여기서 sub(''a'', ''b'')^영어는 ''b'' - ''a''를 나타낸다. 원시 재귀적 정의를 단순화하기 위해 인수의 순서를 일반적인 것과 반대로 하고 있으며, 이는 적절한 사영의 합성으로 수정할 수 있다.

3. 3. 곱셈

곱셈은 덧셈과 유사하게 정의될 수 있는데,

Mul = \rho(C_0^1,Add \circ(P_2^3,P_3^3))

로 표현한다. 이 정의는 다음의 잘 알려진 곱셈 방정식을 재현한다.

:

\begin{array}{lll}& Mul(0,y) \\= & \rho(C_0^1,Add \circ(P_2^3,P_3^3)) \; (0,y) & \text{ 정의에 의해 } Mul \\= & C_0^1(y) & \text{ 경우에 따라 } \rho(g,h) \; (0,...)\\= & 0 & \text{ 정의에 의해 } C_0^1 . \\\end{array}

그리고

:

\begin{array}{lll}& Mul(S(x),y) \\= & \rho(C_0^1,Add \circ(P_2^3,P_3^3)) \; (S(x),y) & \text{ 정의에 의해 } Mul \\= & (Add \circ(P_2^3,P_3^3)) \; (x,Mul(x,y),y) & \text{ 경우에 따라 } \rho(g,h) \; (S(...),...) \\= & Add(Mul(x,y),y) & \text{ 정의에 의해 } \circ, P_2^3, P_3^3 \\= & Mul(x,y)+y & \text{ } Add의 성질에 의해 . \\\end{array}

3. 4. 기타

지수와 소수 판별법은 원시 재귀적이다.^[1] 원시 재귀 함수

e

,

f

,

g

,

h

가 주어졌을 때,

e \leq f

이면

g

의 값을 반환하고 그렇지 않으면

h

의 값을 반환하는 함수는 원시 재귀적이다.^[1]

4. 술어와 명제 결합자

일부 환경에서는 숫자와 진리값(참을 나타내는 t와 거짓을 나타내는 f)을 혼합한 튜플을 입력으로 받거나 진리값을 출력하는 원시 재귀 함수를 고려하는 것이 자연스럽다.^[4] 이는 진리값을 어떤 고정된 방식으로 숫자와 식별함으로써 달성할 수 있다. 예를 들어, 진리값 t를 숫자 1로, 진리값 f를 숫자 0으로 식별하는 것이 일반적이다. 이와 같이 숫자로 식별이 이루어지면, 항상 1 또는 0을 반환하는 집합 A의 특성 함수는 숫자가 집합 A에 속하는지 여부를 알려주는 술어로 볼 수 있다.

4. 1. "0인가?" 술어

일부 환경에서는 숫자와 진리값(참을 나타내는

t

와 거짓을 나타내는

f

)을 혼합한 튜플을 입력으로 받거나 진리값을 출력하는 원시 재귀 함수를 고려하는 것이 자연스럽다.^[4] 이는 진리값을 어떤 고정된 방식으로 숫자와 식별함으로써 달성할 수 있다. 예를 들어, 진리값

t

를 숫자

1

로, 진리값

f

를 숫자

0

으로 식별하는 것이 일반적이다. 이러한 방식으로 숫자로 식별이 이루어지면, 항상

1

또는

0

을 반환하는 집합

A

의 특성 함수는 숫자가 집합

A

에 속하는지 여부를 알려주는 술어로 볼 수 있다.

원시 재귀 술어의 예시로, 1변수 함수

IsZero

를 정의하여

x = 0

인 경우

IsZero(x) = 1

이고, 그렇지 않으면

IsZero(x) = 0

이 되도록 한다. 이는

IsZero = \rho(C_1^0,C_0^2)

로 정의함으로써 달성할 수 있다. 그러면

IsZero(0) = \rho(C_1^0,C_0^2)(0) = C_1^0(0) = 1

이고, 예를 들어

IsZero(8) = \rho(C_1^0,C_0^2)(S(7)) = C_0^2(7,IsZero(7)) = 0

이다.

4. 2. "작거나 같은가?" 술어

원시 재귀 함수에서 숫자와 진리값(참은 t, 거짓은 f로 표현)을 함께 입력받거나 진리값을 출력하는 함수를 고려하는 경우가 있다.^[4] 이때 진리값을 숫자로 나타낼 수 있는데, 보통 t는 1, f는 0으로 표현한다. 이렇게 하면 항상 0이나 1을 반환하는 집합 A의 특성 함수는 어떤 숫자가 집합 A에 들어있는지 알려주는 술어로 볼 수 있다.

예를 들어, 1변수 함수

IsZero

는

x = 0

이면

IsZero(x) = 1

, 그렇지 않으면

IsZero(x) = 0

이 되도록 정의한다. 이 함수는

IsZero = \rho(C_1^0,C_0^2)

로 정의할 수 있다. 그러면

IsZero(0) = \rho(C_1^0,C_0^2)(0) = C_1^0(0) = 1

이고,

IsZero(8) = \rho(C_1^0,C_0^2)(S(7)) = C_0^2(7,IsZero(7)) = 0

이 된다.

주어진 섹션 제목은 "작거나 같은가?" 술어 이지만, 주어진 소스에는 해당 술어의 정의가 직접적으로 나타나 있지 않다. 대신, 진리값과 숫자의 식별, 그리고 IsZero 함수의 정의에 대한 내용이 포함되어 있다. 따라서 주어진 소스 내용에 맞추어 섹션 내용을 작성하였다.

4. 3. 논리곱, 논리합, 부정

4. 4. 등식, 초과, 미만 술어

일부 환경에서는 숫자와 진리값(참을 나타내는

t

와 거짓을 나타내는

f

)을 혼합한 튜플을 입력으로 받거나 진리값을 출력하는 원시 재귀 함수를 고려하는 것이 자연스럽다.^[4] 이는 진리값을 어떤 고정된 방식으로 숫자와 식별함으로써 달성할 수 있다. 예를 들어, 진리값

t

를 숫자

1

로, 진리값

f

를 숫자

0

으로 식별하는 것이 일반적이다. 이 식별이 이루어지면, 항상

1

또는

0

을 반환하는 집합

A

의 특성 함수는 숫자가 집합

A

에 속하는지 여부를 알려주는 술어로 볼 수 있다.

원시 재귀 술어의 예시로, 1변수 함수

IsZero

를 정의하여

x = 0

인 경우

IsZero(x) = 1

이고, 그렇지 않으면

IsZero(x) = 0

이 되도록 한다. 이는

IsZero = \rho(C_1^0,C_0^2)

로 정의함으로써 달성할 수 있다. 그러면

IsZero(0) = \rho(C_1^0,C_0^2)(0) = C_1^0(0) = 1

이고, 예를 들어

IsZero(8) = \rho(C_1^0,C_0^2)(S(7)) = C_0^2(7,IsZero(7)) = 0

이다.

Leq

가 정의되면, 역 연산 술어는

Geq = Leq \circ (P_2^2,P_1^2)

로 정의할 수 있다. 그러면,

Geq(x,y) = Leq(y,x)

는

x \geq y

일 때 참(더 정확히는, 값 1)이다.

위의 함수

Leq

,

Geq

및

And

를 사용하여 정의

Eq = And \circ (Leq, Geq)

는 등식 술어를 구현한다. 실제로,

Eq(x,y) = And( Leq(x,y) , Geq(x,y) )

는

x

가

y

와 같을 때만 참이다.

마찬가지로, 정의

Lt = Not \circ Geq

는 "미만" 술어를 구현하고,

Gt = Not \circ Leq

는 "초과"를 구현한다.

5. 정수 및 유리수 연산

괴델 수를 이용하면 원시 재귀 함수를 정수 및 유리수와 같이 다른 객체에 대해 작동하도록 확장할 수 있다.^[1] 정수를 표준 방식으로 괴델 수로 부호화하면 덧셈, 뺄셈, 곱셈을 포함한 산술 연산은 모두 원시 재귀적이다.^[1] 마찬가지로 유리수를 괴델 수로 나타내면 체 연산은 모두 원시 재귀적이다.^[1]

6. 재귀 함수와의 관계

모든 원시 재귀 함수는 전역 재귀 함수이지만, 그 역은 성립하지 않는다. 아커만 함수는 원시 재귀 함수가 아닌 전역 재귀 함수의 대표적인 예이다. 원시 재귀 함수는 항상 정지하는 튜링 머신으로 계산 가능하며, 아커만 함수를 이용해 그 단계 수를 특정할 수 있다.^[5]

원시 재귀 함수의 중요한 특징은 모든 전재귀 함수 집합의 재귀적 가산 부분 집합이라는 것이다. 이는 다음과 같은 특징을 갖는 단일 계산 가능 함수 ''f''(''m'',''n'')가 존재함을 의미한다.

모든 원시 재귀 함수 ''g''에 대해, 모든 ''n''에 대해 ''g''(''n'') = ''f''(''m'',''n'')이 되는 ''m''이 존재한다.
모든 ''m''에 대해, 함수 ''h''(''n'') = ''f''(''m'',''n'')는 원시 재귀 함수이다.

''f''는 원시 재귀 함수를 생성하는 모든 가능한 방법을 반복하여 명시적으로 구성할 수 있다. 따라서 증명 가능하게 전재귀 함수이다. 대각선화 논법을 사용하여 ''f'' 자체가 원시 재귀 함수가 아님을 보일 수 있다. 만약 그랬다면, ''h''(''n'') = ''f''(''n'',''n'')+1도 그랬을 것이다. 그러나 이것이 어떤 원시 재귀 함수와 같다면, 모든 ''n''에 대해 ''h''(''n'') = ''f''(''m'',''n'')이 되는 ''m''이 존재하며, 그러면 ''h''(''m'') = ''f''(''m'',''m'')이 되어 모순이 발생한다.

하지만 원시 재귀 함수의 집합은 모든 전재귀 함수 집합의 ''가장 큰'' 재귀적 가산 부분 집합은 아니다. 예를 들어, (페아노 산술에서) 증명 가능한 전재귀 함수의 집합도 재귀적으로 열거 가능하며, 이론의 모든 증명을 열거할 수 있기 때문이다. 모든 원시 재귀 함수는 증명 가능하게 전재귀 함수이지만, 그 반대는 성립하지 않는다.

재귀 함수는 μ operator|뮤 연산자^영어를 사용하여 정의할 수 있다. μ 연산자는 입력에 대해 출력이 반환되는 것을 보장하지 않는다. 이러한 함수를 부분 함수 (Partial Function)라고 하며, 시역의 모든 입력에 대해 출력이 반환되는 함수를 전역 함수 (Total Function)라고 한다.

원시 재귀 함수는 모두 전역 재귀적이지만, 전역 재귀 함수가 모두 원시 재귀적인 것은 아니다. 아커만 함수 ''A''(''m'',''n'')는 전역 재귀 함수이면서 원시 재귀적이지 않은 유명한 예이다. 아커만 함수를 사용하여, 원시 재귀 함수가 전역 재귀 함수의 부분 집합이라고 보는 견해도 있다. 이 경우, 함수가 원시 재귀적이라는 것은, 해당 함수가 튜링 머신으로 계산 가능하며, 또한 어떤 ''m''에 대해 ''A''(''m'', ''n'') 이하의 단계 수로 반드시 정지하는 것으로 정의된다.

7. 한계

원시 재귀 함수는 모든 전역 계산 가능 함수를 포함하지 않는다. 이는 칸토어의 대각선 논법을 응용하여 증명할 수 있다. 증명의 개요는 다음과 같다.

:원시 재귀 함수는 계산적으로 열거 가능하다. 즉, 2변수 계산 가능 함수 $f$ 가 존재하여, $f(i,\cdot) (i\in \mathbb{N})$ 가 정확히 원시 재귀 함수 전체와 일치한다. 이때 $f(i,\cdot)$ 를 $f_i$ 로 표기한다. 하나의 원시 재귀 함수 $g$ 에 대해 $g=f_{i}$ 가 되는 $i$ 는 여러 개 존재할 수 있다.^[12]

:다음과 같은 무한×무한 행렬을 생각한다. 제 $i$ 행의 제 $j$ 열에는 $f_i(j)$ 의 값이 적혀 있다고 가정한다. 이 행렬의 대각선 부분에 주목한다.

:함수 $g(x) := f_x(x) + 1$ 을 생각한다. $g$ 는 행렬의 대각선상의 값에 1을 더한 값을 반환한다. 이 함수는 계산 가능하지만, 어떤 원시 재귀 함수도 이 함수를 계산할 수 없다. 왜냐하면 모든 원시 재귀 함수는 이 함수와 대각선 부분에서 값이 다르기 때문이다. 따라서 원시 재귀적이지 않은 계산 가능 함수가 존재한다.

이 논법은 열거 가능한 (전역) 계산 가능 함수의 모든 클래스에 적용할 수 있다.

원시 재귀적이지 않은 전역 재귀 함수의 예시는 다음과 같다.

아커만 함수 $A(x, y)$ 및 두 인수에 같은 값을 대입한 함수 $A(x,x)$ 는 전역 재귀적이지만 원시 재귀적이지 않다.
크누스 윗 화살표 표기법은 전역 재귀적이지만 원시 재귀적이지 않다. 아커만 함수는 크누스 윗 화살표 표기법으로 표현할 수 있다.
그제고르치크 계층의 초기 함수 $E_i(x)$ 는 2변수 함수로서 전역 재귀적이지만 원시 재귀적이지 않다.
파리-해링턴 정리는 원시 재귀적이지 않은 전역 재귀 함수와 관련이 있다. 이 함수는 램지 이론에 기반하고 있기 때문에, 아커만 함수보다 "자연스럽다"고 여겨지기도 한다.
수단 함수
굿스타인 함수Goodstein function|굿스타인 함수^영어

8. 변형

클리니(1952)는 원시 재귀 함수를 정의하기 위한 다양한 변형을 제시했다.^[6] 여기에는 다음이 포함된다.

약한 원시 재귀: 암시적 전임자를 제거하고, 따름수 함수 S(y)를 사용한다.
반복 함수: 함수 h의 인자에서 y와 S(y)를 완전히 제거한 형태로, 원시 재귀 함수의 진부분집합으로 추정된다.

이 외에도, 값의 코스 재귀, 상호 재귀 등도 원시 재귀 함수를 정의하는 방법이다.

LOOP 프로그래밍 언어는 원시 재귀 함수와 동일한 계산 능력을 갖는다.^[6] LOOP 언어는 각 루프가 실행될 횟수가 미리 정해져 있다는 특징이 있다. 이는 튜링 완전 언어와 비교되는 LOOP 언어의 주요 제한 사항이다.

원시 재귀 프로그래밍 언어는 기본적인 산술 연산, 조건문, 제한된 for 루프 등을 포함한다. 앨버트 R. 마이어와 데니스 M. 리치가 1967년에 소개한 LOOP 언어가 그 예시이다.^[6] 더글러스 호프스태터의 책 ''괴델, 에셔, 바흐''에 나오는 BlooP도 LOOP 언어의 변형 중 하나이다.

9. 유한주의 및 무모순성 결과

원시 재귀 산술(PRA)은 자연수와 그에 대한 원시 재귀 함수를 다루는 형식적 공리 체계이다. PRA는 페아노 산술보다 약하지만, 수론과 증명론의 많은 결과를 증명할 수 있다. 예를 들어, 괴델의 불완전성 정리를 PRA로 형식화할 수 있다. 괴델의 불완전성 정리에 따르면, 특정 조건을 만족하는 산술 이론 ''T''와 그 이론의 괴델 문장 ''G''_''T''가 있을 때, PRA는 Con(''T'')→''G''_''T''를 증명할 수 있다.^[1]

증명론의 구문론적 결과들 역시 PRA에서 증명 가능하다. 이는 증명의 구문론적 변환을 수행하는 원시 재귀 함수가 존재함을 의미한다.^[1]

증명론과 집합론에서는 유한주의적 무모순성 증명에 관심을 가진다. 이러한 증명은 이론 ''T''의 무모순성이 이론 ''S''의 무모순성을 함의한다는 것을 보여준다. 예를 들어 어떤 이론 ''S''의 무모순성을 증명하는 모든 증명을 다른 이론 ''T''의 무모순성을 증명하는 증명으로 변환 가능한 원시 재귀 함수를 만들 수 있다. 무모순성 증명이 유한주의적이기 위한 충분 조건 중 하나는 PRA로 형식화할 수 있는지 여부이다. 강제법을 통해 얻어진 집합론의 많은 무모순성 결과는 PRA에서 형식화 가능한 구문론적 증명으로 다시 만들 수 있다.^[1]

10. 역사

귀납적 정의는 이전부터 수학에서 다소 형식적으로 사용되었지만, 원시 재귀의 구성은 1888년 리하르트 데데킨트의 저서 ''Was sind und was sollen die Zahlen?''의 정리 126에서 유래되었다. 이 연구는 특정 재귀적 구성이 고유한 함수를 정의한다는 증명을 처음으로 제시했다.^[7]^[8]^[9]

원시 재귀 산술은 1923년 토랄프 쇠렘에 의해 처음 제안되었다.^[10]

빌헬름 아커만이 1928년에 오늘날 그의 이름을 딴 함수가 원시 재귀적이지 않다는 것을 증명한 후, 1934년 로자 페테르가 현재의 용어를 만들었다. 이는 그 당시 단순하게 재귀 함수라고 불렸던 것들의 이름을 바꿀 필요성을 촉구했다.^[8]^[9]

참조

_[1] 문서 Brainerd and Landweber 1974
_[2] 문서 Hartmanis 1989
_[3] 서적 Formal Models and Semantics Elsevier
_[4] 문서 Kleene 1952
_[5] 서적 An Introduction to Formal Languages and Automata https://books.google[...] Jones & Bartlett Publishers
_[6] 간행물 The complexity of loop programs
_[7] 서적 An Introduction to Gödel's Theorems Cambridge University Press
_[8] 서적 Lectures in Logic and Set Theory: Volume 1, Mathematical Logic Cambridge University Press
_[9] 서적 Turing's Legacy: Developments from Turing's Ideas in Logic Cambridge University Press
_[10] 문서 The foundations of elementary arithmetic Harvard Univ. Press
_[11] 문서 0 項関数とは自然数のことであると取り決める。
_[12] 문서 ただし原始帰納的関数を重複なく枚挙する計算可能関数が存在することが知られている

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com