2

任意の数のテープシンボルを含むチューリングマシンMは、{0、1、B}（B =空白）の3つのテープシンボルのみを含む1つのM'でシミュレートできます。

Mは、テープシンボルが2つしかないM "、たとえば{1、B}でシミュレートできますか？

4

2 に答える 2

7

最初のステップ（任意のTMから1と0だけのTMに移行する）は、思ったほど難しくはありませんが、他の人が言っているほど簡単ではありません。アイデアは、アルファベットの各記号の固定長バイナリエンコーディングを開発することです。次に、有限状態制御を更新して、各ステップでTMが適切なビット数をスキャンし、移動する方法と書き込むシンボルを決定し、新しいシンボルのバイナリ表現を書き込み、繰り返します。これは、巨大な有限状態制御を使用することで実行できます。その動作を確認するのは非常に難しいので、詳細は読者に任せます。:-)。注意すべき1つの詳細は、この構造では、ブランクシンボルを、発明したバイナリシンボルと同じ長さのブランクのシーケンスとして表すことです。

1とBだけを使用してTMを実装するには、同様のトリックを使用します。まず、TMを減らして、1、0、およびBのみを使用します。シンボルセットをさらに小さいもので減らしますが、テープには無限に多くの空白があるため、これを行う方法についてはもう少し賢くする必要があります。それ。次のエンコーディングを使用します。

  1. 11は数値1をエンコードします
  2. 1Bは数値0をエンコードします
  3. BBはブランクをエンコードします。

このエンコード方式を使用してTMを実行しているときに、以前にアクセスしたテープの終わりを通り過ぎると、空白のシンボルのエンコードに対応する、無限に多くの空白のシンボルが発生します。

唯一の課題は、この新しいTMへの入力をエンコードして、上記の形式に変換できるようにする方法です。TM入力にはブランクを表示できないため、入力は単項でエンコードする必要があります。次に、古いマシンのバイナリ文字列wについて、新しいマシンへの入力は数値1wの単一符号化である必要があることを規定します。次に、マシンの最初のステップは、ユニアリーエンコーディングから上記のバイナリエンコーディングに変換することです。これはたった2つのシンボルで行うことができますが、詳細は非常に難しいので、もう一度それらをパントします。必要に応じて詳細を確認できます。

お役に立てれば！

于 2011-01-27T19:28:10.273 に答える
0

最初のものは簡単です、コンピュータ、バイナリを考えてください...。

最初のものでは、各シンボルを0,1表現にエンコードできます。

2つ目では、次の2つのことができます。

  1. Bを0と考えてください...何と呼んでも構いません...そして、0,1のマシンがあり、好きなようにエンコードできます。

  2. シンボルをBで区切られた一連のシンボルとしてエンコードします。N番目のシンボルはN1を保持します。

于 2011-01-27T18:53:10.967 に答える