가치 과정 재귀

이 글에는 참고문헌, 관련 독서 또는 외부 링크 목록이 수록되어 있으나 인라인 인용구가 부족하여 출처가 불분명하다. 보다 정확한 인용문을 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2009년 4월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

계산가능성 이론에서 가치의 과정 재귀는 재귀에 의한 숫자-이론적 함수를 정의하는 기법이다.값 과정 재귀에 의한 함수 f의 정의에서 f(n)의 값은${\displaystyle f}$ f${\displaystyle }$(${\displaystyle 0}$) ,${\displaystyle f}$ (${\displaystyle 1}$ )${\displaystyle }$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle f}$(${\displaystyle \mathrm{n}}$ - 1)${\displaystyle ⟩}${\$displaystyle \langle$f ($0),$f ($1)$ ,\$ldots ,f($n-1$)\rangele }$의 순서로 계산된다$.$

그러한 정의가 더 간단한 형태의 재귀로 정의될 수 있다는 사실은 종종 가치 재귀에 의해 정의된 기능이 원시적인 재귀라는 것을 증명하기 위해 사용된다.값의 과정 재귀와는 반대로, 원시 재귀에서 함수 값의 계산은 이전 값만 필요로 한다. 예를 들어, 1ari 원시 재귀 함수 g의 경우 g(n+1) 값은 g(n)와 n으로만 계산된다.

정의 및 예제

요인 함수 n!은 규칙에 의해 재귀적으로 정의된다.

${\displaystyle 0!=1,}$

${\displaystyle (n+1)!=n!(n+1)}$

이 재귀는 n의 값과 함수의 이전 값 n!을 바탕으로 함수의 다음 값(n+1)을 계산하기 때문에 원시 재귀다.반면 n번째 피보나치 숫자를 반환하는 Fib(n) 함수는 재귀 방정식으로 정의된다.

${\displaystyle Fib(0)=0,}$

${\displaystyle Fib(1)=1,}$

$[\displaystyle Fib(n+2)=Fib(n+1)+Fib(n)]}$

Fib(n+2)를 계산하려면 Fib 함수의 마지막 두 값이 필요하다.마지막으로, 재귀 방정식으로 정의된 함수 g를 고려하십시오.

${\displaystyle g(0)=0,}$

${\displaystyle g(n+1)=\sum _{i=0}^{ng(i)^{n-i}.}$

이러한 방정식을 사용하여 g(n+1)를 계산하려면 g의 모든 이전 값을 계산해야 한다. g의 계산에는 일반적으로 고정된 한정된 이전 값 수가 충분하지 않다.Fib와 g 함수는 값 과정 재귀에 의해 정의된 함수의 예다.

일반적으로 함수 f는 모든 n에 대해 고정된 원시 재귀 함수 h가 있는 경우 값 과정 재귀에 의해 정의된다.

${\displaystyle f(n)=h(n,\langle f(0),f(1),\ldots,f(n-1)\angle )}$

여기서 $⟨{\displaystyle }$ ${\displaystyle \mathrm{f}}$( ${\displaystyle 0}$)${\displaystyle }$, f${\displaystyle }$( ${\displaystyle 1}$)${\displaystyle }$,${\displaystyle }$… ,${\displaystyle }$f${\displaystyle }$( ${\displaystyle \mathrm{n}}$- 1${\displaystyle }$) ${\displaystyle ⟩}$ ${\displaystyle \langle f (0), f(1),\ldots,f(n-1)\rangele }$은 표시된 시퀀스를 인코딩하는 괴델 번호다.특히

${\displaystyle f(0)=h(0,\langle \angle )}$

재귀의 초기 값을 제공한다.함수 h는 명시적인 초기 값을 제공하기 위해 첫 번째 인수를 테스트할 수 있다. 예를 들어 Fib one은 다음에 의해 정의된 함수를 사용할 수 있다.

${\displaystyle h(n,s)={\displaysty}n&{\text}{{n\s[n-2]+s[n-1]&{\text{{n\geq 2\end{case}}}}}}}}$

