Loading article…
カウンターマシンには多くのバリエーションがあり、その中にはヘルメス、エルショフ、ペーター、ミンスキー、ランベック、シェパードソンとスタージス、そしてシェーンハーゲによるものがある。これらについては以下で説明する。
シェパードソンとスタージス（1963）は、「[デジタルコンピュータからチューリングマシンへの]普遍性の証明は、最初にヘルメスによって書き記されたようで、ヘルメスは[7-参照番号]で、理想化されたコンピュータが任意のチューリングマシンの動作を複製するようにプログラムできることを示した」と述べ、さらに「カペンストのアプローチは、少なくとも任意の長さのワードをそれぞれ格納できる無限の記憶レジスタを許容するほど理想化された場合、現代のデジタルコンピュータの普遍性を直接証明するという点で興味深い」と述べている。[ 1 ]
算術命令は2 つだけです。
残りの操作は、レジスタからアキュムレータへの転送、アキュムレータからレジスタへの転送、またはテストジャンプです。
カペンストの論文はドイツ語で書かれており、シェパードソンとスタージスの翻訳では「ミル」や「オーダー」といった用語が使われている。
この機械には「ミル」（アキュムレータ）が含まれています。カペンストはこのミル／アキュムレータを「無限大」記号で表していますが、以下の説明では「A」と表記します。また、「オーダーレジスタ」（「オーダー」は「命令」の意味で、「シーケンス」の意味でではない）も含まれています。（この表記は、バークス、ゴールドスタイン、フォン・ノイマン（1946）の報告書における「…電子計算機」の説明に由来します。）オーダー／命令レジスタはレジスタ「0」です。さらに、シェパードソンとスタージスの解説からは明らかではありませんが、このモデルにはカペンストが「無限大プライム」と表記した「拡張レジスタ」が含まれています。ここでは「E」と表記します。
命令はレジスタに格納されます。
したがって、このモデルは実際にはランダムアクセスマシンです。以下では、[ r ]"はレジスタrの「内容」などを表します。
シェパードソンとスタージス（1963）は、ミル/アキュムレータAを削除し、カペンスト命令をレジスタ間「コピー」、算術演算「インクリメント」、および「レジスタ間比較」に削減しました。デクリメントがないことに注意してください。このモデルは、ほぼそのままミンスキー（1967）に掲載されています。詳細は以下のセクションを参照してください。
シェパードソンとスタージス（1963）は、エルソフのモデルではプログラムをレジスタに格納できることを指摘している。彼らは、エルソフのモデルは以下の通りであると主張している。
シェパードソンとスタージス（1963）は、ペーターの「治療法」（ここではあまり具体的に述べていない）は、次の表に示す指示と同等であると指摘している。彼らはこれらの指示について具体的に次のように述べている。
ミンスキーは、エミール・ポストの問題（タグシステム）とヒルベルトの第10問題（ヒルベルトの問題、ディオファントス方程式）に関する調査から、以下の定義に至った。
彼の「定理 Ia」は、任意の部分再帰関数は「次の形式の命令 Ij を使用して2 つの整数 S1 と S2を操作するプログラム」によって表現されると主張しています。 [ 4 ]
最初の定理は、次の2番目の「定理IIa」の文脈である。
この2番目の形式では、機械はゲーデル数を用いて「整数S」を処理する。彼は、最初の機械／モデルは、利用可能なレジスタが4つあれば、このような処理を行う必要はないと主張する。
彼のモデルの文脈で考えると、「集計する」とは「連続的に増分を加える」（小石を投げ入れる）か「連続的に減分する」ことを意味し、移送とは穴Aから穴Bへ内容物を移動させる（コピーするのではなく）ことを意味し、数値を比較することは自明である。これは、3つの基本モデルを融合させたものと思われる。
メルザックの物理モデルは、地面にある穴{X、Y、Zなど}と、特別な穴S（シンクかサプライか、あるいはその両方か？メルザックは明言していない）にある無限の小石の供給源である。
その命令は、彼が「XYZ」と呼ぶ単一の「三項演算」である。
可能な操作のうち、以下の表に示すように、許可されていない操作がいくつかあります。
メルザックモデルに関するいくつかの考察：
ランベックのオリジナル「そろばん」モデル（1962年）：
ランベックはメルザックの論文を参照している。彼はメルザックの単一の3パラメータ演算（命令アドレスを含めると実際には4）を、2パラメータのインクリメント「X+」と3パラメータのデクリメント「X-」に分解している。また、「プログラム」の非公式および公式の定義も提供している。この形式はミンスキー（1961）モデルとほぼ同一であり、Boolos、Burgess 、 Jeffrey（2007 、p. 45、Abacus Computability）によって採用されている。
ブーロス、バージェス、ジェフリーのそろばんモデル：[ 5 ]
1970年以降の様々な版では、著者はランベック（1961）の「無限そろばん」モデルを使用しています。この一連のウィキペディア記事では、例えば「[ r ] +1 → r」のように、その記号を使用しています。「番号 'r' として識別されるレジスタの内容に 1 を加えたものが、レジスタ番号 'r' の内容に置き換えられます（レジスタ番号 'r' に格納されます）」。
彼らはランベックの「そろばん」という名前を使っているが、メルザックの穴に小石を入れるモデルを、彼ら自身が「箱に石を入れる」モデルに修正したものに従っている。ランベックのオリジナルのそろばんモデルと同様に、彼らのモデルはミンスキー（1961）の非逐次命令の使用法を維持している。つまり、「従来型」のコンピュータのようなデフォルトの逐次命令実行とは異なり、次の命令 I a は命令の中に含まれている。
ただし、BBとBBJでは、ニーモニックで指定パラメータ付きの変数「X」（Lambek版に示されているように「X+」や「X-」など）は使用せず、命令ニーモニックでレジスタ自体を指定します。例えば、「2+」や「3-」などです。
シェパードソンとスタージス（1963）は、ミンスキー（1961）を、 MITリンカーン研究所の報告書の形で参照している。
第10節では、1つまたは2つのテープによる部分再帰関数の計算に関する定理（ミンスキーの結果[21、彼らの参考文献]を含む）が、我々の中間形式の1つから比較的容易に得られることを示す。
—シェパードソン＆スタージス 1963、p.218
彼らのモデルは、 Hao Wang (1957) [ 6 ]のモデルと精神、そして彼のWang Bマシン（ポストチューリングマシンも参照）に強く影響を受けている。彼らは次のように要約している。
…私たちは、王氏が提唱し始めた計算の実践的側面と理論的側面との間の「接近」をさらに一歩進めようと試みました。
無制限レジスタマシン URM : [ 7 ]これは、彼らの「最も柔軟なマシン... 1、2、3、... と番号付けされたレジスタの列挙可能なシーケンスで構成され、それぞれのレジスタは任意の自然数を格納できます... ただし、個々のプログラムは、これらのレジスタの有限個のみを使用します」(p. 219)。言い換えれば、レジスタの数は潜在的に無限であり、各レジスタの「サイズ」は無限です。
彼らは以下の命令セットと以下の「注記」を提供します: [ 1 ]
注記。
実際、彼らはこの集合をさらに縮小する方法を示しており、以下のように縮小できる（それぞれ無限のサイズのレジスタが無限に存在する場合）。
限定レジスタマシン（LRM）：ここでは、マシンを有限個のレジスタNに制限していますが、空の場合はより多くのレジスタを「追加」したり削除したりすることもできます（ 228ページ参照）。レジスタ削除命令は、必ずしも空のレジスタを必要とするわけではないことを示しています。
シングルレジスタマシン（SRM） ：ここでは、エミール・ポストのタグシステムを実装しており、文字列の末尾への書き込みと先頭からの消去のみを可能にしています。これは、図1に、左側に読み取りヘッド、右側に書き込みヘッドを備えたテープとして示されており、テープは右方向にしか移動できません。「A」は彼らの「ワード」です（229ページ）。
また、記号{0, 1}を持つ「カードの山」としてモデルも提示している（ 232ページおよび付録C 248ページ ）。
最終的に、問題11.7-1においてミンスキーは、ごく少数の要素から多くの計算基底を形成できることを指摘している。
彼が扱う様々な指示の定義は以下のとおりです。
ミンスキー（1967）は、3つの操作とHALTを組み合わせたモデルから始めている。
彼は、特定のレジスタ、例えばw が既に「空」である場合、 [ 0 ] を省略できることを指摘している。[ 11 ]さらに彼は、3 つの { [ 0 ]、[ ' ]、[ - ] } を 2 つの { [ ' ]、[ - ] } に圧縮している。[ 12 ]
しかし彼は、擬似命令[O-]（[0]と[-]を組み合わせたもの）と「go(n)」を追加すればモデルが簡単になることを認めている。彼はレジスタwを0に事前設定して「go(n)」を構築し、[O-]( w , (n))が無条件ジャンプとなるようにしている。
第11.5節「プログラムマシンと一般再帰関数の等価性」において、彼は2つの新しいサブルーチンを紹介している。
彼は続けて、「後継者-前継者」集合 { [ 0 ], [ ' ], [ - ] } を「後継者-等価性」集合 { [ 0 ], [ ' ], [ ≠ ] } に置き換える方法を示します。そして、彼は「REPEAT」[RPT] を定義し、 「後継者-繰り返し」集合 { [ 0 ], [ ' ], [RPT] } によって任意の原始再帰関数を定義できることを示します（ただし、[ RPT ] の範囲には自身を含めることはできません。含める場合は、ミュー演算子と呼ばれるものが得られます（ミュー再帰関数も参照）（213 ページ ））。
Schönhage (1980) [ 13 ] は、彼がストレージマシン変更モデル (SMM) と呼んだ「新しい」モデル、つまりポインタマシンの一種の文脈で計算モデルを開発した。彼の開発では、おそらく「条件付きジャンプ」を除いてオペランドを全く必要としない注目すべき命令セットを持つ RAM (ランダムアクセスマシン) モデルが記述されている (そして、それさえもオペランドなしで実現できる)。
シェーンハーゲがこれを実現した方法は興味深い。彼は(i)従来のレジスタ「アドレス:データ」を「アドレス」と「データ」の2つの部分に分解し、(ii)有限状態機械命令（つまり「機械語」）がアクセスできる特定のレジスタnに「アドレス」を生成し、(iii)すべての算術演算が行われる「アキュムレータ」レジスタzを提供する。
彼のRAM0モデルには、「Z」命令による「レジスタzの内容をゼロに設定する」命令と、「A」命令による「レジスタzの内容に1を加える」命令の2つの「算術演算」しかありません。アドレスレジスタnへのアクセスは、「アドレスnを設定する」と呼ばれるAからNへのコピー命令のみで行われます。アキュムレータz内の特定のレジスタに「データ」を格納するには、マシンはnの内容を使用してレジスタのアドレスを指定し、レジスタzを使用してレジスタに送信するデータを提供します。
特異性： Schönhage RAM0 の第一の特異性は、レジスタzへのデータの「ロード」方法です。レジスタzはまずレジスタ アドレスを提供し、次にレジスタからデータを受け取ります。これは間接的な「ロード」の一種です。第二の特異性は、COMPARE 命令の仕様です。これは「アキュムレータ レジスタzがゼロの場合にジャンプする」 （例えば、「zの内容をnが指すレジスタの内容と比較する」ではありません）というものです。テストが失敗した場合、マシンは次の命令をスキップしますが、次の命令は常に「goto λ」の形式でなければなりません。ここで「λ」はジャンプ先アドレスです。 「 zの内容をゼロと比較する」という命令は、より一般的な「レジスタzの内容をレジスタ a の内容と比較して等しいかどうかを判断する」という Schönhage の後継機種 RAM1（または他の既知の後継機種）とは異なります。
主に参考のために（これはRAMモデルであり、カウンタマシンモデルではありません）、以下はSchönhage RAM0の命令セットです。
繰り返しますが、上記の命令セットはランダムアクセスマシン（ RAM ）用です。RAMは間接アドレッシングを備えたカウンタマシンです。命令「N」はアキュムレータの間接格納を可能にし、命令「L」はアキュムレータの間接ロードを可能にします。
シェーンハーゲのモデルは独特ではあるが、従来のカウンタマシンの「レジスタ間」または「読み出し・変更・書き込み」命令セットを、最も単純な0パラメータ形式にまで分解できることを示している。