등록기

수학 논리학과 이론 컴퓨터 과학에서 레지스터 기계는 튜링 기계와 유사한 방식으로 사용되는 추상 기계의 일반 클래스입니다.모든 모델은 튜링 등가입니다.

개요

레지스터 머신은, 1개 이상의 「등록」을 사용하고 있기 때문에,튜링 머신에 의해 사용되는 테이프와 헤드와는 대조적으로, 모델은 각각이 하나의 양의 정수를 보유하는 여러 개의 고유 주소 지정 레지스터를 사용합니다.

문헌에는 적어도 4개의 서브클래스가 있으며, 여기에서는 가장 원시적인 것부터 가장 컴퓨터 같은 것까지 열거되어 있습니다.

• 카운터 머신 – 컴퓨터 하드웨어의 가장 원시적이고 축소된 이론 모델.간접 주소 지정이 없습니다.명령은 하버드 아키텍처의 방식으로 유한 상태 기계에 있습니다.
• 포인터 머신– 카운터 머신과 RAM 모델의 조합.어느 모델보다 덜 일반적이고 더 추상적입니다.명령은 하버드 아키텍처의 방식으로 유한 상태 기계에 있습니다.
• RAM(랜덤 액세스 머신)– 간접 어드레싱과 일반적으로 증강 명령 세트가 있는 카운터 머신.명령은 하버드 아키텍처의 방식으로 유한 상태 기계에 있습니다.
• RASP(Random-access Stored-Program Machine Model) – 범용 튜링 머신과 유사한 레지스터에 명령어가 포함된 RAM으로, 폰 노이만 아키텍처의 한 예입니다.그러나 컴퓨터와 달리 모델은 효과적으로 무한 레지스터(및 사용되는 경우 효과적으로 무한 특수 레지스터(어큐뮬레이터 등)를 사용하여 이상적입니다.컴퓨터에 비해 명령어 세트는 수와 복잡성이 크게 줄어듭니다.

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

실제 컴퓨터 과학에서는 가상 머신이라고 하는 유사한 개념을 사용하여 기본 머신 아키텍처에 대한 의존성을 최소화할 수 있습니다.이런 기계는 가르치는 데도 사용된다."^[1]등록 시스템"이라는 용어는 교과서에서 가상 시스템을 가리키는 데 사용되기도 합니다.

형식적 정의

레지스터 머신은 다음과 같이 구성됩니다.

1. $범위$(용량)에 제한이 없는 라벨 부착, 이산, $무제한$ 레지스터의 수: 각각 무한 범위로 간주되며 각각이 음이 아닌 단일 정수$(0,$ 1, 2, $...)$^[2]를 유지하는 $레지스터{\displaystyle {}_{}}$ $0$ 일부 모델에서는 무한) $세트$.레지스터는 자체 연산을 수행하거나 "어카뮬레이터" 및/또는 "주소 레지스터"와 같은 연산을 수행하는 하나 이상의 특수 레지스터가 있을 수 있습니다.랜덤 액세스 머신을 참조해 주세요.
2. 집계 카운터 또는 표시:^[3] 모델에 적합한 구분 불가능한 개별 객체 또는 한 가지 종류의 표시.가장 감소된 카운터 머신 모델에서는 각 산술 연산마다 하나의 객체/마크만 해당 위치/테이프에 추가 또는 제거됩니다.일부 카운터 머신 모델(예: Melzak(1961), Minsky(1961)) 및 대부분의 RAM 및 RASP 모델은 "추가" 및 일반적으로 "감산"을 사용하여 한 번의 작업으로 두 개 이상의 객체/마크를 추가하거나 제거할 수 있습니다. 때로는 "곱셈" 및/또는 "분할"을 사용합니다.일부 모델에는 레지스터에서 등록으로 개체/마크의 "덩어리"를 이동하는 "복사"(가변: "이동", "로드", "저장")와 같은 제어 작업이 있습니다.
3. (매우) 제한된 명령어 세트: 명령어는 산술과 제어의 두 가지 클래스로 나뉘는 경향이 있습니다.명령 집합은 모델이 튜링 등가(부분 재귀 함수를 계산할 수 있어야 함)가 될 수 있도록 "명령 집합"을 형성하기 위해 두 클래스로부터 명령어를 끌어낸다.
   1. 산술: 산술 명령은 모든 레지스터 또는 특수 레지스터(예: 축전지)에서만 작동할 수 있습니다.일반적으로 다음 세트 중에서 선택됩니다(단, 예외는 있습니다).
      • 카운터 시스템: { 증분(r), 감소(r), 0으로 지우기(r)}
      • 축소 RAM, RASP: { 증분(r), 감소(r), 클리어 투 제로(r), 부하 즉시 상수 k, 추가(r₁,r₂), 적정 감산(r₁,r₂), 증분 어큐뮬레이터, 감소 어큐뮬레이터, 클리어 어큐뮬레이터, 레지스터 r의 어큐뮬레이터에 레지스터 내용 추가, 적산기, 적산자, 적산자, 적산자, 적산자, 적산자, 적산자, 적산자, 적산자, 적산자, 적산자, 적산자, 적산자, 적산자, 적산자, 적산자, 적산자, 적산자, 적산자
      • 증강 RAM, RASP: 모든 축소 명령 플러스: { 곱하기, 나누기, 다양한 부울 비트 단위(좌회전, 비트 테스트 등)}
   2. 제어:
      • 카운터 머신 모델: 옵션 {복사₁(r₂,r)}
      • RAM 및 RASP 모델: 대부분의 모델에는 {복사₁(r₂,r)} 또는 {r에서 로드 어큐뮬레이터, r에 어큐뮬레이터 저장, 즉시 상수 로드 어큐뮬레이터}가 있습니다.
      • 모든 모델: 레지스터 테스트 후 하나 이상의 조건부 "점프"(분기, goto) ({점프-if-zero, Jump-if-not-zero(예: Jump-if-positive), Jump-if-e-equal, Jump-if-not-not equal})
      • 모든 모델 옵션: {무조건 프로그램 점프(goto)}
   3. 등록 주소 지정 방법:
      • 카운터 머신: 간접 어드레싱 없음, 고도로 원자화된 모델에서는 즉시 피연산자가 가능
      • RAM 및 RASP: 간접 주소 지정 가능, 즉시 피연산자
   4. 입출력: 모든 모델에서 옵션
4. 스테이트 레지스터:특수 명령 레지스터 "IR"는 위의 레지스터와 별도로 현재 실행할 명령과 해당 주소를 명령 테이블에 저장합니다. 이 레지스터와 TABLE는 유한 상태 기계에 위치합니다.
   • IR은 모든 모델 출입이 금지되어 있습니다.RAM 및 RASP의 경우, 등록부의 "주소"를 결정하기 위해 모델은 (i) 직접 주소 지정의 경우(테이블에 의해 지정되고 IR에 임시로 위치하는 주소) 또는 (i) IR의 지침에 의해 지정되는 등록부의 내용을 선택할 수 있다.
   • IR은 RASP(또는 기존 컴퓨터)의 "프로그램 카운터"(PC)가 아닙니다.PC는 어큐뮬레이터와 비슷하지만 RASP의 현재 레지스터 기반 명령의 번호를 유지하는 데만 사용됩니다.따라서 RASP는 두 개의 "명령/프로그램" 레지스터(i)와 (ii) 레지스터에 위치한 프로그램을 위한 PC(Program Counter)를 가지고 있다. ('PC' 전용 레지스터와 함께, RASP는 "프로그램-명령 레지스터"(이러한 번호의 "PIR")에 다른 레지스터를 할당할 수 있다.'IR', 'PR' 등)
5. 레이블이 지정된 명령 목록(일반적으로 순차적 순서:$명령{\displaystyle {}_{}}$ I ${\displaystyle {1\mathrm{}}_{}}$… ${\displaystyle I_{}}$ m$$\ $displaystyle$ I_${1$} $\ldots$ I_${m$ . 카운터 머신, 랜덤 액세스 머신(RAM) 및 포인터 머신의 경우 명령 스토어는 유한 상태 머신의 "테이블"에 있습니다.이러한 모델은 하버드 아키텍처의 예입니다.RASP의 경우, 프로그램 스토어는 레지스터에 있습니다.따라서 이것은 von Neumann 아키텍처의 예입니다.랜덤 액세스머신 및 랜덤액세스 스토어드 프로그램머신을 참조해 주세요.
   보통 컴퓨터 프로그램과 마찬가지로 명령이 순차적으로 나열됩니다. 점프가 성공하지 않는 한 기본 시퀀스는 숫자 순서로 계속됩니다.예외는 주판(Lambek(1961), Minsky(1961) 카운터 머신 모델입니다.모든 명령에는 적어도 1개의 "다음" 명령 식별자 "z"가 있으며 조건부 브랜치에는 2개가 있습니다.
   • 또한 주판 모델이 두 개의 명령어(예: { INC ( r , z ) 、 JZDEC ( r , z_truefalse ) )를 조합하는 것에 주의해 주세요.
     조건부 표현에 대한 자세한 내용은 매카시 형식주의를 참조하십시오.IF r =0 THEN_true z_false ELSE z" (cf McCarthy (표준)).

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

1950년대 초에 두 가지 경향이 나타났는데, 첫 번째 경향은 컴퓨터를 튜링 기계로 특징짓는 것이고, 두 번째 경향은 컴퓨터와 유사한 모델을 정의하는 것이다. 즉, 튜링 기계의 힘으로 순차적인 명령 시퀀스와 조건부 점프를 하는 모델이다.이 작업의 필요성은 두 가지 "어려운" 문제, 즉 에밀 포스트가 제기하는 해결할 수 없는 단어 문제, 즉 "태그"와 힐베르트의 문제의 매우 "어려운" 문제, 즉 디오판틴 방정식에 관한 10번째 질문의 맥락에서 수행되었습니다.연구자들은 본질적으로 덜 "논리적"이고 더 "산술적"인 튜링 등가 모델을 찾고 있었다. (cf Melzak (1961) 페이지 281, Shepherdson-Sturgis (1963) 페이지 218).

컴퓨터를 특징짓는 첫 번째 경향은 Hans Hermes(1954년), Rossa Petter(1958년), Hao Kaphengst(1959년)에서 비롯되었으며^[4], 두 번째 경향은 Hao Wang(1954년, 1957년)에서 비롯되었으며, 위에서 언급한 대로 Zdislaw Alexander Melzaks(1961년)와 함께 확대된 것으로 보인다.

마지막 다섯 명의 이름은 유리 마티야세비치에 의해 그 순서대로 명시되어 있다.그는 다음과 같이 후속 조치를 취합니다.

레지스터 머신(일부 저자는 카운터 머신과 같은 의미의 레지스터 머신을 사용한다)은 디오판틴 방정식을 구성하는 데 특히 적합합니다.튜링 기계처럼, 그것들은 매우 원시적인 명령들을 가지고 있고, 게다가 숫자를 다룬다." (유리 마티야세비치, 힐베르트의 10번째 문제, 이 책의 5장에 대한 해설, http://logic.pdmi.ras.ru/yumat/H10Pbook/commch_5htm.)

람베크, 멜작, 민스키, 셰퍼드슨, 스터기스는 동시에 독립적으로 같은 아이디어를 예상한 것으로 보인다.아래의 우선 순위 참고 사항을 참조하십시오.

역사는 왕씨의 모형에서 시작된다.

Wang의 모델(1954년, 1957년):포스트튜어링 머신

Wang의 작업은 Emil Post(1936)의 논문에서 이어졌고, Wang B-machine의 정의를 이끌어 냈습니다. Wang B-machine은 원자 명령이 4개밖에 없는 2개의 기호로 구성된 Post-Turing 기계 계산 모델입니다.

{ LEFT, RIGHT, PRINT, JUMP_if_marked_to_instruction_z }

이 네 명의 왕(1954년, 1957년)과 C.Y. 둘 다.Lee(1961)는 Post set {ERASE }에서 다른 명령을 추가하고 Post의 무조건 점프 {JUMP_to_instruction_z}(또는 쉽게 하기 위해 조건부 JUMP_IF_blank_to_instruction_z 또는 둘 다)를 추가했다.Lee는 이 모델을 "W-machine" 모델이라고 명명했습니다.

{ LEFT, RIGHT, PRINT, ERASE, JUMP_if_marked, [JUMP 또는 JUMP_IF_blank] }

왕은 자신의 모델이 튜링 기계 이론과 컴퓨터의 실제 세계 사이의 "화해"가 될 것이라는 희망을 표현했다.

왕씨의 작품은 영향력이 컸다.우리는 민스키(1961년)와 (1967년), 멜작(1961년), 셰퍼드슨과 스터기스(1963년)가 그를 언급했다.실제로 셰퍼드슨과 스터기스(1963)는 다음과 같이 말한다.

"...우리는 Wang이 제안한 계산의 실용적 측면과 이론적 측면 사이에서 '재조정'을 한 걸음 더 나아가려고 노력했다." (p.218)

Martin Davis는 결국 이 모델을 (2심볼) Post-Turing 기계로 발전시켰습니다.

Wang/Post-Turing 모델의 어려움:

단, 문제가 있었다: Wang 모델(7-to-turing machine의 6개의 명령)은 연속적인 프로그램 명령 흐름이 아무리 좋더라도 여전히 싱글 테이프 튜링과 같은 장치였다.멜작(1961년)과 셰퍼드슨과 스터기스(1963년) 모두 (특정 증거와 조사의 맥락에서) 이것을 관찰했다.

튜링 기계는 특정한 불투명도를 가지고 있다... 튜링 기계는 (가설적인) 동작이 느리고 보통 복잡하다.따라서 설계하기가 다소 어려워지고 시간이나 스토리지 최적화, 두 알고리즘의 효율성 비교 등의 문제를 조사하기가 더욱 어려워집니다.(Melzak (1961) 페이지 281)

"... 어렵지는 않지만... 증명은 두 가지 이유로 복잡하고 지루하다. (1) 튜링 기계는 오직 헤드만을 가지고 있기 때문에 한 자릿수의 아주 작은 단계의 연산을 해야 한다. (2) 그것은 단지 하나의 테이프로만 구성되어 있기 때문에 작업하고 싶은 숫자를 찾기 위해 약간의 노력을 들여야 한다.다른 숫자와 분리" (쉐퍼슨과 스터기스(1963년) 페이지 218).

실제로 튜링 기계의 예, 후-튜링 기계 및 부분 함수의 예에서 보듯이, 작업은 "복잡화"될 수 있다.

Minsky, Melzak-Lambek 및 Shepherdson-Sturgis 모델은 "테이프를 잘라낸다"

그렇다면 '테이프 절단'을 통해 각 테이프는 무한히 길지만 (정수를 수용할 수 있도록) 왼쪽 끝이며, 이 세 개의 테이프를 '포스트-튜링(즉 Wang-Turing)' 테이프라고 부르는 것은 어떨까요?개별 헤드는 왼쪽(감소) 및 오른쪽(증분)으로 이동합니다.어떤 의미에서 헤드는 연결된 마크의 "스택의 맨 위"를 나타냅니다.또는 Minsky(1961) 및 Hopcroft 및 Ullman(1979, 페이지 171ff)에서는 왼쪽 끝에 있는 표시를 제외하고 테이프가 항상 비어 있습니다. 헤드가 인쇄되거나 지워지는 일은 없습니다.

0에 대한 테스트와 점프가 감소하기 전에 발생하도록 지시사항을 작성할 필요가 있습니다.그렇지 않으면 머신이 "끝에서 떨어져" 또는 "끝에 부딪혀" 버프됩니다.일부 함수의 인스턴스가 생깁니다.감소하기 전에 기계는 항상 다음과 같은 질문을 해야 합니다. "테이프/카운터가 비어 있습니까?그렇다면 줄일 수 없고, 그렇지 않으면 줄일 수 있습니다.

Minsky(1961년)와 Shepherdson-Sturgis(1963년)는 테이프 상의 데이터가 Gödel 번호(또는 일부 고유하게 해독 가능한 번호)로 표현되는 경우, 몇 개의 테이프만이 튜링 등가물이 될 수 있음을 증명합니다.이 숫자는 계산이 진행됨에 따라 진화합니다.Gödel 번호를 인코딩하는 1테이프 버전에서는 카운터 머신은 (i) Gödel 번호에 상수(숫자 '2' 또는 '3')를 곱하고 (ii) 정수(숫자 '2' 또는 '3')로 나누어 나머지가 0일 경우 점프할 수 있어야 한다.Minsky(1967)는 테이프가 2개 있는 경우 이 기괴한 명령어 세트의 필요성을 { INC(r), JZDEC(r, z)} 및 편의 명령어 {CLR(r), J(r}로 완화할 수 있음을 보여줍니다.그러나 간단한 괴델라이제이션은 여전히 필요합니다.RASP 모델에 관해서, Elgot-Robinson(1964년)에서도 같은 결과가 나타난다.

멜작(1961년) 모델은 다르다: 조약돌 덩어리가 구멍으로 들어갔다 나왔다 하는

Melzak의 모형(1961)은 유의하게 다릅니다.그는 자신의 모델을 가져다가 테이프를 수직으로 뒤집어서 "땅에 뚫린 구멍"이라고 불렀고 "피블 카운터"로 채워졌다.민스키의 "증가"와 "감소"와는 달리, 멜자크는 어떠한 조약돌의 개수든 적절한 감산을 허용했다.

그는 자신의 모델에 대한 간접 주소 지정을 정의하고 (p. 288) 그 사용의 두 가지 예를 제시합니다; 그의 모델이 튜링과 동등하다는 그의 "증명" (p. 290-292)은 너무 개략적이어서 독자는 그가 간접 주소 지정을 증명에 대한 요구 사항으로 의도했는지 여부를 구별할 수 없습니다.

멜작의 모델의 유산은 람벡의 단순화와 1973년 쿡과 레코에서 그의 기억력 규약이 다시 나타난 것이다.

Lambek(1961)는 Melzak의 모델을 Minsky(1961) 모델로 원자화합니다.INC 및 DEC 테스트

람벡(1961)은 멜작의 삼원 모델을 가져다가 두 개의 단항 명령(가능한 경우 X+, X- else jump)으로 원자화했다. 이는 민스키(1961)가 생각해낸 것과 정확히 같은 두 가지다.

그러나 Minsky(1961) 모델과 마찬가지로 Lambek 모델은 기본 시퀀셜 방식으로 명령을 실행한다(X+와 X 모두 다음 명령의 식별자를 포함하며, 제로 테스트가 성공했을 경우 X도 점프 투 명령을 전송합니다.

Elgot-Robinson(1964) 및 간접 어드레싱이 없는 RASP의 문제

RASP 또는 랜덤 액세스 스토어드·프로그램·머신은, 「명령 프로그램」을 「레지스터」에 배치하는 카운터·머신으로서 개시합니다.유한상태 머신의 "명령 레지스터"와 유사하지만 독립적이며 적어도 하나의 레지스터("프로그램 카운터"(PC)로 명명됨) 및 하나 이상의 "임시" 레지스터는 현재의 명령 번호를 기록하고 동작한다.유한 상태 머신의 명령 테이블은 (i) 적절한 레지스터에서 현재 프로그램 명령을 가져오고 (ii) 프로그램 명령을 해석하고 (ii) 프로그램 명령에 의해 지정된 피연산자를 가져오고 (iv) 프로그램 명령을 실행하는 역할을 합니다.

단, 문제가 있습니다.카운터 머신 섀시에 근거해 이 컴퓨터 같은 것을 사용한다면 폰 노이만 머신은 튜링과 동등하지 않을 것이다.계산 가능한 모든 것을 계산할 수는 없습니다.본질적으로 모델은 그것의 (매우) 유한 상태 기계의 명령의 크기에 의해 제한된다.카운터 머신 기반의 RASP는 모든 원시 재귀 함수(예: 곱셈)를 계산할 수 있지만 모든 뮤 재귀 함수(예: Ackermann 함수)는 계산할 수 없습니다.

Elgot-Robinson은 RASP 모델이 프로그램 명령을 "자기 수정"할 수 있는 가능성을 조사합니다.그 아이디어는 Burks-Goldstine-von Neumann (1946-7)에 의해 제안되었고, 때때로 "계산된 고토"라고 불리기도 했다.멜작(1961)은 구체적으로 "계산된 고토"를 이름으로 언급하지만, 대신 간접적인 주소 지정을 그의 모델에 제공한다.

Calculated goto: 조건부 또는 무조건 점프 프로그램 명령에서 "goto address"를 수정하는 명령의 RASP 프로그램.

그러나 이것은 문제를 해결하지 못한다(Gödel 숫자에 의지하지 않는 한).필요한 것은 유한 상태 머신의 명령 레지스터와 TABLE의 상한을 넘어 (멀리) 프로그램 명령의 주소를 가져오는 방법입니다.

예:무제한 레지스터가 4개밖에 없는 카운터 머신은 예를 들어 두 개의 숫자(m, n)를 함께 곱하여 m과 n의 크기에 관계없이 p를 생성할 수 있습니다.또한 이를 위해 필요한 명령은 20개 미만입니다.예를 들어 { 1 : CLR ( p ) 、 2 : JZ ( m , done ) 、 outer JZ ( doice ) 。m, temp , 5: inner_loop : JZ ( m , outer_loop ) , 6: DEC ( m ) , 7: INC ( p ) , 8: J ( inner_loop ) , 9: outer_loop : DEC ( n ) , 10 J ( （ outer_loop ） }

그러나 레지스터가 4개밖에 없기 때문에 이 기계는 곱셈 알고리즘을 프로그램으로 실행할 수 있는 RASP를 구축할 수 있을 만큼 충분히 크지 않습니다.유한 상태 머신을 아무리 크게 구축해도 더 큰 프로그램(파라미터 포함)은 항상 존재합니다.따라서 정의상 Gödel 번호와 같은 무제한 인코딩 트릭을 사용하지 않는 제한 프로그램 기계는 보편적일 수 없습니다.

Minsky(1967)는 명령 {CLR(r), INC(r) 및 RPT("a")에 명령 m을 곱한 명령어 m부터 n)를 갖춘 카운터 머신(그는 "프로그램 컴퓨터 모델"이라고 부릅니다)을 조사하면서 이 문제를 암시합니다.그는 우리에게 문제를 해결하는 방법을 알려주지 않았지만, 그는 다음과 같은 사실을 알고 있습니다.

"... 프로그램 컴퓨터는 몇 개의 RPT가 남아 있는지 추적할 수 있는 방법이 있어야 하며, 이로 인해 컴퓨터의 한정된 부분에 허용되는 특정 스토리지 용량이 소진될 수 있습니다.RPT 운영에는 일반적으로 무한 레지스터가 필요합니다.또, 이러한 레지스터는, 우리가 검토했던 다른 종류의 운영과는 다른 취급을 실시할 필요가 있습니다.(p.214)

그러나 Elgot과 Robinson은 문제를 해결한다.이들은₀ P RASP를 색인화된 명령어 세트로 강화합니다.이것은 간접 어드레싱의 다소 복잡하지만, 보다 유연한 형태입니다.P'₀ 모델은 명령에서 명시적으로 지정된 "인덱스"에 "기본" 레지스터(명령에서 지정됨)의 내용을 추가하여 레지스터를 처리한다(또는 "기본"과 "인덱스"의 스왑).따라서 색인화 P'₀ 명령에는 비색인화₀ P 명령보다 파라미터가 하나 더 있습니다.

예: INC_base ( r , index ) ; 유효 주소는 [r_base] + index가 됩니다.여기서 자연수 "index"는 유한 상태 기계 명령 자체에서 파생됩니다.

하트마니스(1971년)

1971년까지 Hartmanis는 RASP 모델에서 사용하기 위해 인덱싱을 간접으로 단순화했습니다.

간접 어드레싱: 포인터 레지스터는 명령에 필요한 타깃 레지스터의 주소를 유한 상태 머신에 제공합니다.다른 방법으로 말했다:포인터 레지스터의 내용은 명령에 의해 사용되는 "target" 레지스터의 주소입니다.포인터 레지스터가 무제한인 경우 RAM과 섀시에 내장된 적절한 RASP는 Turing에 상당합니다.대상 레지스터는 지침에 지정된 소스 레지스터 또는 대상 레지스터로 사용할 수 있습니다.

유한 상태 머신은, 이 타겟 레지스터의 주소를 명시적으로 지정할 필요는 없습니다.기계의 나머지 부분에는 다음과 같이 표시됩니다.포인터 레지스터로 지시된 레지스터의 내용을 가져와 xyz를 실행해 주세요.이 포인터 레지스터(예를 들어 "N", "72" 또는 "PC" 등)를 이름으로 명시적으로 지정해야 하지만 포인터 레지스터에 실제로 어떤 번호가 포함되어 있는지 알 필요는 없습니다(약 279,431).

Cook and Rechow(1973년) RAM 설명

Cook and Rechow(1973)는 Hartmanis(1971)를 인용하여 그의 모델을 소위 랜덤 액세스 머신(RAM, 즉 간접과 하버드 아키텍처가 있는 머신)으로 단순화합니다.어떤 의미에서 우리는 Melzak(1961년)으로 돌아갔지만 Melzak의 모델보다 훨씬 단순한 모델을 가지고 있다.

우선 순위

민스키는 MIT 링컨 연구소에서 일했고 그곳에서 그의 연구를 발표했다; 그의 논문은 1960년 8월 15일 수학 연보에 발표되기 위해 접수되었지만 1961년 11월에야 출판되었다.멜작과 람벡의 작품이 접수되고 출판되기 1년 전(1961년 5월, 6월 15일, 1961년 9월 나란히 출간)에 수령되었다.(i) 둘 다 캐나다인이며 캐나다 수학 게시판에 발표되었고 (ii) 아직 동료 검토 저널에 발표되지 않았기 때문에 민스키의 연구에 대한 언급은 없었을 것이지만, (iii) 멜자크는 왕, 람벡은 멜자크를 언급함으로써 그들의 연구가 동시에 독립적으로 일어났다는 가설을 세운다.

셰퍼드슨과 스터기스에게도 거의 똑같은 일이 일어났다.그들의 논문은 Melzak과 Lambek의 작품이 접수된 지 불과 몇 달 후인 1961년 12월에 접수되었다.다시, 그들은 Minsky의 작업을 검토하는 데 거의 또는 전혀 도움이 되지 않았다.그들은 Ershov, Kaphengst 및 Peter의 논문이 "최근에" 나타났다는 것을 각주를 통해 관찰하는 데 신중했다.이것들은 훨씬 더 일찍 출판되었지만 독일 학술지에 독일어로 실렸기 때문에 접근성 문제가 제기됩니다.

셰퍼드슨과 스터기스의 마지막 논문은 1963년이 되어서야 동료 평가 저널에 실렸다.그리고 그들이 부록 A에서 공정하고 정직하게 언급했듯이, 카펑스트(1959), 에르쇼프(1958), 피터(1958)의 '시스템'은 모두 나중에 얻은 결과와 매우 유사하여 다음 집합과 구별할 수 없다.

0(예: 0 → n)을 생성한다.

n+1 → n과 같은 숫자를 증가시킨다.

"즉, 자연수를 생성하는 연산 수행"(246페이지)

숫자 복사(예: n → m)

두 숫자를 비교하거나 0까지 감소하여 "계산 과정을 변경"하다

사실, 셰퍼슨과 스터기스는 다음과 같이 결론짓는다.

"다양한 최소 시스템은 매우 유사합니다." (p.246)

출판일 순으로 카펑스트(1959년), 에르쇼프(1958년), 피터(1958년)의 작품이 1위였다.

「 」를 참조해 주세요.

참고 문헌

배경 텍스트:다음 출처 논문 목록에는 배경으로 사용될 많은 텍스트가 포함되어 있습니다.1950년대와 1960년대에 추상 기계에 관한 논문의 난립을 이끈 수학은 Frege(1879)에서 Gödel(1931)까지 50년에 걸친 원본 논문의 집합인 van Heijenoort(1967)에서 찾을 수 있다.데이비스(ed)Undecable (1965)은 Gödel (1931)에서 Gödel (1964)의 추신 (71)까지 성화를 운반한다; Alan Turing (1936-7)과 Emil Post (1936)의 원본 논문은 Undecomable에 포함되어 있다.The Undecomable에서 원본 논문의 전재물로 나타나는 처치, 로서, 그리고 클린의 수학은 기계 뒤에 있는 수학에 대한 더 깊은 이해를 추구하는 사람들에게 필수 텍스트인 클린(1952)에서 더 많이 다뤄진다.클린(1952)과 데이비스(1958)는 모두 다수의 논문에 의해 언급된다.

카운터 머신의 적절한 취급에 대해서는, Minsky(1967) 제 11 장 「디지털 컴퓨터와 유사한 모델」을 참조해 주세요.그는 카운터 머신을 「프로그램 컴퓨터」라고 부릅니다.최근 개요는 van Emde Boas(1990)에서 찾을 수 있다.민스키(1961)/람베크(1961) 모델의 최근 처리는 Boolos-Burgess-Jeffrey(2002)를 찾을 수 있다.그것들은 튜링 기계와 부분 재귀 함수의 동등성을 증명하기 위해 람베크의 "아바쿠스 모델"을 환생시키고, 추상 기계 모델(카운터, 튜링)과 수학의 두 가지에 대한 단계적인 입문을 제공한다.재귀 이론초판 Boolos-Burgess(1970)를 시작으로 이 모델은 거의 동일한 처리로 등장했다.

백서:그 논문들은 왕(1957)과 그의 튜링 기계의 극적인 단순화로 시작한다.튜링(1936), 클린(1952), 데이비스(1958)와 특히 포스트(1936)가 왕(1957)에서 인용되었다. 차례로, 왕(Wang)은 독립적으로 튜링 테이프를 카운터(counter)로 줄이기 위해 멜작(1961), 민스키(1961) 및 셰퍼드슨-스터기스(1961-3)에 의해 언급되었다.Melzak(1961)은 그의 조약돌-in-holes 카운터 머신 모델에 간접적인 방법을 제공하지만 더 이상의 치료 방법은 제공하지 않습니다.Elgot-Robinson(1964)의 연구는 RASP(컴퓨터와 같은 랜덤 액세스 저장 프로그램 머신)를 정의하고 mu-recursive 함수를 계산하기 위한 경계 카운터 머신의 고장을 최초로 조사한 것으로 보인다.이 실패—민스키(1961년) 방식으로 괴델 수를 엄격하게 사용한 경우를 제외하고-RASP 모델의 "인덱스화된" 명령(간접 주소 지정)의 정의에 따릅니다.Elgot-Robinson(1964) 등은 Hartmanis(1971)가 자체 수정 프로그램을 사용하여 RASP를 조사했다.Hartmanis(1971)는 Cook(1970)의 강의 노트를 인용하여 간접 명령 집합을 지정한다.계산 복잡도 조사에 사용하기 위해 쿡과 그의 대학원생 레코(1973)는 RAM의 정의를 제공한다(모델과 니모닉 규칙은 Melzak의 것과 유사하지만 논문에서는 참조를 제공하지 않는다).포인터 기계는 Knuth(1968, 1973년)와 Schönhage(1980년)의 분파이다.

대부분의 논문에 학부 수준을 넘어서는 수학, 특히 클린(1952)에서 우아하게 제시되었던 원시 재귀 함수와 뮤 재귀 함수는 Boolos-Burgess-Jeffrey(2002)에서 제시되었지만 그럼에도 불구하고 유용했다.

별 네 개를 제외한 모든 텍스트와 논문이 목격되었다.이 4개는 독일어로 쓰여져 있으며, 셰퍼드슨-스터기스(1963년)와 엘고트-로빈슨(1964년)에 인용된 것으로 보인다.Shepherdson-Sturgis(1963년)는 Shepherdson-Sturgis의 부록 A에서 그들의 결과에 대해 간략히 논한다.적어도 하나의 논문(Kaphengst(1959)의 용어는 컴퓨터 아키텍처에 대한 Burke-Goldstine-von Neumann(1946-7)의 분석과 관련이 있는 것으로 보인다.

작가.	연도	언급	튜링 기계	카운터 머신	들이받다	밧줄	포인터 머신	간접 주소 지정	자체 수정 프로그램
골드스틴 & 폰 노이만	1947
클린	1952
* 헤르메스	1954, 5			?
왕	1957			힌트				힌트
*피터	1958			?
데이비스	1958
* Ershov	1959			?
* 카펑스트	1959			?
멜작	1961								힌트
람베크	1961
민스키	1961
셰퍼드슨 & 스터기스	1963							힌트
엘고트 & 로빈슨	1964
데이비스-언데터블	1965
반 헤이제노르트	1967
민스키	1967				힌트			힌트
크누스	1968, 73
하트마니스	1971
쿡&레코	1973
숀헤이지	1980
판 엠데 보아스	1990
불로스 & 버지스; 불로스 & 버지스 & 제프리	1970–2002

레퍼런스

메모들

원천

• Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media, Inc. pp. 97-102. ISBN 1-57955-008-8.

외부 링크

• Weisstein, Eric W. "Register machine". MathWorld.
• Igblan - Minsky 등록기