μ 연산자

계산 가능성 이론에서 μ 연산자, 최소화 연산자 또는 무한 검색 연산자는 주어진 속성을 가진 최소 자연수를 검색합니다.원시 재귀 함수에 μ 연산자를 추가하면 모든 계산 가능 함수를 정의할 수 있습니다.

정의.

R(y, x₁, ..., x_k)이 자연수에 대한 고정(k+1)-수 관계라고 가정합니다.μ 연산자 "μy"는 무한 또는 유계 형태이며, 자연수에서 자연수까지 정의되는 "수 이론 함수"이다.그러나 "μy"는 자연수보다 술어가 충족되면 참을 전달하고 그렇지 않으면 거짓을 전달하는 술어를 포함한다.

유계 μ 연산자는 Kleene(1952) 제9장 원시 재귀 함수, §45 술어, 소인수 표현에 앞서 다음과 같이 나타난다.

"

\mu y_{y<z}R(y).\ \ {\mbox{The least}}\ y<z\ {\mbox{such that}}\ R(y),\ {\mbox{if}}\ (\exists y)_{y<z}R(y);\ {\mbox{otherwise}},\ z.

\mu y_{y<z}R(y).\ \ {\mbox{The least}}\ y<z\ {\mbox{such that}}\ R(y),\ {\mbox{if}}\ (\exists y)_{y<z}R(y);\ {\mbox{otherwise}},\ z.

<

\mu y_{y<z}R(y).\ \ {\mbox{The least}}\ y<z\ {\mbox{such that}}\ R(y),\ {\mbox{if}}\ (\exists y)_{y<z}R(y);\ {\mbox{otherwise}},\ z.

R

\mu y_{y<z}R(y).\ \ {\mbox{The least}}\ y<z\ {\mbox{such that}}\ R(y),\ {\mbox{if}}\ (\exists y)_{y<z}R(y);\ {\mbox{otherwise}},\ z.

(

\mu y_{y<z}R(y).\ \ {\mbox{The least}}\ y<z\ {\mbox{such that}}\ R(y),\ {\mbox{if}}\ (\exists y)_{y<z}R(y);\ {\mbox{otherwise}},\ z.

)

\mu y_{y<z}R(y).\ \ {\mbox{The least}}\ y<z\ {\mbox{such that}}\ R(y),\ {\mbox{if}}\ (\exists y)_{y<z}R(y);\ {\mbox{otherwise}},\ z.

。

displaystyle \mu

\ \ \ \ mbox { \ mbox

최소}}\ y <\ mbox

{

that

} \ R (

y

) \

mbox

{

if

} \ ( \

exists

y )

_ { y

<

z } R

( y )

;

\

mbox

{ } , \

z

.

\mu y_{y<z}R(y).\ \ {\mbox{The least}}\ y<z\ {\mbox{such that}}\ R(y),\ {\mbox{if}}\ (\exists y)_{y<z}R(y);\ {\mbox{otherwise}},\ z.

} " （ 225 ）。

스티븐 클레이니 어떠한 가변 y의 범위에 대한 6불평등 대한 규제 즉 y<>≤ z, 아니<> 베<>z, 아니<>y≤ z, 아니 ≤는 y<>z등 w≤≤ z."그 때 지정된 범위가 없은 y가 들어 있도록 R(y)["true"]값"μy"범위의 표현은 기수"(페이지의 주 226)y yz,;이것은 왜 허용되다고 말합니다.기본"은 z「」는, 상기의 정의에 표시됩니다.아래와 같이, 유계 μ-연산자 "μy_y<z"는 유한합 δ와 유한곱 δ라고 하는 두 개의 원시 재귀 함수, "검정을 하는" 술어 함수, 그리고 {t, f}를 {0, 1)로 변환하는 표현 함수로 정의된다.

제11장 §57 일반재귀함수에서 클린은 다음과 같은 방법으로 변수 y에 대한 무한 μ 연산자를 정의한다.

"

(\exists y)\mu yR(y)=\{{\mbox{the least (natural number)}}\ y\ {\mbox{such that}}\ R(y)\}

(

(\exists y)\mu yR(y)=\{{\mbox{the least (natural number)}}\ y\ {\mbox{such that}}\ R(y)\}

)

(\exists y)\mu yR(y)=\{{\mbox{the least (natural number)}}\ y\ {\mbox{such that}}\ R(y)\}

y

