카운터 머신 모델

일부 저자는 "counter machine"과 동의어로 "register machine"이라는 이름을 사용하지만, 이 문서에서는 "register machine"속 중 가장 원시적인 종인 "counter machine"의 세부사항과 예만을 설명한다.

카운터머신에는 에르메스(1954년), 카펑스트(1957년), 에르쇼프(1958년), 페테르(1958년), 민스키(1961년) 민스키(1967년), 멜작(1961년), 람베크(1961년), 셰퍼드손(1961년), 슈투르기스슈아게(1963년)의 모델이 있다.이러한 모델에 대해서는, 이하에 자세하게 설명합니다.

모델 상세

1954년: 에르메스 모델

셰퍼슨과 스터기스는 "[디지털 컴퓨터가 튜링 기계에 적용됨]의 보편성의 증거는 헤르메스에 의해 처음 기록된 것으로 보인다. 헤르메스는 [7--그들의 참조 번호]에서 이상적인 컴퓨터가 튜링 기계의 동작을 복제하도록 어떻게 프로그램될 수 있는지를 보여주었다." (셰퍼슨과 스터기스 페이지 219).

셰퍼드슨과 스터기스는 다음과 같이 관찰한다.

「Kaphengst의 어프로치는, 적어도 각각 임의의 긴 단어를 격납할 수 있는 무수한 스토리지 레지스터를 수용할 수 있을 정도로 이상화했을 경우, 현재의 디지털 컴퓨터의 보편성을 직접 증명하는 것이 흥미롭다」(Sheferdson과 Sturgis, 페이지 219).

단 두 개의 산술 명령어는

후계자 조작
두 숫자의 동일성 검정

나머지 작업은 레지스터에서 어큐뮬레이터로, 어큐뮬레이터에서 레지스터로, 또는 테스트 점프로 이행합니다.

Kaphengst의 논문은 독일어로 쓰여져 있습니다.Sheperdson과 Sturgis의 번역에는 mill과 order와 같은 용어가 사용되고 있습니다.

