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

ウィキペディア小見出し辞書

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/02 05:58 UTC 版)

「レジスタマシン」の記事における「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 によって、この問題が解決された。彼らの P0 RASP はインデックス付き命令セットで強化されている。これは、より複雑だがより柔軟性の高い間接指定方式である。そのモデルでは、レジスタを指定する際に、ベースレジスタとインデックスとなる即値（または、ベース即値とインデックスレジスタ）が使われる。つまり、インデックス付き命令ではオペランドが1つ増えている。