レジスターマシン

数理論理学および理論計算機科学において、レジスタマシンは抽象機械の一般的なクラスであり、チューリングマシンに類似しているためチューリング完全である。テープとヘッドを使用するチューリングマシンとは異なり、レジスタマシンは複数の固有のアドレスを持つレジスタを使用して非負整数を格納する。レジスタマシンには、カウンタマシン、ポインタマシン、ランダムアクセスマシン（RAM）、ランダムアクセスプログラム格納マシン（RASP）など、複雑さが異なるいくつかのサブクラスが存在する。これらのマシンは、特に理論研究において、計算プロセスの理解に役立つ。レジスタマシンの概念は、教育目的や特定のハードウェアアーキテクチャへの依存度を低減するために、実用的な計算機科学における仮想マシンにも適用できる。

レジスタマシンは、1つまたは複数の「レジスタ」を使用することからその名が付けられました。チューリングマシンで使用されるテープとヘッドとは対照的に、このモデルは複数の固有のアドレスを持つレジスタを使用し、それぞれのレジスタには単一の非負整数が格納されます。

文献には少なくとも4つのサブクラスが存在する。複雑さの低い順に並べると以下のようになる。

• カウンタマシンは、コンピュータハードウェアの最も原始的で簡略化された理論モデルです。このマシンは間接アドレッシングを持たず、命令はハーバードアーキテクチャと同様の有限状態機械に格納されます。
• ポインタマシンは、カウンタマシンとRAMモデルを組み合わせたもので、どちらのモデルよりも一般的ではなく、より抽象的です。命令は、ハーバードアーキテクチャと同様に、有限状態機械で記述されます。
• ランダムアクセスマシン（RAM）とは、間接アドレッシング方式を採用したカウンタマシンであり、通常は拡張命令セットを備えている。命令は、ハーバードアーキテクチャと同様の有限状態機械に実装されている。
• ランダムアクセス・プログラム内蔵マシンモデル（RASP）は、レジスタに命令が格納されたRAMであり、汎用チューリングマシンに類似しているため、フォン・ノイマン・アーキテクチャの一例と言えます。しかし、コンピュータとは異なり、このモデルは実質的に無限のレジスタ（および、使用される場合はアキュムレータなどの実質的に無限の特殊レジスタ）で理想化されています。とはいえ、現代のコンピュータと比較すると、命令セットの数と複雑さは依然として削減されています。

適切に定義されたレジスタマシンモデルはすべてチューリング完全である。計算速度はモデルの詳細に大きく依存する。

実際のコンピュータサイエンスでは、基盤となるマシンアーキテクチャへの依存度を減らすために、仮想マシンと呼ばれる関連概念が時折用いられます。これらの仮想マシンは教育現場でも利用されています。教科書では、「レジスタマシン」という用語が仮想マシンを説明する際に互換的に使用されることがあります。^{[ 1 ]}

レジスタマシンは以下で構成されます。

