カウンターマシンモデル

カウンターマシンには多くの変種があり、その中にはヘルメス、エルショフ、ペーテル、ミンスキー、ランベック、シェパードソン、スタージス、シェーンハーゲによるものがあります。これらについては以下で説明します。

モデルの詳細

1954年：エルメスのモデル

シェパードソンとスタージス（1963）は、「この[デジタルコンピュータからチューリングマシンへの]普遍性の証明は、ヘルメスによって初めて記述されたようで、彼は[7 - 参照番号]で、理想的なコンピュータがチューリングマシンの動作を複製するようにプログラムできる方法を示した」と指摘し、「カフェンストのアプローチは、少なくとも任意の長さのワードを格納できる無限のストレージレジスタを許容する程度に理想化された場合、現在のデジタルコンピュータの普遍性を直接証明するという点で興味深い」と述べています。[1]

唯一の2つの算術命令は

  1. 後継事業
  2. 2つの数値が等しいかどうかをテストする

残りの操作は、レジスタからアキュムレータへの転送、アキュムレータからレジスタへの転送、またはテストジャンプです。

Kaphengst の論文はドイツ語で書かれており、Sheperdson と Sturgis の翻訳では「mill」や「orders」などの用語が使用されています。

このマシンには「ミル」（アキュムレータ）が搭載されています。カフェンストはミル／アキュムレータを「無限大」の記号で表していますが、以下の説明では「A」を使用します。また、「命令レジスタ」（「命令」は「命令」の意味で、「シーケンス」の意味でなく、「命令」の意味で）も搭載されています。（この用法は、バークス＝ゴールドスタイン＝フォン・ノイマン（1946年）報告書の「…電子計算装置」の説明に由来しています。）命令／命令レジスタはレジスタ「0」です。また、シェパードソンとスタージスの説明からは明らかではありませんが、このモデルにはカフェンストが「無限大素数」と呼ぶ「拡張レジスタ」が搭載されています。以下では「E」を使用します。

命令はレジスタに保存されます。

「...したがって、このマシンは、実際のコンピュータと同様に、独自のプログラムで算術演算を実行できます。」(p. 244)。

したがって、このモデルは実際にはランダムアクセスマシンです。以下では、[ r ] はレジスタ r の「内容」などを示します。

アクション：説明
D1:C(r,A)[ r ] → A、[ r ] → rレジスタrの内容をアキュムレータAにコピーする
D2:車）[ A ] → r、[ A ] → AアキュムレータAの内容をレジスタrにコピーする
C1:O(A)0 → Aゼロ（クリア）アキュムレータA
A1:P(A)[ A ] + 1 → AアキュムレータAの内容を増分（1を加算）する
F1:J(A) [E1]IF [ A ] = 0 の場合、「Exit 1」へジャンプアキュムレータAの内容が0の場合ジャンプ
G1:オン(A)[ A ] = [ r ] の場合 0 → < A > そうでなければ 1 → AA の内容が r の内容と等しい場合は A の内容をクリアし、そうでない場合は A=1 を設定します。
G2:O'(A)1 → AAの内容を1に設定

Shepherdson & Sturgis (1963) は、ミル/アキュムレータ A を削除し、Kaphengst 命令をレジスタ間の「コピー」、算術演算の「インクリメント」、および「レジスタ間の比較」に簡略化しました。デクリメントがないことに注意してください。このモデルは、ほぼそのまま Minsky (1967) にも記載されています。詳細は以下のセクションを参照してください。

アクション：説明：
あ:P(A)[ A ] + 1 → AアキュムレータAの内容を増分（1を加算）する
d.C(r j , r k )[ r j ] → r k、[ r j ] → r jレジスタr jの内容をレジスタr kにコピーする
f:J(r) [E1]IF [ r ] = 0 THEN "Exit 1" へジャンプ ELSE 次の命令へレジスタrの内容が0の場合ジャンプ
c:E(r j , r k )[ r j ] = [ r k ] の場合 0 → E そうでなければ 1 → Er jの内容がr kの内容と等しい場合はレジスタ E の内容をクリアし、そうでない場合は E=1 に設定する

1958年: エルショフの演算子アルゴリズムのクラス

Shepherdson & Sturgis (1963) は、エルソフのモデルではプログラムをレジスタに格納できることを指摘し、エルソフのモデルは以下のように説明している。