기계에는 "a mill"(어큐뮬레이터)이 포함되어 있습니다.Kaphengst는 제분/적금기를 "무한" 기호로 지정하지만, 다음 설명에서는 "A"를 사용합니다.또한 "오더 레지스터"("시퀀스"가 아닌 "명령"과 같은 순서")도 포함됩니다.(이 사용법은 Burks-Goldstine-von Neumann(1946) 보고서의 "... an Electronic Computing Instrument" 설명에서 따온 것입니다.)주문/지시 레지스터는 레지스터 "0"입니다.또한 Sheperdson과 Sturgis의 설명에서는 명확하지 않지만, 이 모델에는 Kaphengst에 의해 "infinity-prime"로 지정된 "확장 레지스터"가 포함되어 있으므로 "E"를 사용합니다.

지침은 레지스터에 저장됩니다.

"...그래서 기계는 실제 컴퓨터와 마찬가지로 자체 프로그램으로 산술 연산을 수행할 수 있습니다." (p.244).

따라서 이 모델은 사실상 랜덤액세스 머신입니다다음 중 "r"은 레지스터 r 등의 내용을 나타낸다.

		액션:	묘사
D1:	C(r, A)	[ r ] → A, [ r ] → r	레지스터 r의 내용을 어큐뮬레이터 A에 복사
D2:	C(A, r)	[A] → r, [A] → A	A의 내용을 복사하여 r를 등록합니다.
C1:	O(A)	0 → A	제로(클리어) 축전지 A
답 1:	P(A)	[ A ] + 1 → A	축전지 A의 내용물을 증가(추가)합니다.
F1:	J(A) [E1]	[A] = 0이면 "1번 출구"로 이동합니다.	축전지 A의 내용물이 0이면 점프합니다.
G1:	온(A)	IF [A] = [r] 그렇다면 0 → < A > ELSE 1 → A	A의 내용이 r의 내용인 경우 A의 내용을 지우고, 그렇지 않은 경우 A=1을 "설정"한다.
G2:	O'(A)	1 → A	A = 1의 "설정" 내용

Shepherdson과 Sturgis는 Mill/Acumulator A를 제거하고 Kaphengst 명령을 줄여 등록 "복사", 산술 연산 "증분" 및 "등록-등록 비교"를 수행합니다.감소가 없는지 관찰합니다.이 모델은 거의 글자 그대로 Minsky(1967)에서 볼 수 있습니다.자세한 내용은 아래 섹션을 참조하십시오.

		액션:	설명:
a:	P(A)	[ A ] + 1 → A	축전지 A의 내용물을 증가(추가)합니다.
d.	C(r_j, r_k)	[ r_j ] → r_k, [ r_j ] → r_j	레지스터_j r의 내용을 복사하여 r을 등록합니다_k.
f:	J(r) [E1]	IF [ r ] = 0인 경우 "1번 종료" 그렇지 않으면 다음 지시로 이동합니다.	레지스터 r의 내용이 0이면 점프합니다.
c:	E(r_j, r_k)	IF [r_j] = [r_k] 그렇다면 0 → EELSE 1 → E	r의 내용이_j r = r의_k 내용이면 레지스터 E의 내용을 지우고, 그렇지 않으면 "설정" E=1

1958: Ershov의 연산자 알고리즘 클래스

Shepherdson과 Sturgis(1963)는 Ersov의 모델이 레지스터에 프로그램을 저장할 수 있음을 관찰했다.그들은 Ersov의 모델이 다음과 같다고 주장한다.

		액션:	설명:
d.	C(r_j,r_k)	[ r_j ] → r_k, [ r_j ] → r_j	레지스터_j r의 내용을 복사하여 r을 등록합니다_k.
d'를 클릭합니다.	C' (r_j,r_k)	[ r_j ] +1 → r_k, [ r_j ] → r_j	레지스터_j r의 증분 내용을 복사하여 r을 등록합니다_k.
e.	J[E1]	'1번 출구'로 이동합니다.	무조건 '1번 출구'로 점프
f*:	J(r_j, r_k)[E1, E2]	IF_k [ r_j ] [ [ r ]그러면 "Exit 1"로 점프하고, 그렇지 않으면 "Exit 2"로 점프합니다.	레지스터_j r의 내용이 r의_k 내용보다 작거나 같으면 E1을 종료하고, 그렇지 않으면 E=2로 점프합니다.

1958년: Petter's "처리"

Shepherdson과 Sturgis(1963)는 Péter의 "치료"가 다음 표에 표시된 지침과 동등하다는 것을 관찰했다.특히, 다음의 순서에 대해 코멘트를 실시합니다.

"모든 부분재귀함수의 계산가능성을 가능한 한 빨리 증명하는 관점에서 Petter's는 아마도 가장 좋을 것이다; 튜링 기계에 의한 계산가능성을 증명하기 위해서는 우리가 위에서 취한 선을 따라 복사연산에 대한 추가 분석이 필요하다." (Sheferdson and Sturgis (1963) 페이지 246)

		액션:	설명:
c:	O(n)	0 → [n]	제로(클리어) 레지스터 n
d.	C(m,n)	[ m ] → n, [ m ] → [ m ]	레지스터 m의 내용을 복사하여 등록 n
d'를 클릭합니다.	C'(m,n)	[ m ] + 1 → [ n ], [ m ] → [ m ]	레지스터 m의 증가된 내용을 복사하여 n을 등록합니다.
e.	J(m, n)[E1, E2]	[m]=[n] E1로 점프하고 그렇지 않으면 E2로 점프합니다.	m의 내용이 n의 내용과 같으면 조건부로 E1로 점프하고, 그렇지 않으면 E2로 점프합니다.

1961년: Minsky의 부분 재귀 함수 모델은 단 두 개의 명령의 "프로그램"으로 축소됨

에밀 포스트(태그 체계)와 힐베르트의 10번째 문제(힐베르트의 문제, 디오판타인 방정식)에 대한 그의 연구에서 민스키는 다음과 같은 정의를 내렸다.

"가장 간단한 산술 연산의 프로그램만을 포함하는 재귀 함수 이론의 흥미로운 기초" (민스키(1961) 페이지 437).

그의 "Theorem Ia"는 모든 부분 재귀 함수는 "형식의 명령 Ij를 사용하여 두 정수 S1과 S2에서 작동하는 프로그램"으로 표현된다고 주장한다.민스키(1961) 페이지 449):

		액션:	설명:
a.	ADD(r, I_j1)	[ r ] + 1 → r; 명령_j1 I로 이동합니다.	레지스터 r의 내용을 증가시키고(추가 1), 명령_j1 I로 이동합니다.
b.	서브(r, I_j1, I_j2)	[ r ] 0 0일 경우 instr로 이동합니다.I_j2 ELSE [ r ]-1 → r로 이동하여 instr로 이동합니다.나_j1	레지스터 r의 내용이 0인 경우_j2 명령 I로 점프하고 레지스터 r의 내용을 ELSE에서 감소(감산)한 후 instr로 점프합니다.제가_j1.

첫 번째 정리는 두 번째 "Theorem IIa"의 맥락이다.

"...폼의 명령_j I를 사용하여 하나의 정수 S[단일 레지스터 r1에 포함]에서 작동하는 프로그램에 의한 부분 재귀 함수를 나타냅니다."

		액션:	설명:
a.	멀티(K_j, I_j1)	[ r1 ]*K_j → r1. 명령_j1 I로 이동합니다.	레지스터 r1의 내용에 상수_j K를 곱합니다.
b.	DIV(K_j, I_j1, I_j2)	[ r1 ] / Kj = 0 으로 이동하고, 그렇지_j2 않으면 I로 이동합니다_j1.	레지스터 1의 내용을 상수_j K로 나누면 나머지가 없을 경우 instr.그렇지_j1 않으면.나_j2

이 두 번째 형태에서 기계는 "정수 S"를 처리하기 위해 Gödel 숫자를 사용합니다.그는 첫 번째 머신/모델에 사용 가능한 레지스터가 4개 있으면 이를 수행할 필요가 없다고 단언한다.

1961: Melzak 모델: 가감산 및 적절한 감산을 포함한 단일 삼원 명령

"Q-머신이라고 불리는 원시적인 장치를 설명하는 것이 우리의 목표입니다. 이 장치는 논리가 아닌 산술을 통해 효과적인 계산 능력을 얻습니다.그 세 가지 연산은 계산, 음이 아닌 정수 비교, 전송이다." (Melzak (1961) 페이지 281)

그의 모델의 문맥을 사용하면, 「계속적으로 가산한다」(자갈을 던져 넣는다) 또는 「계속적으로 감산한다」를 의미하고, 「전송한다」는 것은, A공에서 B공으로 컨텐츠를 이동한다(복사하지 않는다)는 것을 의미해, 수치를 비교하는 것은 자명하다.이것은 세 가지 기본 모형이 혼합된 것으로 보입니다.

Melzak의 물리적 모델은 땅에 있는 구멍 {X, Y, Z 등}과 특수 구멍 S(싱크 또는 공급 또는 둘 다)에 조약돌을 무제한 공급하는 것이다.Melzak은 말하지 않는다.)

