レジスタマシン

レジスタマシン（英: Register machine）とは、数理論理学や理論計算機科学で使われる汎用計算模型の一種であり、チューリングマシンと似たような使われ方をされる。レジスタマシンのモデルは全てチューリング等価である。

また、スタックマシンの対として、オペランドがレジスタである機械を指してもレジスタマシンと言う。実機ではほとんどにあてはまるのでわざわざ言わないが、仮想機械では、たとえばLua 5の仮想機械を指して使われる。

概要

レジスタマシンは、1つ以上の「レジスタ」を持つところからそのように呼ばれる。チューリングマシンでテープとヘッドが果たす役割を「複数の一意にアドレスが振られたレジスタ群」で代替する。各レジスタには1つの正の整数が格納される。

レジスタマシンは非常に基本的なものから実際のコンピュータに近いものまで、次のように4階層に分類できる。

カウンタマシン

最も基本的なモデル。間接アドレシングができない。命令列は有限状態機械で構成される。

ポインタマシン

カウンタマシンとRAMモデルの中間。それらより一般的ではないが、より抽象的である。命令列は有限状態機械で構成される。

ランダムアクセスマシン（RAM）

カウンタマシンに間接アドレシングを付加し、一般に命令セットが強化されている。命令列は有限状態機械で構成される。

ランダムアクセス・プログラム内蔵機械モデル（RASP）

RAM で、レジスタ内に命令を格納できる。万能チューリングマシンに対比され、ノイマン型アーキテクチャの一例でもある。ただし、モデルとして理想化されているため、事実上無限個のレジスタを持つ。また、命令セットもRISCに比較してもさらに少ない。

正しく定義されたレジスタマシンモデルは、チューリング等価である。計算速度はモデルによって異なる。

実用的な意味では、このような概念を仮想機械と呼び、ハードウェア・アーキテクチャへの依存性を削減する目的で用いられる。また、このようなマシンは教育用としても利用される。

形式的定義

標準的用語は存在しない。書籍によって個々に用語やシンボルを定義している。多くの場合、「レジスタ転送」的な記号を使うが、構文定義はその都度行う必要がある。

レジスタマシンは以下のような要素から成る。

1. 有限個数でかつ無限長のレジスタ: 有限個（またはモデルによっては無限個）のレジスタ群 r₀, ..., r_n があり、個々のレジスタは無限長で1つの非負整数（0, 1, 2, ...）を格納する。レジスタ同士の算術ができるか、一部のレジスタがアキュムレータとして算術に使われたり、アドレスレジスタとして使われたりする。
2. タリーカウンタ/マーク: モデルにおける離散的識別可能オブジェクト/マーク。最も単純なカウンタマシンでは、1回の算術演算で1つのオブジェクト/マークが追加または削除される（つまり、インクリメントまたはデクリメント）。Melzak (1961) や Minsky (1961) のカウンタマシンや RAM または RASP では、1回の加算や減算で1つ以上のオブジェクト/マークの追加・削除が行われる。モデルによっては、コピー制御命令によってオブジェクト/マークの「かたまり」をレジスタからレジスタに1回の操作で移動させることができる。
3. （非常に）制限された命令セット: 命令は算術演算命令と制御命令の2種類に分類される。「命令セット」はそのモデルがチューリング等価となるよう選択される（つまり、任意の計算可能関数を計算可能である）。
   1. 算術演算命令: 全レジスタを対象に実行できる場合とアキュムレータだけを対象に実行できる場合がある。次のようなセットから選択される（例外もある）。
      • カウンタマシン: {インクリメント (r)、デクリメント (r)、ゼロクリア (r)}
      • 最小構成 RAM、RASP: {インクリメント (r)、デクリメント (r)、ゼロクリア (r)、即値ロード k、加算 (r₁,r₂)、減算 (r₁,r₂)、インクリメント アキュムレータ、デクリメント アキュムレータ、クリア アキュムレータ、レジスタ r の内容をアキュムレータに加算、レジスタ r の内容をアキュムレータから減算、}
      • 最大構成 RAM、RASP: 上記に加えて {乗算、除算、各種ビット論理演算（左シフト、ビットテストなど）}
   2. 制御命令:
      • カウンタマシン: オプションで {コピー (r₁,r₂)}
      • RAM、RASP: {コピー (r₁,r₂)} または {r からアキュムレータへのロード、アキュムレータから r へのストア、即値のアキュムレータへのロード} のどちらかが必須
      • 全モデル: レジスタ内容のテストを伴う条件付き分岐命令が少なくとも1つ必要。例えば {ゼロのとき分岐、ゼロでないとき分岐、等しいとき分岐、等しくないとき分岐}
      • 全モデルでオプション: { 無条件分岐（GOTO） }
   3. レジスタ指定方法:
      • カウンタマシン: 間接指定（レジスタの内容が別のレジスタの番号を指定）はなく、オペランドで直接指定する。
      • RAM、RASP: 間接指定可能で、オペランドでの直接指定もある。
   4. 入出力: 全モデルでオプション
