레지스터 머신

레지스터 머신(register machine) 또는 레지스터 기계는 수리 논리학 및 이론 컴퓨터 과학에서 튜링 기계와 유사한 방식으로 사용되는 추상 기계의 일반적인 클래스이다. 레지스터 기계의 모든 모델은 튜링 동등이다.

개요

레지스터 머신은 하나 이상의 "레지스터"를 사용하여 이름을 취한다. 튜링 기계에서 사용하는 테이프 및 헤드와 달리 이 모델은 고유하게 주소가 지정된 여러 개의 레지스터를 사용하며 각 레지스터에는 단일한 양의 정수가 포함된다.

문헌에는 최소한 네 가지 하위 클래스가 있으며, 여기에는 가장 원시적인 것부터 컴퓨터와 가장 유사한 것까지 나열되어 있다.

• 카운터 머신 – 컴퓨터 하드웨어의 가장 원시적이고 축소된 이론적 모델이다. 간접 주소 지정이 부족한다. 명령은 하버드 아키텍처 방식으로 유한 상태 기계에 있다.
• 포인터 머신 – 카운터 머신과 RAM 모델이 혼합된 형태이다. 두 모델보다 덜 일반적이고 추상적이다. 명령은 하버드 아키텍처 방식으로 유한 상태 기계에 있다.
• RAM(랜덤 접근 기계) – 간접 주소 지정 기능이 있는 카운터 머신으로, 일반적으로 확장된 명령어 세트를 사용한다. 명령은 하버드 아키텍처 방식으로 유한 상태 기계에 있다.
• RASP(Random-Access Stored Program Machine Model) - 범용 튜링 기계와 유사한 레지스터에 명령어가 있는 RAM이다. 따라서 이는 폰 노이만 구조의 한 예이다. 그러나 컴퓨터와 달리 이 모델은 사실상 무한 레지스터(사용하는 경우 누산기와 같은 사실상 무한 특수 레지스터)로 이상화된다. 컴퓨터에 비해 명령어 세트의 수와 복잡성이 훨씬 줄어든다.

적절하게 정의된 레지스터 머신 모델은 튜링 동등이다. 계산 속도는 모델 사양에 따라 크게 달라진다.

실제 컴퓨터 과학에서는 가상 머신으로 알려진 관련 개념이 기본 머신 아키텍처에 대한 의존도를 줄이기 위해 사용되는 경우가 있다. 이러한 가상 머신은 교육 환경에서도 활용된다. 교과서에서 "레지스터 머신"이라는 용어는 때때로 가상 머신을 설명하기 위해 같은 의미로 사용된다.

같이 보기

• 랜덤 접근 기계
• 튜링 기계
• 알고리즘
• 정지 문제
• 바쁜 비버
• 스택 머신

외부 링크

• Weisstein, Eric Wolfgang. “Register machine”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Igblan - Minsky Register Machines