여기서 s[i]는 인코딩된 시퀀스 s에서 요소 i를 추출하는 것을 의미한다. 이는 원시 재귀 함수(적절한 괴델 번호 매기기 사용으로 가정)로 쉽게 보인다.

원시 재귀에 대한 동등성

값 과정 재귀에 의한 정의를 원시 재귀로 변환하기 위해 보조(헬퍼) 함수를 사용한다.어떤 사람이 갖고 싶어한다고 가정하자.

$f$( ${\displaystyle n}$)${\displaystyle }$= ${\displaystyle h}$(,${\displaystyle ⟨}$ ${\displaystyle f}$( ${\displaystyle 0}$)${\displaystyle }$, ${\displaystyle f}$( ${\displaystyle 1}$) ,${\displaystyle }$…${\displaystyle }$,${\displaystyle f}$ ( 1 ) , f ( $1$ )${\displaystyle (}$ ) ${\displaystyle f(n)=h(n,\langle f(0),$ f(1$),\ldots,$ f$(n-1)\angle$ $)\}\}.$

원시 재귀법을 사용하여 f를 정의하려면 먼저 충족해야 하는 보조 가치 과정 함수를 정의하십시오.

${\displaystyle {\f}(n)=\langle f(0),f(1),\ldots,f(n-1)\angle }$

여기서 오른쪽은 괴델 번호 매기기 시퀀스로 간주된다.