アクション：説明：
d.C(r j ,r k )[ r j ] → r k、[ r j ] → r jレジスタr jの内容をレジスタr kにコピーする
d'。C' (r j ,r k )[ r j ] +1 → r k、[ r j ] → r jレジスタr jの増分内容をレジスタr kにコピーする
e.J[E1]「出口1」へジャンプ「出口1」への無条件ジャンプ
f*:J(r j , r k )[E1, E2]IF [ r j ] ≤ [ r k ] の場合、「出口 1」へジャンプし、そうでない場合は「出口 2」へジャンプします。レジスタ r jの内容が r kの内容以下の場合は E1 出口にジャンプし、そうでない場合は E=2 にジャンプします。

1958年：ペーテルの「治療」

シェパードソンとスタージス（1963）は、ペーテルの「治療」（ここではあまり具体的ではない）は、以下の表に示す指示と同等であると指摘しています。彼らはこれらの指示について、具体的に次のように述べています。

「すべての部分再帰関数の計算可能性を可能な限り速く証明するという観点からは、ペーターの方法はおそらく最良である。チューリングマシンによる計算可能性を証明するには、上で述べた方法に沿ってコピー操作のさらなる分析が必要である。」[2]
アクション：説明：
c:の上）0 → [ n ]ゼロ（クリア）レジスタ n
d.C(m,n)[ m ] → n、[ m ] → [ m ]レジスタmの内容をレジスタnにコピーする
d'。C'(m,n)[ m ] + 1 → [ n ]、[ m ] → [ m ]レジスタmの増分内容をレジスタnにコピーする
e.J(m, n)[E1, E2]IF [m]=[n] の場合、E1 へジャンプ、ELSE の場合、E2 へジャンプm の内容が n の内容と等しい場合は E1 に条件ジャンプし、そうでない場合は E2 にジャンプします。

1961年: ミンスキーの部分再帰関数モデルが、わずか2つの命令からなる「プログラム」に簡約された。

エミール・ポストの問題(タグシステム) とヒルベルトの第 10 問題 (ヒルベルトの問題、ディオファントス方程式)に関する調査で、ミンスキーは次のように定義しました。

「最も単純な算術演算のみのプログラムを含む再帰関数理論の興味深い基礎」[3]

彼の「定理Ia」は、任意の部分再帰関数は「 2つの整数S1とS2を次の形式の命令Ijで操作するプログラム」で表されると主張している。 [4]

アクション：説明：
a.ADD (r, I j1 )[ r ] + 1 → r; 命令I j1に進みます。レジスタ r の内容をインクリメント（1 を加算）し、命令 I j1に進みます。
b.SUB (r, I j1 ,I j2 )[ r ] ≤ 0 の場合、命令 I j2へ進み、そうでない場合、[ r ] -1 → r へ進み、命令 I j1へ進むレジスタ r の内容がゼロの場合、命令 I j2にジャンプします。そうでない場合、レジスタ r の内容をデクリメント (1 を減算) して、命令 I j1にジャンプします。

最初の定理は、2番目の「定理IIa」の文脈であり、

「…は、1つの整数S（単一レジスタr1に含まれる）に対して、次の形式の命令I jを使用して操作するプログラムによって、任意の部分再帰関数を表します。」
アクション：説明：
a.乗算 (K j , I j1 )[ r1 ]*K j → r1; 命令I j1に進みます。レジスタr1の内容を定数K jで乗算する
b.DIV (K j , I j1 , I j2 )[ r1 ]/Kj = 0 の場合は命令 I j2に進み、そうでない場合は I j1に進みます。レジスタ1の内容を定数K jで割った結果、余りが出ない場合はinstr. I j1、そうでない場合はinstr. I j2

この2番目の形式では、マシンは「整数S」を処理するためにゲーデル数を使用します。彼は、最初のマシン/モデルでは4つのレジスタが利用可能であれば、これを行う必要はないと主張しています。

1961年: メルザックモデル: 加算と減算を含む単一の3値命令

「我々の目的は、論理ではなく算術によって効果的な計算可能性に到達するQマシンと呼ばれる原始的な装置を記述することである。その3つの操作は、計数、非負整数の比較、そして転送である。」（メルザック（1961）p.281）

