랜덤 액세스 머신

이 문서에는 여러 가지 문제가 있습니다.개선을 돕거나 토크 페이지에서 이러한 문제에 대해 논의해 주십시오.(이러한 템플릿메시지를 삭제하는 방법과 타이밍에 대해 설명합니다) 이 문서에는 일반적인 참조 목록이 포함되어 있지만 대응하는 충분한 인라인 인용이 없습니다. 좀 더 정확한 인용문을 도입하여 개선해주시기 바랍니다. (2017년 12월) (템플릿 메시지 삭제 방법 및 삭제 시기 확인) 이 기사는 대부분의 독자들이 이해하기에는 너무 전문적일 수 있다. 기술적인 세부사항을 삭제하지 않고 비전문가도 쉽게 이해할 수 있도록 개선해주시기 바랍니다. (2017년 12월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인) 이 문서의 어조나 문체는 위키피디아에서 사용되는 백과사전적 어조를 반영하지 못할 수 있습니다. 더 나은 기사 작성에 대한 Wikipedia 가이드를 참조하십시오. (2017년 12월) (이 템플릿 메시지 제거 방법 및 제거 시기 확인) (이 템플릿메시지를 삭제하는 방법과 타이밍을 확인합니다)

컴퓨터 과학에서 RAM(Random-Access Machine)은 레지스터 머신의 일반적인 클래스에 속하는 추상 머신입니다.RAM은 카운터 머신과 매우 유사하지만 레지스터의 '간접 주소 지정' 기능이 추가되었습니다.카운터 머신과 마찬가지로 RAM은 머신의 유한 상태 부분(이른바 하버드 아키텍처)에 명령을 가지고 있습니다.

RAM은 범용 튜링 머신과 동등하며, 레지스터에 프로그램뿐만 아니라 데이터도 포함되며, 랜덤 액세스 스토어드 프로그램 머신(RASP)이라고 불립니다.이것은 이른바 폰 노이만 아키텍처의 한 예이며 컴퓨터의 공통 개념에 가장 가깝습니다.

튜링 머신 및 카운터 머신 모델과 함께 RAM 및 RASP 모델은 계산 복잡도 분석에 사용됩니다.Van Emde Boas(1990)는 이 세 가지와 포인터 머신을 "시퀀셜 머신" 모델이라고 부르며 이들을 "병렬 랜덤 액세스 머신" 모델과 구별한다.

모델 소개

랜덤 액세스 머신(RAM)의 개념은 가장 단순한 모델, 이른바 카운터 머신 모델로부터 시작됩니다.그러나 2개의 추가 기능으로 카운터 머신에서 멀어집니다.첫 번째는 간접 어드레싱의 편리성으로 기계를 향상시키고, 두 번째는 하나 이상의 보조(전용) 레지스터를 추가하여 모델을 보다 전통적인 어큐뮬레이터 기반 컴퓨터로 이동합니다. 이 레지스터 중 가장 일반적인 레지스터는 "어큐뮬레이터"입니다.

형식적 정의

Random-Access Machine(RAM; 랜덤액세스 머신)은 간접 어드레싱이 추가된 다중 레지스터 카운터 머신과 동일한 추상 계산 머신 모델입니다.유한 상태 기계의 TABLE로부터의 명령 재량에 따라 기계는 (i) 명령 자체로부터 직접 또는 (ii) 명령에서 지정된 "포인트" 레지스터의 내용(예를 들어 번호, 라벨)으로부터 간접적으로 "타깃" 레지스터의 주소를 도출한다.

정의:레지스터는 주소(자연수에 해당하는 고유하고 구별 가능한 지정/로케이터)와 내용(단일 자연수)을 모두 가진 위치입니다.정확하게 하기 위해 Boolos-Burgess-Jeffrey(2002)의 준형식 기호를 사용하여 레지스터, 그 내용 및 레지스터의 연산을 지정합니다.

• [r]는 "주소가 r인 등록의 내용"을 의미한다.여기서 라벨 "r"은 자연수, 문자(예: "A") 또는 이름으로 채워질 수 있는 "변수"입니다.
• →는 "복사/복사" 또는 "복사"를 의미하지만 소스를 파괴하지는 않습니다.

예: [3] +1 → 3. 즉, "주소가 "3"인 소스 레지스터의 컨텐츠와 주소가 "3"인 소스 레지스터에 추가된다(여기서 소스와 대상은 같은 장소이다).[3]=37 즉, 레지스터 3의 내용이 숫자 "37"이면 37+1 = 38이 레지스터 3에 입력된다.

예: [3] → 5; "주소가 "3"인 소스 레지스터의 내용은 주소가 "5"인 대상 레지스터에 입력된다"는 의미입니다.[3]=38인 경우, 즉 레지스터 3의 내용이 38인 경우, 이 번호는 레지스터 5에 입력된다.레지스터 3의 내용은 이 조작에 의해 방해받지 않으므로 [3]는 38로, 현재 [5]와 같다.

정의:직접 명령은 명령어 자체에서 내용이 명령어의 대상이 되는 소스 또는 대상 레지스터의 주소를 지정하는 명령어입니다.정의:간접 명령이란, 「포인트 레지스터」를 지정하는 명령으로, 그 내용은 「타깃」레지스터의 주소입니다.타겟 레지스터는 송신원 또는 수신처가 될 수 있습니다(다양한 COPY 명령으로 이러한 예를 제시합니다).레지스터는 간접적으로 주소를 지정할 수 있습니다.

표준/관습이 없기 때문에 이 문서에서는 지침의 파라미터(또는 파라미터)로서 "d/i"로 축약된 "직접/간접"을 지정합니다.

예: COPY ( d , A , i , N )는 명령 자체에서 소스 레지스터의 주소(레지스터 "A")를 직접 취득하는 것을 의미하지만 간접적으로 포인터 레지스터 N에서 수신처 주소를 취득한다. [N]→3이라고 가정하면 레지스터 3이 수신처이고 명령이 [A] → 3을 수행합니다.

정의:소스 레지스터의 내용은 명령에 의해 사용됩니다.소스 레지스터의 주소는 (i) 명령에 의해 직접 지정되거나 (ii) 명령에 의해 지정된 포인터 레지스터에 의해 간접적으로 지정될 수 있습니다.

정의:포인터 레지스터의 내용은 "target" 레지스터의 주소입니다.

정의:포인터 레지스터의 내용은 대상 레지스터를 가리키며, "대상"은 소스 레지스터 또는 대상 레지스터일 수 있습니다.

정의:목적지 레지스터는 명령이 결과를 보관하는 곳입니다.소스 레지스터의 주소는 (i) 명령에 의해 직접 지정되거나 (ii) 명령에 의해 지정된 포인터 레지스터에 의해 간접적으로 지정될 수 있습니다.소스 레지스터와 수신처 레지스터는 1개일 수 있습니다.

리프레셔:카운터 머신 모델

멜작(1961년)은 카운터 머신을 쉽게 시각화할 수 있는 "등록부"는 땅에 뚫린 구멍이며 이 구멍들은 조약돌을 담고 있다.지시에 따라서, 이러한 구멍에 「컴퓨터」(사람 또는 머신)를 출입해, 1개의 페블을 추가(INCrements) 또는 삭제(DECREments)합니다.필요에 따라 추가 자갈이 나오고, 여분의 자갈이 무한 공급으로 돌아갑니다. 만약 구멍이 너무 작아서 자갈을 수용할 수 없다면 "컴퓨터"는 구멍을 더 크게 파게 됩니다.