"Q-머신은 무한히 많은 로케이션으로 구성되어 있습니다.S, A1, A2, ..., 이들 로케이션 사이에 분산되어 있는 카운터의 무한히 큰 공급, 프로그램, 명령의 실행만을 목적으로 하는 오퍼레이터입니다.처음에는 로케이션 중 유한한 수를 제외한 모든 수가 비어 있으며, 나머지 각각은 유한한 수의 카운터를 포함합니다.(p.283, 굵은 글씨 추가)

이 명령은 그가 "XYZ"라고 부르는 단일 "삼원 연산"입니다.

"XYZ"는 다음과 같은 동작을 나타냅니다.

구멍 Y의 조약돌 수를 세어봐
다시 Y로 돌려보내고
이 번호를 X번 구멍에서 제거해 보겠습니다.홀 X가 비어 있기 때문에 이것이 불가능한 경우 아무것도 하지 않고 명령 #I;ELSE로 이동합니다.
X에서 Y 양을 제거하고 (iv) 그것들을 Z 구멍의 양에 더한다.

가능한 모든 작업 중 일부는 허용되지 않습니다(아래 표 참조).

허용된	설명	구멍 'X'	구멍 "Y"	구멍 'Z'	지시의 의미
아니요.	XXX
	XXY	( [ X ] - [ X ] ) = 0 → X	[ Y ] + [ X ] →	[ Z ] → Z	X의 모든 조약돌을 X에서 가져와 Y에 추가하다
	XXS	( [ X ] - [ X ] ) = 0 → X	[Y] → Y	[ Z ] → Z	X의 모든 조약돌을 X에서 가져와 싱크/소스 S에 넣는다.
아니요.	XYX
	XYY	[X] - [Y] → X	[ Y ] + [ Y ] → Y	[ Z ] → Z	X에서 Y에 배치되어 Y의 자갈 수를 Y의 두 배로 늘립니다.
	XYS
아니요.	XSX
아니요.	XSY
아니요.	XSS
	XYZ	[X] - [Y] → X	[Y] → Y	[ Z ] + [ Y ] → Z	X에서 추출하여 Z에 더한 Y의 조약돌의 수
	시스템	[X] → X	[ Y ] + [ Y ] → Y	[ Z ] → Z	S에서 추출하여 Y에 더한 Y의 조약돌 개수, Y의 수를 두 배로 늘립니다.
	시스템	[X] → X	[Y] → Y	[ Z ] + [ Y ] → [ Z ]	S에서 추출하여 Z에 더한 Y의 자갈 수

Melzak 모형에 대한 일부 관측치:

모든 홀이 0으로 시작되면 어떻게 증가합니까?이것은 불가능한 것 같습니다.한 구멍에 조약돌을 1개씩 넣어야 합니다.
조건부 "점프"는 XYZ 유형의 모든 인스턴스에서 발생합니다.이는 X에 충분한 카운터/피블이 없기 때문에 실행할 수 없는 경우 점프가 발생하고 실행할 수 있는 경우 다음 순서로 명령이 계속되기 때문입니다.
SXY도 XXY도 항상 실행할 수 있기 때문에 점프를 일으킬 수 없습니다.
Melzak은 자신의 모델에 간접(랜덤 액세스 머신 참조)을 추가하여 두 가지 사용 예를 제시합니다.하지만 그는 이것을 더 이상 추구하지 않는다.이것은 문헌에 등장하는 최초의 검증된 "간접" 인스턴스입니다.
두 논문 모두 Z의 논문입니다. 알렉산더 멜작(윌리엄 로웰 푸트남 수학 콩쿠르 우승자 1950)은 1961년 5월 15일, 요아힘 람벡은 한 달 뒤인 1961년 6월 15일 각각 같은 권에 수록되어 있다.
멜작의 주장은 사실인가요?– 이 모델은 "몇 분간의 설명 후에 평균적인 초등학생이 이해할 수 있을 정도로 단순하다"(p.282).독자가 결정해야 할 것이다.

1961년: Lambek "abacus" 모델: Melzak 모델을 X+로 원자화, X- 테스트 포함

람베크의 원래 "아바쿠스" 모델(1962) :

Lambek는 Melzak의 논문을 참조한다.그는 Melzak의 단일 3-파라미터 연산(명령 주소를 카운트하면 실제 4개)을 2-파라미터 증분 "X+" 및 3-파라미터 감소 "X-"로 원자화합니다.그는 또한 "프로그램"에 대한 비공식적 정의와 공식적인 정의를 제공한다.이 형태는 민스키(1961년) 모델과 사실상 동일하며 Boolos-Burgess-Jeffrey(2002년)에 의해 채택되었다.

		액션:	설명:
a.	X+(r, I_a)	[ r ] + 1 → r; 명령_a I로 이동합니다.	레지스터 r의 내용 증가(1을 추가)
b.	X-(r, I_a, I_b)	[ r ] ,0 의 경우는, instr 로 이동합니다.그렇지_b 않으면 [r]-1 → r로 이동하고 instr로 이동합니다.나_a	레지스터 r의 0에 대한 첫 번째 테스트 후 감소(에서 1 빼기) 내용

Boolos-Burgess(1970년 등), Boolos-Burgess-Jeffrey(2002년)의 주판 모델:

1970년부터 저자들은 람베크(1961)의 무한 주판 모델을 사용한다.이 일련의 위키피디아 문서는 상징성을 사용하고 있습니다. 예를 들어, "[ r ] +1 → r" "숫자 'r'로 식별되는 레지스터의 내용 + 1은 [] 레지스터 번호 'r'의 내용을 대체합니다."

그들은 람벡의 이름 "abacus"를 사용하지만, 멜작의 조약돌-in-holes 모델을 따르며, 이 모델에 의해 "stones-in-boxes" 모델로 변형되었다.Lambek의 원래 주판 모델과 마찬가지로, 이 모델에서는 Minsky(1961)의 비순차 명령어 사용이 유지되고 있습니다.기존의 컴퓨터와 같은 기본 순차 명령어 실행과는 달리 다음 명령어_a I는 명령어에 포함되어 있습니다.

단, B-B와 B-B-J는 지정된 파라미터(Lambek 버전에 나타난 바와 같이)를 가진 니모닉에서 변수 "X"를 사용하지 않고 명령 니모닉은 레지스터 자체를 지정합니다(예: "2+" 또는 "3-3").

		액션:	설명:
a1.	1+(I_a)	[ r1 ] + 1 → r1 그런 다음 명령_a I로 이동합니다.	레지스터 #1의 내용 증가(추가 1)
b1.	1_a - (I_b, I)	[ r1 ] 0 0이면 I else [ r1 ]-1 → r1로 이동하고_b I로 이동합니다_a.	레지스터 r1의 내용이 레지스터 #1의 0 ELSE 감소(감산 1) 내용인 경우 명령_b I로 이동합니다.

1963년: 셰퍼드슨과 스터기스의 모델

218페이지에서 쉐퍼드슨과 스터기스는 민스키(1961년)가 MIT 링컨 연구소의 보고서 형식으로 그들에게 나타났다고 언급하고 있다.

섹션 10에서 우리는 하나 또는 두 개의 테이프로 부분 재귀 함수를 계산하기 위한 정리(민스키의 결과 [21, 참조] 포함)를 중간 형식 중 하나에서 비교적 쉽게 얻을 수 있다는 것을 보여준다(p.218).

그들의 모델은 Hao Wang(1957)과 그의 Wang B-machine의 모델과 정신에 큰 영향을 받았다(Post-Turing machine 참조).다음과 같이 요약합니다.

