랜덤 액세스 스토어드 프로그램 머신
Random-access stored-program machine |
이론 컴퓨터 과학에서 RASP(Random-Access Stored-Program) 기계 모델은 알고리즘 개발과 알고리즘 복잡성 이론의 목적으로 사용되는 추상 기계입니다.
RASP는 RAM과 달리 프로그램이 입력과 함께 "레지스터"에 있는 RAM 모델입니다.레지스터는 무제한(용량 무한)입니다. 레지스터 수가 유한한지 여부는 모델에 따라 다릅니다.따라서 RASP와 RAM은 범용 튜링 기계가 튜링 기계와 같은 역할을 합니다.RASP는 von Neumann 아키텍처의 한 예이며 RAM은 Harvard 아키텍처의 한 예입니다.
RASP는 모든 추상 모델 중에서 컴퓨터의 일반적인 개념에 가장 가깝습니다.그러나 실제 컴퓨터와 달리 RASP 모델에는 보통 매우 단순한 명령어 세트가 있으며, CISC 및 RISC 프로세서의 명령어보다 가장 간단한 산술 명령어, 등록에서 등록으로의 이동 명령어 및 테스트/점프 명령어로 대폭 축소되어 있습니다.일부 모델에는 어큐뮬레이터와 같은 몇 개의 추가 레지스터가 있습니다.
레지스터 머신, RAM, 포인터 머신과 함께 RASP는 4개의 일반적인 순차 머신 모델을 구성하며, 이를 "병렬" 모델(예: 병렬 랜덤 액세스 머신)과 구별하기 위해 이 모델을 부릅니다 [cf. van Emde Boas(1990).
비공식 정의: 랜덤 액세스 스토어드 프로그램 모델(RASP)
RASP의 개요:
- RASP는 랜덤액세스 머신 RAM 섀시에 구축된 Universal Turing Machine(UTM; 유니버설튜링 머신)입니다
독자는 UTM이 튜링 5-튜플의 문자열로 테이프에 쓰여진 잘 형성된 "프로그램"을 해석할 수 있는 "범용" 유한 상태 명령어 테이블을 가진 튜링 기계라는 것을 기억할 것이다.고전적인 UTM 모델은 테이프에서 튜링 5-튜플을 찾기를 기대하지만, 튜링 기계가 그것들을 찾기를 기대한다면, 상상할 수 있는 어떤 프로그램 집합도 거기에 놓일 수 있다 - 그것의 유한 상태 테이블이 그것들을 해석하고 그것들을 원하는 동작으로 변환할 수 있다는 것을 고려하면.프로그램과 함께 테이프에 인쇄되는 것은 입력 데이터/파라미터/숫자(보통 프로그램 오른쪽에 있음)와 출력 데이터/숫자(보통 양쪽의 오른쪽에 있음, 입력과 혼합됨, 또는 치환됨)입니다."사용자"는 튜링 머신의 머리를 첫 번째 명령 위에 배치해야 하며, 입력은 테이프 상의 프로그램 및 유한 상태 머신의 명령 테이블 모두에 적합한 특정 장소와 형식에 배치되어야 한다.
RASP는 이 구조를 모방하여 "프로그램"과 "데이터"를 구멍(레지스터)에 배치합니다.그러나 UTM과 달리 RASP는 조건부 테스트를 통해 다른 곳으로 전송되지 않는 한 순차적으로 명령을 가져옵니다.
혼란스러운 점: 두 가지 명령어 세트:UTM과 달리 RASP 모델에는 두 가지 명령 세트가 있습니다. 즉, 상태 기계 명령 테이블('인터프리터')과 구멍에 있는 '프로그램'입니다.두 세트를 동일한 세트에서 그릴 필요는 없습니다.
RASP로서 기능하는 RAM의 예
다음 프로그램 예시는 레지스터(홀) #18의 내용을 레지스터(홀) #19로 이동하여 프로세스에서 #18의 내용을 지웁니다.
5: 03 18 15 JZ 18,15 ; [18]이 0인 경우 15로 점프하여 프로그램을 종료합니다. 02 18 DEC 18 ; 감소 [18] 01 19 주식회사 19 ; 증분 [19] 03 15 05 JZ 15, 5 ; [15]가 0인 경우 5로 점프하여 루프를 반복합니다(무조건 점프를 시뮬레이션하려면 Halt 사용). 15: 00 H 정지 18: n ; 복사할 소스 값 19: ; 복사지 이 RASP 머신에서 사용할 수 있는 프로그램 명령은 예를 짧게 하기 위한 간단한 세트입니다.
| 설명 | 니모닉 | 레지스터 "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 |
예를 쉽게 하기 위해 RAM-as-RASP 상태 머신에 동일한 세트에서 가져온 기본 명령을 장착하지만 두 개의 간접 복사 명령으로 보강합니다.
- RAM 상태 기계 지침:
- { INC h; DEC h; JZ h, xxx; CPY "ha", "ha", "h"; CPY "ha", "ha"}
RASP 머신의 스테이트 머신이 레지스터의 프로그램을 해석할 때 스테이트 머신은 정확히 무엇을 하고 있을까요?! 마크가 포함된 열에는 프로그램을 "해석"할 때 상태 머신의 액션이 시간 순서대로 나열됩니다.
| PC | 적외선 | ||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 홀 번호 → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| 프로그램, 매개 변수 → | 5 | JZ | 18 | 15 | DEC | 18 | 주식회사 | 19 | JZ | 15 | 5 | H | n | ||||||
| 인코딩된 프로그램 → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||
| 상태 기계 지침 ↓ | |||||||||||||||||||
| ! |
기존 방식에서는 상태 머신의 액션을 Fetch와 Execute라는 두 가지 주요 "단계"로 나눕니다.이하에서는, 이 2개의 주요한 국면에 「하위 단계」가 있는 것을 확인할 수 있습니다.규약에 동의한 것은 없습니다.모든 모델에는 정확한 설명이 필요합니다.
가져오기 단계
상태 시스템은 직간접적으로 모든 레지스터에 액세스할 수 있습니다.즉, 프로그램 카운터 PC로서 #1을 채용하고 있습니다.프로그램 카운터의 역할은 프로그램 목록에 "장소를 유지"하는 것입니다. 상태 시스템에는 전용 상태 레지스터가 있습니다.
스테이트 머신은, 기동시에 PC내의 번호를 검색합니다.이것은 프로그램의 첫 번째 「Program-Instruction」(즉, #5).
(간접 복사 기능을 사용하지 않는 경우, 프로그램에 대한 지시사항을 #2에 넣는 작업은 다소 어렵습니다.스테이트 머신은 간접적으로 포인트 투 레지스터를 감소시키면서 레지스터 #2를 직접 증가시킵니다.「파스」단계에서는, #2 의 카운트를 희생하는 것으로, #5 의 희생된 컨텐츠가 복원됩니다.
위의 우회도로의 요점은 스테이트 머신이 다음 두 종류의 간접복사에 접근할 수 있을 때 생활이 훨씬 쉬워진다는 것을 보여주는 것입니다.
- i에서 j로 간접 복사: CPY "hi", "hj"
- i에서 j로 직접 복사 및 간접 복사: CPY "hi", "hj"
다음 예시는 상태 머신의 "fetch" 단계 중에 발생하는 작업을 보여 줍니다.상태 시스템의 작업이 "상태 시스템 지침 ↓" 열에 나열됩니다.가져오기 종료 시 레지스터 #2에 첫 번째 명령 JZ의 "조작 코드"("opcode") 숫자 값 3이 포함되어 있는지 확인합니다.
| PC | PIR | ||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 홀 번호 → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | ||
| 프로그램, 매개 변수 → | 5 | JZ | 18 | 15 | DEC | 18 | 주식회사 | 19 | JZ | 15 | 5 | H | n | ||||||||
| 인코딩된 프로그램 → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||||
| 걸음 | 상태 기계 지침 ↓ | ||||||||||||||||||||
| 1 | fetch_instr: | CPY '1', '2' | 5 i | [3] | [3] | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n |
해석 단계
이제 프로그램 명령의 번호(예: 3 = "JZ")가 레지스터 #2 - "Program-Instruction Register" PIR에 있으므로 상태 기계는 IR이 비워질 때까지 숫자를 감소시킵니다.
감소하기 전에 IR이 비어 있으면 프로그램 명령은 0 = HALT가 되고 기계는 "HALT" 루틴으로 점프합니다.첫 번째 감소 후 홀이 비어 있으면 명령어는 INC가 되고 기계는 명령어 "inc_routine"으로 점프합니다.두 번째 감소 후 빈 IR은 DEC를 나타내며 기계는 "dec_routine"으로 점프합니다.세 번째 감소 후에는 IR이 실제로 비어 있으므로 "JZ_routine" 루틴으로 점프합니다.IR에 예기치 않은 숫자가 아직 존재한다면 기계가 오류를 검출하고 HALT(예를 들어, HALT)가 발생할 수 있습니다.
| PC | 적외선 | ||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 홀 번호 → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | ||
| 프로그램, 매개 변수 → | 5 | JZ | 18 | 15 | DEC | 18 | 주식회사 | 19 | JZ | 15 | 5 | H | n | ||||||||
| 인코딩된 프로그램 → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||||
| 상태 기계 지침 ↓ | |||||||||||||||||||||
| CPY '1', '2' | 5 i | [3] | [3] | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||||
| JZ 2, 홀트 | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | |||||||
| 3 | DEC 2 | 5 | 2 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||
| 4 | JZ 2,inc_routine: | 5 | 2 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||
| 5 | DEC 2 | 5 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||
| 6 | JZ 2,dec_routine | 5 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||
| 7 | DEC 2 | 5 | 0 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||
| 8 | JZ 2, JZ_routine | 5 | 0 ! | ||||||||||||||||||
| — | 정지: | 정지하다 | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| — | inc_inc_inc_inc: | 기타. | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| — | dec_filename: | 기타. | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 9 | JZ_routine: | 기타. | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n |
실행 단계, JZ_routine
이제 상태 머신은 어떤 프로그램 명령을 실행해야 하는지 알고 있습니다. 실제로 "JZ_routine" 명령 시퀀스로 점프했습니다.JZ 명령에는 (i) 테스트할 레지스터의 번호 및 (ii) 테스트가 성공했을 때(구멍이 비어 있는 경우) 가는 주소가 2개의 오퍼랜드가 있습니다.
(i) 피연산자 가져오기 - 어떤 레지스터가 비어 있는지 테스트합니다.유한 상태 기계는, 페치 단계와 같이, PC가 가리키는 레지스터의 내용, 즉 구멍 #6을 프로그램 명령 레지스터 PIR #2로 이동시킨다.그런 다음 레지스터 #2의 내용을 사용하여 테스트 대상 레지스터, 즉 레지스터 #18을 가리킨다.18번 구멍에는 숫자 "n"이 포함되어 있습니다.테스트를 실시하기 위해서, 스테이트 머신은 PIR 의 내용을 사용하고, 레지스터 #18 의 내용을 스페어 레지스터 #3 에 간접적으로 카피합니다.즉, 2개의 이벤트(ia)가 있습니다.레지스터 #18은 비어 있고 (ib)레지스터 #18은 비어 있지 않습니다.
(ia): 레지스터 #3이 비어 있는 경우 상태 머신은 (ii) 두 번째 오퍼랜드 가져오기 - 점프 주소를 가져옵니다.
(ib): 레지스터 #3이 비어 있지 않은 경우 상태 머신은 (ii) 두 번째 오퍼랜드 페치를 건너뛸 수 있습니다.PC의 2배로 늘린 후 무조건 명령 가져오기 단계로 돌아가 프로그램 명령 #8(DEC)을 가져옵니다.
(ii) 오퍼랜드 가져오기 - 점프 주소.레지스터 #3이 비어 있는 경우 상태 머신은 PC를 사용하여 자신이 가리키는 레지스터의 내용을 간접적으로 복사한다(#8).이것으로, PC는 점프 투 주소 15를 보관 유지합니다.그런 다음 상태 머신은 무조건 명령 가져오기 단계로 돌아가 프로그램 명령 #15(HALT)를 가져옵니다.
| PC | 적외선 | ||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 홀 번호 → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | ||
| 프로그램, 매개 변수 → | 5 | JZ | 18 | 15 | DEC | 18 | 주식회사 | 19 | JZ | 15 | 5 | H | n | ||||||||
| 인코딩된 프로그램 → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||||
| 걸음 | 상태 기계 지침 ↓ | ||||||||||||||||||||
| 9 | JZ_routine | INC 1 | [6] | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 10 | CPY '1', '2' | 6 i | [18] | 3 | [18] | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||
| 11 | 테스트 홀: | CPY '2', '3' | 6 | 18 i | [n] | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | [n] | ||||
| 12 | 테스트 홀: | JZ 3, 점프 | 6 | 18 i | [n] | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||
| n | n | ||||||||||||||||||||
| 13 | no_filename: | INC 1 | [7] | 18 | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||
| 14 | INC 1 | [8] | 18 | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 15 | J fetch_instr | 8 | 18 | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 1 | fetch_instr: | CPY '1', '2' | 8 i | [2] | n | 3 | 18 | 15 | [2] | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||
| 2 | 해석: | 기타. | |||||||||||||||||||
| 13 | 점프: | INC 1 | [7] | 18 | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||
| 14 | CPY '1', '1' | [15] | 18 | n | 3 | 18 | [15] | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 15 | J fetch_instr | 15 | 18 | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 1 | fetch_instr: | CPY '1', '2' | 15 i | [0] | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | [0] | n | ||||
| 2 | 해석: | 기타. |
단계 INC, DEC 실행
다음은 프로그램 명령 INC h, DEC h에 대한 RAM의 상태-기계 해석을 완료하고 RAM이 RASP를 "인칭"하는 방법에 대한 데모를 완료합니다.
- 대상 프로그램 명령 집합: { INC h; DEC h; JZ h, xxx, HALT }
간접 스테이트 머신 명령 INCi 및 DECi가 없으면 INC 및 DEC 프로그램 명령을 실행하기 위해 스테이트 머신은 포인트 내용을 취득하기 위해 간접 복사를 사용하여 스페어 레지스터 #3, DEC 또는 INC에 등록한 후 간접 복사를 사용하여 포인트 투 레지스터로 되돌려 보내야 합니다.
| PC | 적외선 | ||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 홀 번호 → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | ||
| 프로그램, 매개 변수 → | 5 | JZ | 18 | 15 | DEC | 18 | 주식회사 | 19 | JZ | 15 | 5 | H | n | ||||||||
| 인코딩된 프로그램 → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||||
| 상태 기계 지침 ↓ | |||||||||||||||||||||
| 15 | J fetch_instr | 8 | 18 | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 16 | fetch_instr: | CPY '1', '2' | 8 i | [2] | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||
| 17 | 해석: | JZ 2, 홀트 | 8 | 2 | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||
| 18 | DEC 2 | 8 | [1] | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 19 | JZ 2, inc_routine: | 8 | 1 | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 20 | DEC 2 | 8 | [0] | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 21 | JZ 2, dec_routine: | 8 | 0 ! | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 22 | dec_filename: | INC 1 | 9 | 0 | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||
| 23 | CPY '1', '2' | 9 i | 18 | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 24 | CPY '2', '3' | 9 | 18 i | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 25 | JZ 3,*+2 | 9 | 18 | n | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 26 | DEC 3 | 9 | 18 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||
| 27 | CPY '3', '2' | 9 | 18 i | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | |||||
| 28 | INC 1 | 10 | 18 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | |||||
| 29 | J fetch_instr | 10 | 18 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | |||||
| 30 | fetch_instr: | CPY '1', '2' | 10 i | 1 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | ||||
| 31 | 해석: | JZ 2, 홀트 | 10 | 1 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | ||||
| 32 | DEC 2 | 10 | 0 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | |||||
| 33 | JZ 2,inc_routine: | 10 | 0 ! | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | |||||
| 34 | inc_inc_inc_inc: | INC 1 | 11 | 0 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | ||||
| 35 | CPY '1', '2' | 11 i | 19 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | |||||
| 36 | CPY '2', '3' | 11 | 19 i | 0 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | 0 | ||||
| 37 | INC 3 | 11 | 19 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | 0 | ||||
| 38 | CPY '3', '2' | 11 | 19 i | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | 1 | ||||
| 39 | INC 1 | 12 | 19 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | 0 | ||||
| 40 | J fetch_instr | 12 | 19 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | 0 | ||||
| 41 | fetch_instr: | 기타. | 12 | 19 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | 0 |
대체 절차:데모 결과, 4개의 명령의 원시적인 RASP를 얻을 수 있었습니다만, 독자는 「ADD 「h」또는 「MULT 「hhab」등의 추가의 명령이 어떻게 행해지는지를 상상할 수 있습니다.
자동 수정 RASP 프로그램
RAM이 RASP로 동작하고 있는 경우, 새로운 것을 얻을 수 있었습니다.RAM과 달리 RASP는 프로그램 명령의 자기 수정 능력을 갖추고 있습니다(상태 머신의 명령은 동결되어 머신에 의해 수정할 수 없습니다).Cook-Reckhow(1971) (75페이지)는 RASP 모델에 대한 설명에서 Hartmanis(1971) (239ff)와 같이 이에 대해 언급한다.
이 개념의 초기 설명은 Goldstine-von Neumann(1946)에서 찾을 수 있다.
- "우리는 주어진 주문에 숫자를 대입할 수 있는 주문[지시]이 필요합니다.이러한 순서를 통해 계산 결과를 해당 명령 또는 다른 계산을 지배하는 명령에 도입할 수 있다.(p.93)
이러한 기능에 의해, 다음의 것이 가능하게 됩니다.
- subroutines - 호출 루틴(또는 서브루틴)은 서브루틴의 마지막 명령어(즉 "JMP return_address")에 리턴 주소 "return_address"를 저장합니다.
- 이른바 점프 테이블
- 자기 인식 코드
RASP 프로그램-요리 및 레크하우의 명령어 세트(1973년)
영향력 있는 논문에서 스테판 A. 쿡과 로버트 A.RASP 버전을 정의하는 방법:
- "여기에 설명된 RASP(Random Access Stored-Program Machine)는 Hartmanis에서 설명한 RASP와 유사합니다 [1971](페이지 74).
그들의 목적은 복잡도 분석 이론에 사용되는 RAM, RASP 및 멀티 테이프 튜링 기계 등 다양한 모델의 실행 시간을 비교하는 것이었다.
RASP 모델의 주요 특징은 간접적인 프로그램 명령에 대한 조항이 없다는 것입니다(논의 페이지 75페이지 75 참조).이는 프로그램 자체를 수정하도록 요구함으로써 달성됩니다.필요한 경우 명령은 특정 명령의 "파라미터"(즉, "operand")를 수정할 수 있습니다.그들은 각각의 "명령어"가 두 개의 연속된 레지스터를 사용하도록 그들의 모델을 설계했다. 하나는 "연산 코드"(그들의 단어)와 매개 변수 "주소 또는 정수 상수".
RASP의 레지스터는 용량과 수에 제한이 없습니다.또한 어큐뮬레이터 AC와 명령 카운터 IC도 제한이 없습니다.명령 세트는 다음과 같습니다.
| 작동 | 니모닉 | 조작 코드 | 묘사 |
|---|---|---|---|
| 부하 상수 | LOD, k | 1 | 축전지에 상수 k를 넣다 |
| 더하다 | 추가, j | 2 | 레지스터 j의 내용을 어큐뮬레이터에 추가하다 |
| 빼다 | SUB, j | 3 | 레지스터 j의 내용을 어큐뮬레이터에서 빼다 |
| 가게 | STO, j | 4 | 어큐뮬레이터의 내용을 레지스터 j에 복사하다 |
| 양의 축전지에 분기하다 | BPA, xxx | 5 | 어큐뮬레이터의 내용이 0보다 크면 xxx, 그렇지 않으면 다음 명령으로 이동합니다. |
| 읽어주세요 | RD, j | 6 | 레지스터 j에 대한 다음 입력 |
| 인쇄물 | PRI, j | 7 | 레지스터 j의 출력 내용 |
| 멈추다 | HLT | 기타 - 또는 + 정수 | 이제 그만 |
레퍼런스
대부분의 경우 RAM 머신과 RASP 머신은 같은 기사에 함께 기재되어 있습니다.이것들은 랜덤 액세스머신으로부터 카피되고 있습니다만, 몇개의 예외를 제외하고, 이러한 참조는 Register머신에서의 참조와 같습니다.
- 조지 불로스, 존 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. ISBN0-07-004357-4.
- 스테판 A 쿡과 로버트 A.Rechow(1972), 시간 제한 랜덤 액세스 머신, Journal of Computer Systems Science 7(1973), 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, received August 15, 1960). "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.
{{cite journal}}:날짜 값 확인:date=(도움말) - Marvin Minsky (1967). Computation: Finite and Infinite Machines (1st ed.). Englewood Cliffs, N. J.: Prentice-Hall, Inc. ISBN 0-13-165449-7. 특히 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.
- SMM에 대한 Van Emde Boas의 치료는 페이지 32-35에 나와 있습니다.이 처리는 1980년 쇼나게를 명확히 한다.쇼나게 처리는 약간 확대된다.효과적인 이해를 위해서는 두 가지 참고 자료가 모두 필요할 수 있습니다.
- Hao Wang(1957), 튜링의 컴퓨터 이론 변종, JACM (컴퓨팅 기계 협회 저널) 4; 63-92.1954년 6월 23일부터 25일까지 협회 회의에서 발표.