彼のモデルの文脈を用いると、「数える」とは「連続的に増加させる」（小石を投げ入れる）か「連続的に減少させる」（減算する）ことを意味し、「移す」とは、中身を穴Aから穴Bへ（コピーではなく）移動させることを意味し、数値の比較は自明である。これは3つの基本モデルを組み合わせたものと思われる。

メルザックの物理モデルは、地面にある穴 { X、Y、Z など } と、特別な穴Sに無制限に供給される小石です(シンクか供給か、それとも両方か? メルザックは言及していません)。

「Qマシンは、S、A1、A2、…といった無限に多い数のロケーション、これらのロケーションに分散された無限に多い数のカウンター、プログラム、そして命令を実行することを唯一の目的とするオペレータから構成されます。初期状態では、これらのロケーションのうち有限数を除くすべてのロケーションは空で、残りのロケーションにはそれぞれ有限数のカウンターが含まれています。」（283ページ、太字は筆者による）

この命令は、彼が「XYZ」と呼ぶ単一の「三項演算」です。

「XYZ」は、
  1. 穴Yにある小石の数を数えます。
  2. それらをYに戻し、
  3. 同じ数字をX穴から取り除こうとする。X穴が空になるため不可能な場合は何もせず命令#Iへジャンプする。そうでなければ
  4. XからYの量を取り除き、(iv)それを穴Zの量に移す、つまり追加する。

可能なすべての操作のうち、以下の表に示すように、許可されない操作もあります。

許可された命令穴「X」穴「Y」穴「Z」指示の意味
いいえXXX
XXY([ X ] - [ X ])=0 → X[ Y ] + [ X ] → Y[Z] → ZXの小石はすべてXから取られ、Yに追加された
XXS([ X ] - [ X ])=0 → X[ Y ] → Y[Z] → ZXの小石はすべてXから取られ、シンク/ソースSに入れられる
いいえXYX
XYY[ X ] - [ Y ] → X[ Y ] + [ Y ] → Y[Z] → ZXから取られてYに置かれたYの小石の数を数えると、Yの数が2倍になる
XYS
いいえXSX
いいえXSY
いいえクロスサイトスクリプティング
XYZ[ X ] - [ Y ] → X[ Y ] → Y[ Z ] + [ Y ] → ZXから取られてZに加えられたYの小石の数、
SYY[ X ] → X[ Y ] + [ Y ] → Y[Z] → ZSから取られたYの小石の数をYに加えると、Yの数は2倍になる
SYZ[ X ] → X[ Y ] → Y[ Z ] + [ Y ] → [ Z ]Sから取り出されZに追加されたYの小石の数

メルザックモデルに関するいくつかの観察:

  1. すべての穴が 0 から始まる場合、どのように増加させるのでしょうか。どうやらこれは不可能のようです。1 つの穴に小石が 1 つ入っている必要があります。
  2. 条件付き「ジャンプ」は、XYZ タイプのインスタンスごとに発生します。これは、X に十分なカウンター/ペブルがないため実行できない場合はジャンプが発生し、そうでない場合は実行され、命令が次のシーケンスに進みます。
  3. SXY と XXY はどちらも常に実行できるため、どちらもジャンプを引き起こすことはできません。
  4. メルザックは自身のモデル（ランダムアクセスマシンを参照）に間接性を加え、その使用例を2つ挙げている。しかし、彼はこれについてそれ以上深く掘り下げていない。これは文献に現れる「間接性」の検証された最初の例である。
  5. 両方の論文、つまり Z. Alexander Melzak ( William Lowell Putnam Mathematical Competition、1950 年の優勝者) の論文は 1961 年 5 月 15 日に受理され、Joachim Lambek の論文は 1 か月後の 1961 年 6 月 15 日に受理され、同じ巻に続けて収録されています。
  6. メルザックの主張は真実だろうか？ ― このモデルは「非常に単純なので、平均的な小学生でも数分の説明でその仕組みを理解できるだろう」（282ページ） ― 読者が判断するしかない。

1961年: ランベックの「アバカス」モデル:メルザックのモデルをX+、X-に原子化し、テストを実行

ランベックのオリジナル「そろばん」モデル（1962年）：

