일반재귀함수

수학적 논리학 및 컴퓨터학에서 일반적인 재귀 함수, 부분 재귀 함수 또는 μ-재귀 함수는 자연수에서 자연수까지의 부분 함수로서, 직관적 의미에서는 물론 형식적으로도 "계산 가능한" 함수다.함수가 합계일 경우, 총재귀함수(재귀함수로 단축되기도 한다)라고도 한다.^[1]계산가능성 이론에서 μ-재순환 함수는 정확하게 튜링 기계에^[2]^[4] 의해 계산될 수 있는 함수(Church-Turing 논문을 뒷받침하는 이론 중 하나임)임을 알 수 있다.μ-재귀 함수는 원시 재귀 함수와 밀접한 관계가 있으며, 이들의 귀납적 정의(아래)는 원시 재귀 함수의 그것과 기초한다.그러나 모든 총 재귀 함수가 원시 재귀 함수는 아니다. 가장 유명한 예는 애커만 함수다.

다른 등가 등급의 함수는 람다 미적분 함수와 마르코프 알고리즘으로 계산할 수 있는 함수들이다.

${0,1$ }의 값을 갖는 전체 재귀 함수의 하위 집합은 계산 복잡도 이론에서 복잡도 등급 R으로 알려져 있다.

정의

μ-재귀함수(또는 일반재귀함수)는 유한한 자연수의 튜플을 취하고 단일 자연수를 반환하는 부분함수다.초기 함수를 포함하는 부분함수의 가장 작은 부류로 구성, 원시 재귀, μ 연산자로 폐쇄된다.

초기 기능을 포함하며 구성 및 원시 재귀(즉, 최소화가 없는 경우)에 따라 닫히는 최소 수준의 함수는 원시 재귀 함수의 등급이다.모든 원시 재귀 함수는 총합이지만, 이는 부분 재귀 함수에 대해서는 해당되지 않는다. 예를 들어, 후속 함수의 최소화는 정의되지 않는다.원시 재귀 함수는 전체 재귀 함수의 하위 집합으로, 부분 재귀 함수의 하위 집합이다.예를 들어, Ackermann 함수는 총 재귀성이며, 비원리성이라는 것이 증명될 수 있다.

원시 또는 "기본" 함수:

$상수함수 k n$ C: 각 자연수 $n$ 과 모든 $k$ 에 대해
$C_{n}^{k}(x_{1},\ldots,x_{k})\\\\\\\stackrel {\mathrm {def}{=}}\n$

대안적 정의는 대신 제로 함수를 항상 0을 반환하는 원시 함수로 사용하고, 제로 함수, 후계 함수, 구성 연산자로부터 상수 함수를 구축한다.
후속 함수 S:
$S(x)\\\stackrel {\mathrm {def}{=}\x+1\,$
투영 함수 $P_{i}^{k}$ $P_{i}^{k}$ $P_{i}^{k}$ ${\$ ID 함수라고도 함): $모든$ 자연수 $i$ , k $i,k$ 에 $i,k$ 대해 1 $1\leq i\leq k$ $1\leq i\leq k$ $1\leq i\leq k$ k ${\displaystyle 1\leq$ i $\leq k$
$P_{i}^{k}(x_{1},\ldots,x_{k})\\\\\stackrel {\mathrm {def}{=}}\x_{i}\,$

연산자( 연산자가 정의한 함수의 영역은 연산 중에 수행되어야 하는 모든 함수 응용이 잘 정의된 결과를 제공하는 것과 같은 인수 값의 집합이다.

합성 연산자 $\circ \,$ ▼ ${\$ 대체 연산자라고도 함): $\circ \,$ Given an m-ary function $h(x_{1},\ldots ,x_{m})\,$ and m k-ary functions $g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})$ :
$h\circ (g_{1},\ldots ,g_{m})\ {\stackrel {\mathrm {def} }{=}}\ f,\quad {\text{where}}\quad f(x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})).$

