チューリングマシンの状態テーブルの設計

Question

アルゴリズムの疑似コードがすでにある場合、それらはチューリング マシンの動作を説明するのに役立つガイドラインですか?

私は複雑性理論のコースを受講しているのですが、C やアセンブリなどでコーディングする方法はわかっていても、言語 (状態、遷移など) を決定または受け入れるチューリング マシンを説明するのに時間がかかります。 。チューリングマシンの練習がまだ足りていないだけだと思います（取り組んでいます）が、何か提案があれば感謝します。

編集

私はチューリング マシン シミュレーターを作りたいのではなく、言語を決定するためにチューリング マシンを紙上 (アルファベット、状態、遷移) で記述したいのです。

ここで私が言いたいことの簡単な例を示します。たとえば、0 と 1 の文字列を調べて、その中のすべての 0 を 1 に変更するチューリング マシンを作成する必要があるとします。たとえば、テープ (入力) で 11010 で開始すると、テープ (出力) で 11111 で停止します。高級言語では次のようなものになることがわかります。

Go over every character on tape
    If character is 0 change it to 1

チューリングマシンの説明は非公式には次のようなものです。

q と halt という 2 つの状態があります。State Qで1を表示したら、変更せずに右に進みます。0が表示されている場合は、1に変更して右に移動します。空白のシンボル（テープの終わり）が表示されている場合は、停止状態に移動します。

形式的には、状態としては {q, halt} のようなものになります。{((q, 1) -> (q, 1, R))、((q, 0) -> (q, 1, R))、((q, #) -> (停止, 0, L) )} トランジション用。

この問題は簡単ですが、もっと複雑な問題は他にもあります (単項数を追加したり、a、b、c の数が等しい言語を認識したりするなど)。疑似コードを書くのは簡単ですが、チューリング マシンを書くのははるかに難しく (長い時間がかかります)、そのような問題をより上手に解決できるようになるためのヒント、リソース、またはガイドラインがあればと考えていました。

Answer 1

免責事項: あなたの質問は非常に一般的であるため、この答えも同様です。私はTMSの専門家ではないことに注意してください。このアプローチは通常、それほど効率的ではありません（常に効果的であると約束することさえできません）。ここでちょっと考えたことを書き留めておきます。

次のようなアプローチを試してみることをお勧めします。擬似コードを取り、a）ブール変数とb）のみで構成されるように削減します if-ステートメント。例えば：

if THIS_LETTER_IS("A"):
    found_an_even_number_of_A = not found_an_even_number_of_A

if THIS_LETTER_IS("Q") and previous_letter_was_X and found_an_even_number_of_A
        and not checking_for_alternative_2:
    # can't be a word of alternative 1, so check for alternative 2
    going_back_to_start_to_check_for_alternative_2 = True

if going_back_to_start_to_check_for_alternative_2:
    MOVE_TO_PREVIOUS
else:
    MOVE_TO_NEXT

if going_back_to_start_to_check_for_alternative_2 and THIS_LETTER_IS(EMPTY):
    # reached the beginning, so let's check for alternative 2
    going_back_to_start_to_check_for_alternative_2 = False
    checking_for_alternative_2 = True

ネストしたとき ifs、それらを次のように置き換えます ands;取り除く else を使用してブロックします not:

if something:
    if something_else:
        do_a
    else:
        do_b

になる

if something and something_else:
    do_a

if something and not something_else:
    do_b

それぞれ if ブロックには 1 つだけを含める必要があります MOVE_TO_PREVIOUS または MOVE_TO_NEXT, 、おそらく WRITE コマンドと数の変数割り当て。

すべて完了する if そのような条項 ひとつひとつ あなたのブーチと現在の文字は常にチェックされ、壊死のブロックを複製します。例：

if something and something_else:
    do_a

になる

if THIS_LETTER_IS("A") and something and something_else and something_i_dont_care_about_here:
    do_a

if THIS_LETTER_IS("A") and something and something_else and not something_i_dont_care_about_here:
    do_a

if THIS_LETTER_IS("Q") and something and something_else and something_i_dont_care_about_here:
    do_a

if THIS_LETTER_IS("Q") and something and something_else and not something_i_dont_care_about_here:
    do_a

さて、もしあなたが持っているなら、 n ブール値と メートル 手紙、あなたは持っているべきです メートル * 2ⁿ ifs.ブールンをビットフィールドに保管したことを想像してみてください。そのため、ブーリアンの可能な組み合わせのそれぞれが整数を表しています。したがって、上記は次のようになります

if THIS_LETTER_IS("A") and bitfield[0] and bitfield[1] and bitfield[2]:
    do_a

if THIS_LETTER_IS("A") and bitfield[0] and bitfield[1] and not bitfield[2]:
    do_a

# ...

それは次のようになります

if THIS_LETTER_IS("A") and bitfield == 7:
    do_a

if THIS_LETTER_IS("A") and bitfield == 3:
    do_a

# ...

ビットフィールドのこの整数値は、チューリング マシンの状態です。の do_a 部分はブール値への単なる代入です (つまり、ビットフィールド、だからそれはあなたの新しい状態です）、書き込みコマンド（いない場合は、すでにそこにあった手紙を書くだけです）、および運動コマンド、したがって明示的にチューリングマシンの遷移です。

上記のいずれかが意味をなすことを願っています。

Answer 2

あなたはすぐに使用できるツール、チューリングマシンのシミュレータが必要ですか？ 非常に多くの利用可能なのがあります。それとも実際にあなた自身を作りたいですか？これはJavaScriptで有効な実装のようだ： http://klickfamily.com/david/学校/ cis119 / TuringSim.html のあなたがコードを解析し、非常に簡単にCまたはC ++に翻訳することができます。