ラムベックはメルザックの論文を参照しています。彼はメルザックの単一の3パラメータ演算（命令アドレスを数えると実際には4つ）を、2パラメータのインクリメント「X+」と3パラメータのデクリメント「X-」に分解しています。また、「プログラム」の非公式な定義と公式な定義の両方を提供しています。この形式はミンスキー（1961）のモデルと実質的に同一であり、Boolos、Burgess、Jeffrey 2007、p. 45、Abacus Computabilityでも採用されています。

アクション：説明：
a.X+ (r, I a )[ r ] + 1 → r; 命令I aに進みます。レジスタrの内容をインクリメント（1を加算）する
b.X- (r, I a , I b )[ r ] ≤ 0の場合はinstr.I bへ、そうでない場合は[ r ]-1 → rへ進みinstr. I aへ進むまずゼロかどうかテストし、次にレジスタrの内容をデクリメント（1を減算）します。

Boolos、Burgess、Jeffreyのそろばんモデル：[5]

1970年以降の様々な版では、著者はLambek (1961)の「無限算盤」モデルを採用しています。この一連のWikipedia記事では、その記号表現が用いられています。例えば、「 [ r ] +1 → r」は「番号 'r' で識別されるレジスタの内容に1を加えたものが、番号 'r' レジスタの内容と置き換わる[置かれる]」です。

彼らはラムベックの「アバカス」という名称を採用しているが、メルザックの「穴の中の小石」モデルを踏襲しており、それを「箱の中の石」モデルへと改良している。ラムベックのオリジナルのアバカスモデルと同様に、彼らのモデルはミンスキー（1961）の非順次命令の使用法を維持している。つまり、「従来型」のコンピュータのようなデフォルトの順次命令実行とは異なり、次の命令I aは命令内に含まれている。

ただし、BB と BBJ では、Lambek バージョンに示されているように、ニーモニックで指定パラメータ付きの変数「X」 (つまり「X+」と「X-」) は使用されず、命令ニーモニックでレジスタ自体が指定されます (例:「2+」または「3-」)。

アクション：説明：
a1.1+ (I a )[ r1 ] + 1 → r1 、命令I aに進みます。レジスタ#1の内容をインクリメント（1を加算）する
b1.1- (I a、I b )[ r1 ] ≤ 0 の場合は I bへ進み、そうでない場合は [ r1 ] -1 → r1 となって I aへ進みます。レジスタr1の内容がゼロの場合は命令I bにジャンプし、そうでない場合はレジスタ#1の内容をデクリメント（1を減算）する

1963年: シェパードソンとスタージスのモデル

Shepherdson & Sturgis (1963) は、MIT リンカーン研究所の報告書の形で Minsky (1961) を参照しています。

第10節では、1つまたは2つのテープによる部分再帰関数の計算に関する定理（ミンスキーの結果[21、その参考文献]を含む）が、中間形式の1つからかなり簡単に得られることを示します。

— シェパードソン＆スタージス 1963年、218ページ

彼らのモデルは、 Hao Wang (1957) [6]と彼のWang Bマシン（ポストチューリングマシンも参照）のモデルと精神に強く影響を受けている。彼らは次のように要約している。

...私たちは、王氏が提案し始めた計算の実際的側面と理論的側面の間の「和解」をさらに一歩進めようと努めてきました。

無制限レジスタマシン URM : [7]これは彼らの「最も柔軟なマシン…は、1、2、3、…と番号が付けられた可算なレジスタの列で構成されており、各レジ​​スタには任意の自然数を格納できます…ただし、各プログラムはこれらのレジスタを有限の数しか使用しません」(p. 219)。言い換えれば、レジスタの数は潜在的に無限であり、各レジ​​スタの「サイズ」も無限です。

彼らは以下の命令セットと以下の「注意」を提供している：[1]

URM モデル:アクション：説明：
a.P(n)[ r ] + 1 → rレジスタrの内容をインクリメント（1を加算）する
b.D(n)[ r ] - 1 → rレジスタrの内容をデクリメント（1を減算）する
c:の上）0 → rゼロ（クリア）レジスタ r
d.C(m,n)[ r j ] → r k、[ r j ] → r j、レジスタr jの内容をレジスタr kにコピーする
e.J[E1]「出口1」へジャンプ「出口1」への無条件ジャンプ
f:J(r) [E1]IF [ r j ] = 0 THEN "Exit 1" [9] ELSE 次の命令 へジャンプレジスタrの内容が0の場合、「Exit 1」命令にジャンプ[9]し、そうでない場合は次の命令 にジャンプする