Minsky(1961)와 Hopcroft-Ullman 1979(p.171)는 "레지스터"만큼 많은 왼쪽 테이프가 있는 멀티 테이프 튜링 기계를 시각화합니다. 각 테이프의 길이는 오른쪽으로 제한되지 않으며 표시된 왼쪽 끝을 제외한 모든 사각형은 비어 있습니다. 테이프 "헤드"의 왼쪽 끝으로부터의 거리는 테이프 제곱의 수로 측정되며 "레지스터"의 자연수를 나타냅니다. DECrement 하려면 , 테이프 헤드가 왼쪽으로 이동하고, INCrement에서는 오른쪽으로 이동합니다. 테이프에 마크를 인쇄하거나 지울 필요는 없습니다.단, 조건부 지침은 왼쪽 끝에 헤드가 있는지 확인하는 것입니다.단, 왼쪽 끝에 마크가 붙어 있는지 확인하는 것입니다.

다음 명령 "니모닉"은 임의이며, 표준이 존재하지 않습니다.

레지스터 머신에는 유한 상태 머신 외부에 있는 메모리에 대해 "레지스터"라고 불리는 무제한 용량으로 구분된 고유 라벨이 부착된 위치들의 무제한(cf: 각주 계산 가능 및 무제한) 컬렉션이 있습니다.이러한 레지스터에는 자연수(0 및 양의 정수)만 저장됩니다.유한 상태 기계의 TABLE에 있는 순차 명령 목록에 따라, 몇 가지(예: 2) 유형의 원시 연산이 이러한 "등록부"의 내용에 대해 작동한다.마지막으로 IF-THEN-ELSE 형식의 조건식을 사용하여 1개 또는 2개의 레지스터의 내용을 테스트하고 유한 상태 머신을 기본 명령 시퀀스에서 "분기/점프"할 수 있습니다.

기본 모델 1: Minsky의 시각화(1961)와 Lambek(1961)에 가장 가까운 모델:

• { 레지스터 r의 instrument 내용, 레지스터 r의 decrement 내용, 레지스터 r의 내용이 제로인 경우 다음 명령으로_z 넘어갑니다.IESELSE는 다음 명령으로 넘어갑니다.

설명	니모닉	레지스터 "r"에 대한 작업	유한 상태 기계의 명령 레지스터(IR)에 대한 작업
인크루먼트	INC ( r )	[r] + 1 → r	[IR] + 1 → IR
디크리먼트	DEC ( r )	[r] - 1 → r	[IR] + 1 → IR
0인 경우 점프	JZ ( r , z )	없음.	IF [r] = 0 THEN z → IR ELSE [IR] + 1 → IR
정지	H	없음.	[IR] → IR

기본 모델 2: "승계자" 모델(Peano 공리의 후속 함수의 이름을 따서 명명됨):

• {등록부 r의 내용을 CLEAR에 등록부 r의 내용을 등록부_j r의 내용과 같게 하고, 레지스터_kz r의 내용을 지시로 점프합니다.}

설명	니모닉	레지스터 "r"에 대한 작업	유한 상태 기계의 명령 레지스터(IR)에 대한 작업
분명한	CLR ( r )	0 → r	[IR] + 1 → IR
인크루먼트	INC ( r )	[r] + 1 → r	[IR] + 1 → IR
같으면 점프	JE(r1, r2, z)	없음.	IF [r1] = [r2] 그렇다면 z → IR ELSE [IR] + 1 → IR
정지	H	없음.	[IR] → IR

기본 모델 3: Elgot-Robinson(1964)이 경계 및 경계 없는 RASP를 조사할 때 사용합니다.이것은, CLEAR 대신에 COPY를 탑재한 「승계기」모델입니다.

• {등록부_j r의 내용을 복사하여 등록부 r의_k 내용을 복사하고, 등록부 r의_j IF 내용을 레지스터 r의_k 내용과 동등하게 한 후 명령으로_z 건너뛰기 IESELSE는 다음 명령으로 이동합니다.

설명	니모닉	레지스터 "r"에 대한 작업	유한 상태 기계의 명령 레지스터(IR)에 대한 작업
알았다.	복사(r1, r2)	[r1] → r2	[IR] + 1 → IR
인크루먼트	INC ( r )	[r] + 1 → r	[IR] + 1 → IR
같으면 점프	JE(r1, r2, z)	없음.	IF [r1] = [r2] 그렇다면 z → IR ELSE [IR] + 1 → IR
정지	H	없음.	[IR] → IR

기본 세트에서 "편의 지침" 작성

위의 3개의 기본 세트 1, 2, 또는 3은 다른 세트의 명령을 사용하여 한 세트의 명령을 만들 수 있다는 점에서 동등합니다(재미있는 연습: Minsky의 힌트). 예를 들어 예약된 레지스터를 "0"(또는 "0"은 "0", "Erase"는 숫자 0을 포함)이라고 선언합니다.모델의 선택은 어떤 작성자가 시연, 증명 등에서 가장 사용하기 쉽다고 생각하는가에 따라 달라집니다.

게다가 베이스 세트 1, 2, 또는 3으로부터, 임의의 원시 재귀 함수(cf Minsky(1967), Boolos-Burgess-Jeffrey(2002))를 작성할 수 있습니다(전체 재귀 함수 및 부분 뮤 재귀 함수를 캡처하기 위해 네트워크를 더 넓게 캐스트 하는 방법은 간접 어드레싱의 맥락에서 설명합니다).그러나 명령 집합이 너무 원시적이기 때문에 원시 재귀 함수를 구축하는 것은 어렵습니다.하나의 솔루션은 다른 세트에서 "편의 지침"을 사용하여 특정 세트를 확장하는 것입니다.

이러한 명령어는 기존의 서브루틴이 아니라 기본 집합에서 생성되어 니모닉이 지정되는 명령어 블록이 됩니다. 형식적인 의미에서 이러한 블록을 사용하려면 (i) 기본 명령 등가물로 확장해야 합니다. 즉, 임시 레지스터 또는 보조 레지스터를 사용해야 하므로 모델은 이를 고려해야 합니다. 또는 (ii) 기계/모델을 '빌트인' 지침으로 설계해야 합니다.

예: 베이스 세트1 。CLR(r)을 작성하려면 명령 블록을 사용하여 레지스터 r을 0까지 카운트다운합니다.상기의 힌트의 사용법에 주의해 주세요.

• CLR(r) =_equiv
• 루프: JZ(r, exit)

• DEC(r)
• JZ(0, 루프)

• 종료: 등

다시 말하지만, 이 모든 것은 단지 편의상일 뿐이며, 이 중 어느 것도 모델의 본질적인 힘을 증가시키지 않습니다.

예를 들어, 가장 확장된 세트에는 세 세트의 고유 명령과 조건 없는 점프 J(z)가 포함됩니다.

• { CLR (r), DEC (r), INC (r), CPY (r_s, r_d), JZ (r, z), JE (r_j, r_k, z), J(z) }

대부분의 저자는 조건부 점프 중 하나를 선택한다.Shepherdson-Sturgis(1963)는 위의 집합에서 JE를 뺀 값을 사용합니다(정확히 말하면 JNZ 대신 Jump if Not Zero를 사용합니다).또 다른 편의 지침도 사용할 수 있습니다).

'간접' 조작

간접 주소 지정의 예

일상 생활에서 "간접 수술"이라는 개념은 드문 일이 아닙니다.

예: 보물찾기.

"Tom_&_Becky's_cave_in_pirate_chest" 로케이션에서는 "the treasure" 로 향하는 지도를 찾을 수 있습니다.

(1) "Tom_&_Becky's_cave" 로케이션으로 이동합니다.나무상자를 찾을 때까지 파헤쳐라.

(2) 상자 안에는 보물의 위치를 나타내는 지도가 있다. "under"대처의 프런트 포치"

(3) '아래' 로케이션으로 이동합니다.대처의 앞부분 포치는 콘크리트를 망치로 치우고 "보물"을 발견한다: 녹슨 문고리 자루.

Indirection은 "Tom_&_Becky's_cave"에서 해적 상자로 식별되는 위치를 지정합니다.다른 위치(자체 포함)에 대한 포인터 역할을 하는 것: 그 내용(보물 지도)은 대상 위치의 "아래" 주소를 제공합니다.실제 행동이 일어나는 대처의 '프론트_포치'입니다.

간접 조작이 필요한 이유:카운터 머신 모델의 두 가지 주요 문제

다음에서 이들 모델은 물리적인 실제와 두 가지 근본적인 차이를 가진 추상적 모델이라는 것을 기억해야 합니다. 즉, 각각 무제한 용량을 가진 레지스터의 수입니다.이 문제는 카운터 머신모델을 사용하여 튜링에 상당하는 RASP를 구축하여 부분 mu 재귀 함수를 계산하려고 할 때 가장 극적으로 나타납니다.

• 멜작(1961)은 그의 "홀 앤 페블" 모델에 간접을 추가하여 그의 모델이 "계산된 고토"로 스스로를 수정할 수 있도록 하고 두 가지 사용 예("d의 척도로 십진수 표현"과 "크기에 의한 정렬")를 제공했는데, 이것이 "프로그램 자체가 튜링 등가"라는 그의 증명에 사용되는지는 불분명하다.연습으로서 독자에게. (292페이지)민스키(1961, 1967)는 적절한 (그러나 사용하기 어려운) 괴델 번호 인코딩을 통해 레지스터 모델이 튜링 등가물이 되도록 간접할 필요는 없었지만 적어도 하나의 무제한 레지스터가 필요했음을 증명할 수 있었다.아래에 기술한 바와 같이 Minsky(1967)는 RASP의 문제를 시사하고 있지만 해결책을 제시하지 않았습니다.Elgot과 Robinson(1964년)은 RASP 모델₀ P가 방향 전환 기능이 없는 경우 모든 "재귀 순차 함수" (임의 길이의 매개변수를 갖는 함수)를 계산할 수 없다는 것을 증명했다. 그러나 명령어를 수정하는 기능이 있는 경우에는 Gödel 번호를 통해 계산할 수 있다(p.395-397; 특히 그림 2와 footn).ote p.395).한편, 「인덱스 레지스터」(간접 어드레싱)를 갖춘 RASP 모델 P'₀는, 모든 「부분 재귀 순차 함수」(mu 재귀 함수)를 계산할 수 있다(p.397-398).