1. ラベル付きの離散的なレジスタの無制限の数、範囲（容量）に制限なし：有限（または一部のモデルでは無限）のレジスタの集合$\displaystyle r_{0}\ldots r_{n}}$それぞれ無限の規模を持つとみなされ、それぞれが単一の非負整数 (0, 1, 2, ...) を保持します。^{[注 1 ]}レジスタは独自の演算を実行する場合もあれば、演算を実行する 1 つ以上の特別なレジスタ (たとえば「アキュムレータ」および/または「アドレス レジスタ」) が存在する場合もあります。ランダム アクセス マシンも参照してください。
2. タリーカウンターまたはマーク：^{[注2 ]}モデルに適した、区別できない単一のオブジェクトまたはマーク。最も簡略化されたカウンタマシンモデルでは、各算術演算ごとに、1 つのオブジェクト/マークのみがその位置/テープに追加または削除されます。一部のカウンタマシンモデル（例：メルザック^{[ 2 ]} 、ミンスキー^{[ 3 ]}）およびほとんどの RAM および RASP モデルでは、「加算」と通常は「減算」で、1 つの操作で複数のオブジェクト/マークを追加または削除できます。場合によっては、「乗算」および/または「除算」でも追加または削除できます。一部のモデルには、「コピー」（または代替として「移動」、「ロード」、「ストア」）などの制御操作があり、オブジェクト/マークの「塊」を 1 つのアクションでレジスタからレジスタに移動します。
3. 限られた命令セット：命令は算術と制御の2つのクラスに分けられる傾向がある。命令はこれら2つのクラスから抽出され、「命令セット」を形成する。命令セットは、モデルがチューリング等価であること（任意の部分再帰関数を計算できること）を可能にするものでなければならない。
   1. 算術: 算術命令は、すべてのレジスタまたはアキュムレータなどの特定のレジスタに対して動作できます。通常、次のセットから選択されますが、例外もあります。カウンタマシン: { インクリメント (r)、デクリメント (r)、クリア ゼロ (r) } 縮小 RAM、RASP: { インクリメント (r)、デクリメント (r)、クリア ゼロ (r)、即値定数 k のロード、加算 ($\displaystyle r_{1},r_{2}}$) 適切な減算 ($\displaystyle r_{1},r_{2}}$)、アキュムレータをインクリメント、アキュムレータをデクリメント、アキュムレータをクリア、レジスタの内容を加算${\displaystyle r}$アキュムレータへ、レジスタの内容を正しく減算する${\displaystyle r}$アキュムレータから} 拡張RAM、RASP: 削減された命令すべてに加え、次の命令も含​​まれます: { 乗算、除算、さまざまなブールビット演算(左シフト、ビットテストなど) }。
   2. コントロール: カウンターマシンモデル: オプションで含める { コピー ($\displaystyle r_{1},r_{2}}$) }. RAM および RASP モデル: ほとんどのモデルには { コピー ($\displaystyle r_{1},r_{2}}$) }、または { ロードアキュムレータ${\displaystyle r}$、蓄積器を${\displaystyle r}$、即値定数でアキュムレータをロードします。すべてのモデル: レジスタのテストの後に、{ ゼロの場合ジャンプ、ゼロでない場合ジャンプ (つまり、正の場合ジャンプ)、等しい場合ジャンプ、等しくない場合ジャンプ } のような条件付き「ジャンプ」(分岐、goto) を少なくとも 1 つ含めます。すべてのモデルには、オプションで { 無条件プログラムジャンプ (goto) } を含めることができます。
   3. レジスタアドレッシング方式：
      • カウンタマシン：間接アドレッシングなし、高度にアトマイズされたモデルでは即値オペランドが可能
      • RAMとRASP：間接アドレッシングが可能、即値オペランドが一般的
   4. 入出力：全モデルでオプション
4. 状態レジスタ：前述のレジスタとは異なる特別な命令レジスタ（IR）は、現在実行される命令とその命令テーブル内のアドレスを格納します。このレジスタは、関連するテーブルとともに、有限状態機械内に配置されます。IRは、すべてのモデルにおいてアクセスできません。RAMおよびRASPの場合、レジスタの「アドレス」を決定するために、モデルは、（i）テーブルで指定され、IRに一時的に格納されるアドレス（直接アドレッシング用）、または（ii）IR内の命令で指定されるレジスタの内容（間接アドレッシング用）のいずれかを選択できます。IRは、RASP（または従来のコンピュータ）の「プログラムカウンタ」（PC）ではないことに注意することが重要です。PCは、アキュムレータに似た別のレジスタですが、RASPの現在のレジスタベースの命令番号を保持するために特別に予約されています。したがって、RASPは2つの「命令/プログラム」レジスタを備えています。(i) IR（有限状態機械の命令レジスタ）、および(ii) レジスタに格納されたプログラム用のPC（プログラムカウンタ）。さらに、PCとは別に、RASPは「プログラム命令レジスタ」（「PIR」、「IR」、「PR」など様々な名称で呼ばれる）専用のレジスタを別途設ける場合もあります。
5. ラベル付き命令のリスト（通常は順序通り）：命令の有限リスト$\displaystyle I_{1}\ldots I_{m}}$カウンタマシン、ランダムアクセスマシン（RAM）、ポインタマシンの場合、命令ストアは有限状態マシンの「TABLE」にあるため、これらのモデルはハーバードアーキテクチャの例です。RASPの場合、プログラムストアはレジスタにあるため、これはフォンノイマンアーキテクチャの例です。ランダムアクセスマシンとランダムアクセスストアードプログラムマシンも参照してください。命令は通常、コンピュータプログラムのように順番にリストされますが、ジャンプが成功した場合は例外です。この場合、デフォルトのシーケンスは数値順に続きます。例外はアバカス^{[ 4 ] [ 3 ]}カウンタマシンモデルで、すべての命令に少なくとも1つの「next」命令識別子「z」があり、条件分岐には2つあります。
   • また、そろばんモデルは、JZ と DEC の 2 つの命令を組み合わせていることにも注目してください。例: { INC ( r, z ), JZDEC ( r, z _true , z _false ) }。