注意事項。

  1. この命令セットは、経済性よりも部分再帰関数の計算をプログラミングしやすくするために選択されています。セクション 4 では、このセットがより小さなセットと同等であることが示されています。
  2. m、n [ r jの内容など] の範囲はすべての正の整数にわたるため、このリストには無限の数の命令があります。
  3. 命令 a、b、c、d では、n を除くすべてのレジスタの内容は変更されないことになっています。命令 e、f では、すべてのレジスタの内容は変更されません (p. 219)。

実際、彼らはこのセットをさらに次のように縮小する方法を示しています (レジスタの数が無限で、それぞれサイズが無限の場合)。

URM の削減:アクション：説明：
a1.P(r)[ r ] + 1 → rレジスタrの内容をインクリメント（1を加算）する
b1.D(n)[ r ] - 1 → rレジスタrの内容をデクリメント（1を減算）する
~f1:J(r) [E1]IF [ r ] ≠ 0 の場合、「Exit 1」へジャンプレジスタmの内容が0でない場合、命令「Exit 1」にジャンプし、そうでない場合は続行する。

限定レジスタマシン（LRM）: このマシンでは、レジスタ数を有限個Nに制限するが、より多くのレジスタを「取り込む」、あるいは空であれば削除することを許可している（228ページ参照）。レジスタ削除命令は必ずしも空のレジスタを必要としないことを示す。

シングルレジスタマシン（SRM） ：ここではエミール・ポストのタグシステムを実装し、文字列の末尾への書き込みと先頭からの消去のみを可能にしています。これは図1に示されており、左側に読み取りヘッド、右側に書き込みヘッドを持つテープであり、テープは右方向にしか移動できません。「A」が彼らの「ワード」（229ページ）です。

a. P(i) ;Aの末尾にaiを追加する
b. D;Aの最初の文字を削除します
f'. Ji[E1] ;Aがaiで始まる場合は出口1にジャンプします。

彼らはまた、{0,1}の記号を持つ「カードの山」としてのモデルも提供しています（p.232および付録C p.248）。

  1. 上部にカードを追加 1 印刷
  2. 上部にカードを追加 0 印刷
  3. 一番下のカードを取り除きます。1 と印刷されている場合は命令 m にジャンプし、そうでない場合は次の命令にジャンプします。

1967年: ミンスキーの「プログラムコンピュータのための単純な普遍基底」

最終的に、問題 11.7-1 でミンスキー氏は、小さな集合から多くの計算基底を形成できることを指摘しています。

