RegisterMaschine – ウィキペディア

タブ（RM）は、理論的なコンピューターサイエンスの抽象的なマシンです。登録機はそうです
チューリングファクト、つまり、原則として、すべての計算のためにチューリングマシンまたは実際のコンピューターを実行することができます。レジスタマシンとチューリングマシンが多項式用語で互いにシミュレートできることを証明できるため、チューリングマシンにも証明できるステートメントはレジスタマシン、したがって任意の計算機にも適用されます。これは、多くのステートメントがチューリングマシンを使用してより簡単に証明できるため、理論的なコンピューターサイエンスの利点です。 ^[初め]

after-content-x4

このモデルは、1963年からジョンC.シェパードソンとハワードE.スタージス（* 1936）の作品に戻り、ハインツカフェントで先駆者がいました。 ^[2]

レジスタマシンには、さまざまなわずかに異なる定義があります。著者に応じて、コマンドとその意味は異なります。 3つの基本操作を備えた単純なレジスタマシンについては、以下に説明します。

レジスタマシンは自然数で動作します。これから発生したすべての数字は、この文脈で考慮する必要があります。

レジスタマシンは次のとおりです。

最終的に番号付きのコマンドで構成されるプログラム（番号1で始まる）
コマンドメーターb
入力値m
出力値n
そして、番号付きストレージセルの無限に大きなメモリ（レジスタ）R（1）、R（2）、R（3）、…各レジスタは自然数を保存します。

プログラムは次のコマンドで構成されています。

指図	効果1	効果2	説明
${displaystyle A_{i}}$ $A_{i}$ 次に、p	r（i）：= r（i） + 1	B：= p	1によるレジスタの増分。
${displaystyle S_{i}}$ $S_{i}$ 次に、p	r（i）> 0の場合、r（i）：= r（i）-1	B：= p	レジスタのコンテンツがまだ0でない場合、レジスタの減少1。
もしも ${displaystyle T_{i}}$ $T_{i}$ 次に、P else q		r（i）= 0の場合、b：= p それ以外の場合はb：= q	レジスタ0が含まれているかどうかをテストします。

プログラムの開始に加えて、注文されたMで構成される入力レートも利用できる必要があります。

最初は、コマンドポインターBがプログラムの開始ブランドの価値に配置されます。数字1からmまでのメモリセルは、入力データセットの対応する値に配置されます。残りのメモリセルは値0を受け取ります。

レジスタマシンは、次々とプログラムのコマンドを実行します。コマンドは常に番号Bで実行されますこのプログラムは、存在しないコマンドを実行する予定です。

スケジュール後、R（1）からR（s）からR（s）までのすべての値が出力されます。

すべてのマシンと同様に、レジスタマシンはフロー図で明確に表示できます。

アイデンティティ関数の例 [ 編集 | ソーステキストを編集します ]

レジスタマシンの例

右側に描かれているレジスタマシンは、常に最初の入力値である値を費やします。

フロー図の青い配置ボックスはテストを表します。これが負の場合、レジスタマシンはループを通過し、すべての研削パスで減少しました

{displaystyle r_ {1}}

$R_{1}$ そして増加

{displaystyle r_ {0}}

$R_0$ 。最後に含まれます

{displaystyle r_ {1}}

$R_{1}$ 値0、テストは正であり、マシンは保持ステータスになります。入力値が常に保持ステータスで出ていることは明らかです

{displaystyle r_ {1}}

$R_{1}$ の

{displaystyle r_ {0}}

$R_0$ 立っている必要があります。したがって、使用可能なレジスタマシンは、ID関数の簡単な実装です。

ランダムアクセスマシン （短い RAM ）特別なタイプのレジスタマシンです。レジスタに対処する間接に対処する機能があります。

ランダムアクセスマシンは次のとおりです。

最終的に番号付きのコマンドで構成されるプログラム（番号1で始まる）
コマンドメーターb
アキュムレータC（0）
数字の記憶セル（レジスタ）c（1）、c（2）、c（3）の無限に大きな記憶

各レジスタ（BおよびC（0）を含む）は、自然数を保存します。

最初に、コマンドメーターBには値1、アキュムレータに値0が含まれています。1番のメモリセルには、最初の有限入力が含まれています。残りのメモリセルには値0が含まれています。

プログラムは次のコマンドで構成されています。

指図	効果1	効果2
iロードi	c（0）：= c（i）	B：= B+1
クロードi	c（0）：= i	B：= B+1
indload i	c（0）：= c（c（i））	B：= B+1
iを保存します	c（i）：= c（0）	B：= B+1
Indstore i	c（c（i））：= c（0）	B：= B+1
Iを追加します	c（0）：= c（0）+c（i）	B：= B+1
cadd i	c（0）：= c（0）+i	B：= B+1
Indadd i	c（0）：= c（0）+c（c（i））	B：= B+1
サブi	${displaystyle c（0）：= max（c（0）-c（i）、0）}$	B：= B+1
csub i	${displaystyle c（0）：= max（c（0）-i、0）}$	B：= B+1
indsub i	${displaystyle c（0）：= max（c（0）-c（c（i））、0）}$	B：= B+1
多くの	c（0）：= c（0）*c（i）	B：= B+1
cmul i	c（0）：= c（0）*i	B：= B+1
indmul i	c（0）：= c（0）*c（c（i））	B：= B+1
div i	${displaystyle c（0）：= lfloor c（0）/c（i）rfloor}$	B：= B+1
cdiv i	${displaystyle c（0）：= lfloor c（0）/irfloor}$	B：= B+1
inddiv i	${displaystyle c（0）：= lfloor c（0）/c（c（i））rfloor}$	B：= B+1
goto i		B：= i
c（0）の場合 ${displaystyle alpha、l}$

[1] 証拠と比較して、機械とチューリングマシンを登録します

[2] コンピューティングの起源と基礎、フリードリッヒL.バウアー、S。96

アイデンティティ関数の例 [ 編集 | ソーステキストを編集します ]

Recent Posts

Recent Comments

Archives

Categories

Meta