따라서 $f{\displaystyle \stackrel{}{}}$ ${\displaystyle (}$ ($){\displaystyle{\bar{f}(n)$은 f의 첫 번째 n 값을 부호화한다$$.The function ${\displaystyle {\bar {f}}}$ can be defined by primitive recursion because ${\displaystyle {\bar {f}}(n+1)}$ is obtained by appending to ${\displaystyle {\bar {f}}(n)}$ the new element ${\displaystyle h(n,{\bar {f}}(n))}$:

${\displaystyle \stackrel{}{f}\text{'}(0}$)${\displaystyle }$= ${\displaystyle =}$ ${\displaystyle {\f$}($0)=\langle \angle$ $\},$

${\displaystyle {\bar}{f}(n+1)={\mathit{n}}(n, {\bar {f})(n), h(n, {\bar {{f})(n),}$

여기서 부록(n,s,x)은 s가 길이 n의 순서를 인코딩할 때마다 t[n] = x 및 t[i] = s[i]인 길이 n + 1의 새 시퀀스를 계산한다.이것은 적절한 괴델 번호 매기기를 전제로 한 원시 재귀 함수로서, h는 처음부터 원시 재귀로 가정한다.따라서 재귀 관계는 원시 재귀로 기록할 수 있다.

${\displaystyle {\bar {{f}(n+1)=g(n,{\bar {f}(n))}$

여기서 g는 그 자체로 원시적인 재귀성이며, 두 가지 그러한 기능의 구성이 된다.

${\displaystyle g(i,j)={\mathit {append}(i,j,h(i,j),}$

${\$가 주어진 경우$,$ 원래 함수 $f$는${\displaystyle }$f ${\displaystyle (n}$)${\displaystyle \stackrel{}{}}$= ${\displaystyle f\stackrel{}{}}$(${\displaystyle \mathrm{n}}$+${\displaystyle }$1 $]{\displaystyle f(n)={\bar{f}(n+1)[n$로 정의할 수 있는데, 이 기능도 원시적인 재귀 함수임을 보여준다.

원시 재귀 함수에 적용

원시 재귀함수의 맥락에서, 자연수의 유한한 순서를 하나의 자연수로 나타내는 수단을 갖는 것이 편리하다.그러한 방법 중 하나인 괴델의 인코딩은 양의 정수 ${\displaystyle {}_{}}$인 $⟨{\displaystyle {n\mathrm{}}_{}{0\mathrm{}}_{}}$,${\displaystyle {}_{}{}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$, n ${\displaystyle {}_{}}$…, ${\displaystyle n_{}}$ $k ⟩$ {\$displaystyle$\langle n_${0},n_{1},n_{2},\ldots ,n_{k}\rangele}$를 나타낸다$$.

${\displaystyle \prod _{}^{}}$ ${\displaystyle \underset{}{\overset{}{i}}}$= ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle i_{}^{}}$ ${\displaystyle {{}_{}}_{}^{}}$ ${\displaystyle {n_{}}_{}^{}}$ ${\$

여기서 p는_i ith preme을 나타낸다.이러한 표현으로, 시퀀스에 대한 통상적인 연산은 모두 원시적인 재귀임을 알 수 있다.이 작업에는 다음이 포함된다.

• 시퀀스 길이 결정,
• 주어진 순서에서 요소를 추출하면
• 두 개의 시퀀스를 연결 중.

이러한 시퀀스의 표현을 사용하면 h(m)가 원시 재귀일 경우 함수임을 알 수 있다.

${\displaystyle f}$( ${\displaystyle n}$)${\displaystyle }$= h${\displaystyle }$( ${\displaystyle ⟨}$ f${\displaystyle }$( ${\displaystyle 0}$)${\displaystyle }$, ${\displaystyle f}$( ${\displaystyle 1}$)${\displaystyle }$, ${\displaystyle f}$( 2${\displaystyle }$)${\displaystyle }$,${\displaystyle }$… ,${\displaystyle }$f${\displaystyle }$( ${\displaystyle \mathrm{n}}$- 1${\displaystyle }$) ${\displaystyle ⟩}$) ${\displaystyle f(n)=h(\langle f(0),$f$(1),$f$(2),\ldots ,f(n-1)\angle$ $)\}.$

원시적인 재귀도 있어

${\displaystyle {}_{}}$ 0$,{\displaystyle {}_{}{}_{}}$ 1,${\displaystyle {}_{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ , n k${\displaystyle {}_{}}$ ${\displaystyle \langle n_{0},n_{1},n_{2},\ldots ,n_{k}\rangele }$ 시퀀스가 0을 포함할 수 있으면$$ 대신 0으로 표시된다.

${\displaystyle \prod _{}^{}}$ ${\displaystyle \underset{}{\overset{}{i}}}$= ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{}}{}_{}^{}}$ ${\displaystyle i_{}^{}}$(${\displaystyle {{}_{}}_{}^{}}$ ${\displaystyle {i_{}}_{}^{}}$+ ${\displaystyle 1_{}^{}}$) ${\$

따라서 시퀀스 $⟨{\displaystyle }$ ${\displaystyle 0}$ {\$displaystyle$ \$langle 0\angle }$과${\displaystyle (}$와)${\displaystyle }$⟨ ${\displaystyle 0}$ ${\displaystyle ⟩}$ ${\displaystyle \langle$ 0$,0\langle }$의 코드를 구별할 수 있다$.$

제한 사항

모든 재귀적 정의가 원시적 재귀적 정의로 변형될 수 있는 것은 아니다.한 가지 알려진 예는 A(m,n) 형태의 Ackermann의 기능이며, 분명히 원시적인 재귀성은 아니다.

실제로, 모든 새로운 값 A(m+1, n)는 이전에 정의된 값 A(i, j)의 순서에 따라 달라지지만, 이 순서에 포함되어야 하는 값은 이전에 계산된 함수 값, 즉 (i, j) = (m, A(m+1, n)에 따라 달라진다.따라서 앞에서 제시한 방식(또는 이 기능이 원시적 재귀성이 아닌 것으로 판명된 것처럼)으로 이전에 계산된 값의 순서를 원시적 재귀 방식으로 인코딩할 수 없다.

참조

• 힌만, P.G. 2006, 수학논리의 기초, A K Peters.
• 1989년 오디프레디, P.G., 북 홀랜드 고전 재귀 이론; 1999년 2판.