Cook and Rechow(1973)는 가장 간결하게 말한다.

입력이 변화함에 따라 고정 프로그램이 무제한의 레지스터에 액세스하기 위해서는 간접지시가 필요합니다.(p.73)

• 레지스터의 무제한 용량 대 상태-기계 명령의 제한 용량:기계의 소위 유한 상태 부분은 알고리즘의 일반적인 정의에 의해 "상태"의 수(명령)와 명령의 크기(기호/부호를 유지하는 능력) 모두에서 매우 유한하다고 가정됩니다.그렇다면 상태 기계는 어떻게 임의로 큰 상수를 레지스터로 직접 이동시킬까요? 예를 들어 MOVE(k, r)(등록을 위해 상수 k 이동)거대한 상수가 필요한 경우 레지스터 자체에서 시작하거나 INC 및 DEC를 사용하여 한정된 수의 명령을 사용하여 상태 기계에 의해 생성되어야 합니다(단, 이들 중 준무한 수는 제외).

때때로 상수 k는 CLR(r )에 이어 INC(r)를 k회 반복하여 생성될 수 있습니다. 예를 들어, 상수 k→3을 레지스터 r에 넣기 위해 [r]→3: CLR(r), INC(r), INC(R)와 같이 명령 끝에 생성됩니다. 이 속임수는 클린(1952) 페이지 223에 의해 언급된다. 이 문제는 생성되는 수가 유한 상태 머신에서 사용할 수 있는 명령의 수를 모두 소진할 때 발생합니다.항상 유한 상태 머신에서 사용할 수 있는 명령의 수보다 큰 상수가 존재합니다.

• 레지스터의 무제한 수와 제한 상태 시스템 명령:이것은 첫 번째 문제보다 더 심각하다.특히, 이 문제는 우리가 레지스터에 있는 "명령어 프로그램"을 해석하기 위해 유한 상태 기계를 사용하는 "유니버설 머신"(Universal Turing 머신에서 더 많이 참조)이라고 불리는 소위 "RASP"를 구축하려고 할 때 발생합니다. 즉, 우리는 오늘날 폰 노이만 아키텍처로 컴퓨터라고 불리는 것을 구축하고 있습니다.

카운터 머신의 유한 상태 머신은 이름/번호에 의해 명시적으로(직접) 레지스터를 호출해야 합니다.INC(65,356)는 레지스터 번호 「65,365」를 명시적으로 호출합니다.레지스터의 수가 유한 상태 머신의 어드레싱 능력을 초과하면, 그 범위 밖에 있는 레지스터는 도달할 수 없게 됩니다.예를 들어, 유한 상태 기계가 65,536 = 2 레지스터에만¹⁶ 도달할 수 있다면, 어떻게 65,537번째 레지스터에 도달할 수 있을까요?

그렇다면 유한 상태 머신의 경계를 넘어서는 레지스터를 어떻게 취급해야 할까요?한 가지 방법은 프로그램 명령(레지스터에 저장된 명령)을 수정하여 두 개 이상의 명령을 포함하도록 하는 것입니다.그러나 이 역시 명령이 (잠재적으로) 무한 크기인 경우가 아니면 모두 소진될 수 있습니다.따라서 하나의 "über-instruction" (정말 큰 숫자)을 사용하면 됩니다.그 안에 인코딩된 모든 프로그램 명령이 포함되어 있습니다.Minsky는 이렇게 문제를 해결하지만, 그가 사용하는 Gödel 번호는 모델에 큰 불편함을 나타내며, 그 결과는 "저장된 프로그램 컴퓨터"라는 직관적인 개념과는 전혀 다릅니다.

Elgot과 Robinson(1964)은 "최종 결정"된 RASP에 관해 유사한 결론을 도출했다.실제로 RASP가 프로그램 명령의 "자기 수정"을 허용하고 "데이터"를 Gödel 번호로 인코딩한 경우에만 레지스터의 무제한 수(예: 레지스터로부터 명령을 가져오기 위해)에 액세스할 수 있습니다(그림 2 페이지 396).

