랜덤 접근 기계

3. 비공식적 설명

RA-기계(RAM의 다른 표현)는 다음으로 구성된다.

• '''레지스터''' : 무한한 수의 메모리 위치로, 각 레지스터는 주소를 가지며, 이는 자연수 또는 0이다. 각 레지스터는 임의 크기의 자연수 하나 또는 0을 저장할 수 있다.
• '''명령표''' : 실행 명령어를 포함하는 표이다. 정확한 명령 집합은 저자에 따라 다르다. 일반적인 명령어에는 증가, 감소, 0으로 초기화, 복사, 조건부 점프, 정지가 포함된다. 다른 명령어는 명령 집합의 명령어 조합으로 생성할 수 있으므로 불필요하다.
• '''명령 레지스터'''(IR) : 명령표에서 실행 중인 명령어를 가리키는 특수 레지스터이다.

4. 간접 연산

"간접 연산"은 일상생활에서 드물지 않게 찾아볼 수 있다. 보물찾기를 예로 들어보자.

• '''보물 찾기'''

4. 1. 간접 주소 지정의 필요성

• 유한 상태 머신의 명령어 용량 제약: 유한 상태 머신은 상태와 명령어 크기가 제한되어 있어, 임의로 큰 상수를 레지스터로 직접 이동시키기 어렵다. 큰 상수가 필요한 경우 레지스터에서 시작하거나 유한한 수의 명령어를 사용해야 하지만, 유한 상태 머신에서 사용 가능한 명령어 수보다 더 큰 상수가 항상 존재한다.^[1]
• 유한 상태 머신의 레지스터 접근 제약: 카운터 머신의 유한 상태 머신은 레지스터를 이름/번호로 직접 호출해야 한다. 레지스터 수가 유한 상태 머신의 처리 능력을 초과하면, 경계 밖의 레지스터는 접근할 수 없게 된다. 예를 들어, 유한 상태 머신이 65,536개의 레지스터에만 접근할 수 있다면, 65,537번째 레지스터에는 접근할 수 없다.^[1]

4. 2. 간접 주소 지정의 예시

• '''보물 찾기'''

4. 3. 간접 COPY 명령어

5. 누산기(Accumulator)

누산기(Accumulator)는 일련의 산술 연산 동안 숫자를 누적하는 "산술 기관" 역할을 하는 레지스터이다.^[1] 골드스타인과 폰 노이만은 누산기를 "숫자를 받아 기존 숫자에 더할 수 있고, 내용을 지울 수 있으며, 내용을 저장할 수 있는 병렬 저장 기관"으로 정의했다.^[1] 이는 데스크톱 곱셈기, 표준 IBM 카운터, 릴레이 기계, 에니악 등 다양한 컴퓨터에서 공통적으로 사용되는 구성 요소이다.^[1]

누산기는 산술 연산 결과를 누적하는 특별한 레지스터이다. 누산기 기반 RAM 모델은 (i) 누산기의 내용과 (ii) 지정된 레지스터의 내용을 사용하여 모든 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

CPY 명령어를 누산기 없이 작성하면 명령어는 모호해지거나 빈 매개변수를 가져야 한다.

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

• 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 )

6. 간접 주소 레지스터(N)

만약 우리 모델이 '무제한 누산기'를 가지고 있다면, 다른 모든 레지스터들을 '제한'할 수 있을까? 간접 주소를 파생할 무제한 레지스터를 적어도 하나 제공하기 전까지는 불가능하다.

최소한의 접근 방식은 그 자체를 사용하는 것이다(쇠네이게가 이렇게 한다).

또 다른 접근 방식(쇠네이게도 이렇게 한다)은 특정 레지스터를 "간접 주소 레지스터"로 선언하고 이 레지스터와 관련된 간접 참조로 제한하는 것이다(쇠네이게의 RAM0 모델은 직접 명령어뿐만 아니라 간접 명령어에도 A 및 N 레지스터를 사용한다). 다시 말하지만, 우리의 새로운 레지스터는 "iNdex", "iNdirect" 또는 "address Number"에서 유래된 "N"과 같은 기존 명칭이 없다.