条件式「IF r=0 THEN z _true ELSE z _false」の詳細については、マッカーシー形式論を参照してください^{[ 5 ]。}

1950年代初頭には2つの傾向が現れた。1つ目は、コンピュータをチューリングマシンとして特徴づけることである。2つ目は、チューリングマシンの能力を持つコンピュータのようなモデル、すなわち、逐次的な命令シーケンスと条件分岐を持つモデルを定義すること、いわゆるチューリング等価性である。この研究の必要性は、2つの「難問」の文脈で行われた。1つはエミール・ポスト^{[ 6 ]}が提起した解決不可能な単語問題、すなわち「タグ」問題であり、もう1つはヒルベルト問題という非常に「難問」、すなわちディオファントス方程式に関する第10問である。研究者たちは、より「論理的」ではなく「算術的」な性質を持つチューリング等価モデルを探求していた。^{[ 2 ] : 281 [ 7 ] : 218}

コンピュータの特性を明らかにするための第一歩は^、ハンス・ヘルメス（1954年）[8]、^{ローザ・ペーター（} 1958年）^{[ 9 ] 、}ハインツ・カフェングスト（1959年）^{[ 10 ]}によって始まり、第二歩はハオ・ワン（1954年、^{[ 11 ]} 1957年^{[ 12 ]}）によって、そして前述のように、ズジスワフ・アレクサンダー・メルザック（1961年）^{[ 2 ]} 、ヨアヒム・ランベック（1961年）^{[ 4 ]}、マービン・ミンスキー（1961年、^{[ 3 ]} 1967年^{[ 13 ]}）によってさらに進められました。

最後の5人の名前は、ユーリ・マティヤセヴィチによってその順序で明示的にリストアップされている。彼は続けて次のように述べている。

「レジスタマシン（一部の著者は「レジスタマシン」を「カウンタマシン」と同義語として使用しています）は、ディオファントス方程式の構築に特に適しています。チューリングマシンと同様に、非常に原始的な命令を持ち、さらに数値を扱います。」^{[ 14 ]}

ランベック、メルザック、ミンスキー、シェパードソン、スタージスは、それぞれ独立して同時期に同じアイデアを発見した。先行研究に関する注記は下記を参照のこと。

その歴史は王氏のモデルから始まる。

{ LEFT、RIGHT、PRINT、JUMP_if_marked_to_instruction_z }

{ 左、右、印刷、消去、マークされている場合はジャンプ、[場合によってはジャンプまたは空白の場合はジャンプ] }