"...우리는 Wang이 제안하고 시작한 계산의 실용적 측면과 이론적 측면 사이에서 '재조정'을 한 걸음 더 나아가려고 노력했습니다."

Unlimited Register Machine URM: 이것은 가장 유연한 머신입니다.는 1, 2, 3, ...번호가 매겨진 레지스터의 디넘버블 시퀀스로 구성되며, 각 레지스터는 임의의 자연수를 저장할 수 있습니다.그러나 각 특정 프로그램에는 이러한 레지스터의 수가 한정되어 있습니다.(p.219).즉, 레지스터의 수는 무한하며 각 레지스터의 "크기"는 무한합니다.

이들은 다음과 같은 명령 집합(페이지 219)과 다음과 같은 "참고"를 제공합니다.

	URM 모델:	액션:	설명:
a.	P(n)	[ r ] + 1 → r	레지스터 r의 내용 증가(1을 추가)
b.	D(n)	[ r ] - 1 → r	레지스터 r의 감소(제1절감) 내용
c:	O(n)	0 → r	제로(클리어) 레지스터 r
d.	C(m,n)	[ r_j ] → r_k, [ r_j ] → r_j,	레지스터_j r의 내용을 복사하여 r을 등록합니다_k.
e.	J[E1]	'1번 출구'로 이동합니다.	무조건 '1번 출구'로 점프
f:	J(r) [E1]	IF [ r_j ] = 0인 경우 "1번 종료" 그렇지 않으면 다음 지시로 이동합니다.	레지스터 r의 내용이 0인 경우 "1 종료" 명령으로 이동하거나, 그렇지 않은 경우 다음으로 이동합니다. 설명

메모들.

이 명령어 세트는 경제성보다는 부분 재귀 함수의 계산을 프로그래밍하기 쉽도록 선택되었다. 섹션 4에서 이 세트는 더 작은 세트와 동등하다는 것을 보여준다.
m, n [contents of r etc_j]이 모든 양의 정수에 걸쳐 있기 때문에 이 목록에는 무한히 많은 명령이 있습니다.
명령 a, b, c, d에서는 n을 제외한 모든 레지스터의 내용을 변경하지 않는 것으로 하고, 명령 e, f에서는 모든 레지스터의 내용을 변경하지 않는다(p.219).

실제로 이 세트는 다음 세트로 축소하는 방법을 보여줍니다(각각 무한 크기의 레지스터가 무한대일 경우).

	URM 감소:	액션:	설명:
a1.	P(r)	[ r ] + 1 → r	레지스터 r의 내용 증가(1을 추가)
b1.	D(n)	[ r ] - 1 → r	레지스터 r의 감소(제1절감) 내용
~f1:	J(r) [E1]	IF [ r ] 0 0 0 、 [ Exit 1 ]으로 점프합니다.	레지스터 m의 내용이 then 0인 경우 명령 "Exit 1"으로 이동하며 그렇지 않으면 계속 진행됩니다.

제한된 레지스터 머신 LRM: 여기서는 머신을 한정된 수의 레지스터 N으로 제한하지만 더 많은 레지스터를 "가져오거나" 비워둘 경우 제거할 수도 있습니다(p.228 참조).이러한 명령어는 레지스터 제거 명령에 빈 레지스터가 필요하지 않음을 나타냅니다.

싱글 레지스터 머신의 SRM: 여기서는 Emil Post의 태그 시스템을 실장하고 있기 때문에 문자열 끝에 쓰기 및 삭제만 허용됩니다.이것은, 그림 1에, 왼쪽의 판독 헤드와 오른쪽의 기입 헤드가 있는 테이프로, 테이프를 오른쪽으로 밖에 이동할 수 없는 것을 나타내고 있습니다."A"는 그들의 "단어"이다(229페이지):

a. P(i);A의 끝에 ai를 더하다

B. D;A의 첫 글자를 삭제하다

f'. ji[E1];A가 ai로 시작하면 1번 출구로 점프한다.

또한 기호가 {0, 1 }인 "카드 스택"으로 모델을 제공합니다(페이지 232 및 부록 C 페이지 248).

맨 위에 인쇄된 카드 추가 1
맨 위에 인쇄된 카드 추가 1
하단 카드를 제거합니다. 지침 m으로 1점프 인쇄된 경우, 그렇지 않은 경우.

1967년: Minsky의 "프로그램 컴퓨터의 심플한 유니버설 베이스

궁극적으로 문제 11.7-1에서 Minsky는 작은 집합에서 많은 연산 기반이 형성될 수 있다고 관찰한다.

"[0 ], [ ], [ - ], [ O - ], [ → ] 및 [RPT ]의 다른 많은 조합이 보편적 기반을 형성합니다.이 중 몇 가지를 찾아보세요.다음 중 범용 기반이 아닌 세 가지 작업의 조합은 무엇입니까?다른 조작을 발명하다..." (p.214)