(\exists y)\mu yR(y)=\{{\mbox{the least (natural number)}}\ y\ {\mbox{such that}}\ R(y)\}

(

(\exists y)\mu yR(y)=\{{\mbox{the least (natural number)}}\ y\ {\mbox{such that}}\ R(y)\}

)

=

{

(\exists y)\mu yR(y)=\{{\mbox{the least (natural number)}}\ y\ {\mbox{such that}}\ R(y)\}

(

(\exists y)\mu yR(y)=\{{\mbox{the least (natural number)}}\ y\ {\mbox{such that}}\ R(y)\}

y (

(\exists y)\mu yR(y)=\{{\mbox{the least (natural number)}}\ y\ {\mbox{such that}}\ R(y)\}

)

(\exists y)\mu yR(y)=\{{\mbox{the least (natural number)}}\ y\ {\mbox{such that}}\ R(y)\}

{

displaystyle

(\

displaystyle)\mu

yR

(y

)=\{\

mbox{최소 (자연수)}

}}\ y\

{

mbox

{

that

}\

R

( y

(\exists y)\mu yR(y)=\{{\mbox{the least (natural number)}}\ y\ {\mbox{such that}}\ R(y)\}

} （ 279 ）

(\exists y)

。여기서 " (

(\exists y)

y )\ displaystyle ( \

exists

y

(\exists y)

)"는 "y가 존재하여 ..."를 의미합니다.")

이 경우 R 자체 또는 그 대표 함수는 만족할 때 0을 전달한다(즉, true를 전달한다). 그러면 함수는 숫자 y를 전달한다.y에는 상한이 없기 때문에 부등식은 정의에 나타나지 않습니다.

주어진 R(y)에 대해 무한 μ-operator μyR(y)( "(Ey)"에 대한 요구사항 없음)은 부분 함수이다.Kleene은 대신 전체 함수로 만든다 (p.317 참조):

$\displaystyle \varepsilon yR(x,y)="begin {case}{\text{최소 }}y"텍스트{\text{x,y}}}R(x,y)\0,{\text}}.\end {case}}$

무한 μ 연산자의 전체 버전은 다음과 같은 형태로 고차 역수학(Kohlenbach(2005))에서 연구된다.