ミンスキーはMITリンカーン研究所で研究を行い、そこで論文を発表しました。彼の論文は1960年8月15日にAnnals of Mathematicsに掲載するために受理されましたが、1961年11月まで出版されませんでした。 ^{[ 3 ]受理はメルザック[ 2 ]}とランベック^{[ 4 ]}の研究が受理され出版される1年前でした（それぞれ1961年5月と6月15日に受理され、1961年9月に並んで出版されました）。(i) 両者ともカナダ人で、Canadian Mathematical Bulletinに掲載されたこと、(ii) ミンスキーの研究はまだ査読付きジャーナルに掲載されていなかったため、どちらもミンスキーの研究を参照することはなかったこと、(iii) メルザックがワンを参照し、ランベックがメルザックを参照していることから、彼らの研究は同時期に独立して行われたと推測されます。

シェパードソンとスタージスにもほぼ同じことが起こった。^{[ 21 ]}彼らの論文は1961年12月に受理されたが、これはメルザックとランベックの論文が受理されてからわずか数か月後のことだった。ここでも、彼らはミンスキーの論文をレビューする機会はほとんど（せいぜい1か月）もなかった。彼らは脚注で、エルショフ^{[ 22 ]} 、カペンスト^{[ 10 ]}、ペーター^{[ 9 ]}の論文が「最近発表された」^{[ 21 ]と注意深く記している。219}これらはかなり前に発表されたものだが、ドイツ語でドイツ語の雑誌に掲載されたため、アクセスの問題が生じる^。

シェパードソンとスタージスの最終論文は、1963年まで査読付きジャーナルには掲載されなかった。^{[ 7 ]}また、彼らが付録Aで指摘しているように、カペンスト（1959年）^{[ 10 ]} 、エルショフ（1958年）^{[ 22 ]} 、ペーター（1958年）^{[ 9 ]}の「システム」はすべて、後に得られた結果と非常によく似ており、以下のセットと区別がつかない。

0を生成する、つまり0 → n

数値をインクリメントする（例：n+1 → n）

「すなわち、自然数を生成する演算を実行すること」^{[ 7 ]： 246}

数値をコピーする（例：n → m）

2つの数値を比較するか、0になるまでデクリメントすることで、「計算の進行を変更する」

実際、シェパーソンとスタージスは次のように結論付けている。

「様々な最小システムは非常によく似ている」^{[ 7 ]： 246}

出版日の順では、カペンスト（1959年） ^{[ 10 ]}、エルショフ（1958年）^{[ 22 ] 、ペーテル（1958年） [ 9 ]}の著作が最初である。

背景テキスト:以下の文献目録には、背景として使用されるテキストが多数含まれています。1950 年代と 1960 年代に抽象機械に関する論文が急増した原因となった数学は、van Heijenoort (1967) ^{[ 23 ]に見られます。これは、Frege (1879) [ 24 ]}からGödel (1931) ^{[ 25} ]までの 50 年間にわたるオリジナルの論文を集めたものです。Davis (編) The Undecidable (1965) ^{[ 26 ]}は、Gödel (1931) ^{[ 25 ]から Gödel (1964) の追記まで、}その流れを受け継いでいます。^{[ 27 ] : 71}アラン・チューリング(1936 ^{[ 28 ]} –1937) とエミール・ポスト (1936) ^{[ 6 ]}の原著論文はThe Undecidableに収録されている。The Undecidableに原著論文の再録として掲載されているチャーチ、ロッサー、クリーネの数学は、クリーネ (1952) ^{[ 29 ]}でさらに発展しており、機械の背後にある数学をより深く理解しようとする者にとって必読のテキストとなっている。クリーネ (1952) ^{[ 29 ]}とデイビス (1958) ^{[ 30 ]}の両方が、多くの論文で参照されている。

