레지스터 머신

3. 레지스터 머신의 형식적 정의

레지스터 머신은 다음 요소들로 구성된다.

# '''레지스터''' : 유한 개(또는 일부 모델에서는 무한 개)의 레지스터 집합($r\_0\; \backslash ldots\; r\_n$)이 있으며, 각 레지스터는 하나의 음이 아닌 정수(0, 1, 2, ...)를 저장한다. 레지스터는 자체 산술 연산을 수행하거나, 특정 레지스터(예: "누산기")가 산술 연산에 사용될 수 있다.

# '''계수기/표시''' : 모델에 사용되는 이산적이고 구별 가능한 객체 또는 표시다. 가장 단순한 카운터 머신 모델에서는 각 산술 연산마다 하나의 객체/표시만 추가되거나 제거된다. 멜작(), 민스키() 등의 일부 카운터 머신 모델과 대부분의 임의 접근 기계(RAM) 및 임의 접근 저장 프로그램 기계(RASP) 모델에서는 한 번의 연산으로 여러 개의 객체/표시를 추가하거나 제거할 수 있다.

# '''제한된 명령어 집합''' : 명령어는 산술 명령어와 제어 명령어로 나뉜다. 명령어 집합은 모델이 튜링 동치가 되도록 구성된다.

## 산술 명령어 : 모든 레지스터 또는 특정 레지스터에서 작동한다.

## 제어 명령어 : 카운터 머신은 선택적으로 { 복사($r\_1,r\_2$) }를 포함한다. RAM 및 RASP는 { 복사($r\_1,r\_2$) } 또는 { 레지스터 $r$에서 누산기로 로드, 누산기를 $r$에 저장, 즉시 상수로 누산기 로드 }를 포함한다. 모든 모델은 레지스터 값에 따른 조건부 "점프"(분기, goto)를 최소한 하나 포함한다.

## 레지스터 주소 지정 방식 :

##* 카운터 머신: 간접 주소 지정이 없다.

##* RAM 및 RASP: 간접 주소 지정이 가능하다.

## 입출력 : 모든 모델에서 선택 사항이다.

# '''상태 레지스터''' : 명령어 레지스터(IR)는 실행될 현재 명령어와 명령어 테이블에서의 해당 주소를 저장하며, 유한 상태 기계 내에 있다. RAM 및 RASP는 레지스터 주소를 결정하기 위해 직접 또는 간접 주소 지정을 사용한다. RASP의 프로그램 카운터(PC)는 현재 명령어 번호를 보관하는 레지스터이다.

# '''명령어 목록''' : 명령어는 일반적으로 순차적으로 실행된다. 카운터 머신, 임의 접근 기계(RAM), 포인터 머신은 하버드 아키텍처를 따르고, 임의 접근 저장 프로그램 기계(RASP)는 폰 노이만 아키텍처를 따른다.

3. 1. 레지스터

• '''유한 개수의 레지스터''': 유한 개수(또는 모델에 따라 무한 개수)의 레지스터가 있으며, 각 레지스터는 하나의 음이 아닌 정수를 저장한다.

• 자체 산술 연산이 가능하다.
• 누산기와 같은 특정 레지스터가 산술 연산에 사용될 수 있다.
• 주소 레지스터로 사용될 수 있다.

3. 2. 카운터/표시

3. 3. 명령어 집합

산술 명령어는 레지스터의 값을 변경하고, 제어 명령어는 프로그램의 실행 흐름을 제어한다. RAM과 RASP는 최소 구성과 확장 구성으로 나뉘며, 확장 구성은 최소 구성의 명령어에 추가적인 명령어들을 포함한다.

3. 3. 1. 산술 명령어

3. 3. 2. 제어 명령어

3. 4. 레지스터 주소 지정 방식

• 카운터 머신: 간접 주소 지정을 지원하지 않으며, 고도로 원자화된 모델에서는 즉시 피연산자를 사용할 수 있다.
• 임의 접근 기계(RAM) 및 임의 접근 저장 프로그램 기계(RASP): 간접 주소 지정이 가능하며, 즉시 피연산자는 일반적이다.

3. 5. 입출력

4. 레지스터 머신 모델의 역사적 발전

1950년대 초, 컴퓨터를 튜링 기계로 특징짓고, 튜링 동등성을 가진 컴퓨터와 유사한 모델을 정의하려는 두 가지 경향이 나타났다. 이러한 연구는 에밀 포스트의 "태그" 문제와 힐베르트의 문제 중 디오판토스 방정식 문제 해결을 위한 노력의 일환이었다. 연구자들은 덜 논리적이고 더 산술적인 튜링 동등 모델을 찾고자 했다.

한스 헤르메스(1954), 로자 페테르(1958), 하인츠 카펭스트(1959)는 컴퓨터를 튜링 머신으로 특징짓는 첫 단계를 밟았고, 하오 왕(1954, 1957)은 튜링 머신과 동등한 컴퓨터와 유사한 모델을 정의하는 두 번째 단계를 시작했다. 이후 즈디슬라우 알렉산더 멜자크(1961), 요아힘 람벡(1961), 마빈 민스키(1961, 1967)가 이 연구를 발전시켰다.

유리 마티야세비치는 레지스터 머신이 디오판토스 방정식 구성에 특히 적합하며, 튜링 머신처럼 기본적인 명령으로 숫자를 다룬다고 언급했다. 람벡, 멜자크, 민스키, 셰퍼드슨, 스터지스는 거의 동시에 같은 아이디어를 독립적으로 발견했다.

4. 1. 왕 (Wang, 1954, 1957) 모델: 포스트-튜링 머신

• { LEFT, RIGHT, PRINT, JUMP_if_marked_to_instruction_z }

• { LEFT, RIGHT, PRINT, ERASE, JUMP_if_marked, [maybe JUMP or JUMP_IF_blank] }

4. 2. 민스키 (Minsky), 멜자크-람벡 (Melzak-Lambek), 셰퍼드슨-스터지스 (Shepherdson-Sturgis) 모델

4. 3. 엘고트-로빈슨 (Elgot-Robinson, 1964)과 RASP 문제

4. 4. 하트마니스 (Hartmanis, 1971)

4. 5. 쿡과 레크호 (Cook and Reckhow, 1973)의 RAM

참조

_[1] 서적 Structure and Interpretation of Computer Programs MIT Press 1996
_[2] 서적 Structure and Interpretation of Computer Programs MIT Press 1996