4. 状態レジスタ: 上述のレジスタ群とは別に、命令レジスタ(IR)に現在の命令と命令テーブル上のその命令のアドレスを格納する。このレジスタと命令テーブルは有限状態機械内にある。
   • IR はモデル上はアクセスできない。RAM や RASP でレジスタのアドレス指定をする場合、命令テーブルまたはIRの内容で直接指定されるか、IR内の命令で指定されるレジスタの内容で間接指定される。
   • IR はいわゆる「プログラムカウンタ」(PC)ではない。RASP には PC もあり、これはアキュムレータのようなレジスタであり、現在のレジスタ上の命令を指す。RASP はさらに第三のレジスタ「プログラム命令レジスタ」も持つ場合がある。
5. ラベル付き命令のリスト、一般に逐次的順序: 有限な命令列 I₁, ..., I_m。カウンタマシン、RAM、ポインタマシンの場合、命令は有限状態機械内のテーブルに格納される。したがって、これらは一種のハーバード・アーキテクチャであり、命令とデータが明確に分離されている。RASP の場合、プログラムはレジスタに格納される。したがって、RASP はノイマン型アーキテクチャの一種である。一般的なプログラムのように命令は逐次的順序で置かれ、分岐が発生する場合以外は命令は逐次的に実行される。例外として、Lambek (1961) や Minsky (1961) の abacus カウンタマシンモデルがある。この場合、各命令には少なくとも1つの次の命令を指す識別子 "z" があり、条件付き分岐命令ではそれが2つになる。
   • abacus モデルにはデクリメントと条件付き分岐を1つに組み合わせた命令（JZ + DEC = JZDEC）がある。例えば、{ INC ( r, z ), JZDEC ( r, z_true, z_false ) } のようになる。

レジスタマシンモデルの歴史的発展

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) が後に続いた。

後者の名前を挙げた順序は、ユーリ・マチャセビッチがリストアップした順序である。彼は、次のように述べている。

