7

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

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

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

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

4

4 に答える 4

7

あなたが書いたものを読んで私はあなたがただ必要だと言うでしょう：

  • 直接インクリメント命令（現在のテープ位置に追加するため）
  • 間接インクリメント命令（テープを移動するため）
  • 現在のテープ位置の値に応じて動作するもの

たとえば、ARMのようなアセンブリでは、テープにアドレスを含む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

これは多かれ少なかれBrainfuckの仕組みです。

于 2010-08-21T13:26:06.753 に答える
3

正方形にマークされた無限のテープの形で得られる無限のメモリ容量。それぞれに記号を印刷できます。

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

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

int inxSym;
int scannedSymbol = Symbols[inxSym];

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

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

Symbols[inxSym] = newSymbol;

そしてその振る舞いはそのシンボルによって部分的に決定されます、

switch(scannedSymbol) {....}

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

ただし、他の場所にあるテープ上の記号は、マシンの動作に影響を与えません。

そこでは何もしません。

ただし、テープはマシン内を前後に移動できます。これは、マシンの基本的な操作の1つです。

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

（CPUレベルでは、これはJMPオペコードで処理されます）

于 2010-08-21T13:21:08.193 に答える
1

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

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

頭の動きの制御は、フロー制御命令、つまりJMPとその兄弟と同等であることに注意してください。

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

最後に、これはフォンノイマンアーキテクチャでは完全に機能しますが、ハーバードアーキテクチャでは、命令用とデータ用の2つの異なるテープを使用することに注意してください。

于 2010-08-21T23:28:19.113 に答える
0

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

状態をQnと呼びましょう。これは、テープから読み取ったAlfabet文字Aiです。マシンはトランジションテーブルから次の状態を判断し、Aoをテープに書き込み、D：L/Rの方向に移動します。

マシンは、その書き込みによって定義することができます

QnAi-> QmAoD

ウィキペディアからの追加プログラムは次のようになります

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

受け入れ状態と拒否状態を示します。これは非常にコンパクトで、遷移マトリックスの読みやすい表現です。

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

これを実装するには、左側にタプル、右側にトリプルがあるため、これは2D配列のルックアップにマッピングされ、トリプレットを読み取ります。テープ上の文字の#bitsで状態をシフトし、それらを貼り合わせます。掛け算（OK、別のシフト操作）してトリプレット用のスペースを作り、それをテーブルのオフセットとして使用してトリプレットを読み取ります。

トリプレットにデータが見つかった場合、またはデータがない場合は、状態レジスタに新しい状態を書き込み、テープにcharを書き込み、インクリメントします。組み立ては楽しいはずです。

于 2010-08-21T13:52:49.747 に答える