RPT(반복) 명령을 사용하는 보다 컴퓨터와 유사한 모델의 맥락에서 Minsky(1967)는 문제에 대한 해결책으로 우리를 자극하지만(cf. 214, 페이지 259), 확실한 해결책을 제시하지는 않습니다.그는 다음과 같이 주장한다.

"일반적으로 RPT 연산은 기계의 유한 상태 부분에서는 명령이 될 수 없습니다.이것은 컴퓨터의 유한한 부분에 허용되는 특정 양의 스토리지를 소진할 수 있습니다[sic, RAM 모델에 대한 그의 이름].RPT 조작에는, 독자적인 무한 레지스터가 필요합니다.(p.214).

그는 CLR(r) 및 INC(r)와 함께 모든 원시 재귀 함수를 계산할 수 있는 경계 RPT를 제공하고, μ 연산자의 역할을 하는 위에서 인용한 경계 없는 RPT를 CLR(r) 및 INC(r)와 함께 mu 재귀 함수를 계산할 수 있는 경계 RPT를 제공합니다.그러나 그는 "간접"이나 RAM 모델 자체에 대해서는 언급하지 않았습니다.

Hartmanis(1971년)의 참고 자료에서 쿡은 간접 주소 지정 개념을 완성한 것으로 보인다.이는 쿡과 레크하우(1973년)의 논문에서 더욱 분명해졌다. - 쿡은 레크하우의 석사논문 고문이다.Hartmanis의 모델은 Melzak의 모델(1961)과 매우 유사하며, 2개의 레지스터 덧셈과 뺄셈과 2개의 파라미터 복사본을 사용한다.Cook and Rechow의 모델은 누적기 "AC"를 사용하여 파라미터(프로그램 명령에서 호출된 레지스터)의 수를 1개의 호출로 줄인다.

간단히 말하면, 델의 머신/모델을 무제한의 다이렉트로 설계할 수 있습니다.수량에 관계없이 모든 레지스터에 이름을 붙일 수 있는 무제한의 「주소」레지스터를 제공합니다.일반적으로 이 기능이 작동하려면 무제한 레지스터를 클리어한 후 잠재적으로 무한 루프에 의해 증가(및 감소)하는 기능이 필요합니다.이러한 의미에서 솔루션은 원하는 것을 찾을 때까지 레지스터의 무제한 스트링에 따라 ad ininitim을 헌트할 수 있는 무제한 μ 연산자를 나타냅니다.포인터 레지스터는 한 가지 예외를 제외하고 다른 레지스터와 똑같습니다. 즉, "간접 주소 지정"이라고 불리는 상황에서는 대상 레지스터의 주소로서 스테이트 머신의 TABLE에 주소 오퍼랜드가 아닌 내용을 제공합니다(가능성이 있는 경우!).

경계 간접 및 원시 재귀 함수

하나의 레지스터에서 하나의 몬스터 숫자에 대한 Minsky 접근방식을 회피하고 기계 모델이 "컴퓨터"가 되도록 지정하면 재귀 함수(μ-재귀 함수라고도 함)를 계산하려면 이 간접 문제에 직면해야 합니다.

우리의 단순한 카운터 머신 모델은 "경계" 형태의 간접을 할 수 있고, 이에 따라 "사례별 정의"라고 불리는 원시 재귀적 "연산자"를 사용하여 원시 재귀 함수의 하위 클래스를 계산할 수 있습니다(Kleene(1952) 페이지 229 및 Boolos-Burgess-Jeffrey 페이지 74에서 정의).이런 '한계 우회'는 힘들고 지루한 일이다."사례에 의한 정의"는 기계가 성공하기 전까지 이 내용을 사례 운영자가 명시적으로 선언한 번호/이름과 일치시킴으로써 포인터 레지스터의 내용을 결정/구별할 것을 요구한다.따라서 케이스별 정의는 예를 들어 하한 주소에서 시작하여 상한 주소까지 계속하여 일치시키려 합니다.

레지스터 N의 숫자는 0입니까?그렇지 않다면 1? 2? 3? 65364?그렇지 않으면 마지막 번호인 65365에 도달하게 됩니다.이 번호가 맞으면 좋겠는데, 그렇지 않으면 문제가 생깁니다.

"Bounded" indirection은 부분 재귀 함수를 계산할 수 없습니다.무제한 indirection은 μ 연산자라고도 합니다.

65367번까지 계속할 수 있었고, 실제로 레지스터는 우리가 찾던 것을 가지고 있었다고 가정해 봅시다.그럼 계산을 성공적으로 마칠 수 있었을 텐데!하지만 65367이 우리가 필요로 하는 것을 가지고 있지 않다고 가정해 보자.어디까지 계속 가야 하나요?

튜링 등가물이 되기 위해서는 카운터 머신은 불행한 단일 레지스터의 Minsky Gödel 수법을 사용하거나 레지스터 문자열의 끝을 탐색하는 능력으로 증강해야 합니다.필요에 따라 "아웃"을 찾지 못하면 알고리즘이 종료되지 않는 것이 무엇을 의미하는지 정의합니다; cf Kleene(1952)pp.316ff 12장 부분 재귀 함수, 특히 페이지 323-325).자세한 것은, 다음의 예를 참조해 주세요.

무제한 간접 및 부분 재귀 함수

무제한의 방향성을 실현하기 위해서는, 머신 모델의 「하드웨어」를 변경할 필요가 있습니다.이 변경을 실시하면 모델은 카운터 머신이 아니라 랜덤 액세스 머신이 됩니다.

이제 예를 들어,INC가 지정되면 유한 상태 머신의 명령은 관심 레지스터의 주소가 어디에서 오는지를 지정해야 합니다.여기서 이 명령어는 (i) 명시적 라벨을 제공하는 상태 머신의 명령 또는 (ii) 내용이 관심 주소인 포인터 레지스터 중 하나입니다.명령에서 레지스터 주소를 지정할 때마다 "i/d" – "간접/직접" 매개 변수를 추가로 지정해야 합니다.어떤 의미에서 이 새로운 "i/d" 파라미터는 명령에 지정된 대로 직접 주소를 얻기 위해 한 방향으로 플립하거나 포인터 레지스터에서 간접 주소를 얻기 위해 다른 방식으로 플립하는 "스위치"입니다(어떤 모델에서는 모든 레지스터가 포인터 레지스터가 명령에 의해 지정됩니다).이 "상호 배타적이지만 포괄적인 선택"은 "사례에 의한 정의"의 또 다른 예이며, 아래 예에서 보여지는 산술적 등가물은 Kleene(1952) 페이지 229의 정의에서 파생되었다.

예: CPY (간접_source, r_source, 직접_destination, r_destination )

직접 주소를 d="0"으로 지정하고 간접 주소를 i="1"로 지정하는 코드를 할당합니다.다음에, 송신원주소를 다음과 같이 판별할 수 있습니다.

i*[r_s] + (1-i)*r_s

예를 들어, 레지스터 3의 내용이 "5"(즉, [3]=5)이고 레지스터 4의 내용이 "2"(즉, [4]=2)라고 가정합니다.

예: CPY (1, 3, 0, 4 ) = CPY (간접, reg 3, direct, reg 4 )

1*[3] + 0*3 = [3] = 소스 레지스터 주소 5