「レジスタマシンは特にディオファントス方程式の構築に適している。チューリングマシンのように、それらは非常に基本的な命令しか持たず、さらに数を扱う」(Yuri Matiyasevich (1993), Hilbert's Tenth Problem, commentary to Chapter 5 of the book, at http://logic.pdmi.ras.ru/~yumat/H10Pbook/commch_5.htm )

Lambek、Melzak、ミンスキー、Shepherdson、Sturgis らは、ほぼ同時期に同じ考え方に到達した。

歴史は、Wang のモデルから始まる。

(1954, 1957) Wang のモデル: ポスト-チューリング機械

エミール・ポストの1936年の論文の基づいた Wang の研究により、Wang はBマシンの定義に到達した。これは、2種類のシンボルと4種類の命令を持つポスト-チューリング機械であった。命令は以下の通り。

{ LEFT, RIGHT, PRINT, JUMP_if_marked_to_instruction_z }

Wang (1954, 1957) と C.Y. Lee (1961) は、これらにポストの命令 { ERASE } とポストの無条件分岐 { JUMP_to_ instruction_z } を追加した（あるいは簡略化すれば JUMP_IF_blank_to_instruction_z という命令を追加した）。Lee はこれをWマシンモデルと称した。

{ LEFT, RIGHT, PRINT, ERASE, JUMP_if_marked, [maybe JUMP or JUMP_IF_blank] }

Wang は、彼のモデルがチューリングマシンと現実のコンピュータの架け橋となることを望んでいた。

Wang の研究成果は大きな影響を及ぼし、彼の論文はミンスキー (1961, 1967）、Melzak (1961)、Shepherdson and Sturgis (1963) で引用された。特に Shepherdson and Sturgis (1963) では次のような記述がある。

「…我々は、Wang が示唆した計算の実用面と論理面の和解をさらに推し進めようとした」(p. 218)

Matin Davis は、このモデルを（2シンボルの）ポスト-チューリング機械に発展させた。

Wang/ポスト-チューリングのモデルには問題があった。すなわち、Wang のモデルはチューリング機械のような1つのテープの使用を前提としていた。Melzak (1961) と Shepherdson and Strugis (1963) ではこれについて次のように述べている。

「…チューリング機械にはある曖昧さが存在する…チューリング機械は手順が多く複雑である。このため設計が困難で、記憶領域や時間の最適化を検討するのも難しく、2つのアルゴリズムの効率を比較するのも困難である」（Melzak (1961) p. 281）

「…困難ではないが…次の2つの理由から、証明過程が複雑で、それを追うのが退屈な作業となる。(1) チューリング機械にはヘッドが1つしかないため、計算を一桁ずつの操作を積み重ねて構成しなければならない。(2) テープも1つしかないため、テープ上のある部分を保持しようとすると非常に複雑な操作が必要になる」（Shepherdson and Sturgis (1963) p. 218)

実際、チューリング機械の動作例を見れば、それが複雑であることがわかる。

ミンスキー、Melzak-Lambek、Shepherdson-Sturgis モデルによるテープの切り刻み

そこで、テープを無限長（任意の整数を格納できる）の断片に分けるという考え方が出てくる。それぞれにヘッドがあり、デクリメントでは左に移動し、インクリメントでは右に移動する。ある意味で、ヘッドの位置がマークのスタックの先端を指す。ミンスキー (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) でなされている。

(1961) Melzak のモデル: 穴を出入りする小石の集まり

Melzak (1961) のモデルは上記とは大きく異なる。テープを縦にして、これを「地面の穴; holes in the ground」と呼び、その穴を「小石カウンタ; pebble counters」で満たすというモデルであった。ミンスキーの「インクリメント」と「デクリメント」とは異なり、Melzak のモデルでは任意個の小石の加減算が可能であった。

また、間接指定も定義し（p. 288）、それを使った例も2つ示している（p. 89）。このモデルがチューリング等価であることの証明（p. 290-292）は概略的であって、間接指定がその証明に必須なのかどうかも判然としない。

Melzak のモデルは Lambek が単純化し、後に Cook and Reckhow (1973) でも用語が踏襲されている。

Lambek (1961) は Melzak のモデルをミンスキー (1961) のモデルに単純化する: テスト付きのインクリメント/デクリメント

Lmbek (1961) は Melzak のモデルを2つの単項命令（ X+ 命令と、可能ならば X- し、そうでなければ分岐）に単純化した。これはミンスキー (1961) と全く同じである。

Elgot-Robinson (1964) と間接指定のないRASPの問題

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" 回実行） } という命令を備えたカウンタマシンを示唆している。問題の解決策は示されていないが、彼は次のように述べている。

「…プログラムカウンタは RPT があと何回命令を実行しなければならないかを記憶する必要があり、これが有限なコンピュータの限られた記憶装置を消費するかもしれない。RPT 命令自体は有限個のレジスタしか必要としないが、一般に他の命令とは扱い方を変える必要があるだろう」（p. 214）

しかし、Elgot and Robinson によって、この問題が解決された。彼らの P₀ RASP はインデックス付き命令セットで強化されている。これは、より複雑だがより柔軟性の高い間接指定方式である。そのモデルでは、レジスタを指定する際に、ベースレジスタとインデックスとなる即値（または、ベース即値とインデックスレジスタ）が使われる。つまり、インデックス付き命令ではオペランドが1つ増えている。

ハルトマニス (1971)

1971年、ユリス・ハルトマニスは、RASPモデルでの間接指定を単純化した。間接指定とは、ポインタレジスタを使って命令が実際に利用するレジスタを（番号またはアドレスで）指定することである。ポインタレジスタに制限がなければ、RAM や RASP はチューリング等価となる。間接指定されるレジスタは命令形式上の指定される位置によって、演算の入力にも出力先にもなる。

つまり、有限状態機械は対象レジスタのアドレスを明示的に示す必要がない。あるポインタレジスタが指しているレジスタの内容を使って、xyz という演算をする。命令においてはポインタレジスタは明確に名前で指定しなければならないが、その内容が何であるかを知る必要はない。

Cook and Reckhow (1973) による RAM

Cook and Reckhow (1973) は、ハルトマニス (1971) を参照し、そのモデルを単純化したランダムアクセスマシン（RAM）を提案した。Melzak (1961) に戻ったかのように見えるが、Melzak のモデルよりも単純化されている。

関連項目

• カウンタマシン
• ポインタマシン
• ランダムアクセスマシン (RAM)
• ランダムアクセス・プログラム内蔵機械 (RASP)
• チューリングマシン
• アルゴリズム
• 停止性問題
• ビジービーバー

参考文献

• George Boolos, John P. Burgess, Richard Jeffrey (2002), Computability and Logic: Fourth Edition, Cambridge University Press, Cambridge, England. The original Boolos-Jeffrey text has been extensively revised by Burgess: more advanced than an introductory textbook. "Abacus machine" model is extensively developed in Chapter 5 Abacus Computability; it is one of three models extensively treated and compared -- the Turing machine (still in Boolos' original 4-tuple form) and recursion the other two.
• Arthur Burks, Herman Goldstine, John von Neumann (1946), Preliminary discussion of the logical design of an electronic computing instrument, reprinted pp. 92ff in Gordon Bell and Allen Newell (1971), Computer Structures: Readings and Examples, mcGraw-Hill Book Company, New York. ISBN 0070043574 .
• Stephen A. Cook and Robert A. Reckhow (1972), Time-bounded random access machines, Journal of Computer Systems Science 7 (1973), 354-375.
• Martin Davis (1958), Computability & Unsolvability, McGraw-Hill Book Company, Inc. New York.
• Calvin Elgot and Abraham Robinson (1964), Random-Access Stored-Program Machines, an Approach to Programming Languages, Journal of the Association for Computing Machinery, Vol. 11, No. 4 (October, 1964), pp. 365-399.
• J. Hartmanis (1971), "Computational Complexity of Random Access Stored Program Machines," Mathematical Systems Theory 5, 3 (1971) pp. 232-245.
• John Hopcroft, Jeffrey Ullman (1979). Introduction to Automata Theory, Languages and Computation, 1st ed., Reading Mass: Addison-Wesley. ISBN 0-201-02988-X. A difficult book centered around the issues of machine-interpretation of "languages", NP-Completeness, etc.
• Stephen Kleene (1952), Introduction to Metamathematics, North-Holland Publishing Company, Amsterdam, Netherlands. ISBN 0-7204-2103-9.
• Donald Knuth (1968), The Art of Computer Programming, Second Edition 1973, Addison-Wesley, Reading, Massachusetts. Cf pages 462-463 where he defines "a new kind of abstract machine or 'automaton' which deals with linked structures."
• Joachim Lambek （1961, 受理は1961年6月15日）, How to Program an Infinite Abacus, Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 295-302. In his Appendix II, Lambek proposes a "formal definition of 'program'. He references Melzak (1961) and Kleene (1952) Introduction to Metamathematics.
• Z. A. Melzak （1961, 受理は1961年5月15日）, An informal Arthmetical Approach to Computability and Computation, Canadian Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 279-293. Melzak offers no references but acknowledges "the benefit of conversations with Drs. R. Hamming, D. McIlroy and V. Vyssots of the Bell telephone Laborators and with Dr. H. Wang of Oxford University."
• Marvin Minsky (1961年、受理は1960年8月15日). “Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines”. Annals of Math 74: 437–455. 
• Marvin Minsky (1967年). Computation: Finite and Infinite Machines, 1st ed., Englewood Cliffs, N. J.: Prentice-Hall, Inc..  In particular see chapter 11: Models Similar to Digital Computers and chapter 14: Very Simple Bases for Computability. In the former chapter he defines "Program machines" and in the later chapter he discusses "Universal Program machines with Two Registers" and "...with one register", etc.
• John C. Shepherdson and H. E. Sturgis (1961) received December 1961 Computability of Recursive Functions, Journal of the Association of Computing Machinery (JACM) 10:217-255, 1963. An extremely valuable reference paper. In their Appendix A the authors cite 4 others with reference to "Minimality of Instructions Used in 4.1: Comparison with Similar Systems".

• Kaphengst, Heinz, Eine Abstrakte programmgesteuerte Rechenmaschine', Zeitschrift fur mathematische Logik und Grundlagen der Mathematik:5 (1959), 366-379.
• Ershov, A. P. On operator algorithms, (Russian) Dok. Akad. Nauk 122 (1958), 967-970. English translation, Automat. Express 1 (1959), 20-23.
• Péter, Rózsa Graphschemata und rekursive Funktionen, Dialectica 12 (1958), 373.
• Hermes, Hans Die Universalität programmgesteuerter Rechenmaschinen. Math.-Phys. Semesterberichte (Göttingen) 4 (1954), 42-53.

• Arnold Schönhage (1980), Storage Modification Machines, Society for Industrial and Applied Mathematics, SIAM J. Comput. Vol. 9, No. 3, August 1980. Wherein Schōnhage shows the equivalence of his SMM with the "successor RAM" (Random Access Machine), etc. resp. Storage Modification Machines, in Theoretical Computer Science (1979), pp. 36-37
• Peter van Emde Boas, Machine Models and Simulations pp.3-66, appearing in:

Jan Van Leeuwen, ed. "Handbbook of Theoretical Computer Science. Volumne A: Algorithms and Complexity, The MIT PRESS/Elsevier, 1990. ISBN 0-444-88071-2 (volume A). QA 76.H279 1990.

van Emde Boas' treatment of SMMs appears on pp. 32-35. This treatment clarifies Schōnhage 1980 -- it closely follows but expands slightly the Schōnhage treatment. Both references may be needed for effective understanding.

• Hao Wang (1957), A Variant to Turing's Theory of Computing Machines, JACM (Journal of the Association for Computing Machinery) 4; 63-92. Presented at the meeting of the Association, June 23-25, 1954.

外部リンク

• Weisstein, Eric W. “Register machine”. MathWorld（英語）.
• Igblan - Minsky Register Machines
• Visual Register Machine