「[ 0 ]、[ ' ]、[ - ]、[ O- ]、[ → ]、[ RPT ]といった演算の種類の組み合わせは、普遍的な基底を形成します。これらの基底のいくつかを見つけてください。3つの演算の組み合わせのうち、普遍的な基底ではないものはどれですか？他の演算をいくつか考え出してください…」[10]

彼が扱うさまざまな命令の定義は次のとおりです。

アクション：説明：
a.[ 0 ]0 → rゼロ（クリア）レジスタ r
b.['][ r ] + 1 → rレジスタ r の内容をインクリメント（1 を加算）します（アポストロフィ ' は「後続」を意味します）。
紀元前[ - ]IF [ r ] = 0 THEN 命令zへジャンプ ELSE 次の命令へレジスタrをテストし、内容がゼロの場合は命令zにジャンプします。そうでない場合は、レジスタrの内容をデクリメント（1を減算）します。
d.[ O- ][ r ] ≠ 0 の場合 [ r ] -1 → r そうでなければ次の命令レジスタrの内容がゼロでない場合はレジスタrの内容をデクリメントしてz番目の命令にジャンプし、そうでない場合は0の場合は次の命令にジャンプします。
e.[ → ][ r j ] → r k、[ r j ] → r jレジスタr jの内容をレジスタr kにコピーする
f.[ 参考文献]RPT a:[m,n]。繰り返しは自身の範囲内では動作しません。レジスタ[r]の内容が0になるまで実行します。命令mからnを繰り返します。[r]が0になったら、次の命令に進みます。
グラム。[ H ]停止
h.goto(z)命令zにジャンプ命令zへの無条件ジャンプ
私。[ ≠ ][ r j ] ≠ [ r k ] の場合、z番目の命令にジャンプし、そうでない場合は次の命令にジャンプする条件ジャンプ: レジスタ r jの内容がレジスタ r kの内容と等しくない場合、命令 z にジャンプし、そうでない場合は次の命令にジャンプする
j.[ RPT]*RPT a:[m,n]。繰り返しは自身の範囲内で動作します。* 注意: RPTは無限レジスタ内になければなりません

ミンスキー（1967）は、3 つの操作と HALT で構成されるモデルから始めます。

{ [ 0 ], [ ' ], [ - ], [ H ] }

彼は、特定のレジスタ（例えばw）が既に「空」であると仮定すれば、[ 0 ] を省略できることを指摘している。[11]さらに彼は、3つの{[ 0 ]、[' ]、[ - ] }を2つの{[' ]、[ - ] }に圧縮している。[12]

しかし彼は、いくつかの[擬似]命令[ O- ]（[ 0 ]と[ - ]を組み合わせたもの）と「go(n)」を追加すれば、モデルがより簡単になることを認めている。彼は「go(n)」をレジスタwを0にプリセットした状態で構築し、[O-] ( w , (n))が無条件ジャンプになるようにしている。

セクション 11.5「一般再帰関数を持つプログラムマシンの同等性」では、2 つの新しいサブルーチンを紹介しています。

f. [ → ]
j. [ ≠ ]
等しくない場合はジャンプする": IF [ r j ] ≠ [ r k ] THEN z番目の命令にジャンプし、ELSE 次の命令にジャンプする

彼は次に、「後続-先行」集合 { [ 0 ], [ ' ], [ - ] } を「後続-等価」集合 { [ 0 ], [ ' ], [ ≠ ] } に置き換える方法を示します。そして「REPEAT」[RPT] を定義し、 「後続-繰り返し」集合 { [ 0 ], [ ' ], [RPT] } によって任意の原始再帰関数を定義できることを示します（ただし、[ RPT ] の値域には自身を含めることはできません。もし自身を含む場合は、いわゆる「mu演算子」（ mu再帰関数も参照）（p. 213））。

一般的な再帰関数は、RPT演算が自身の範囲内にあることを許容すれば、[ 0 ]、[ ' ]、[ RPT ]演算のみを用いてプログラムコンピュータで計算できます。…[ただし]一般に、RPT演算はマシンの有限状態部分における命令にはなり得ません。…[もしそうであれば]マシンの有限状態部分に許容される特定の記憶域を使い果たしてしまう可能性があります。RPT演算は一般に、それ自体に無限のレジスタを必要とします…など。(p. 214)

1980: シェーンハーゲの 0 パラメータ モデル RAM0

シェーンハーゲ（1980）[13]は、ポインタマシンの一種であるストレージマシン修正モデル（SMM）と名付けた「新しい」モデルの文脈で、計算モデルを発展させた。彼の開発では、おそらく「条件付きジャンプ」を除いてオペランドを全く必要としない（そして、条件付きジャンプさえもオペランドなしで実行可能だった）という注目すべき命令セットを備えたRAM（ランダムアクセスマシン）モデルが記述された。

「…RAM0バージョンは、その極めてシンプルな構造から特に注目に値する。その命令セットは、明示的なアドレス指定を必要とせず、わずか数文字のコードから構成されている」（p. 494）

ショーンハーゲがこれを実現した方法は興味深い。彼は(i)従来のレジスタ「アドレス:データ」を「アドレス」と「データ」という2つの部分に分割し、(ii)有限状態マシン命令（すなわち「マシンコード」）がアクセスできる特定のレジスタnに「アドレス」を生成し、(iii)すべての算術演算が行われる「アキュムレータ」レジスタzを提供する。

彼の特定のRAM0モデルには、「算術演算」が2つしかありません。「Z」は「レジスタzの内容をゼロに設定する」、そして「A」は「レジスタzの内容に1を加算する」です。アドレスレジスタnへのアクセスは、「set address n 」と呼ばれるAからNへのコピー命令を介してのみ可能です。アキュムレータzに特定のレジスタに格納する「データ」を格納するために、マシンはnの内容を使用してレジスタのアドレスを指定し、レジスタzを使用してレジスタに送信するデータを指定します。

特異性： Schönhage RAM0の第一の特徴は、レジスタzへの「ロード」方法です。レジスタzはまずレジスタアドレスを供給し、次にレジスタからデータを受け取ります。これは間接的な「ロード」の一種です。第二の特徴は、COMPARE命令の仕様です。これは「アキュムレータレジスタz = 0の場合のジャンプ」命令です（例えば、「レジスタzの内容をnが指すレジスタの内容と比較する」命令とは異なります）。このテストが失敗した場合、マシンは常に「goto λ」（「λ」はジャンプ先アドレス）という形式をとる次の命令をスキップします。「レジスタzの内容をゼロと比較する」命令は、Schonhageの後継モデルであるRAM1（あるいは他の既知の後継モデル）の、より一般的な「レジスタzの内容とレジスタaの内容を比較する」命令とは異なります。

主に参考用です（これは RAM モデルであり、カウンターマシン モデルではありません）。以下は Schönhage RAM0 命令セットです。

命令アクション：説明：
1Z0 → zアキュムレータレジスタzをクリアする
2あ[ z ] + 1 → zアキュムレータレジスタzの内容をインクリメントする
3北[ z ] → n、[ z ] → z「アドレスnを設定」：アキュムレータzの内容をアドレスレジスタnにコピーする
4L[ [ z ] ] → zアキュムレータzが指すレジスタの内容をアキュムレータzに間接的にコピーする
5S[ z ] → [ n ]アキュムレータzの内容をアドレスレジスタnの内容が指すレジスタに間接的に格納する
6C[ z ] = 0の場合、次の命令をスキップします（これはgoto命令I λである必要があります）アキュムレータzの内容が0の場合は次の命令をスキップし、そうでない場合は継続する
7I λへ無条件goto（ジャンプ）命令Iλ無条件goto（ジャンプ）命令Iλ

繰り返しますが、上記の命令セットはランダム アクセス マシン、つまり間接アドレス指定を備えたカウンター マシンであるRAM用です 。命令「N」はアキュムレータの間接的な保存を可能にし、命令「L」はアキュムレータの間接的なロードを可能にします。

奇妙ではありますが、Schönhage のモデルは、従来のカウンターマシンの「レジスタ間」または「読み取り、変更、書き込み」の命令セットを、最も単純な 0 パラメータ形式に分解する方法を示しています。

参考文献

  1. ^ シェパードソン＆スタージス 1963年、219ページより。
  2. ^ シェパードソン＆スタージス 1963年、246ページ。
  3. ^ ミンスキー1961、437ページ。
  4. ^ ミンスキー 1961, p. 449を参照
  5. ^ Boolos、Burgess、Jeffrey 2007、p. 45、Abacus Computability。
  6. ^ 王 1957.
  7. ^ Cutland 1980, p. 9も参照
  8. ^ カットランド 1980、11ページ。
  9. ^ ab 理解：「命令番号E1へジャンプ」[8]
  10. ^ ミンスキー1967、214ページ。
  11. ^ ミンスキー1967、206ページ。
  12. ^ ミンスキー 1967、255ページ以降。
  13. ^ シェーンハーゲ 1980.

参考文献

  • ブーロス, ジョージ;バージェス, ジョン・P.;ジェフリー, リチャード(2007) [1974].計算可能性と論理(第5版). ケンブリッジ, イギリス:ケンブリッジ大学出版局. ISBN 978-0-521-87752-7。Boolos-Jeffreyの原著はBurgessによって大幅に改訂され、入門書よりも高度な内容となっています。「アバカスマシン」モデルは第5章「アバカスの計算可能性」で詳細に展開されています。これは、チューリングマシン（Boolosのオリジナルの4要素形式のまま）と再帰という、今回広く扱われ比較される3つのモデルのうちの1つです。
  • エルショフ、AP通信（1958年）。 「Ob operatsionnykh algoritmakh」[演算子アルゴリズムについて]。Doklady Akademii Nauk SSSR (ロシア語)。122 : 967–970 ., 「演算子アルゴリズムについて」.自動翻訳/プログラミングと翻訳 (Automat. Express) . 1 : 20–23 . 1959.
  • ヘルメス、ハンス(1954)。 「普遍的なプログラムを作成するRechenmaschinen」。数学物理学半期 (ゲッティンゲン) (ドイツ語)。4：42～ 53。
  • カフェンスト、ハインツ (1959)。 「Eine Abstrakte Programmgesteuerte Rechenmaschine」。Zeitschrift für mathematische Logik und Grundlagen der Mathematik (ドイツ語)。5：366～ 379。
  • ドナルド・E.・クヌース(1973) [1968]. 『コンピュータプログラミングの技法』（第2版）. マサチューセッツ州レディング: アディソン・ウェスレー. pp.  462– 463.462～463 ページを参照してください。ここで彼は「リンクされた構造を扱う新しい種類の抽象マシン、つまり『オートマトン』」を定義しています。
  • ランベック、ヨアヒム（1961年9月）「無限アバカスのプログラミング方法」数学速報4 （ 3）：295-302。付録 II で、ラムベックは「プログラム」の「正式な定義」を提案しています。彼はメルザック (1961) とクリーネ (1952) を参照しています。
  • メルザック, Z. A. (1961年9月). 「計算可能性と計算への非公式算術的アプローチ」.カナダ数学速報. 4 (3): 279– 293. doi :10.4153/CMB-1961-031-9.メルザックは参考文献を挙げていないが、「ベル電話研究所のR.ハミング博士、D.マキロイ博士、V.ヴィソッツ博士、およびオックスフォード大学のH.ワン博士との会話が役に立った」と認めている。
  • ミンスキー、マーヴィン(1961). 「ポストの『タグ』問題の再帰的不解法とチューリング機械理論におけるその他の話題」Annals of Mathematics . 74 (3): 437– 455. doi :10.2307/1970290. JSTOR  1970290.
  • ミンスキー、マービン（1967年）『計算：有限機械と無限機械』（第1版）ニュージャージー州エングルウッド・クリフス：プレンティス・ホール社特に第11章「デジタルコンピュータに類似したモデル」と第14章「計算可能性のための非常に単純な基底」を参照してください。前章では「プログラムマシン」を定義し、後章では「2つのレジスタを持つ汎用プログラムマシン」や「1つのレジスタを持つ…」などについて説明しています。
  • ペテル、ロザ(1958)。 「グラフスキーマと再帰関数」。弁証法（ドイツ語）。12 : 373.
  • Schönhage, Arnold (1980). 「ストレージ変更マシン」. SIAM J. Comput . 9 (3). Society for Industrial and Applied Mathematics: 366– 379. doi :10.1137/0209036.ここで、Schönhage は、彼の SMM が「後継 RAM」(ランダム アクセス マシン) などと同等であることを示しています。
  • シュロッペル、リッチ（1972年5月）「2つのカウンタを持つ機械は2Nを計算できない（ AIメモ）」AIM-257. マサチューセッツ工科大学人工知能研究所. hdl :1721.1/6202.著者はミンスキー (1967) を引用し、「フランシス・ヤオは1971 年 4 月に同様の方法を使用して独自に計算不可能性を証明した」と述べています。
  • シェパードソン, ジョン・C. ; スタージス, HE (1963). 「再帰関数の計算可能性」. ACMジャーナル. 10 (2): 217– 255. doi : 10.1145/321160.321170 .非常に貴重な参考文献です。付録Aでは、著者は「4.1で使用される命令の最小性：類似システムとの比較」に関して、他の4つの論文を引用しています。
  • ファン・エムデ・ボアス、ピーター(1990). 「マシンモデルとシミュレーション」.ファン・レーウェン、ヤン(編). 『理論計算機科学ハンドブック』第A巻：アルゴリズムと複雑性（第1版）. MITプレス/エルゼビア. pp.  3– 66. ISBN 9780444880710。ファン・エムデ・ボアスによるSMMの扱いは32～35ページに掲載されています。この扱いはショーンハーゲ（1980）の扱いを明確化しており、ショーンハーゲの扱いをほぼ踏襲しつつも、若干拡張しています。効果的な理解のためには、両方の参考文献が必要になるかもしれません。
  • 王浩(1957). 「チューリングの計算機理論の変種」.計算機協会誌. 4 : 63–92 . 1954年6月23日～25日開催の同協会会議にて発表

さらに読む

「https://en.wikipedia.org/w/index.php?title=カウンターマシンモデル&oldid=1330537214」より取得