finite-automata - チューリングマシン

Question

言語とオートマトンに関する本を読んでいますが、チューリング マシンについて理解していません。DFA の NFA と Pushdown Automata については独学で問題なく学習できました。誰かがこれが何をしているのか説明してもらえますか?

B = {w#w|w ∈ {0, 1}*}

次の図には、入力 011000#011000 で開始されたときにステージ 2 と 3 で計算している Ml のテープのスナップショットがいくつか含まれています。

どうもありがとう！

Answer 1

チューリング マシンは、シンボルが格納されているテープを使用した仮想マシンです。テープからシンボルを読み取ったり、テープにシンボルを書き込んだりできる複数のヘッドを持つことができます。

ここで、あなたの文法は B = {w#w|w ∈ {0, 1}*} と言い、これは "w#w" の形式の任意の文字列です。ここで、w は 0 と 1 の任意の組み合わせであるか、まったく組み合わせていません。したがって、この特定の例では w = 011000 としましょう。結果の文字列は 011000#011000 になり、チューリング マシンはこの文法に従っているかどうかを検証します。

この場合、チューリング マシンにはヘッドが 1 つあります。文字列の先頭から始まります。0 である最初の文字を読み取ります。それを「x」とマークします。これは、これを読んだことを意味します。次に # の直後に進み、読み取った内容が一致するかどうかを確認します。この場合も 0 であるため、「x」に一致するとマークされます。その後、前の位置に戻り、次の文字に対して同じことを行います。これを # に達するまで続けます。ハッシュまたは # を読み取ると、文字列の末尾をチェックし、文字列の末尾である場合は、指定された文法に従っていると答えてこの文字列を受け入れます。