크린의 재귀 정리

계산 가능성 이론에서 Kleene의 재귀 정리는 계산 가능한 함수를 자신의 설명에 적용하는 것에 대한 한 쌍의 기본 결과입니다. 이 정리들은 1938년^[1] 스티븐 크린에 의해 처음으로 증명되었고 1952년 그의 저서 메타수학 개론에 등장합니다.^[2] 계산 가능한 함수의 고정점을 구성하는 관련 정리는 Rogers의 정리로 알려져 있으며 Hartley Rogers, Jr.에 기인합니다.^[3]

재귀 정리는 계산 가능한 함수에 대한 특정 연산의 고정점을 구성하고, 질의 생성 및 재귀 정의를 통해 정의된 함수를 구성하는 데 적용할 수 있습니다.

표기법

정리 문은 부분 재귀 함수의 허용되는 번호 지정$$φ ${\$displaystyle$$\varphi}을 참조하며,$$인덱스 e {\$displaystyle$ ${\displaystyle e_{}}$}에 해당하는 함수는$$φ e${\displaystyle$ $\backslash$varphi_{e}입니다.

If ${\displaystyle F}$ and ${\displaystyle G}$ are partial functions on the natural numbers, the notation ${\displaystyle F\simeq G}$ indicates that, for each n, either ${\displaystyle F(n)}$ and ${\displaystyle G(n)}$ are both defined and are equal, 그렇지 않으면 $F{\displaystyle (n)}$ ${\displaystyle$ F$(n)}$ 및$$ G${\displaystyle (n)}$ ${\displaystyle$ G$(n)}$가 모두 정의되지 않았습니다.

로저스의 고정점 정리

함수 $F$ ${\displaystyle$ $F$$}$가 주어졌을 때$,$ $F$ ${\displaystyle$ F$}$의 $고정점$은 인덱스$$ ${\displaystyle$ e$}$이므로 ≃ φ e φ F ($e)$ {\$displaystyle \$varphi _{e}\simeq \varphi _$\{$F(e)}입니다. 여기서 인과 출력의 비교는 수치의 관점에서 이루어지는 것이 아닙니다. 하지만 연관된 기능의 관점에서 보면요.

Rogers는 다음과 같은 결과를 Kleene의 (두 번째) 재귀 정리의 "간단한 버전"이라고 설명합니다.^[4]

고정점 정리의 증명

증명은 다음과 같이 정의된 특정$$총 계산 가능 $함수$ $h{\displaystyle }$ ${\displaystyle$ h$}$를 사용합니다. 자연수 $x{\displaystyle }$ ${\displaystyle$ $x$$}$가 주어지면$$$함수{\displaystyle }$ h ${\displaystyle$ h$}$는 다음 계산을 수행하는 부분 계산 가능 함수의 인덱스를 출력합니다$$.

입력 $y$ ${\displaystyle y}$가 주어졌을$$때${\displaystyle ,}$ ${\displaystyle \mathrm{먼저}}$φ x (x) ${\displaystyle \varphi_$x}(x)}를 계산해 봅니다. 해당 계산이$출력$ e${\displaystyle$e}를 반환하면$$φ e (y)${\displaystyle$\varphi_{e}(y)}를${\displaystyle {}_{}}$계산하고 값이 있으면 반환합니다.

Thus, for all indices ${\displaystyle x}$ of partial computable functions, if ${\displaystyle \varphi _{x}(x)}$ is defined, then ${\displaystyle \varphi _{h(x)}\simeq \varphi _{\varphi _{x}(x)}}$. If ${\displaystyle \varphi _{x}(x)}$ is not defined, 그러면${\displaystyle {}_{}}$φ${\displaystyle {}_{}}$h(x) ${\displaystyle$ \$varphi _${h(x)}}는 어디에도 정의되지 않은 함수입니다. The function ${\displaystyle h}$ can be constructed from the partial computable function ${\displaystyle g(x,y)}$ described above and the s-m-n theorem: for each ${\displaystyle x}$, ${\displaystyle h(x)}$ is the index of a program which computes the function ${\displaystyle y\mapsto g(x,}$$displaystyle$ y$\mapstog(x,y$

증명을 완료하려면 $F{\displaystyle }$ ${\displaystyle F}$를 임의의 전체 계산 가능 함수라고 하고 위와 같이$$ ${\displaystyle$ h$}$를 구성합니다. ${\displaystyle$ e$}$를 토탈 계산 가능 함수인 $합성$ ${\displaystyle F}$ ∘ h {\$displaystyle$F$\backslash$circ}의 인덱스라고 하자. Then ${\displaystyle \varphi _{h(e)}\simeq \varphi _{\varphi _{e}(e)}}$ by the definition of ${\displaystyle h}$. But, because ${\displaystyle e}$ is an index of ${\displaystyle F\circ h}$, ${\displaystyle \varphi _{e}(e)=(F\circ h)(e)}$, and thus ${\displaystyle \varphi _{\varphi _{e}(e)}\simeq \varphi _{F(h(e))}}$. By the transitivity of ${\displaystyle \simeq }$, this means ${\displaystyle \varphi _{h(e)}\simeq \varphi _{F(h(e))}}$. $따라서$n = h($e) {\displaystyle$ n=h(e) {\displaystyle n=h(e)}에${\displaystyle }$대해$$φ${\displaystyle {}_{}}$n ≃ φ F(n) ${\displaystyle$ \$varphi_{$n}\ simeq \$varphi\_${F(n)}}입니다.

이 증명은 Y 결합기를 구현하는 부분 재귀 함수의 구성입니다.

고정점이 없는 함수

φ$e$를${\displaystyle {}_{}}$≄ φ하는$$함수 F ${\displaystyle$ F$}$ {\displaystyle \$varphi_${e}\n$ot{\displaystyle }$$\simeq \varphi$ _{$F(e)}$ 모든 ${\displaystyle$ e$}$에 대해$$ 고정$$ 소수점 자유라고 합니다. 고정 소수점 정리는 전체 계산 가능 함수가 고정 소수점 자유 함수는 없지만 계산 불가능한 고정 소수점 자유 함수는 많다는 것을 보여줍니다. Arslanov의 완전성 기준은 고정점이 없는 함수를 계산하는 유일하게 재귀적으로 열거 가능한 튜링 정도는 정지 문제의 정도인 0'이라고 말합니다.^[5]

크린의 두 번째 재귀 정리

두 번째 재귀 정리는 함수에 두 번째 입력이 있는 로저스 정리의 일반화입니다. 두 번째 재귀 정리에 대한 한 가지 비공식적인 해석은 자기 참조 프로그램을 구성할 수 있다는 것입니다. 아래의 "어플리케이션 투 퀸"을 참조하십시오.

두 번째 재귀 정리. 임의의 부분 재귀 함수 $Q{\displaystyle }$(${\displaystyle x,}$ y${\displaystyle )}$ ${\displaystyle$ Q$(x,$ y$)}$에 대해${\displaystyle }$p${\displaystyle }$≃ λ${\displaystyle }$y를 φ하는 $인덱스$ p ${\displaystyle p}$가 있습니다.$$Q (p, y) ${\$displaystyle \varphi_{p$}\simeq$ \lambday.$Q(p,y$

$이$ 정리는 F${\displaystyle (p)}$ ${\displaystyle$ F$(p)}$를${\displaystyle {}_{}}$φ${\displaystyle {}_{}}$F(${\displaystyle p)(}$y) = Q$p,$ y) {\displaystyle \varphi _{F(p)}(y) = Q(p,y)}(S-m-n 정리에 의해 설명되는 구성)와 같은 함수로 함으로써 로저스의 정리로부터 증명될 수 있습니다. $그러면{\displaystyle }$ 이 F ${\displaystyle$ F$}$의 고정점이 필요에$$ 따라 $인덱스{\displaystyle }$ p${\displaystyle$ p$}$임을$$ 확인할 수 있습니다. 이 정리는 고정된 계산 가능 함수가 $Q{\displaystyle }$ ${\displaystyle$ $Q$$}$에 대한 인덱스를 인덱스 $p{\displaystyle }$ ${\displaystyle$ $p$$}$에 매핑한다는 점에서 건설적입니다$.$

다음 문장을 사용하여 계산 가능 함수로 확장할 수 있습니다.

$f{\displaystyle :}$ ${\displaystyle N}$ → ${\displaystyle N}$ {\$displaystyle$ f$:\mathbb {N} \rightarrow \mathbb {N}$을 전체 계산 가능 함수라고 합니다. 그러면$\mathbb$ {N}에는 ϕ${\displaystyle {}_{}}$e ${\displaystyle {0_{}}_{}}$ =$$ϕ (f$$($e 0))${\$displaystyle$ \phi _{e_{0}}=\phi _{(f_{(}e_{0})}}인 $프로그램$ $e$ ${\displaystyle 0_{}}$ ∈ N {\$displaystyle e_{0$}\n이 있습니다.

이것은 본질적으로 우리가 프로그램을 취하면 확장적인 방식으로 효과적인 변환(예: 계승, 점프, 선 제거와 같은 명령 교체)을 적용하면, 그 이전이나 이후에도 함수의 변환에 의해 변경되지 않는 프로그램이 항상 존재한다는 것을 의미합니다.

따라서 이 정리는 "프로그램을 변환하는 효과적인 절차가 주어지면, 절차에 의해 수정될 때 이전에 했던 것을 정확히 수행하거나 다른 모든 프로그램의 확장 동작을 변경하는 프로그램을 작성하는 것이 불가능한 프로그램이 항상 존재한다"는 방식으로 해석될 수 있습니다.

로저스의 정리와의 비교

Kleene의 두 번째 재귀 정리와 Rogers의 정리는 서로 비교적 간단하게 증명할 수 있습니다.^[6] 그러나 Kleene의 정리를^[7] 직접적으로 증명하는 것은 보편적인 프로그램을 사용하지 않으며, 이는 그 정리가 보편적인 프로그램이 없는 특정 하위 회귀 프로그래밍 시스템에 대해 유지된다는 것을 의미합니다.

퀸즈 적용

두 번째 재귀 정리를 사용한 고전적인 예는 ${\displaystyle \mathrm{함수}}$ Q${\displaystyle }$(${\displaystyle x,}$ y${\displaystyle )}$ = x ${\$displaystyle Q(x, y) = x}입니다. 이 경우 대응하는 인덱스 p {\displaystyle p}는 임의의 값에 적용될 때 자신의 인덱스를 출력하는 계산 가능 함수를 산출합니다. 컴퓨터 프로그램으로 표현하면 그러한 지수를 퀸(quine)이라고 합니다.

리스프의 다음 예는 $코럴$의 p ${\displaystyle p}$가 Q ${\displaystyle Q}$ 함수에서 효과적으로 생성될 수 있는 방법을 보여줍니다$.$ 함수. s11 코드는 S-m-n 정리에 의해 생성된 이름의 함수입니다.

Q 모든 2 argument 기능으로 변경할 수 있습니다.

(setq Q '(람다 (x y) x)) (setq s11 '(람다 (f x) (목록. ' '(y) (목록. f x 'y')))) (setq n (목록. ' '(x y) (목록. Q (목록. s11 x x) 'y'))) (setq p (평가하다 (목록. s11 n n))) 

다음 식들의 결과는 동일해야 합니다. $φ$ p(nil)

(평가하다 (목록. p 영의)) 

Q(p, nil)

(평가하다 (목록. Q p 영의)) 

재귀제거적용

$g{\displaystyle }$ ${\displaystyle$ g$}$ 및$$ h ${\displaystyle$ h$}$가 함수 $f{\displaystyle }$ ${\displaystyle f}$에 대한 재귀적 정의에 사용되는 총 계산 가능 함수라고 가정합니다$.$

${\displaystyle f(0,y)\ simeq g(y),}$

${\displaystyle f(x+1,y)\simeq h(f(x,y),x,y),}$

두 번째 재귀 정리는 이러한 방정식이 계산 가능한 함수를 정의한다는 것을 보여주는 데 사용될 수 있으며, 여기서 계산 가능성의 개념은 재귀적 정의를 위해 기본적으로 허용할 필요가 없습니다(예를 들어 μ-재귀 또는 튜링 기계에 의해 정의될 수 있음). 이 재귀적 정의는 재귀를 $시뮬레이션하기$위해 e{\displaystyle e}가 자체 인덱스라고$가정$하는 계산 가능 함수${\displaystyle }$φ F${\displaystyle (}$e${\displaystyle ,}$ x$,$ y) ${\displaystyle \varphi_{F}($e, x, y)}로 변환할 수 있습니다.

${\displaystyle \varphi _{F}(e,0,y)\simeq g(y),}$

${\displaystyle \varphi _{F}(e,x+1,y)\simeq h(\varphi _{e}(x,y),x,y).}$

재귀 정리는${\displaystyle }$φ f${\displaystyle {}_{}}$(${\displaystyle x,}$ y$)$$$≃ φ F (f, $x,$ $y)$ {\displaystyle \varphi_{f}}를$$φ$하도록$ 계산 $가능한 함수$style f {\displaystyle \varphi_{f}(x,y)\simeq \varphi_{F${\displaystyle {}_{}}$f,x,y)}의 존재를 설정합니다. 따라서 f {\displaystyle f}는 주어진 재귀 정의를 만족합니다.

반사 프로그래밍

반사적 또는 반사적 프로그래밍은 프로그램에서 자기 참조를 사용하는 것을 말합니다. Jones는 반사적인 언어에 기초한 두 번째 재귀 정리의 관점을 제시합니다.^[9] 정의된 반사 언어가 반사가 없는 언어보다 강하지 않은 것으로 나타났습니다(반사를 사용하지 않고 반사 언어에 대한 해석기를 구현할 수 있기 때문에). 그런 다음 반사 언어에서 재귀 정리는 거의 사소한 것으로 나타났습니다.

첫 번째 재귀 정리

두 번째 재귀 정리는 계산 가능한 함수의 고정점에 관한 것이지만 첫 번째 재귀 정리는 귀납적 정의의 계산 가능한 아날로그인 열거 연산자에 의해 결정된 고정점과 관련이 있습니다. 열거 연산자는 (A,n) 쌍의 집합입니다. 여기서 A는 (a에 대한) 유한한 수의 집합이고 n은 단일 자연수입니다. 종종 n은 특히 열거 연산자를 통해 함수를 정의할 때 자연수의 순서 쌍에 대한 코드로 간주됩니다. 열거 연산자는 열거 환원성 연구에서 중심적으로 중요합니다.

각 열거 연산자 φ는 자연 집합에서 다음에 의해 주어진 자연 집합으로 함수를 결정합니다.

${\displaystyle \Phi(X)=\{n\mid \exists A\subseteq X[(A,n)\in \Phi]\}}$

재귀 연산자는 부분 재귀 함수의 그래프가 주어졌을 때 항상 부분 재귀 함수의 그래프를 반환하는 열거 연산자입니다.

열거 연산자 φ의 고정점은 φ(F) = F와 같은 집합 F입니다. 첫 번째 열거 정리는 열거 연산자 자체가 계산 가능할 경우 고정점을 효과적으로 얻을 수 있음을 보여줍니다.

첫 번째 재귀 정리. 다음 문장은 유효합니다.

1. 임의의 계산 가능한 열거 연산자 φ φ의 경우, φ(F) = F 및 F가 이 속성을 갖는 가장 작은 집합이 되도록 재귀적으로 열거 가능한 집합 F가 있습니다.
2. 임의의 재귀 연산자 ψ의 경우, ψ(φ) = φ 및 φ가 이 속성을 갖는 가장 작은 부분 계산 가능 함수인 부분 계산 가능 함수 φ이 있습니다.

첫 번째 재귀 정리는 (재귀 이론의) 고정점 정리라고도 불립니다.^[10] 재귀 함수에 다음과 같이 적용할 수 있는 정의도 있습니다.

φ${\displaystyle :}$ ${\displaystyle {}^{}}$(${\displaystyle {}^{}}$ k) →${\displaystyle {}^{}}$($N$k) ${\$displaystyle \$Phi :\$mathbb {F} (\mathbb {N} ^{k})\rightarrow (\mathbb {N} ^{k})}를 재귀 함수라고 합니다. 그러면$$φ${\$displaystyle \Phi}에 $고정$된${\displaystyle {}_{}{}^{}}$ ${\displaystyle {}^{}}$ φ가 최소입니다. N k → N {\displaystyle f_{\$Phi:\mathbb {N} ^{k}\rightarrow \mathbb {N},$ 즉 계산$$ 가능합니다.

1) ${\displaystyle }$φ${\displaystyle {}_{}}$ϕ (f φ) =$F$φ {\displaystyle \Phi (f_${\$phi}) = f_{\Phi}}

2) ${\displaystyle }$∀ ${\displaystyle {}^{}}$ ∈ F($Nk$) {\$displaystyle$ \$forall g\in \mathbb {F}(\$mathbb {N}^{$k{\displaystyle \})\}}$에서 F$$φ$$⊆$$g {\displaystyle \Phi(g)=$g$$}$가 유지되도록 φ g (Nk)${\$displaystyle \forall g\in \mathbbb {F}(\mathbb {N} }$Phi }\subseteq g}$

3) ${\displaystyle {}_{}}$F$$φ {\displaystyle$$f_{\$Phi}}$은(는) 계산 가능합니다.

예

두 번째 재귀 정리와 마찬가지로 첫 번째 재귀 정리는 재귀 방정식 체계를 만족하는 함수를 얻는 데 사용될 수 있습니다. 첫 번째 재귀 정리를 적용하려면 먼저 재귀 방정식을 재귀 연산자로 재귀해야 합니다.

요인 함수 f에 대한 재귀 방정식을 생각해 보십시오.

$${\displaystyle {\begin{aligned}&f(0)=1\&f(n+1)=(n+1)\cdot f(n)\end{aligned}}$$

다음으로 각 n과 m에 대해 φ에는 쌍${\displaystyle (\{}$ ${\displaystyle (}$n${\displaystyle ,m}$) ${\displaystyle \},}$(${\displaystyle \mathrm{n}}$ ${\displaystyle +1,}$(n ${\displaystyle +1}$ ) ⋅ m ) ${\displaystyle(\{(n,$m)\}, (n +$$1$)\backslash$cdot m)}이 포함됩니다. 이는 f(n)이 m이면 f(n + 1)m이므로 쌍 (n + 1, (n + 1)m)이 f의 그래프에 있음을 나타냅니다. 기준 사례 f(0) = 1과 달리 재귀 연산자는 f(n + 1)의 값을 정의하기 전에 f(n)에 대한 일부 정보를 필요로 합니다.

첫 번째 재귀 정리(특히 1부)는 φ(F) = F가 되는 집합 F가 존재한다는 것을 말합니다. 집합 F는 전체적으로 자연수의 순서쌍으로 구성되며, 원하는 대로 계승 함수 f의 그래프가 될 것입니다.

재귀 연산자로 재귀할 수 있는 재귀 방정식에 대한 제한은 재귀 방정식이 실제로 최소 고정점을 정의하는 것을 보장합니다. 예를 들어, 재귀 방정식의 집합을 생각해 보십시오.

$${\displaystyle {\begin{aligned}&g(0)=1\&g(n+1)=1\\&g(2n)=0\end{aligned}}$$

첫 번째 재귀 정리에 대한 증명 스케치

첫 번째 재귀 정리의 파트 1의 증명은 빈 집합으로 시작하는 열거 연산자 φ를 반복함으로써 얻어집니다. 먼저 $k$ = ${\displaystyle 0,}$ $,$ … {\displaystyle k = 0,1,\ldots}에 대한 수열 F를 구성합니다. F를 빈 집합이라고 합니다. 귀납적으로 각 k에 대해 F를 ${\displaystyle {FK}_{}}$ ∪ φ(Fk) {\$displaystyle$ F_{k}\cup \Phi(F_{k}}라고 하자. 마지막으로 F는 ⋃ Fk {\textstyle \bigcup F_{k}}라고 합니다. 나머지 증명은 F가 재귀적으로 열거 가능하며 φ φ의 최소 고정점이라는 검증으로 구성됩니다. 이 증명에서 사용된 수열 F는_k Kleene 고정점 정리의 증명에서 Kleene 사슬에 해당합니다.

첫 번째 재귀 정리의 두 번째 부분은 첫 번째 부분부터 이어집니다. φ가 재귀 연산자라는 가정은 φ의 고정점이 부분 함수의 그래프임을 보여주는 데 사용됩니다. 핵심은 고정점 F가 함수의 그래프가 아닌 경우, F가_k 함수의 그래프가 아닌 k가 존재한다는 것입니다.

두 번째 재귀 정리와의 비교

두 번째 재귀 정리와 비교하여 첫 번째 재귀 정리는 더 좁은 가설이 만족될 때만 더 강력한 결론을 내립니다. Rogers는 첫 번째 재귀 정리에 약한 재귀 정리를 사용하고 두 번째 재귀 정리에 강한 재귀 정리를 사용합니다.^[3]

제1 재귀 정리와 제2 재귀 정리의 한 가지 차이점은 제1 재귀 정리에 의해 얻어진 고정점은 최소 고정점으로 보장되는 반면, 제2 재귀 정리로부터 얻어진 고정점은 최소 고정점이 아닐 수 있다는 것입니다.

두 번째 차이점은 첫 번째 재귀 정리가 재귀 연산자로 재귀할 수 있는 방정식 체계에만 적용된다는 것입니다. 이 제한은 순서 이론의 Kleene 고정점 정리에서 연속 연산자에 대한 제한과 유사합니다. 두 번째 재귀 정리는 모든 재귀 함수에 적용될 수 있습니다.

일반화 정리

에르쇼프는 그의 숫자 이론의 맥락에서 Kleene의 재귀 정리가 모든 완전한 숫자에 대해 성립한다는 것을 보여주었습니다.^[11] 괴델 번호 부여는 계산 가능한 함수 집합에 대한 완전한 번호 부여이므로 일반화된 정리는 특수한 경우로 크린 재귀 정리를 산출합니다.^[12]

완전한 번호 부여$$ν {\displaystyle \n이 주어졌을 때$u$ 그렇다면 두 개의 매개 변수를$$ 갖는 임의의 부분 계산 가능 $함수{\displaystyle }$ f$${\$displaystyle$f}에 대하여, 한 개의 매개 변수를$$ 갖는 총 $계산{\displaystyle }$ 가능 함수$t$ {\$displaystyle$ t$}$가 존재하므로, 다음과 같은 경우

${\displaystyle \fall n\in \mathbb {N}:\nu \circ f(n,t(n))=\nu \circ(n)}$

참고 항목

• 표시 의미론. 다른 최소 고정점 정리가 첫 번째 재귀 정리와 동일한 목적으로 사용되는 경우.
• 람다 미적분학에서 첫 번째 재귀 정리와 같은 목적으로 사용되는 고정점 조합기.
• 대각선 보조정리는 수학 논리학에서 밀접하게 관련된 결과입니다.

참고문헌

• Ershov, Yuri L. (1999). "Part 4: Mathematics and Computability Theory. 14. Theory of numbering". In Griffor, Edward R. (ed.). Handbook of Computability Theory. Studies in logic and the foundations of mathematics. Vol. 140. Amsterdam: Elsevier. pp. 473–503. ISBN 9780444898821. OCLC 162130533. Retrieved 6 May 2020.
• Jones, Neil D. (1997). Computability and complexity: From a Programming Perspective. Cambridge, Massachusetts: MIT Press. ISBN 9780262100649. OCLC 981293265.
• Kleene, Stephen C. (1952). Introduction to Metamathematics. Bibliotheca Mathematica. North-Holland Publishing. ISBN 9780720421033. OCLC 459805591. Retrieved 6 May 2020.
• Rogers, Hartley (1967). Theory of recursive functions and effective computability. Cambridge, Massachusetts: MIT Press. ISBN 9780262680523. OCLC 933975989. Retrieved 6 May 2020.

각주

더보기

• Jockusch, C. G.; Lerman, M.; Soare, R.I.; Solovay, R.M. (1989). "Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion". The Journal of Symbolic Logic. 54 (4): 1288–1323. doi:10.1017/S0022481200041104. ISSN 0022-4812. JSTOR 2274816. S2CID 32203705.

외부 링크

• Piergiorgio Odifreddi가 스탠포드 철학 백과사전에 수록한 "Recursive Functions" 항목, 2012.