0*[4] + 1*4 = 4 = destination-register address 4

예: CPY (0, 3, 0, 4 )

0*[3] + 1*3 = 3 = 소스 레지스터 주소 3

0*[4] + 1*4 = 4 = destination-register address 4

예: CPY (0, 3, 1, 4 )

0*[3] + 1*3 = 3 = 소스 레지스터 주소 3

1*[4] + 0*4 = [4] = 수신처 등록 주소 2

간접 복사 명령

추가된 명령 중 가장 유용한 것은 COPY일 것입니다.실제로 Elgot-Robinson(1964)은 모델₀ P'와 P'₀에 COPY 명령을 제공하고, Cook-Reckhow(1973)는 축전지 기반 모델에 간접적으로 축전지에 복사, 축전지에서 간접적으로 복사라는 두 가지 간접적인 명령만 제공한다.

너무 많은 지시:단일 레지스터에 작용하는 명령은 간접적인 "듀얼"(조건부 및 무조건 점프, Elgot-Robinson 모델 cf 포함)로 증강될 수 있기 때문에, 간접 명령의 포함은 단일 매개변수/레지스터 명령의 수를 두 배로 증가시킨다(예: INC(d, r), INC(i, r).게다가 각 2개의 파라미터/레지스터 명령에는 4개의 가능한 종류가 있습니다.예를 들어 다음과 같습니다.

CPY (d, r_s, d, r_d ) = 소스 레지스터에서 수신처 레지스터로 직접 복사

CPY(i, r_sp, d, r_d) = 송신원 레지스터_sp r에 있는 송신원주소를 사용해 수신처에 간접적으로 카피합니다.

CPY(d, r_s, i, r_dp) = 수신처 레지스터 r에_dp 있는 수신처 주소를 사용해 소스 레지스터의 내용을 레지스터에 간접적으로 카피한다.

CPY (i, r_sp, i, r_dp ) = 소스 레지스터의_sp 내용을 소스 레지스터 r에서 찾을 주소를 가진 소스 레지스터의 내용을_dp 수신처 레지스터 r에서 찾을 주소를 가진 수신처 레지스터에 간접적으로 복사합니다.

마찬가지로 2개의 소스 레지스터_s1 r과_s2 수신처 레지스터_d r을 포함하는 모든 3개의 레지스터 명령은 8가지 종류가 됩니다(예: 추가).

[r_s1] + [r_s2] → r_d

결과:

• ADD ( d , r_s1 , d , r_s2 , d , r_d )
• ADD ( i , r_sp1 , d , r_s2 , d , r_d )
• ADD ( d , r_s1 , i , r_sp2 , d_d , r )
• ADD ( i , r_sp1 , i , r_sp2 , d , r_d )
• ADD ( d , r_s1 , d , r_s2 , i_dp , r )
• ADD ( i , r_sp1 , d , r_s2 , i_dp , r )
• ADD ( d , r_s1 , i , r_sp2 , i_dp , r )
• ADD ( i , r_sp1 , i , r_sp2 , i_dp , r )

1개의 레지스터를 「어큐뮬레이터」(아래 참조)로 지정하고, 허가된 다양한 지시에 엄격한 제한을 가하면, 직간접 조작의 번잡함을 큰폭으로 줄일 수 있습니다.단, 결과적으로 감소된 명령 집합이 충분한지 확인해야 하며, 감소는 "중요한" 작업당 더 많은 명령을 희생하는 것이어야 합니다.

어큐뮬레이터 A의 개념

이력 규약은 레지스터를 일련의 산술 연산 중에 문자 그대로 그 숫자를 누적하는 "산술 기관"인 누산기에 전용으로 지정합니다.

"우리 산술기관의 첫 번째 부분은...번호를 수신하여 이미 있는 번호에 추가할 수 있는 병렬 저장 기관이어야 하며, 이 기관은 해당 내용을 지우고 포함된 내용을 저장할 수도 있습니다.우리는 그러한 기관을 축적기라고 부를 것이다.데스크 멀티플라이어, 표준 IBM 카운터, 보다 현대적인 릴레이 머신, ENIAC" 등 과거와 현재의 컴퓨터 머신에서는 원칙적으로 매우 전통적인 방식입니다.(원문 굵은 글씨: Goldstine and von Neumann, 1946년, Bell and Newell 1971 페이지 98).

그러나 누산기는 특히 "r2"가 가리키는 레지스터의 내용을 간접적으로 증가시킨다. "A"는 "누산기" 레지스터 A를 지정한다.

라벨.	설명		A	r2	r378,426	묘사
			. . .	378,426	17
INCi(r2):	CPY(i, r2, d, A )		17	378,426	17	r2의 내용은 r378,426을 가리키며, 내용은 "17"입니다.이것을 A에 카피합니다.
	INC ( A )		18	378,426	17	A의 내용
	CPY( d, A, i, r2)		18	378,426	18	r2 포인트의 r378,426: A의 내용을 r378,426에 복사합니다.

축전지의 특정 이름(예: "A")을 계속 사용하면 지침에서 축전지를 암시할 수 있습니다. 예를 들어,

INC ( A ) = INCA

그러나 호출된 누적기 없이 CPY 명령을 작성하는 경우 명령이 모호하거나 매개 변수가 비어 있어야 합니다.

CPY ( d , r2, d , A )= CPY ( d , r2, , )

CPY ( d , A , d , r2) = CPY ( , , d , r2)

역사적으로 이 2개의 CPY 명령에는 구별되는 이름이 붙었지만, 규약은 존재하지 않습니다.기존(예: Knuth의 상상의 MIX 컴퓨터)에서는 LOAD와 STORE라는 두 가지 이름을 사용합니다.여기에서는 "i/d" 파라미터를 추가합니다.

LDA ( d/i, r_s ) =_def CPY ( d/i, r_s, d, A )

STA ( d/i, r_d ) =_def CPY ( d, A, d/i, r_d )

일반적인 어큐뮬레이터 기반 모델에는 (i) 지정된 레지스터의 콘텐츠와 함께 (i) ADD (A, r), SUB (A, r) 등 모든 2 변수 산술 및 상수 연산(예를 들어 ADD (A, r), SUB (A, r))이 사용됩니다.1 변수 연산(예: INC(A), DEC(A) 및 CLR(A))에는 축전지만 필요합니다.두 명령 유형 모두 결과(예: 합계, 차이, 곱, 몫 또는 나머지)를 누적기에 저장합니다.

예: INCA = [A] +1 → A

예: ADDA(r_s) = [A] + [r_s] → A

예: MULA(r_s) = [A] * [r_s] → A

선택할 경우 적어도1개의 소스 레지스터와 수신처 레지스터가 항상 어큐뮬레이터A이기 때문에 니모닉을 생략할 수 있습니다.다음과 같은 것이 있습니다.

{ LDA (i/d, r_s), STA (i/d, r_d), CLRA, INCA, DECA, ADDA(r_s), SUBA(r_s), MULA(r_s), DIVA(r_s 등)

간접 주소 레지스터 "N"의 개념

우리 모델에 무제한 축전지가 있는 경우 다른 모든 레지스터를 바인딩할 수 있습니까?간접 주소를 얻을 수 있는 최소 하나의 무제한 레지스터를 제공하기 전까지는 안 됩니다.

최소주의 접근방식은 그 자체를 사용하는 것이다(Schönhage는 이것을 한다).

또 다른 접근법(Schönhage도 이것을 한다)은, 특정의 레지스터를 「간접 주소 레지스터」라고 선언해, 이 레지스터에 대해서 인다이렉션을 제한하는 것입니다(Schonhage의 RAM0 모델은, 직접 명령 뿐만이 아니라 A 레지스터와 N 레지스터를 모두 사용합니다).또, 새로운 등록부에는, 「iNdex」의 「N」, 「iNdirect」, 또는 「주소 번호」의 「N」이라고 하는 통상적인 이름은 없습니다.

최대한의 유연성을 확보하기 위해 어큐뮬레이터 A와 마찬가지로 N은 증가, 감소, 클리어, 테스트, 다이렉트 카피 등의 대상이 되는 다른 레지스터에 불과하다고 생각합니다.예를 들어 명령어를 방향과 간접을 제공하는 단일 파라미터로 축소할 수 있습니다.

LDAN(i/d) = CPY(i/d, N, d, A), iN방향 레지스터를 통한 LoaD 축전지

STAN(i/d) = CPY(d, A, i/d, N). iN방향 레지스터를 통한 STORE 축전지

왜 이것이 그렇게 흥미로운 접근법일까요?최소 두 가지 이유:

(1) 파라미터가 없는 명령어 세트:

Schönhage는 이를 통해 RAM0 명령 집합을 생성합니다.아래 섹션을 참조하십시오.

(2) RAM을 Post-Turing 머신으로 줄입니다.

미니멀리스트로 가장하여 축적기 A와 간접 레지스터 N을 제외한 모든 레지스터를 줄입니다. 예를 들어 r = { r0, r1, r2, ...(매우) 경계가 있는 용량 비둘기 구멍의 무제한 문자열에 }을(를) 적용합니다.예를 들어 값이 {0, 1 }인 단일 비트처럼 제한되는 숫자만 유지합니다. 마찬가지로 축척기를 단일 비트로 축소합니다.모든 산술은 레지스터 {A, N}로 제한합니다. 간접 연산을 사용하여 레지스터의 내용을 어큐뮬레이터로 끌어오고 어큐뮬레이터에서 레지스터에 0 또는 1을 씁니다.

{ LDA(i, N), STA(i, N), CLR(A/N), INC(A/N), DEC(N), JZ(I_zz), H }

「ERASE」와 「PRINT」라고 불리는 2개의 레지스터 「ERASE」=0, 「PRINT」=1을 사용해 A를 한층 더 밀어내고, 모두 없앱니다.

{ CPY(d, ERASE, i, N), CPY(d, PRINT, i, N), CLR(N), INC(N), DEC(N), JZ(i, N, I_z), JZ(I_z, H)

COPY 지침의 이름을 변경하고 INC(N) = RIGHT, DEC(N) = LEFT로 전화하면 Post-Turing 기계와 동일한 지침과 추가 CLRN:

{소거, 인쇄, CLRN, 오른쪽, 왼쪽, JZ(i, N, I_z), JZ(I_z), H }

RAM과 간접의 튜링 동등성

위의 항에서는 무제한 인다이렉션 기능을 갖춘 RAM이 Post-Turing 머신을 생성하는 것을 비공식적으로 보여 주었습니다.Post-Turing 기계는 튜링 등가이므로, 우리는 간접이 있는 RAM이 튜링 등가임을 보여 주었다.

여기서는 조금 더 공식적인 데모를 보여 드리겠습니다.먼저 3개의 예약된 레지스터 "E", "P" 및 "N"과 오른쪽에 있는 레지스터 1, 2, ..., n의 무제한 집합을 사용하여 모델을 설계합니다.레지스터 1, 2, ..., n은 "테이프의 정사각형"으로 간주됩니다."N" 점을 "헤드"가 현재 관찰 중인 "스캔된 사각"을 가리킵니다."머리"는 조건부 점프에 있는 것으로 간주될 수 있습니다. 간접 주소 지정을 사용하는 것을 관찰하십시오(cf Elgot-Robinson 페이지 398)."N"을 줄이거나 늘리면 (외관상) 헤드가 정사각형을 따라 "왼쪽" 또는 "오른쪽"으로 이동합니다.간접 CPY를 사용하여 "E"=0" 또는 "P"=1"의 내용을 "N"이 지적한 "정사각형"으로 이동시킨다.

테이프가 왼쪽 끝에 있다는 사실로 인해 다음과 같은 사소한 문제가 발생합니다.왼쪽이 발생할 때마다 명령어는 "N"의 내용이 0인지 여부를 확인하기 위해 테스트해야 합니다. 만약 그렇다면 그 수를 "0"으로 두어야 합니다(이는 설계자로서 우리가 선택한 것입니다. 예를 들어 기계/모델이 원하는 이벤트를 트리거하도록 할 수도 있습니다).

명령어 세트 1(증강): { INC(N), DEC(N), CLR(N), CPY(d, r_s, i, N), JZ(i, r, z), HALT }

다음 표에서는 RAM에 상당하는 지침의 관점에서 치료 후 지침을 정의하고 작동 예를 보여 줍니다.레지스터 r0 ~ r5 의 테이프를 따라서 헤드의 (외관상) 위치가 음영 처리되어 있습니다.

니모닉	라벨:			E	P	N		r0	r1	r2	r3	r4	r5	기타.	레지스터에 대한 작업	유한 상태 기계 명령 레지스터 IR에 대한 작업
	시작:			0	1	3					1	0
R	오른쪽:	INC ( N )		0	1	4					1	0			[N] +1 → N	[IR] +1 → IR
P	인쇄:	CPY( d, P, i, N )		0	1	4					1	1			[P] → 1 → [N] → r4	[IR] +1 → IR
E	지우기:	CPY( d, E, i, N )		0	1	4					1	0			[E] → 0 → [N] → r4	[IR] +1 → IR
L	왼쪽:	JZ(i, N, end)		0	1	4					1	0			없음.	N =r4] =0이면 "종료" → IR else [IR]+1 → IR
		DEC ( N )		0	1	3					1	0			[N] -1 → N
J0(정지)	jump_if_blank:	JZ(i, N, end)		0	1	3					1	0			없음.	N =r3] =0이면 "종료" → IR else [IR]+1 → IR
J1(정지)	jump_if_mark:	JZ(i, N, 정지)		0	1	3					1	0			N = r3] → A	N =r3] =0이면 "종료" → IR else [IR]+1 → IR
	끝.	.기타.		0	1	3					1	0
	정지:	H		0	1	3					1	0			없음.	[IR] +1 → IR

