元のチューリングマシンの操作のアセンブリ言語同等物はどのようなものになりますか？

StackOverflow https://stackoverflow.com/questions/3537715

質問

元のチューリングマシンの定義を次のように取る場合：

...無限のメモリ容量は、シンボルを印刷することができる正方形にマークされた無限のテープの形で得られます。いつでもマシンに1つのシンボルがあります。スキャンされたシンボルと呼ばれます。マシンはスキャンされたシンボルを変更でき、その動作はそのシンボルによって部分的に決定されますが、他の場所のテープのシンボルはマシンの動作に影響しません。ただし、テープはマシンを介して前後に移動できます。これは、マシンの初等操作の1つです。したがって、テープ上のシンボルは最終的にイニングがある場合があります。 （チューリング1948、p。61）

これらの操作をアセンブラー/バイナリ命令を解釈できるプロセッサで行われた操作にマッピングする場合 - どの操作がマッピングされますか？

（この質問に内在するチューリングマシンからフォンノイマンマシンへのジャンプを知っています）

役に立ちましたか？

解決

あなたが書いたものを読む私はあなたがただ必要だと言う：

  • 直接増分命令（現在のテープの場所に追加するため）
  • 間接的な増分命令（テープを移動するため）
  • 現在のテープの位置値に応じて行動すべきこと

たとえば、腕のようなアセンブリでは、テープにアドレスを含むR0がある場合は、必要なだけです

ADDS r0, r0, #1 ;moves the tape forward
ADDS r0, r0, #-1 ;moves the tape backwards
ADDS [r0], [r0], #1 ;increments the value 'pointed by' the tape
ADDS [r0], [r0], #-1 ;decrements the value 'pointed by' the tape

次に、現在のシンボルで想定されている特定の値の場合に備えて枝を作成します

BEQ Somewhere

これは多かれ少なかれ脳のファックの仕組みです。

他のヒント

無限のメモリ容量は、シンボルを印刷することができる正方形にマークされた無限のテープの形で得られます。

それをint配列と呼びましょう。 int[] Symbols

いつでもマシンに1つのシンボルがあります。スキャンされたシンボルと呼ばれます。 

int inxSym;
int scannedSymbol = Symbols[inxSym];

（CPUレベルでは、これは「メインメモリ」または最新のシステム「プログラムセグメント」として知られています。

マシンはスキャンされたシンボルを変更できます 

Symbols[inxSym] = newSymbol;

そして、その動作はそのシンボルによって部分的に決定されます、

switch(scannedSymbol) {....}

（CPUレベルでは、これは「命令を実行する」ことです。そうするように指示するOPコードはありません。それはまさにCPUがしていることです。）

しかし、他の場所のテープのシンボルは、マシンの動作に影響しません。

そこに何もすることはありません。

ただし、テープはマシンを介して前後に移動できます。これは、マシンの初等操作の1つです。 

  ++inxSym;
  --inxSym
   inxSym +=10;
 // etc.

（CPUレベルでは、これはJMP OPコードのハンドルです）

これが100％正しいかどうかはわかりませんが、次のようになります。

  • チューリングマシンヘッド（特定の時間にシンボルを「スキャン」するもの）は、命令ポインターと同等です。
  • したがって、命令フェーズとデコードフェーズは、スキャンされたシンボルの解釈と同等です。
  • 実行は、TM操作のより複雑なシーケンスとして表されます。たとえば、メモリの書き込みを考えてみましょう。特定のメモリの位置に頭を移動し、レジスタから場所にデータを移動し、IPレジスタで扱われている場所に戻り、それをインクリメントします。

ヘッドの動きの制御は、フロー制御命令、すなわちJMPとその兄弟と同等であることに注意してください。

また、レジスタは古典的なTMへの重要な追加であることに注意してください。それらは、テープ上の特別なセル（またはセルのセット）または別々のエンティティとして表現できます。を参照してください 登録機 詳細については。

最後に、これはVon Neumann Architectureで完全に機能しますが、Harvard Architectureは2つの異なるテープを使用して、1つは指示とデータ用のテープを使用していることに言及することが重要です。

チューリングマシンはテープ上のアルファベットの定義によって完全に決定されているため、テープを読んでいる状態マシンは、言語をテーブルのようにするのが最も理にかなっています

状態qnを呼び出してみましょう。アルファベットの文字AIはテープから読みます。マシンは、トランジトンテーブルAnから次の状態を決定し、AOをテープに書き込み、方向D：L/Rに移動します

その後、マシンを書くことで定義できます

Qnai-> qmaod

Wikipediaからのプログラムを追加することになります

QbA0 -> QbA1R
QbA1 -> QbA1R
Q0A- -> Q0A-L
Q1A0 -> QrA-L
Q1A1 -> QaA-L
Q1A- -> QrA-L

認められている状態とr拒否国家。これは非常にコンパクトで、移行マトリックスの読みやすいプレゼンテーションです。

もちろん、これはテープにあるものがデータとして解釈されることを前提としています。しかし、遷移マトリックスを作成して、テープからのステートマシンの命令を繰り返すことを止めるものはありません。

これを実装するには、左側にタプルがあり、右側にトリプルがあるため、これは2Dアレイのルックアップをマップしてトリプレットを読み取ります。テープ上のキャラクターの＃ビットで状態をシフトし、それらを一緒に貼り付けます。トリプレットのスペースを作成するために（OK、別のシフト操作）を掛け、それをテーブルのオフセットとして使用してトリプレットを読み取ります。

トリプレットにデータが見つかった場合、またはそこにデータがない場合、州登録簿の新しい州、テープのchar、およびincの減少を記述します。アセンブリは楽しいはずです。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top