This means that $f(x_{1},\ldots ,x_{k})$ is defined only if $g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}),$ and $h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))$ $h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))$ $h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))$ ) $h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})$ 이(가) 모두 정의되어 있다 $h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))$ .
원시 재귀 연산자 ρ: k-ary 함수 $g(x_{1},\ldots ,x_{k})\,$ ( x $g(x_{1},\ldots ,x_{k})\,$ , $g(x_{1},\ldots ,x_{k})\,$ … , $g(x_{1},\ldots ,x_{k})\,$ $g(x_{1},\ldots ,x_{k})\,$ ) ${\$ k $g(x_{1},\ldots ,x_{k})\,$ +2 -ary $h(y,z,x_{1},\ldots ,x_{k})\,$ h $h(y,z,x_{1},\ldots ,x_{k})\,$ z $h(y,z,x_{1},\ldots ,x_{k})\,$ $h(y,z,x_{1},\ldots ,x_{k})\,$ 1 $h(y,z,x_{1},\ldots ,x_{k})\,$ , $h(y,z,x_{1},\ldots ,x_{k})\,$ $h(y,z,x_{1},\ldots ,x_{k})\,$ ) ${\$ :}).
${\begin{aligned}\rho (g,h)&\ {\stackrel {\mathrm {def} }{=}}\ f\quad {\text{where the k+1 -ary function }}f{\text{ is defined by}}\\f(0,x_{1},\ldots ,x_{k})&=g(x_{1},\ldots ,x_{k})\\f(S(y),x_{1},\ldots ,x_{k})&=h(y,f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})\,.\end{정렬}}$