예: 제한적 간접으로 인해 튜링에 상당하지 않는 기계가 생성됩니다.

이 데모를 통해 우리는 유한 상태 기계의 TABLE에 있는 명령이 한정되어 있다는 것을 유념해야 한다. 즉, 유한:

"특정 유형의 문제를 해결하기 위한 일련의 연산을 제공하는 유한한 규칙 집합일 뿐 아니라, 알고리즘은 다섯 가지 중요한 특징[최종성, 정의성, 입력, 출력, 효과성]을 가지고 있습니다." (이탈릭, Knuth 페이지 4-7).

이 문제는 레지스터에 명시적인 "이름"(숫자)이 있고, 이 레지스터에 액세스하기 위해 기계가 각각의 이름을 불러야 하기 때문에 발생합니다.

CASE 연산자와 간접 CPY(i, q, d, ) )를 구축합니다.대상 레지스터의 주소는 레지스터 "q"의 내용으로 지정되며, CASE 연산자가 이 번호를 결정하면 CPY는 해당 번호를 가진 레지스터의 내용을 레지스터 "φ"에 직접 입금한다."y"라고 부르는 추가 레지스터가 필요합니다. 즉, 업카운터 역할을 합니다.

따라서 다음은 카운터 머신/모델에 대한 "하드웨어" 설계 변경 없이 간접 CPY(i, q, d, ))를 실제로 시뮬레이션할 수 있다는 것을 실제로 입증하거나 증명하는 것입니다.단, 이 간접 CPY는 유한 상태 머신의 크기/확장에 의해 "경계"되기 때문에 이 간접 CPY를 사용하는 RASP는 mu 재귀 함수의 전체 스위트가 아닌 원시 재귀 함수만 계산할 수 있습니다.