최대 유연성을 위해 누산기 A에 대해 해왔던 것처럼 N을 증가, 감소, 지우기, 테스트, 직접 복사 등을 수행하는 또 다른 레지스터로 간주할 것이다. 마찬가지로 명령어를 방향 및 간접 참조를 제공하는 단일 매개변수로 축소할 수 있다. 예를 들어 다음과 같다.

• LDAN (i/d) = CPY (i/d, N, d, A); 간접 참조 레지스터를 통해 누산기 로드
• STAN (i/d) = CPY (d, A, i/d, N). 간접 참조 레지스터를 통해 누산기 저장

7. 간접 주소 지정을 통한 튜링 완전성

Random-access machine^영어 (RAM)은 간접 주소 지정 기능을 추가하여 다중 레지스터 카운터 머신과 동일한 추상적인 계산 모델이다. 간접 주소 지정을 가진 RAM은 포스트-튜링 기계와 동등하며, 튜링 완전성을 가진다. 이를 증명하기 위해 포스트-튜링 기계의 명령어를 RAM 명령어로 변환할 수 있다.

세 개의 예약된 레지스터 "E", "P", "N"과 오른쪽으로 무제한인 레지스터 1, 2, ..., n을 가진 모델 설계를 사용한다. 레지스터 1, 2, ..., n은 "테이프의 사각형"으로 간주된다. 레지스터 "N"은 현재 "헤드"가 관찰하고 있는 "스캔된 사각형"을 가리킨다. "N"을 감소시키거나 증가시키면 헤드는 사각형을 따라 "왼쪽" 또는 "오른쪽"으로 이동하는 것처럼 보인다. 간접 CPY를 사용하여 "E"=0 또는 "P"=1의 내용을 N이 가리키는 "스캔된 사각형"으로 이동한다.

테이프가 왼쪽으로 끝난다는 사실은 LEFT 명령어가 "N"의 내용이 0인지 테스트해야 하는 문제를 야기한다.

RAM을 위한 명령어 집합 1(확장): { INC (N), DEC (N), CLR (N), CPY (d, r_s,i, N), JZ ( i, r, z ), HALT }

다음 표는 RAM에 해당하는 명령어를 기준으로 포스트-튜링 명령어를 정의한다.

8. 간접 주소 지정의 한계: 원시 재귀 함수

간접 주소 지정(Indirect addressing)의 제한된 형태(경우별 정의)로는 원시 재귀 함수만 계산할 수 있다. 완전한 재귀 함수(부분 재귀 함수)를 계산하려면 무제한 간접 주소 지정(μ 연산자)이 필요하다.

카운터 머신 모델은 제한된 형태의 간접 참조를 통해 원시 재귀 함수의 하위 클래스를 계산할 수 있다. 이는 "경우별 정의"라는 원시 재귀 연산자를 사용한다. "경우별 정의"는 기계가 포인터 레지스터의 내용을 결정하기 위해, 경우 연산자가 명시적으로 선언한 숫자/이름과 일치하는지 확인하는 방식이다. 따라서 경우별 정의는 하한 주소에서 시작하여 상한 주소로 진행하면서 일치를 시도한다.

"경계가 있는" 간접 참조는 부분 재귀 함수를 계산할 수 없게 한다. 이를 위해서는 무경계 간접 참조, 즉 μ 연산자가 필요하다.

튜링 완전하려면 카운터 머신은 단일 레지스터의 괴델 넘버 방법을 사용하거나, 필요하다면 무한정으로 레지스터 문자열의 끝을 탐색할 수 있는 능력을 갖추어야 한다.

9. 다양한 RAM 모델 예시

다양한 RAM 모델의 예시로는 쿡과 레크호우(Cook and Reckhow) 모델, 쇤하게(Schönhage, 1980) 모델 등이 있다. 쿡과 레크호우 모델은 레지스터 간 연산(read-modify-write)을 기반으로 하며, 쇤하게 모델은 RAM0와 RAM1 두 가지 모델을 제시한다.

9. 1. Cook and Reckhow (1973) 모델

9. 2. Schönhage (1980) 모델