2シンボルチューリングマシン

導入
チューリングマシンは、数学的モデルでは、無限の長いテープを使用して、記号や命令のセットを使用して計算されます.1936年にアランチューリング(覚えている)によって提案された.
すべてのプログラミング言語はチューリング完全であり、すべてのコンピュータハードウェア(よくほとんど)はチューリング完全です、チューリングマシンが行うことができるすべてを行うことができることを意味します.つのシンボルチューリングマシンは、計算のために2つのシンボル(例えば0と1の)を使用するチューリングマシンです.
まあ!ポイントをまっすぐに取得し、2シンボルチューリングマシンのものを参照してください.

コンポーネント
チューリングマシンには3つのコンポーネントがあります

無限長テープ

リード/ライトヘッド

命令のセット
チューリングマシンは、無限のテープを使用して、一連の命令に従ってテープ上のヘッドを使用してシンボルを読み書きする.

どうやって動くの?
単項加算の例を通してチューリングマシンの動作を見てみましょう.
単項加算は、単純なストロークの追加は、我々はストロークを得る2ストロークで3ストロークを追加すると言う

||| + || = |||||

それで、我々のチューリングマシンが2つのシンボル0と1を使用すると仮定しましょう.
最初のテープは以下で与えられます.ここで*はマシンの読み取り/書き込みヘッドを表します.

      * 
0 0 0 1 1 1 0 1 1 0 0 0 

命令は3枚です.

マシンは以下のように動作し、

マシンは、初期のカードから始まる
ヘッドはテープのシンボルを読み取る

ヘッドは消去し、シンボル読み取り

に従ってテープ上に新しいシンボルを書き込む

は、シンボル読取り

に従って方向(左または右)でヘッドシフトします

コンピュータは、読まれたシンボル

に従って次のカードに続きます

機械は、haltカード(カード―0)

までステップ2から5まで繰り返される

ウォークスルー
私たちのマシンは、最初のカードで最初のテープで- 1を開始します.

INITIAL STATE
      * 
0 0 0 1 1 1 0 1 1 0 0 0

ヘッドはシンボル1に遭遇するので、それは右に1つのシフトを書き、次のカード、カード- 1からの指示に従います.同じことが2回起こる.

STEP 1
        * 
0 0 0 1 1 1 0 1 1 0 0 0

STEP 2
          * 
0 0 0 1 1 1 0 1 1 0 0 0

STEP 3
            * 
0 0 0 1 1 1 0 1 1 0 0 0

ステップ3では、マシンの静止画のカードに従ってください.ヘッドはシンボル0を読み取り、現在ヘッド0を消去し、1を書き込み、右にシフトし、次の命令のカード2に行く.するとヘッドは1を読み、1を書き込み、右に移動する.これを再び繰り返す.

STEP 4
              * 
0 0 0 1 1 1 1 1 1 0 0 0

STEP 5
                * 
0 0 0 1 1 1 1 1 1 0 0 0

STEP 6
                  * 
0 0 0 1 1 1 1 1 1 0 0 0

現在、ヘッドはカード0からの指示に従ってシンボル0を読み込み、0を書き、左にシフトして、次の命令をCRD - 3から取得する.

STEP 7
                * 
0 0 0 1 1 1 1 1 1 0 0 0

今、ヘッドはシンボル1を読み、消去して0を書き込み、右にシフトし、次のカードはカード- 0 (停止)

結論
この記事では、チューリングマシン、特に2シンボルチューリングマシンについて簡単に議論しました.つのシンボルのチューリングマシンの作業を通して単項加算の例を通して行った.
私はCで2州Turing機械を実装しました、そして、あなたはこのlinkを通してアクセスすることができます.
ステップバイステップの可視化とカスタム命令とテープを追加する柔軟性を持つ独自のチューリングマシンを作成することができます.私はいくつかの興味深いテープやカードを実装するために追加しました.
我々はちょうど氷山の一角に触れたところだ.私たちはチューリングマシンで遊ぶことができる非常に興味深いパズルがあります.そのようなパズルは、忙しいビーバーの問題は、本当に魅力的なものです.興味があればちょっと覗いてみてください.Githubのリンクにはいくつかの忙しいビーバーカードやテープも含まれています.