レジスタマシン（英: Register machine）とは、数理論理学や理論計算機科学で使われる汎用計算模型の一種であり、チューリングマシンと似たような使われ方をされる。レジスタマシンのモデルは全てチューリング等価である。また、スタックマシンの対として、オペランドがレジスタである機械を指してもレジスタマシンと言う。実機ではほとんどにあてはまるのでわざわざ言わないが、仮想機械では、たとえばLua 5の仮想機械を指して使われる。レジスタマシンは、1つ以上の「レジスタ」を持つところからそのように呼ばれる。チューリングマシンでテープとヘッドが果たす役割を「複数の一意にアドレスが振られたレジスタ群」で代替する。各レジスタには1つの正の整数が格納される。レジスタマシンは非常に基本的なものから実際のコンピュータに近いものまで、次のように4階層に分類できる。正しく定義されたレジスタマシンモデルは、チューリング等価である。計算速度はモデルによって異なる。実用的な意味では、このような概念を仮想機械と呼び、ハードウェア・アーキテクチャへの依存性を削減する目的で用いられる。また、このようなマシンは教育用としても利用される。レジスタマシンは以下のような要素から成る。1950年代初期に2つの方向性が現れた。第一はコンピュータをチューリングマシンとしてモデリングする方向で、第二はチューリングマシンと同等の能力がある、よりコンピュータ的モデル（つまり、逐次命令実行と条件付き命令のあるモデル）を定義する方向である。これらの研究は2つの難しい問題の解を得る努力の過程でなされた。ひとつはエミール・ポストの提示した未解決問題（タグ問題）、もうひとつはヒルベルトの23の問題の10番目のディオファントス方程式にまつわる問題である。研究者らは、「論理」性がより少なく、「算術」性が強いチューリング等価なモデルを捜し求めていた。(cf Melzak (1961) p. 281, Shepherdson-Sturgis (1963) p. 218)。第一の方向性は、Hans Hermes (1954) や Heinz Kaphengst (1959) が創始し、第二の方向性は Hao Wang (1954, 1957) が創始し、上述のように Z. A. Melzak (1961)、Joachim Lambek (1961)、マービン・ミンスキー (1961, 1967)、John Shepherdson と H. E. Sturgis (1963) が後に続いた。後者の名前を挙げた順序は、ユーリ・マチャセビッチがリストアップした順序である。彼は、次のように述べている。Lambek、Melzak、ミンスキー、Shepherdson、Sturgis らは、ほぼ同時期に同じ考え方に到達した。歴史は、Wang のモデルから始まる。エミール・ポストの1936年の論文の基づいた Wang の研究により、Wang はBマシンの定義に到達した。これは、2種類のシンボルと4種類の命令を持つポスト-チューリング機械であった。命令は以下の通り。Wang (1954, 1957) と C.Y. Lee (1961) は、これらにポストの命令 { ERASE } とポストの無条件分岐 { JUMP_to_ instruction_z } を追加した（あるいは簡略化すれば JUMP_IF_blank_to_instruction_z という命令を追加した）。Lee はこれをWマシンモデルと称した。Wang は、彼のモデルがチューリングマシンと現実のコンピュータの架け橋となることを望んでいた。Wang の研究成果は大きな影響を及ぼし、彼の論文はミンスキー (1961, 1967）、Melzak (1961)、Shepherdson and Sturgis (1963) で引用された。特に Shepherdson and Sturgis (1963) では次のような記述がある。Matin Davis は、このモデルを（2シンボルの）ポスト-チューリング機械に発展させた。Wang/ポスト-チューリングのモデルには問題があった。すなわち、Wang のモデルはチューリング機械のような1つのテープの使用を前提としていた。Melzak (1961) と Shepherdson and Strugis (1963) ではこれについて次のように述べている。実際、チューリング機械の動作例を見れば、それが複雑であることがわかる。そこで、テープを無限長（任意の整数を格納できる）の断片に分けるという考え方が出てくる。それぞれにヘッドがあり、デクリメントでは左に移動し、インクリメントでは右に移動する。ある意味で、ヘッドの位置がマークのスタックの先端を指す。ミンスキー (1961) および Hopcroft and Ullman (1979, p. 171ff) では、テープは左端から続くマーク部分以外は常に空白状態とされた（ヘッドがそこまで移動したことがない場合でも）。つまり、記録されたマークの個数が整数値に対応する。このモデルでは、デクリメントする前にゼロかどうかを確認しないと、テープの端をつき抜けてしまう。ミンスキー (1961) と Shpepherdson-Sturgis (1963) は、テープが1つであっても、このモデルがチューリング等価であることを示した。この場合、テープ上のデータはゲーデル数（あるいは何らかの一意に符号化/複号化可能な数）とされる。この数は計算の進行に伴って変化する。ゲーデル数の符号化を伴う1つのテープのバージョンでは、カウンタマシンは (1) ゲーデル数に定数（2とか3）をかける操作ができ、(2) 定数（2や3）で割って、余りがゼロなら分岐する操作ができる必要があるとされた。ミンスキー (1967) では、これらの奇妙な命令の代わりに { INC (r), JZDEC (r, z) } で十分とされ、さらにテープ（すなわちレジスタ）が2つあれば { CLR (r), J (r) } で等価となることが示された。ただし、単純なゲーデル数化は依然として必要である。RASP モデルについての同様の研究は Elgot-Robinson (1964) でなされている。Melzak (1961) のモデルは上記とは大きく異なる。テープを縦にして、これを「地面の穴; holes in the ground」と呼び、その穴を「小石カウンタ; pebble counters」で満たすというモデルであった。ミンスキーの「インクリメント」と「デクリメント」とは異なり、Melzak のモデルでは任意個の小石の加減算が可能であった。また、間接指定も定義し（p. 288）、それを使った例も2つ示している（p. 89）。このモデルがチューリング等価であることの証明（p. 290-292）は概略的であって、間接指定がその証明に必須なのかどうかも判然としない。Melzak のモデルは Lambek が単純化し、後に Cook and Reckhow (1973) でも用語が踏襲されている。Lmbek (1961) は Melzak のモデルを2つの単項命令（ X+ 命令と、可能ならば X- し、そうでなければ分岐）に単純化した。これはミンスキー (1961) と全く同じである。RASP（ランダムアクセス・プログラム内蔵機械）は、レジスタにプログラムを構成する命令を格納するカウンタマシンとして生まれた。有限状態機械内の命令レジスタとは別に、プログラムカウンタ(PC)と現在の命令を表す数を格納する一時レジスタが必要となる。有限状態機械の命令テーブルは、(1) 実行すべき命令を適当なレジスタからフェッチし、(2)その命令を解析し、(3) その命令のオペランドで指定されたレジスタをフェッチし、(4) その命令を実行する。ただし、これをカウンタマシンに基づいて構築してもチューリング等価とはならず、計算可能なあらゆるものを計算可能とは言えない。このモデルは本質的に有限状態機械の持つ命令セットに制限されている。カウンタマシン・ベースのRASPは、任意の原始再帰関数（例えば乗算）は計算可能だが、全てのμ再帰関数（例えばアッカーマン関数）は計算できない。Elgot-Robinson はRASPモデルによる命令の自己書き換えの可能性を研究した。この考え方は古くからあり、Durks-Goldstine-von Neumann (1946-7) で提案されていた。Melzak (1961) ではこれを "comnputed goto" と称していたが、実際にはその代わりに間接指定を使っている。Computed goto とは、RASP のプログラムにおいて、条件分岐や無条件分岐の分岐先を計算によって求めるものである。しかし、これは（少なくともゲーデル数に頼らない限り）解決策とはならない。必要なのは、有限状態機械の命令レジスタや命令テーブルの限界を超えて命令をフェッチする方法であった。例として、4つの無限長レジスタを持つカウンタマシンを考える。2つの数（m, n）の乗算を行おうとすると、m や n の大きさとは関係なく、20個程度の命令が必要となる。従って、4つしかレジスタのないRASPでは、このプログラムをレジスタに格納できない。プログラムをゲーデル数化して1つのレジスタに格納できないかぎり、このRASPは万能とは言えない。ミンスキー (1967) では、{ CLR (r), INC (r), RPT （命令 m を n に対して "a" 回実行） } という命令を備えたカウンタマシンを示唆している。問題の解決策は示されていないが、彼は次のように述べている。しかし、Elgot and Robinson によって、この問題が解決された。彼らの P RASP はインデックス付き命令セットで強化されている。これは、より複雑だがより柔軟性の高い間接指定方式である。そのモデルでは、レジスタを指定する際に、ベースレジスタとインデックスとなる即値（または、ベース即値とインデックスレジスタ）が使われる。つまり、インデックス付き命令ではオペランドが1つ増えている。1971年、ユリス・ハルトマニスは、RASPモデルでの間接指定を単純化した。間接指定とは、ポインタレジスタを使って命令が実際に利用するレジスタを（番号またはアドレスで）指定することである。ポインタレジスタに制限がなければ、RAM や RASP はチューリング等価となる。間接指定されるレジスタは命令形式上の指定される位置によって、演算の入力にも出力先にもなる。つまり、有限状態機械は対象レジスタのアドレスを明示的に示す必要がない。あるポインタレジスタが指しているレジスタの内容を使って、xyz という演算をする。命令においてはポインタレジスタは明確に名前で指定しなければならないが、その内容が何であるかを知る必要はない。Cook and Reckhow (1973) は、ハルトマニス (1971) を参照し、そのモデルを単純化したランダムアクセスマシン（RAM）を提案した。Melzak (1961) に戻ったかのように見えるが、Melzak のモデルよりも単純化されている。

出典:wikipedia