다음은 그가 다루는 다양한 명령의 정의입니다.

		액션:	설명:
a.	[ 0 ]	0 → r	제로(클리어) 레지스터 r
b.	[ ' ]	[ r ] + 1 → r	레지스터 r의 내용 증가(1을 추가) ("apostrophe "는 "successor"를 나타냅니다)
c.	[ - ]	IF [ r ] = 0이면 명령 z ELSE 다음 명령으로 건너뜁니다.	레지스터 r을 테스트하고 내용이 0인 경우 명령 z로 점프합니다.그렇지 않은 경우 레지스터 r의 내용 감소(감산 1)
d.	[O-]	[ r ] 0 0이면 [ r ]-1 → r ELSE 다음 명령	레지스터 r의 내용이 레지스터 r의 감소 내용이 0이 아닌 경우 z번째 명령으로 점프하고, 그렇지 않으면 0이면 다음 명령입니다.
e.	[ → ]	[ r_j ] → r_k, [ r_j ] → r_j	레지스터_j r의 내용을 복사하여 r을 등록합니다_k.
f.	[RPT]	RPT a:[m,n]반복은 자체 범위 내에서 작동할 수 없습니다.	register [ r ] = 0 의 내용까지 실행 : m ~ n 의 지시사항을 반복합니다.[ r ] = 0이면 다음 명령으로 이동합니다.
g.	[H]	정지하다
h.	goto(z)	명령 z로 이동	명령 z로 무조건 점프
i.	[ ≠ ]	[ r_j ] [ [ r ]인_k 경우 z번째 명령 ELSE 다음 명령으로 이동합니다.	조건부 점프: 레지스터_j r의 내용이 레지스터_k r의 내용과 같지 않으면 명령 z ELSE 다음 명령으로 점프합니다.
j.	[RPT]*	RPT a:[m,n]반복은 자체 범위 내에서 작동할 수 있습니다.	* 참고: RPT는 무한 레지스터여야 합니다.

Minsky(1967)는 다음 3가지 연산에 HALT를 더한 모델로 시작합니다.

{ [ 0 ] , [ ] , [ - ] , [ H ] }

그는 특정 레지스터(예: w가 이미 "빈" 상태)를 허용할 경우 [0 ]을 생략할 수 있다고 관찰합니다(민스키(1967) 페이지 206).이후(255ff페이지)는 3개의 {[ 0 ], [ ], [ - ]}을(를) 2개의 {[ ' ], [ - ] } 로 압축합니다.

그러나 그는 일부 [의사]-명령 [O-]([0]과 [-] 결합)과 "go(n)"를 추가하면 모델이 더 쉽다는 것을 인정한다.0으로 사전 설정된 레지스터에서 "go(n)"를 빌드하여 [O-](w, (n))가 무조건 점프가 되도록 한다.

섹션 11.5 "일반 재귀 기능과 프로그램 기계의 동등성"에서 그는 두 가지 새로운 서브루틴을 소개한다.

f. [ → ]

j. [ ]

같지 않은 경우 점프": IF_j [ r ] [ [ r_k ]그러면 z번째 명령 ELSE 다음 명령으로 점프합니다.

이어 "successor-predecessor" 집합 {[ 0 ], [ ], [ - ] } 를 "success-equality" 집합 { [ 0 ], [ ' ] } 로 대체하는 방법을 보여 줍니다.그리고 "REPEAT" [RPT] 를 정의하여 "successure" 집합 {reat} 에서 원시 재귀 함수를 정의할 수 있음을 보여 줍니다.e 그 자체입니다.이 경우 mu 연산자(mu 재귀 함수 참조):

일반적인 재귀 함수는 프로그램컴퓨터가 RPT 연산을 독자적인 범위 내에 둘 수 있는 경우 [0 ], [ ], [RPT ]만을 사용하여 계산할 수 있습니다.[다만] 일반적으로 RPT 연산은 기계의 유한 상태 부분에서 명령이 될 수 없습니다.[그럴 경우] 이것은 기계의 유한한 부분에 허용되는 특정 양의 스토리지를 소진할 수 있습니다.RPT 작업에는 일반적으로 무한 레지스터가 필요합니다.기타" (p.214)

1980: Schönhage의 0-파라미터 모델 RAM0

Schönhage(1980)는 다양한 포인터 머신인 스토리지 머신 수정 모델(SMM)이라고 불리는 "새로운" 모델의 맥락에서 계산 모델을 개발했습니다.그의 개발은 피연산자를 전혀 필요로 하지 않는 놀라운 명령어 세트를 가진 RAM(랜덤 액세스 머신) 모델을 기술했습니다.단, "조건부 점프"는 제외됩니다(그리고 피연산자 없이도 달성할 수 있습니다).

"... RAM0 버전은 매우 단순하기 때문에 특별히 주목할 필요가 있습니다. 명령어 세트는 (명시적인) 어드레싱 없이 몇 개의 1글자 코드만으로 구성되어 있습니다."(494페이지)

Schönhage가 이것을 한 방법은 흥미롭다.그는 (i) 종래의 레지스터 「address:datum」을 「address」와「datum」의 2부분으로 분무해, (ii) 유한 상태 머신 명령(즉, 「머신 코드」)이 액세스 할 수 있는 특정 레지스터 n에 「address」를 생성해, (ii) 모든 산술 연산이 발생하는 「accumulator」레지스터 z를 제공한다.

그의 특정 RAM0 모델에는 " 레지스터 z의 내용을 0으로 설정"을 나타내는 "Z"와 " 레지스터 z의 내용에 1을 추가"를 나타내는 "A" 두 개의 "산술 연산"만 있습니다.주소 레지스터 n에 대한 유일한 액세스는 "set address n"이라고 불리는 복사 From A-to-N 명령을 사용하는 것입니다.주어진 레지스터의 축적기 z에 "데이터"를 저장하기 위해 기계는 n의 내용을 사용하여 레지스터의 주소를 지정하고 레지스터 z를 레지스터에 전송할 데이텀을 제공합니다.

특징:Schönhage RAM0의 첫 번째 특징은 레지스터 z에 무엇인가를 "로드"하는 방법입니다. 레지스터 z는 먼저 레지스터 주소를 제공하고 다음으로 레지스터로부터 데이텀을 수신합니다.이것은 간접적인 "로드"의 한 형태입니다.두 번째 특징은 Compare 동작의 사양입니다.이는 "축적기-register z=0인 경우"입니다(예를 들어 "z의 내용을 n이 가리키는 레지스터의 내용으로 변환하지 않음).테스트에 실패하면 머신은 다음 명령을 건너뜁니다.다음 명령어는 항상 "goto "" 형식이어야 합니다.여기서 """은 점프 주소입니다.명령 – "z의 내용을 0에 비교"는 보다 일반적인 "레지스터 z의 내용을 레지스터 a의 내용과 비교"하는 Schonhage 후속 모델-RAM1 모델(또는 다른 알려진 후속 모델)과 다릅니다.

주로 참고용으로, 이것은 카운터 머신 모델이 아닌 RAM 모델입니다.다음은 Schönhage RAM0 명령 세트입니다.

	설명	액션:	설명:
1	Z	0 → z	축전지-레지스터 z 지우기
2	A	[ z ] + 1 → z	축전지-레지스터 z의 내용을 늘리기
3	N	[ z ] → n, [z ] → z	"주소 n 설정": 축전지 z의 내용을 주소 레지스터 n에 복사합니다.
4	L	[ [ z ] → z	축전지 z가 가리키는 레지스터의 내용을 축전지 z에 간접적으로 복사합니다.
5	S	[ z ] → [ n ]	어드레스 레지스터의 내용이 가리키는 레지스터에 어큐뮬레이터 z의 내용을 간접적으로 저장한다.
6	C	[ z ] = 0인 경우(goto_λ 명령 I이어야 함)	축전지 z = 0이면 다음 명령을 건너뜁니다. 그렇지 않으면 계속 진행됩니다.
7	goto I_λ	무조건 goto(점프 투) 명령_λ I	무조건 goto(점프 투) 명령_λ I

위의 명령 세트는 RAM - 간접 어드레싱을 사용하는 카운터 머신용입니다.명령어 "N"은 어큐뮬레이터의 간접 저장을 허용하고 명령어 "L"은 어큐뮬레이터의 간접 부하를 허용합니다.

특이하지만, Schönhage의 모델은 기존의 카운터 머신의 "register-to-register" 또는 "read-modify-write" 명령 세트를 가장 단순한 0 파라미터 형태로 원자화할 수 있는 방법을 보여준다.

레퍼런스

조지 불로스, 존 P. Burgess, Richard Jeffrey(2002), 계산성과 논리: 영국 케임브리지 대학 출판부 제4판원래 Boulos-Jeffrey 텍스트는 Burgess에 의해 광범위하게 수정되었습니다: 소개 교과서보다 더 고급입니다."Abacus machine" 모델은 5장 "Abacus Computability"에서 광범위하게 개발되었습니다. 이것은 광범위하게 처리되고 비교되는 세 가지 모델 중 하나입니다. 튜링 머신(아직도 Boolos의 원래 4-태플 형태)과 나머지 두 가지 모델입니다.
튜링 머신의 계층과 유사한 카운터 머신의 시간 계층과 공간 계층 이론을 개발합니다Fischer, Patrick C.; Meyer, A. R.; Rosenberg, Arnold L. (1968), "Counter machines and counter languages", Mathematical Systems Theory, 2: 265–283, doi:10.1007/bf01694011, MR 0235932.
도널드 크누스(1968), The Art of Computer Programming, 1973년 제2판, 매사추세츠, 애디슨 웨슬리.462-463페이지에서 "연결된 구조를 다루는 새로운 종류의 추상 기계 또는 '자동화'"를 정의합니다.
요아힘 람베크(1961년 6월 15일 수신), 무한 주판 프로그래밍 방법, 수학 게시판, 제4, 제3권.1961년 9월 295-302쪽.Lambek는 부록 II에서 "프로그램의 공식 정의"를 제안한다.그는 멜작(1961년)과 클린(1952년) 메타수학 입문서를 언급했다.
Z. A. Melzak(1961년, 1961년 5월 15일 수신), 계산성과 계산에 대한 비공식 산술적 접근, Canadian Mathematical Bulletin, vol. 4, no. 3.1961년 9월 279-293쪽.Melzak은 어떠한 언급도 하지 않았지만 "Dr. R. Hamming, D. McIlroy 및 V와의 대화의 이점"을 인정한다.벨 연구소의 비소츠 씨와 옥스포드 대학의 H. 왕 박사의 전화입니다.
Marvin Minsky (1961). "Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines". Annals of Mathematics. Annals of Mathematics. 74 (3): 437–455. doi:10.2307/1970290. JSTOR 1970290.
Marvin Minsky (1967). Computation: Finite and Infinite Machines (1st ed.). Englewood Cliffs, N. J.: Prentice-Hall, Inc. 특히 11장: 디지털 컴퓨터와 유사한 모델 및 14장: 계산가능성을 위한 매우 단순한 기본을 참조하십시오.앞 장에서는 "Program machines"를 정의하고 뒷 장에서는 "Universal Program machines with Two Registers"와 "..."에 대해 설명합니다.등기부" 등
John C. Shepherdson과 H. E. Sturgis(1961)는 1961년 12월, JACM(Association of Computing Machine) 10:217-255, 1963년 저널, 재귀 함수의 계산 능력을 받았습니다.매우 귀중한 참고 자료입니다.저자들은 부록 A에서 "4.1에서 사용된 지침의 최소성: 유사한 시스템과의 비교"와 관련하여 다른 4가지를 인용한다.
- 카펑스트, 하인츠, 아이네 압스트라크테 프로그래밍 프로그램 거슈테 레첸마샤인, Zeitschrift 모피 수학자 Logike und Grundlagen der Mathik: 5(1959), 366-379.
- Ershov, A.P. 연산자 알고리즘, (러시아) Dok.아카드, 나우크 122(1958), 967-970.영어 번역, Automat.익스프레스 1(1959), 20-23
- Péter, Rossa Graphschemata und rekursive Funktionen, Fentiica 12(1958년), 373.
- 에르메스, 한스 Die Universalitét 프로그래머 Rechenmaschinen.수학.-물리학Temperberichte (Göttingen) 4 (1954), 42 ~ 53.
A. Schohnhage(1980), 스토리지 수정 기계, 산업 및 응용 수학 협회, SIAM J. Compute.제9권 제3호 1980년 8월여기서 쇼나게는 SMM과 '후계자 RAM'(랜덤 액세스 머신)의 동등성을 나타내고 있습니다.
Rich Schroppel, 1972년 5월, Massachusetts Institute of Technology, A. I. Laboratory, 인공지능 메모 #257, "두 개의 카운터 기계는 계산할^N 수 없습니다"저자는 민스키 1967을 언급하며 프랜스 야오가 1971년 4월 비슷한 방법을 사용해 독립적으로 계산 불가능성을 증명했다고 지적한다.
Peter van Emde Boas, 기계 모델 및 시뮬레이션 페이지 3-66에 나오는 내용:

얀 반 리우웬, ed. "이론 컴퓨터 과학 핸드북"A권: 알고리즘과 복잡성, MIT PRESS/Elsevier, 1990. ISBN 0-444-88071-2(볼륨 A). QA 76.H279 1990.

SMM에 대한 Van Emde Boas의 치료는 페이지 32-35에 나와 있습니다.이 처리는 1980년 쇼나게를 명확히 한다.쇼나게 처리는 약간 확대된다.효과적인 이해를 위해서는 두 가지 참고 자료가 모두 필요할 수 있습니다.

Hao Wang(1957), 튜링의 컴퓨터 이론의 변종, JACM (컴퓨팅 기계 협회 저널) 4; 63–92.1954년 6월 23일부터 25일까지 협회 회의에서 발표.

Search