레지스터 머신

레지스터 머신 (Register Machine)은 튜링 완전성을 갖춘 추상적인 계산 모델의 하나입니다. 레지스터 머신은 유한한 개수의 레지스터와 유한한 개수의 명령어로 구성됩니다. 각 레지스터는 임의의 크기의 자연수를 저장할 수 있습니다. 명령어는 레지스터의 값을 증가시키거나, 감소시키거나, 조건에 따라 분기하는 연산을 수행합니다.

레지스터 머신은 컴퓨터의 기본적인 작동 원리를 단순화하여 표현한 것으로, 이론 전산학에서 계산 가능성 및 복잡도를 연구하는 데 사용됩니다. 튜링 기계와 마찬가지로, 레지스터 머신은 모든 계산 가능한 함수를 계산할 수 있다는 점에서 튜링 완전성을 가집니다.

레지스터 머신의 기본적인 구조는 다음과 같습니다:

• 레지스터: R1, R2, ..., Rn과 같이 번호가 매겨진 유한한 개수의 레지스터. 각 레지스터는 음이 아닌 정수를 저장합니다.
• 명령어: 다음과 같은 형태의 명령어로 구성됩니다.
  • INC(Ri): 레지스터 Ri의 값을 1 증가시킵니다.
  • DEC(Ri, L): 레지스터 Ri의 값이 0이 아니면 1 감소시키고, 0이면 레이블 L로 점프합니다.
  • HALT: 계산을 중단합니다.

레지스터 머신은 특정 문제에 대한 알고리즘을 일련의 레지스터 머신 명령어로 표현하여 계산을 수행합니다. 레지스터 머신 모델은 계산 이론의 여러 중요한 개념을 이해하고 증명하는 데 유용한 도구로 활용됩니다.