カウンタマシンの優れた解説については、ミンスキー (1967) の第 11 章「デジタル コンピュータに類似したモデル」を参照してください。彼はカウンタマシンを「プログラム コンピュータ」と呼んでいます。^{[ 13 ]}最近の概説は、van Emde Boas (1990) にあります。^{[ 31 ]}ミンスキー (1961) ^{[ 3 ]} / ランベック (1961) ^{[ 4 ]}モデルの最近の解説は、Boolos–Burgess–Jeffrey (2002) にあります。^{[ 32 ]彼らは、チューリング マシンと部分再帰関数の等価性を示すためにランベックの「そろばんモデル」を復活させ、抽象マシン モデル (カウンタとチューリング) と再帰理論の数学の両方について大学院レベルの入門を提供しています。Boolos–Burgess (1970) [ 33 ]}の初版から、このモデルはほぼ同じ解説で登場しました。

論文: 論文は、Wang (1957) ^{[ 12 ]}によるチューリングマシンの劇的な単純化から始まります。Wang (1957) ^{[ 12 ]では、Turing (1936) [ 28 ]}、Kleene ( 1952) ^{[ 29 ]}、Davis (1958) ^{[ 30 ]}、特に Post (1936) ^{[ 6 ]}が引用されています。一方、Wang は Melzak (1961) [ 2 ]、Minsky (1961) [ 3 ]、Shepherdson–Sturgis (1961–1963) [ 21 ] [ 7 ] によって参照されており、^{彼らはそれぞれ}独立^{してチューリング}テープ^{を「カウンタ」に還元}しています。Melzak (1961) ^{[ 2 ]は}、間接性を備えたペブルインホールカウンタマシンモデルを提供していますが、それ以上の処理は行っていません。 Elgot–Robinson (1964) ^{[ 17 ]}の研究は、コンピュータのようなランダムアクセス・プログラム内蔵マシンである RASP を定義し、制限付きカウンタマシンがμ 再帰関数を計算できないことを初めて調査したようです。この失敗は、 Minsky (1961) ^{[ 3 ]}のやり方でゲーデル数を厳しく使用しない限り、RASP モデルに「インデックス付き」命令 (つまり間接アドレッシング) を定義することにつながります。Elgot–Robinson (1964) ^{[ 17 ]}と、特に Hartmanis (1971) ^{[ 20 ]は、自己修正プログラムを備えた RASP を調査しています。Hartmanis (1971) [ 20 ]}は、Cook (1970 ) の講義ノートを引用して、間接アドレッシングを備えた命令セットを指定しています。^{[ 34 ]}計算複雑性の研究で使用するために、クックと彼の大学院生レックハウ (1973) ^{[ 18 ]}は RAM の定義を提供しています (彼らのモデルとニーモニックの慣習はメルザックのものと似ていますが、論文ではメルザックへの言及はありません)。ポインターマシンは、クヌース (1968、^{[ 35 ]} 1973) と独立にシェーンハーゲ (1980) の派生です。^{[ 36 ]}

論文の大部分は学部レベルを超える数学を含んでおり、特にクリーネ（1952）^{[ 29 ]}で優雅に提示された原始再帰関数とμ再帰関数、そしてブーロス–バージェス–ジェフリー（2002） ^{[ 32 ]}ではそれほど深くはないものの有用な内容となっている。

星印の付いた 4 つを除くすべてのテキストと論文は、目撃されています。これら 4 つはドイツ語で書かれており、Shepherdson–Sturgis (1963) ^{[ 7 ]}および Elgot–Robinson (1964) ^{[ 17 ]}の参考文献として掲載されています。Shepherdson –Sturgis (1963) ^{[ 7 ]}は、Shepherdson–Sturgis の付録 A で、彼らの結果について簡単に説明しています。少なくとも 1 つの論文 (Kaphengst (1959) ^{[ 10 ]の用語は、Burke–Goldstine–von Neumann (1946–1947) [ 19 ]}によるコンピュータ アーキテクチャの分析を彷彿とさせます。

• ウルフラム、スティーブン（ 2002）。『新しい科学』ウルフラム・メディア社、 97-102ページ。ISBN  1-57955-008-8。

• ワイスタイン、エリック W. 「レジスターマシン」。マスワールド。
• Igblan - Minsky Register Machines (2007年3月12日アーカイブ)