CASE "연산자"는 Kleene(1952)(229페이지)과 Boolos-Burgess-Jeffrey(2002)에 기술되어 있다. 후자의 저자는 그 효용성을 강조한다.다음 정의는 Kleene 단위이지만 익숙한 "IF-THEN-ELSE" 구조를 반영하도록 수정되었습니다.

CASE 연산자는 "case_0"부터 시작하여 "case_last"까지 이어지는 "case_last"에 따라 자연수를 "return"합니다.대소문자가 충족되지 않으면 "default"(일명 "woops")라는 숫자가 반환됩니다(여기서 x는 register q 및 string r0, last 등 파라미터의 일부 선택 항목을 나타냅니다).

대소문자에 의한 정의 ((x,

• case_0: Q(x, y)가 참이면 then₀(x₀, y) ELSE
• case_1: Q(x, y)가 참이면 then₁(x₁, y) ELSE
• cases_2 ~ case_next_to_last : 등, ..., ..., ELSE
• case_last: Q(x, y)가_last true이면 ((x_last, y)ELSE
• 디폴트: do (x_default, y)

Kleene은 테스트를 수행하는 모든 "예측" Q가 상호_n 배타적일 것을 요구합니다. "예측"은 출력에 대해 {true, false}만을 생성하는 함수입니다.Boolos-Burgess-Jeffrey는 케이스가 "완전"하다는 요건을 추가합니다.

우선 레지스터 q 내의 숫자로 시작합니다.이 숫자는 타겟 레지스터의 주소를 나타냅니다.하지만 이 숫자는 무엇일까요?JE(q, y, z)에 이어 INC(y)까지 차례로 시험하여 "예약"이 이를 확인합니다.번호가 명시적으로 식별되면 CASE 연산자는 이 레지스터의 내용을 직접 또는 명시적으로 §에 복사합니다.

사례 CPY(i, q, d, )) =_def ((q, r0, ..., rlast, y) =에 의한 정의

• case_0: CLR(y), [q] - [y]=0 다음 CPY(r0, θ), J(표준) ELSE
• case_1: IF INC(y), [q] = [y] = 1 다음 CPY (r1, j), J (selse) ELSE
• case_2 ~ 대소문자 n: IF . . . . 그 다음 . . . ELSE
• case_n: IF INC (y), [q] = [y] = n 그 후 CPY (rn, ),), J (selse) ELSE
• case_n+1에서 case_last: if . . . 그 다음 . . . ELASE
• case_last: IF INC (y), [q] = [y] = "last" 다음 CPY ( rlast , ), ) , J ( ) ) ELSE
• 디폴트: woops

Case_0(y 재귀의 기본 단계)은 다음과 같습니다.

• case_0:

• CLR( y ); 레지스터 y 설정 = 0
• JE ( q, y, _ )0 )
• J(case_1)

• _ : 0 : CPY ( r0 , ) )
• J(종료)

• case_1: 등

case_n(유도 단계)은 다음과 같습니다. "n", "n+1", ..., "last"의 각 인스턴스는 명시적인 자연수여야 합니다.

• 케이스_n:

• INC ( y )
• JE ( q, y, _ )n )
• J(case_n+1)

• _nn: CPY ( rn, ) )
• J(종료)

• case_n+1: 등

Case_last는 유도를 중지하고 CASE 연산자를 제한합니다(따라서 "간접 복사" 연산자를 제한합니다).

• case_last:

• INC ( y )
• JE(q, y, _'마지막')
• J(우프)

• 마지막 : CPY ( 마지막, ) )
• J(종료)

• 외부 시도에 대처하려면 어떻게 해야 하나요?
• 종료: 등

CASE가 adinitum을 계속할 수 있다면 mu 연산자일 것입니다.그러나 이는 불가능합니다. 즉, 유한 상태 머신의 "상태 레지스터"가 최대 카운트에 도달했거나(예: 65365 = 111111₂,111111 ) 테이블에서 명령이 부족합니다. 결국 유한 시스템입니다.

모델의 예

Cook and Rechow의 Register-to-register("읽기-수정-쓰기") 모델(1973년)

흔히 볼 수 있는 Cook and Rechkow 모델은 3진 레지스터 Malzek 모델과 약간 유사합니다(원래 명령어에는 TRA, Read, Print 이외에는 니모닉이 없었습니다).

• LOAD ( C, rd ) ; C → rd, C는 임의의 정수입니다.

예:LOAD ( 0, 5 )레지스터 5를 클리어합니다.

• ADD ( rs1, rs2, rd ) ; [rs1] + [rs2] → rd레지스터는 같거나 다를 수 있습니다.

예:ADD ( A, A, A )레지스터 A의 내용을 2배로 합니다.

• SUB ( rs1, rs2, rd ) ; [rs1] - [rs2] → rd레지스터는 같거나 다를 수 있습니다.

예:SUB ( 3, 3, 3 )레지스터 3을 클리어합니다.

• COPY ( i, rp, d, rd ) ; [[rp] ] → rdpointer-register_p r이 가리키는 source-register의 내용을 수신처 레지스터에 간접적으로 복사합니다.
• COPY ( d, rs, i, rp ) ; [rs] → [rp]소스 레지스터_s r의 내용을 포인터 레지스터_p r이 가리키는 데스티네이션 레지스터에 복사합니다.
• JNZ ( r, Iz ) ;[r]가 양수일 경우 조건부 점프, 즉[r] > 0이면 명령 z로 건너뛰고, 그렇지 않으면 순서대로 계속 진행합니다(쿡 및 Rechow는 이것을 "Xj > 0이면 TRANsfer control to line m"이라고 부릅니다).
• READ ( rd ) ;「입력」을 행선지 레지스터에_d 카피합니다.
• PRINT ( rs ) ;소스 레지스터_s r의 내용을 "출력"에 복사합니다.

Schönhage의 RAM0 및 RAM1 (1980)

Schönhage(1980)는 SMM 포인터 머신 모델의 동등성을 증명하기 위해 선택된 매우 원시적이고 원자화된 모델을 설명한다.

"명시적인 주소 지정을 피하기 위해 RAM0에는 컨텐츠 z를 포함한 어큐뮬레이터와 현재 컨텐츠 n(처음에는 0)을 포함한 추가 주소 레지스터가 있습니다."(p.494).