$(\displaystyle (\displaystyle \mu ^{1})(\forall f^{1}){\big (\display n^0}(f(n)=0)\rightarrow f(\mu (f)=0)},$

여기서 위 첨자는 n이 0차, f가 1차, μ가 2차임을 의미합니다.이 공리는 고차 역수학의 일반적인 기본 이론과 결합되면 5대 시스템₀ ACA를 발생시킵니다.

특성.

(i) μ 연산자의 탐색 변수 y가 경계가 되는 원시 재귀 함수의 맥락에서, 예를 들어 아래 공식의 y < z가 술어 R이 원시 재귀인 경우(Kleene Proof #E 페이지 228)

μyR_y<z(y, x₁, ..., x_n)는 원시 재귀 함수입니다.

(ii) 총재귀 술어 R의 파라미터의 모든 값 x에_i 대해 검색 변수 y가 무제한이지만 존재함을 보증하는 (총재귀 함수)의 맥락에서

(x₁),...(x_n)(Ey) R(y, x_i, ..., x_n)는 μyR(y, x_i, ..., x_n)가 총재귀함수임을 의미한다.

여기서 (x_i)는 "모든_i x에 대하여"를 의미하며, Ey는 "y의 값이 적어도 하나 이상 존재하여..."를 의미합니다(cf Kleene(1952) 페이지 279).

그러면 5개의 원시 재귀 연산자와 무제한의 총 μ 연산자는 클린이 "일반" 재귀 함수(즉, 6개의 재귀 연산자에 의해 정의된 총 함수)라고 부르는 것을 발생시킨다.

3) 부분재귀함수의 경우부분 재귀 함수가 0으로 수렴하는 경우에만 R이 관계를 유지한다고 가정합니다.또한 부분 재귀 함수가 μyR(y, x₁, ..., x_k)가 정의되고 y가 μyR(y, x₁, ..., x_k) 이하일 때마다 (꼭 0이 아닌) 무언가로 수렴된다고 가정합니다.그러면 함수 μyR(y, x₁, ..., x_k)도 부분 재귀 함수입니다.

μ 연산자는 계산 가능 함수를 μ 재귀 함수로 특성화하는 데 사용됩니다.

건설 수학에서, 무한 검색 연산자는 마르코프 원리와 관련이 있다.

예

예 1: 경계된 μ 연산자는 원시 재귀 함수입니다.

다음 x는 문자열_i x, ..., x를_n 나타냅니다.

경계 μ 연산자는 CASE 함수를 정의하는 데 사용되는 두 개의 원시 재귀 함수(이하 "prf")로 단순하게 표현될 수 있습니다. 즉, 용어 곱 δ와 용어합 δ(cf Kleene #B 페이지 224).(필요에 따라 s t t 또는 t < z, 5 < x < 17 등 변수의 경계는 모두 적절합니다).예를 들어 다음과 같습니다.

δ_s≤t_s f(x₀, s) = f(x, 0₁) × f_t(x, 1) × ... × f(x, t)
δ_t<z_t g(x₀, t) = g(x, 0₁) + g_z-1(x, 1) + ... + g(x, z-1)

다음으로 넘어가기 전에 술어 R의 "대표함수"라는 함수 called를 도입할 필요가 있다.함수 θ는 입력(t = "진실", f = "진실")에서 출력(0, 1)까지 정의됩니다(순서 참고).이 경우 ψ. 즉, {t, f}에 대한 입력은 R의 출력에서 나옵니다.

θ(R = t) = 0
θ(R = f) = 1

Kleene은 μyR_y<z(y)이 다음과 같이 정의됨을 나타냅니다. 우리는 곱 함수 δ가 부울 OR 연산자처럼 작용하고, 합 δ가 부울 AND처럼 다소 작용하지만 단순히 {1,0}이 아닌 {δ0, δ=0}을 생성하고 있음을 알 수 있습니다.

μyR_y<z(y) = δ_t<z_s≤t(R(x, t, s)) =

[(x, 0, 0)]+

[((x, 1, 0) × ((x, 1, 1)]+

[((x, 2, 0) × ((x, 2, 1) × ((x, 2, 2)] +

...+

[((x, z-1, 0) × ((x, z-1, 1) × ((x, z-1, 2) × . ((x, z-1, z-1)]

δ는 실제로는 베이스가 δ(x, 0) = 0이고 유도 스텝이 δ(x, y+1) = δ(x, y) + δ(x, y)인 원시 재귀입니다.곱 δ는 기본 단계 δ(x, 0) = δ(x, 0) 및 유도 단계 δ(x, y+1) = δ(x, y) × δ(x, y+1)인 원시 재귀이기도 합니다.

클린에 의해 주어진 것처럼 예를 들어 방정식을 관찰하는 것이 더 쉽다.대표함수 ((R(y))의 엔트리를 작성했습니다.그는 θ(x, y) 대신 대표 함수 θ(y)를 지정했다.

y	0	1	2	3	4	5	6	7=z
((y)	1	1	1	0	1	0	0
((y) = π_s≤y(s)	1	1	1	0	0	0	0	0
((y) = σ_t<y(t)	1	2	3	3	3	3	3	3
R(y)이 "참"이 되도록 최소 y < z: µ(y) = μyR_y<z(y)				3

예 2: 무제한 μ 연산자는 원시 재귀가 아닙니다.

무한 μ 연산자(함수 μy)는 텍스트에서 일반적으로 정의된 연산자입니다.그러나 독자는 무한 μ 연산자가 왜 다른 자연수가 아닌 0을 산출하기 위한 함수 R(x, y)을 찾고 있는지 궁금할 수 있다.

각주에서는 Minsky는 내부 함수가 파라미터 "k"와 일치할 때 연산자가 종료할 수 있도록 합니다.이 예제는 다른 작성자의 형식을 보여주기 때문에 유용합니다.

"μ[col(t) = k]의 경우_t"(페이지 210)

0의 이유는 무한 연산자 μy가 함수 "product" δ의 관점에서 정의되고 μ 연산자 검색에 따라 지수 y가 "성장"할 수 있기 때문이다.위의 예에서 알 수 있듯이, 숫자 스트링 「(x, 0) *, ..., *」(x, y)의 곱 δ는_x<y, 그 멤버의 1개 「(x, i)」가 제로가 될 때마다 제로가 됩니다.

δ_s<y = δ(x, 0) * , ..., * δ(x, y) = 0

(x, i) = 0(여기서 0)입니다.따라서 δ는 부울 AND와 같이 동작합니다.

함수 μy는 단일 자연수 y = {0, 1, 2, 3, ...}을(를) "출력"으로 생성합니다.그러나 연산자 내부에는 (a) 단일 자연수를 생성하는 "숫자 변환 함수" δ 또는 (b) {t = 참, f = 거짓 중 하나를 생성하는 "증명서" R이 나타날 수 있다. (그리고 부분 재귀 함수의 맥락에서 Kleene은 나중에 세 번째 결과 "μ = 미정"^[1]을 인정한다.)

클라인은 무한 μ 연산자에 대한 자신의 정의를 두 가지 상황(a)과 (b)을 처리하기 위해 분할한다.상황(b)에서는 술어 R(x, y)이 제품 δ에서 연산능력이 되기 전에 먼저 그 대표함수 θ에 의해 출력 {t, f}이 "연산"되어 {0, 1)이 산출되어야 한다.그리고 상황 (a)에서 하나의 정의를 사용해야 하는 경우, μ 연산자를 만족시키기 위해 수 이론 함수 θ는 0을 생성해야 한다.이 문제가 해결된 상태에서, 그는 유형 (a) 또는 (b) 중 하나가 5개의 원시 재귀 연산자와 함께 (총) 재귀 함수를 산출한다는 것을 단일 "증명 III"로 증명한다.

모든 파라미터 x에 대해 (a)μyδ(x, y) 또는 (b)μyR(x, y)를 만족시키는 y가 존재함을 나타내는 데모를 제공해야 한다.

클린은 또한 "모든 x a y가 존재하기 때문에 θ(x, y)가 존재한다"는 것을 증명할 필요가 없는 세 번째 상황(c)을 인정한다.그는 이것을 열거할 수 있는 것보다 더 많은 총재귀 함수가 존재한다는 것을 증명하는데 사용한다.각주 총함수 시연.

클라인의 증명은 비공식적이며 첫 번째 예시와 유사한 예를 사용하지만, 먼저 그는 μ 연산자를 함수 δ에 대해 작동하는 "용어곱" δ를 사용하는 다른 형태로 캐스팅한다. 함수 δ는 자연수 n을 산출할 수 있으며, 자연수 n이 될 수 있으며, u 연산자의 테스트가 "만족"될 경우 0을 산출한다.

정의는 π 함수로 다시 캐스트됩니다.

μy420_y<z(y) =

(i): π(x, y) = χ_s<y(x, s)
(ii): φ(x) = ((x, y), ((x, y'), y
(iii): u = 0 또는 v > 0에 대하여 θ(z', 0, y) = y ;sig(u, v, w)가 정의되지 않는다.

이거 미묘한데?언뜻 보면 방정식은 원시 재귀를 사용하는 것처럼 보인다.그러나 Kleene은 기본 단계와 일반적인 형태의 유도 단계를 제공하지 않았습니다.

기본 단계: φ(0, x) = φ((x)
유도 단계: :(0, x) = ((y, ((0,x, x)

무슨 일이 일어나고 있는지 확인하려면 먼저 변수 x마다_i 파라미터(자연수)가 할당되어 있음을 상기해야 합니다.두 번째로 y(즉, y')를 반복하고 있는 후계 연산자를 볼 수 있습니다.셋째, 함수 μy δ(y, x)는 인스턴스가 0이 될 때까지 δ(0,x), δ(1,x)의 인스턴스만 생성하는 것을 알 수 있습니다.넷째, 인스턴스 θ(n, x)가 0을 산출하면, 중간항인 v = θ(x, y')가 0을 산출한다.마지막으로 중간항 v = 0일 때 μyδ_y<z(y)는 line iii 및 "line"을 실행한다.클린 방정식 (ii)과 (iii)의 제시를 통해 라인 (ii)이 출구를 나타내며, 검색이 성공적으로 θ(y)를 만족시킬 y를 찾고 중간 곱항 θ(x, y')가 0일 때만 취해지는 출구를 나타내며, 연산자는 검색을 θ(z', 0, y') = y로 종료한다.

θ(x, y), θ(x, y'), 즉,

((((x, 0), ,(x, 1), 0,
((x, 1), ((x, 2), 1)
τ(x, 2), ((x, 3), 2)
((x, 3), ((x, 4), 3)
...y=n에서 일치가 발생할 때까지 다음 작업을 수행합니다.
μ(z', 0, y) = μ(z', 0, n) = n 그러면 μ(μ)의 검색이 수행됩니다.

예를_i 들어, Kleene "..." (x_n, ..., x)의 고정값과 "x_i(x_n, ..., x, y)"에 대해 간단히 " '(y)"라고 하는 것은 다음과 같습니다.

y	0	1	2	3	4	5	6	7	기타.
((y)	3	1	2	0	9	0	1	5	. . .
π(y) = π_s≤y(s)	1	3	3	6	0	0	0	0	. . .
				↑
R(y)이 "참"이 되도록 최소 y < z: µ(y) = μyR_y<z(y)				3

예 3: 추상 머신에 대한 무한 μ 연산자의 정의

Minsky(1967) 페이지 21과 Boolos-Burgess-Jeffrey(2002) 페이지 60-61은 모두 μ 연산자를 추상 기계로 정의한다. 각주 μ의 대체 정의를 참조한다.

다음 시연은 각주에 언급된 "독특함" 없이 민스키를 따라한다.시연에서는 Peano Axioms 및 원시 재귀 함수와 밀접하게 관련된 "successor" 카운터 머신 모델을 사용합니다.이 모델은 (i) "명령 레지스터"(IR)의 이름을 변경하는 "명령 레지스터"(ii)와 (ii) 하나의 자연수만 포함할 수 있는 몇 개의 "등록기" 및 (ii) 다음 표에 설명된 4개의 "명령어 집합으로 구성된 유한 상태 머신으로 구성됩니다.

다음에서 기호 "[ r ] "는 "내용"을 의미하며, "→r"은 등록 r에 관한 동작을 의미한다.

설명	니모닉	레지스터 "r"에 대한 작업	지시대장에 대한 조치, IR
CLEAR 레지스터	CLR ( r )	0 → r	[ IR ] + 1 → IR
인크루먼트 레지스터	INC ( r )	[ r ] + 1 → r	[ IR ] + 1 → IR
같으면 점프	JE(r₁, r₂, z)	없음.	IF [r₁] = [r₂ ] 그러면 z → IR 기타 [IR] + 1 → IR
정지	H	없음.	[IR] → IR

최소화 연산자 μy[φ(x, y)]알고리즘은 본질적으로 파라미터 y(자연수)의 값이 증가함에 따라 함수 ((x, y)의 인스턴스 시퀀스를 작성합니다.이 프로세스는 함수 ((x, y)의 출력과 미리 설정된 수(일반적으로 0) 사이에 일치가 발생할 때까지 계속됩니다.따라서 θ(x, y)를 평가하려면 처음에 각 변수 x에 자연수를 할당하고 레지스터 w에 match-number(일반적으로 0)를 할당하고 y를 등록하기 위한 숫자(일반적으로 0)를 할당해야 한다.

주: 무제한 μ 연산자는 이 일치 시도 프로세스를 무한히 계속하거나 일치가 발생할 때까지 계속합니다. 따라서 "y" 레지스터는 무제한이어야 합니다. 임의 크기의 수를 "유지"할 수 있어야 합니다. "실제" 컴퓨터 모델과 달리 추상 기계 모델은 이를 가능하게 합니다. 유계 μ 연산자의 경우 하한 μ 연산자는 y의 내용이 0이 아닌 수치로 설정된 상태에서 시작합니다. 상한 μ 연산자는 상한을 나타내는 숫자와 추가 비교 연산을 포함하는 추가 레지스터 "ub"가 필요합니다. 알고리즘은 하한과 상한을 모두 제공할 수 있습니다.

다음에서는 명령 레지스터(IR)가 명령 번호 "n"에서 μy "루틴"을 만난다고 가정합니다.첫 번째 액션은 전용 "w" 레지스터에 숫자를 확립하는 것입니다.이것은 알고리즘이 종료하기 전에 함수 θ(x, y)가 생성해야 하는 숫자의 "예"입니다(일반적으로 이것은 숫자 0이지만, 0 이외의 숫자의 사용에 대해서는 각주를 참조해 주세요).명령어 "n+1"에서 알고리즘의 다음 액션은 "y" 레지스터를 클리어하는 것입니다. "y"는 0부터 시작하는 "업 카운터"로 작동합니다.다음으로 명령 "n+2"에서 알고리즘은 함수 "(x, y)"를 평가하며, 이 작업을 수행하려면 j 명령이 필요하다고 가정하고, 평가 종료 시 "(x, y)" 레지스터 """에 출력을 저장합니다.(n+j+3)rd 명령에서 알고리즘은 "w" 레지스터의 수(예를 들어 0)와 """ 레지스터의 수를 비교합니다. 알고리즘이 성공하고 출구를 통해 탈출하는 경우, "y" 레지스터의 내용을 증가시키고 이 새로운 y 값으로 루프하여 함수 test(x, y)를 다시 테스트합니다.

적외선		설명	레지스터에 대한 작업	지시대장 IR에 대한 조치
n	μy[gl(x, y)],	CLR ( w )	0 → w	[ IR ] + 1 → IR
n+1		CLR( y )	0 → y	[ IR ] + 1 → IR
n+2	루프:	§(x, y)	φ([x], [y]) → φ	[ IR ] + j + 1 → IR
n+j+3		JE(,, w, exit)	없음.	케이스: { IF [ ]=[ w ] 그런 다음 → IR을 종료합니다. 기타 [IR] + 1 → IR }
n+j+4		INC ( y )	[ y ] + 1 → y	[ IR ] + 1 → IR
n+j+5		JE(0, 0, 루프)	무조건 점프	케이스: { IF [ r₀ ]=[ r₀ ] 그러면 루프 → IR ELSE 루프 → IR }
n+j+6	종료:	기타.

「」를 참조해 주세요.

매카시 형식주의

각주

전체 기능 시연

함수가 전체 함수가 될 경우 반드시 필요한 것은 파라미터_i x 자연수 y의 각 조합에 대해 μ 연산자를 만족시켜 계산을 나타내는 알고리즘이 종료되도록 하는 다른 방법(예: 유도)에 의한 시연입니다.

"...우리는 항상 방정식의 시스템이 실제로 일반적인 함수를 정의한다고 가정하는 것을 주저해야 합니다(즉, 총함수입니다.우리는 보통 이에 대한 보조 증거를 필요로 한다. 예를 들어, 각 인수 값에 대해 연산이 고유한 값으로 끝나는 귀납적 증거의 형태로." (민스키(1967) 페이지 186)

즉, 함수는 일반 재귀라는 설명이 효과적이지 않는 한 일반(즉, 전체) 재귀적이라는 것을 증명했다는 이유로 효과적으로 계산할 수 있다고 주장해서는 안 된다.

이 관습에 지성에 대한 예를 들어 그 예에 보이는 음악 재귀적 functions—even 가장 단순한 절단 뺄셈 알고리즘"x-y)d" 수 있는 만큼의 확실하지 않은 경우)<>y,(1)도 종결,(2)수는(즉 뭔가 형식과 잘못된 그래서 수익 자연수로 간주되지 않는다), 또는(3)속임수: 잘못된 numbe.개발올바른 형식으로."적절한" 감산 알고리즘은 모든 "사례"에 세심한 주의를 기울여야 합니다.

(x, y) = {(0, 0), (a, 0), (0, b), (a4b, b), (a=b, b), (a<b, b)}.

그러나 알고리즘이 인스턴스 {(0, 0), (1, 0), (0, 1), (2, 1), (1, 2)에서 예상 출력을 생성하는 것으로 나타났다고 해도, 케이스(x, y) = (n, m)가 모두 예상 결과를 산출하는 "실증적 데모"를 고안할 수 있을 때까지 우리는 불안한 느낌을 받게 된다.Kleene의 요점은 우리의 "시연" (즉, 우리의 시연인 알고리즘)이 효과적이라고 여겨질 만큼 충분히 설득력이 있는가?

Minsky(1967년)와 Boolos-Burgess-Jeffrey(2002년)의 무한 μ 연산자의 대체 추상 기계 모델

무한 μ-입자는 Minsky(1910) 페이지 210에 의해 정의되지만 독특한 결함이 있다. 즉, 술어(IF-THEN-ELSE 테스트)가 충족될 때 t=0을 산출하지 않고 오히려 t=2를 산출한다.Minsky 버전에서는 카운터는 "t"이며 함수 θ(t, x)는 레지스터 θ에 그 번호를 저장합니다.통상적인 μ정의 레지스터에서는 w는 0을 포함하지만 Minsky는 임의의 숫자 k를 포함할 수 있음을 관찰합니다.민스키의 명령 집합은 다음과 같습니다. 여기서 "JNE" = 같지 않으면 z로 점프:

{ CLR (r), INC (r), JNE (r_j, r_k, z) }

적외선		설명	레지스터에 대한 작업	지시대장에 대한 조치, IR
n	μy(x):	CLR ( w )	0 → w	[ IR ] + 1 → IR
n+1		CLR ( t )	0 → t	[ IR ] + 1 → IR
n+2	루프:	§ (y, x)	φ ( [ t ] , [ x ]) → φφ	[ IR ] + j + 1 → IR
n+j+3		INC ( t )	[ t ] + 1 → t	[ IR ] + 1 → IR
n+j+4		JNE(,, w, 루프)	없음.	케이스: { IF [ ]≠ [ w ] 그러면 "확장" → IR 기타 [IR] + 1 → IR }
n+j+5		INC ( t )	[ t ] + 1 → t	[ IR ] + 1 → IR
n+j+6	종료:	기타.

무한 μ 연산자는 다음과 같은 명령 집합을 가진 카운터 머신에 대해 Boolos-Burgess-Jeffrey(2002) 페이지 60-61에 의해 정의됩니다.

{ CLR (r), INC (r), DEC (r), JZ (r, z), H }

이 버전에서 카운터 "y"는 "r2"라고 불리며 함수 f(x, r2)는 레지스터 "r3"에 그 번호를 저장합니다.아마도 Boolos-Burgess-Jeffrey clear r3가 무조건적인 루프 점프를 용이하게 하기 위해서일 것이다.이는 종종 "0"을 포함하는 전용 레지스터 "0"을 사용하여 이루어진다.

적외선		설명	레지스터에 대한 작업	지시대장에 대한 조치, IR
n	μ_r₂[f(x, r₂)],	CLR ( r₂ )	0 → r₂	[ IR ] + 1 → IR
n+1	루프:	f(y, x)	f( [ t ] , [ x ]) → r₃	[ IR ] + j + 1 → IR
n+2		JZ(r₃, exit)	없음.	IF [r₃] = 0 그런 다음 → IR을 종료합니다. 기타 [IR] + 1 → IR
n+j+3		CLR ( r₃ )	0 → r₃	[ IR ] + 1 → IR
n+j+4		INC ( r₂ )	[ r₂ ] + 1 → r₂	[ IR ] + 1 → IR
n+j+5		JZ(r₃, 루프)		케이스: { IF [ r₃ ]= 0 그러면 루프 → IR 기타 [IR] + 1 → IR }
n+j+6	종료:	기타.

레퍼런스

^ 페이지 332ff

Kleene, Stephen (2009) [1952], Introduction to Metamathematics, North-Holland, ISBN 9780923891572, OCLC 935015457
Kohlenbach, Ulrich (2005), Higher Order Reverse Mathematics, Reverse Mathematics 2001, Lecture notes in Logic, Cambridge University Press, doi:10.1017/9781316755846.018, ISBN 9781316755846
Minsky, Marvin L. (1972) [1967], Computation: Finite and Infinite Machines, Prentice-Hall, ISBN 9780131654495, OCLC 974146753

210~215페이지에서 Minsky는 레지스터 머신 모델을 사용하여 μ 연산자를 생성하는 방법을 보여줌으로써 일반적인 재귀 함수에 대한 등가성을 보여준다.

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

[1] 페이지 332ff

[1]

Search

μ 연산자

네임스페이스

더

목차

정의.

특성.

예

예 1: 경계된 μ 연산자는 원시 재귀 함수입니다.

예 2: 무제한 μ 연산자는 원시 재귀가 아닙니다.

예 3: 추상 머신에 대한 무한 μ 연산자의 정의

「」를 참조해 주세요.

각주

전체 기능 시연

Minsky(1967년)와 Boolos-Burgess-Jeffrey(2002년)의 무한 μ 연산자의 대체 추상 기계 모델

레퍼런스

Search

μ 연산자

정의.

특성.

예

예 1: 경계된 μ 연산자는 원시 재귀 함수입니다.

예 2: 무제한 μ 연산자는 원시 재귀가 아닙니다.

예 3: 추상 머신에 대한 무한 μ 연산자의 정의

「 」를 참조해 주세요.

각주

전체 기능 시연

Minsky(1967년)와 Boolos-Burgess-Jeffrey(2002년)의 무한 μ 연산자의 대체 추상 기계 모델

레퍼런스

「」를 참조해 주세요.