This means that $f(y,x_{1},\ldots ,x_{k})$ is defined only if $g(x_{1},\ldots ,x_{k})$ and $h(z,f(z,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})$ are defined for $z<y.$ z $z<y.$ < $z<y.$ ${\displaystyle z.$ $}$
최소화 연산자 μ: a (k+1)-ary $f(y,x_{1},\ldots ,x_{k})\,$ f ( $f(y,x_{1},\ldots ,x_{k})\,$ , $f(y,x_{1},\ldots ,x_{k})\,$ , … $f(y,x_{1},\ldots ,x_{k})\,$ , $f(y,x_{1},\ldots ,x_{k})\,$ k $f(y,x_{1},\ldots ,x_{k})\,$ ) ${\$ f $(y,x_{1},\ldots ,x_{k}\,},},$ k-ary 함수 $\mu (f)$ ) ${\displaysty$ sty $\mu$ ( $f)$ 는 다음과 같이 정의된다 $\mu (f)$ .
${\begin{aligned}\mu (f)(x_{1},\ldots ,x_{k})=z{\stackrel {\mathrm {def} }{\iff }}\ f(i,x_{1},\ldots ,x_{k})&>0\quad {\text{for}}\quad i=0,\ldots ,z-1\quad {\text{and}}\\f(z,x_{1},\ldots ,x_{k})&=0\quad \end{aligned}}$

직관적으로 최소화는 0에서 검색을 시작하고 0에서 위로 진행함, 함수를 0으로 되돌리는 최소 인수, 그러한 인수가 없거나 $F$ 가 정의되지 않은 인수에 부딪히면 검색이 종료되지 않으며 $\mu (f)$ $\mu (f)$ $\mu(f)$ 이 인수에 대해 정의되지 않는다 $\mu (f)$ . ${\displaystyle (x_{1},\ldots ,x_{k}).$ $}$

일부 교과서는 여기서 정의한 대로 μ-operator를 사용하는 반면,^[5]^[6] 다른 교과서는 μ-operator를 총 함수 $f$ 에만 적용해야 한다는 요구를 좋아한다^[7]^[8].이는 여기서 주어진 정의에 비해 μ 연산자를 제한하지만, μ-recursive 함수의 등급은 그대로 유지되는데, 이는 클린의 정상 형태 정리(아래 참조)^[5]^[6]에서 따온 것이다.유일한 차이점은 계산 가능한(즉, μ-recursive) 함수가 총체적인지 불분명하기 때문에 특정 함수 정의가 μ-recurs 함수를 정의하는지 여부를 불분명하게 된다는 것이다.^[7]

강등 연산자 $≃{\displaystyle \simeq }$ 을(를) 사용하여 부분 μ-재귀 함수를 비교할 수 있다 $\simeq$ .이것은 모든 부분함수 f와 g에 대해 정의되어 있다. 그래야 한다.

f(x_{1},\ldots,x_{k})\simeq g(x_{1},\ldots,x_{l}

두 함수가 정의되고 두 함수의 값이 동일하거나 두 함수가 정의되지 않은 경우에만 보유한다.

예

최소 연산자와 관련되지 않은 예는 원시 재귀 함수#에서 찾을 수 있다.예.

다음의 예들은 단지 최소화 운영자의 사용을 증명하기 위한 것이다; 그것들은 모두 원시적인 재귀성이기 때문에 더 복잡한 방법일지라도 그것 없이 정의될 수 있다.

$x$ $x$ 의 정수 제곱근은 $(z+1)^{2}>x$ ( $(z+1)^{2}>x$ + 1 $(z+1)^{2}>x$ ) 2 $(z+1)^{2}>x$ > $(z+1)^{2}>x$ ${\displaystyle (z+1)^{2$ 처럼 최소 $z$ $z$ ${\displaystyle$ z $}$ 로 정의할 수 있다 $x$ . $}>x}$ . Using the minimization operator, a general recursive definition is ${\displaystyle Isqrt=\mu (Not\circ Gt\circ (Mul\circ (S\circ P_{1}^{2},S\circ P_{1}^{2}),$ $P_{2}^{2$ 여기서 $N$ $o$ t ${\displaystyle Not$ G $t$ $Gt$ 및 $M$ $u$ l ${\displaysty Mul}$ 은 $Mul$ (는) 논리적 부정, 보다 큼, 곱셈이다.^[9]In fact, ${\displaystyle (Not\circ Gt\circ (Mul\circ (S\circ P_{1}^{2},S\circ P_{1}^{2}),$ $P_{2}^{2}})\;(z,x)=(\lnot$ S( $z)*S(z$ )> $x}$ 이(가) $0$ $0$ 인 $(Not\circ Gt\circ (Mul\circ (S\circ P_{1}^{2},S\circ P_{1}^{2}),P_{2}^{2}))\;(z,x)=(\lnot S(z)*S(z)>x)$ 경우에만 $0$ S $S(z)*S(z)>x$ $S(z)*S(z)>x$ ) $S(z)*S(z)>x$ > ${\displaysty S(z)*S(z)}$ 가 유지된다 $S(z)*S(z)>x$ .따라서 $Isqrt(x)$ $Isqrt(x)$ $Isqrt(x)$ t $Isqrt(x)$ ( x $Isqrt(x)$ ) $Isqrt(x)$ 은 $S(z)*S(z)>x$ ( z $S(z)*S(z)>x$ ) $S(z)*S(z)>x$ $S(z)*S(z)>x$ ( $S(z)*S(z)>x$ ) $S(z)*S(z)>x$ > x $S(z)*S(z)>x$ 이 $S(z)*S(z)>x$ ( $S(z)*S(z)>x$ ) 고정되는 $z$ z ${\displaystystyle$ z $}$ 이다 $Isqrt(x)$ . $G$ t $Gt$ 이(가) 진리를 $1$ ${\displaystyle$ 1 $}$ 만큼 인코딩하는 $Gt$ $반면$ $1$ $\mu$ {\ $displaystyle \mu}$ 은(는 $)$ $0$ ${\displaystyle$ 0 $}$ 을(를) 추구하기 $\mu$ 때문에 부정 정관절 $N$ $o$ $t$ ${\displaysty not}$ 이 필요하다 $Not$ $0$

다음 예에서는 원시 재귀가 아닌 일반적인 재귀 함수를 정의하므로 최소 연산자의 사용을 피할 수 없다.

^{[필요하다]}

총재귀함수

일반적인 재귀 함수는 모든 입력에 대해 정의되는 경우 총 재귀함수, 또는 총 튜링 기계에 의해 계산될 수 있는 경우 동등하게 총 재귀함수라고 한다.주어진 일반 재귀 함수가 전체인지 계산적으로 알 수 있는 방법은 없다. 자세한 내용은 문제 중지를 참조하십시오.

다른 계산 능력 모형과 동등성

연산성 모델의 등가성에서는 특정 입력에 대해 종료되지 않는 튜링 기계와 해당 부분 재귀 함수의 입력에 대한 정의되지 않은 결과 사이에 병렬이 그려진다.무제한 검색 연산자는 "무한 루프"(미정의 값)를 위한 메커니즘을 제공하지 않기 때문에 원시 재귀 규칙으로 정의할 수 없다.

정상형 정리

A normal form theorem due to Kleene says that for each k there are primitive recursive functions $U(y)\!$ and $T(y,e,x_{1},\ldots ,x_{k})\!$ such that for any μ-recursive function ${\displaystyle f(x_{1},\ldots ,x_{k})\!$ $}$ k 자유 변수를 사용하는 경우 $f(x_{1},\ldots ,x_{k})\!$ 다음과 같은 e가 있음

f(x_{1},\ldots ,x_{k})\simeq U(\mu y\,T(y,e,x_{1},\ldots ,x_{k}))

(

f(x_{1},\ldots ,x_{k})\simeq U(\mu y\,T(y,e,x_{1},\ldots ,x_{k}))

f(x_{1},\ldots ,x_{k})\simeq U(\mu y\,T(y,e,x_{1},\ldots ,x_{k}))

,

f(x_{1},\ldots ,x_{k})\simeq U(\mu y\,T(y,e,x_{1},\ldots ,x_{k}))

… ,

f(x_{1},\ldots ,x_{k})\simeq U(\mu y\,T(y,e,x_{1},\ldots ,x_{k}))

x

f(x_{1},\ldots ,x_{k})\simeq U(\mu y\,T(y,e,x_{1},\ldots ,x_{k}))

)

f(x_{1},\ldots ,x_{k})\simeq U(\mu y\,T(y,e,x_{1},\ldots ,x_{k}))

f(x_{1},\ldots ,x_{k})\simeq U(\mu y\,T(y,e,x_{1},\ldots ,x_{k}))

,

f(x_{1},\ldots ,x_{k})\simeq U(\mu y\,T(y,e,x_{1},\ldots ,x_{k}))

, x

f(x_{1},\ldots ,x_{k})\simeq U(\mu y\,T(y,e,x_{1},\ldots ,x_{k}))

,

f(x_{1},\ldots ,x_{k})\simeq U(\mu y\,T(y,e,x_{1},\ldots ,x_{k}))

…

f(x_{1},\ldots ,x_{k})\simeq U(\mu y\,T(y,e,x_{1},\ldots ,x_{k}))

,

f(x_{1},\ldots ,x_{k})\simeq U(\mu y\,T(y,e,x_{1},\ldots ,x_{k}))

k

f(x_{1},\ldots ,x_{k})\simeq U(\mu y\,T(y,e,x_{1},\ldots ,x_{k}))

)

{\displaystyle f(x_{1},\ldots ,x_{k}}\simeq U(\mu

y

\,e,x_{1},\ldots,x_{k

숫자 e는 함수 f를 인덱스 또는 괴델 번호라고 한다.^[10]^{: 52–53}이 결과의 결과는 (총) 원시 재귀 함수에 적용되는 μ 연산자의 단일 인스턴스를 사용하여 모든 μ-재귀 함수를 정의할 수 있다.

Minsky는 위에서 정의한 $U$ $U$ $U$ 이(가) 본질적으로 범용 튜링 시스템의 μ-recursive 등가라고 관찰한다.

U를 구축한다는 것은 숫자 n을 정확하게 해석하고 U를 직접 구축하기 위해 x의 적절한 기능을 계산하는 범용-재귀함수 U(n, x)의 정의를 적는 것으로, 우리가 범용 튜링 머신 구축에 투자한 것과 본질적으로 동일한 양의 노력과 본질적으로 동일한 아이디어를 수반할 것이다.

상징성

문헌에는 여러 가지 다른 기호들이 사용된다.상징성을 이용하는 이점은 다른 내부에 있는 연산자의 "둥지"에 의한 함수 도출이 컴팩트한 형태로 쓰기 더 쉽다는 것이다.다음 매개 변수 x₁, ...에서 x는_n x로 축약된다.

상수함수: Kleene은 "Cⁿ
_q(x) = q "를 사용하고 B-Burgess-Jeffrey(2002)는 "const_n(x) = n ":

예: C⁷
₁₃( r, s, t, u, v, w, x ) = 13

예: const₁₃ (r, s, t, u, v, w, x ) = 13

후계 함수: 클레네는 "Successor"에 x'와 S를 사용한다."서커스처"는 원시적인 것으로 간주되기 때문에 대부분의 텍스트는 다음과 같이 아포스트로피를 사용한다.

S(a) = +1 _def= a'로, 여기서 1 _def= 0', 2 _def= 0 ', 등

ID 함수: Kleene(1952)은 변수 x에_i 대한 ID 함수를 나타내기 위해 "Uⁿ
_i"를 사용하고, B-B-J는 변수 x에서₁ x에_n 대한 ID 함수 ID를ⁿ
_i 사용한다.

Uⁿ
_i_i( x ) = IDⁿ
_i( x ) = x

예: U⁷
₃ = ID⁷
₃(r, s, t, u, v, w, x ) = t

구성 (부제) 연산자: 클레네는 대담한 얼굴 S를^m
_n 사용한다("sucercessor"! )에 대해 그의 S와 혼동하지 않기 위해서!).위첨자 "m"은 함수 "f_m"의 m을^th 가리키고, 첨자 "n"은 n 변수^th "x_n"를 가리킨다.

만약 우리에게 h( x )= g(f₁(x), ... , f_m(x) )가 주어진다면.

h_m(x) = Sⁿ
_m(g, f₁, ..., f )

이와 유사하지만 하위 및 상위첨자 없이 B-B-J는 다음과 같이 쓴다.

h(x')=Cn[g, f₁ ,..., f](x_m)

원시 재귀: 클레네는 기호 "Rⁿ(기본 스텝, 유도 스텝)"을 사용하며 여기서 n은 변수 수를 나타내고, B-B-J는 "Pr(기본 스텝, 유도 스텝)(x)"을 사용한다. 주어진 예는 다음과 같다.

기본 단계: h( 0, x )=f( x ) 및
유도 단계: h( y+1, x ) = g(y, h(y, x),x )

예: + b의 원시 재귀 정의:

기본 단계: f( 0, a ) = a = U¹
₁(a)
유도 단계: f(b' , a ) = ( f ( b, a )' = g(b, f(b, a), a) = g(b, c, a) = c' = S(U³
₂(b, c, a))

R² { U¹
₁(a), S [ (U³
₂(b, c, a ) ] }

Pr{ U¹
₁(a), S[ (U³
₂(b, c, a ) ] }

예제: Kleene은 f(b, a) = b + a(변수 a와 b의 공지 반전)의 재귀적 유도를 수행하는 방법을 예시한다.그는 3가지 초기 기능으로 시작한다.

S(a) = a'
U¹
₁(a) = a
U³
₂( b, c, a ) = c
g(b, c, a) = S(U³
₂(b, c, a ) = c'
기본 단계: h( 0, a ) = U¹
₁(a)

유도 단계: h(b', a ) = g(b, h(b, a )

그가 도착하는 곳은 다음과 같다.

a+b = R²[ U¹
₁, S³
₁(S, U³
₂) ]

예

참고 항목

참조

^ "Recursive Functions". The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University. 2021.
^ 스탠포드 철학 백과사전, 항목 재귀 함수, 제1.7장: "[μ-재귀 함수의 등급]은 알론조 교회가 도입한 λ-정의 함수의 등급뿐만 아니라 앨런 튜링에 의해 도입된 튜링-컴퓨팅 함수의 등급과 일치하는 것으로 나타났다."
^ Kleene, Stephen C. (1936). "λ-definability and recursiveness". Duke Mathematical Journal. 2 (2): 340–352. doi:10.1215/s0012-7094-36-00227-2.
^ 튜링, 앨런 Mathison(12월 1937년)."계산 가능성과 λ-Definability".필기장 상징적 논리학. 2(4):153–163. doi:10.2307/2268280. JSTOR 2268280.프루프 윤곽 p.153에:λ-definable{\displaystyle \lambda{\mbox{-definable}}}⟹ tr나는 v{\displaystyle{\stackrel{triv}{\implies}}}λ-K-definable{\displaystyle \lambda{\mbox{-}}K{\mbox{-definable}}}}}튜링 computab 160{\displaystyle{\stackrel{160}{\implies}⟹. ${\mbox{Turing computable}}$ ${\stackrel {161}{\implies }}$ $\mu {\mbox{-recursive}}$ ${\stackrel {Kleene}{\implies }}$ ^[3] $\lambda {\mbox{-definable}}$
^ ^a ^b Enderton, H. B. 수학논리개론, 학술언론, 1972
^ ^a ^b Boolos, G. S, Burgess, J. P, Jeffrey, R. C, Computability and Logic, Cambridge University Press, 2007
^ ^a ^b Jones, N. D. 계산성 및 복잡성:프로그래밍 관점에서 보면, MIT 프레스, 캠브리지, 매사추세츠, 런던, 1997년
^ Kfoury, A. J, R. N. Moll, M. A. Arbib, 연산성에 대한 프로그래밍 접근법, 2차 개정, Springer-Verlag, 베를린, 하이델베르크, 1982년, 뉴욕
^ 원시 재귀 함수에 정의됨#Junctors, 원시 재귀 함수#동일성 술어, 원시 재귀 함수#복제
^ Stephen Cole Kleene (Jan 1943). "Recursive predicates and quantifiers" (PDF). Transactions of the American Mathematical Society. 53 (1): 41–73. doi:10.1090/S0002-9947-1943-0007371-8.
^ 민스키 1972, 페이지 189.

Kleene, Stephen (1991) [1952]. Introduction to Metamathematics. Walters-Noordhoff & North-Holland. ISBN 0-7204-2103-9.
Soare, R. (1999) [1987]. Recursively enumerable sets and degrees: A Study of Computable Functions and Computably Generated Sets. Springer-Verlag. ISBN 9783540152996.
Minsky, Marvin L. (1972) [1967]. Computation: Finite and Infinite Machines. Prentice-Hall. pp. 210–5. ISBN 9780131654495.

210-215페이지에서 민스키는 레지스터 머신 모델을 사용하여 μ-operator를 생성하는 방법을 보여주므로 일반적인 재귀 기능에 대한 동등성을 입증한다.

Boolos, George; Burgess, John; Jeffrey, Richard (2002). "6.2 Minimization". Computability and Logic (4th ed.). Cambridge University Press. pp. 70–71. ISBN 9780521007580.

외부 링크

[1] "Recursive Functions". The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University. 2021.

[2] 스탠포드 철학 백과사전, 항목 재귀 함수, 제1.7장: "[μ-재귀 함수의 등급]은 알론조 교회가 도입한 λ-정의 함수의 등급뿐만 아니라 앨런 튜링에 의해 도입된 튜링-컴퓨팅 함수의 등급과 일치하는 것으로 나타났다."

[3] Kleene, Stephen C. (1936). "λ-definability and recursiveness". Duke Mathematical Journal. 2 (2): 340–352. doi:10.1215/s0012-7094-36-00227-2.

[4] 튜링, 앨런 Mathison(12월 1937년)."계산 가능성과 λ-Definability".필기장 상징적 논리학. 2(4):153–163. doi:10.2307/2268280. JSTOR 2268280.프루프 윤곽 p.153에:λ-definable{\displaystyle \lambda{\mbox{-definable}}}⟹ tr나는 v{\displaystyle{\stackrel{triv}{\implies}}}λ-K-definable{\displaystyle \lambda{\mbox{-}}K{\mbox{-definable}}}}}튜링 computab 160{\displaystyle{\stackrel{160}{\implies}⟹. ${\mbox{Turing computable}}$ ${\stackrel {161}{\implies }}$ $\mu {\mbox{-recursive}}$ ${\stackrel {Kleene}{\implies }}$ ^[3] $\lambda {\mbox{-definable}}$

[Enderton.1972-5] Enderton, H. B. 수학논리개론, 학술언론, 1972

[Boolos.Burgess.Jeffrey.2007-6] Boolos, G. S, Burgess, J. P, Jeffrey, R. C, Computability and Logic, Cambridge University Press, 2007

[Jones.1997-7] Jones, N. D. 계산성 및 복잡성:프로그래밍 관점에서 보면, MIT 프레스, 캠브리지, 매사추세츠, 런던, 1997년

[8] Kfoury, A. J, R. N. Moll, M. A. Arbib, 연산성에 대한 프로그래밍 접근법, 2차 개정, Springer-Verlag, 베를린, 하이델베르크, 1982년, 뉴욕

[9] 원시 재귀 함수에 정의됨#Junctors, 원시 재귀 함수#동일성 술어, 원시 재귀 함수#복제

[10] Stephen Cole Kleene (Jan 1943). "Recursive predicates and quantifiers" (PDF). Transactions of the American Mathematical Society. 53 (1): 41–73. doi:10.1090/S0002-9947-1943-0007371-8.

[FOOTNOTEMinsky1972189-11] 민스키 1972, 페이지 189.

[1]

[2]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[3]

Search