RAM1 모델:Schönhage는 이 기사의 기억법을 사용하여 보다 보편적이고 사용 가능한 형태의 "승계자" RAM을 형성하기 위해 어떻게 그의 구조를 사용할 수 있는지를 보여준다.

• LDA k ; k --> A , k는 상수이며 "47"과 같은 명시적 숫자입니다.
• LDA ( d, r ) ; [r] → A ;A를 직접 로드하다
• LDA ( i, r ) ; [[r]] → A ;A를 간접적으로 로드하다
• STA ( d, r ) ; [A] → r ;A를 직매장하다
• STA ( i, r ) ; [A] → [r] ;A를 간접적으로 저장하다
• JEA ( r, z ) ; IF [A] = [r] then Iz else continue
• INCA ; [A] + 1 --> A

RAM0 모델:Schönhage의 RAM0 머신에는 6개의 명령어가 1개의 문자로 표시됩니다(6번째 "C xxx"는 '다음 매개 변수 건너뛰기'를 포함하는 것으로 보입니다).Schönhage는 축전지를 "z", "N"은 "n" 등으로 지정했다.우리는 Schönhage의 연상법 대신 위에서 개발한 연상법을 사용할 것이다.

• (Z), CLRA: 0 → A
• (A), INCA: [A] +1 → A
• (N), CPYAN: [A] → N
• (A), LDAA: [[A]] → A ; 주소등록을 위한 A포인트의 내용; A에 레지스터의 내용을 넣는다.
• (S), STAN: [A] → [N] ; 주소등록을 위한 N점 내용; A의 내용을 N이 가리키는 레지스터에 입력
• (C), JAZ ( z ): [A] = 0 then go to Iz 그의 처우가 애매하다.

indirection은 (i) store_와 함께 작업하는 CPYAN(copy/transfer contents A to N)에서 옵니다.A_via_N STAN 및 (ii) 고유의 간접 명령LDAA ( [[A]] → [A] ).

각주

유한과 무한

무제한 레지스터 "address" 레지스터가 없는 카운터 머신은 레지스터 "r"을 이름으로 지정해야 한다는 정의적 사실은 모델이 작업을 수행하는 데 필요한 레지스터 수에 대한 상한을 의미하지 않는다는 점에서 "unbounded"이지만 모델이 "r"을 유한해야 함을 나타냅니다.예를 들어 r <83,617,563,821,029,283,746 또는 r <2^1,000,001 등은 필요 없습니다.

따라서 특정 계산을 수행하기 위해 필요한 경우, 우리의 모델은 레지스터의 수를 "확장"할 수 있습니다.그러나 이는 모델이 확장되는 숫자는 유한해야 한다는 것을 의미합니다. 즉, 자연수로 지수화 가능해야 합니다. θ는 옵션이 아닙니다.

간접 주소를 지정하는 레지스터의 주소를 제공하는 무제한 레지스터를 제공함으로써 이 제한을 피할 수 있습니다.

「 」를 참조해 주세요.

• 실제 RAM
• 트랜스디코모형

외부 링크

• 랜덤 액세스 머신 에뮬레이터
• 랜덤 액세스 머신 에뮬레이터
• 랜덤 액세스 머신 에뮬레이터

레퍼런스

몇 가지 예외를 제외하고 이러한 참조는 Register 머신에서의 참조와 동일합니다.

• • Goldstine, Herman H. 및 von Neumann, John, "전자계산기기의 문제와 부호화 계획", 1947년, 프린스턴 고등연구소의 의원.뉴욕 맥그로힐 북 컴퍼니, 컴퓨터 구조: 독서 및 예문, Bell, C. Gordon and Newell, Allen(1971)에서 92-119페이지에 전재. ISBN0-07-004357-4}.
• 조지 불로스, 존 P. Burgess, Richard Jeffrey(2002), 계산성과 논리: 영국 케임브리지 대학 출판부 제4판원래 Boulos-Jeffrey 텍스트는 Burgess에 의해 광범위하게 수정되었습니다: 소개 교과서보다 더 고급입니다."Abacus machine" 모델은 5장 "Abacus Computability"에서 광범위하게 개발되었습니다. 이것은 광범위하게 처리되고 비교되는 세 가지 모델 중 하나입니다. 튜링 머신(아직 Boolos의 원래 4-태플 형태)과 나머지 두 가지 모델입니다.
• Arthur Burks, Herman Goldstine, John von Neumann(1946), 전자계산기 논리설계의 예비논의, Gordon Bell과 Allen Newell(1971), 컴퓨터 구조: Readings and Examplems, McGrow-Hill Book Company, News, New York.ISBN 0-07-004357-4.
• 스테판 A 쿡과 로버트 A.Rechow(1973), 시간 제한 랜덤 액세스 머신, 컴퓨터 시스템 과학 저널 7(4): 354-375.
• Martin Davis(1958), McGrow-Hill Book Company, Inc., Computability & Unsolvability & Unsolvability뉴욕.
• Calvin Elgot과 Abraham Robinson(1964), Random-Access Stored-Program Machines, 프로그래밍 언어에 대한 접근법, 컴퓨터 기계 협회 저널, 제11권, 제4호(1964년 10월), 페이지 365-399.
• J. Hartmanis(1971), "랜덤 액세스 저장 프로그램 기계의 계산 복잡도", 수학 시스템 이론 5, 3(1971) 페이지 232–245.
• 존 홉크로프트, 제프리 울먼(1979년).오토마타 이론, 언어 및 계산 입문, 제1판, 독서 미사: 애디슨 웨슬리.ISBN 0-201-02988-X언어, NP-완전성 등의 기계 해석 문제를 중심으로 한 난해한 책.
• Stephen Kleene(1952), 네덜란드 암스테르담 노스홀랜드 출판사 메타수학 입문.ISBN 0-7204-2103-9.
• 도널드 크누스(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. The Annals of Mathematics, Vol. 74, No. 3. 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.
• 에르메스, 한스 다이 유니버설리트 프로그래머 레첸마스키넨수학.-물리학Semsterberichte (Göttingen) 4 (1954), 42-53.

• Arnold Schönhage(1980), 스토리지 수정 기계, 산업 및 응용 수학 협회, SIAM J. Compute.제9권 제3호 1980년 8월여기서 쇼나게는 SMM과 '후계자 RAM'(랜덤 액세스 머신)의 등가성을 나타낸다.스토리지 수정 기계, 이론 컴퓨터 과학(1979), 36-37페이지
• Peter van Emde Boas, "기계 모델과 시뮬레이션" 페이지 3-66 (Jan van Leeuwen, ed)이론 컴퓨터 과학 핸드북 A권: 알고리즘과 복잡성, MIT PRESS/Elsevier, 1990.ISBN 0-444-88071-2(볼륨 A).QA 76.H279 1990. van Emde Boas의 SMM 처리는 페이지 32-35에 나와 있다.이 처리는 1980년 쇼나게를 명확히 합니다.쇼나게 처리는 약간 확대됩니다.효과적인 이해를 위해서는 두 가지 참고 자료가 모두 필요할 수 있습니다.
• Hao Wang(1957), 튜링의 컴퓨터 이론 변종, JACM (컴퓨팅 기계 협회 저널) 4; 63-92.1954년 6월 23일부터 25일까지 협회 회의에서 발표.