2

計算定理を復習するだけです。そして、次のような質問に出会いました。状態 とアルファベット記号を持つ
決定論k-tape的チューリング マシンを考えてみましょう。このチューリング マシンが、各テープで 最大セルを使用した後に停止したとします。最大稼働時間は？ 答えはなぜ ですか？そして、と はどういう意味ですか？ありがとう！q
σ
h
q X(σ^hk)X(h^k)
σ^hkh^k

4

2 に答える 2

4

重要な洞察は、チューリング マシンが停止するために、ループに入ることができないということです。チューリング マシンは、特定の状態になると常に同じシーケンスに従うため、同じ状態が 2 回発生した場合、マシンが無限ループに陥り、決して終了しないことがわかります。したがって、実行できる理論上の最大ステップ数は、マシンがまったく同じ状態に 2 回ならずに可能な異なる状態の最大数です。

この例では、一意の状態は次のもので構成されています。

  1. 各kテープの値 (hセルの最大値)、
  2. マシンの現在の状態 (q可能性の 1 つ)、
  3. k各ミシンヘッドの現在位置。

σ可能な記号があるため、各テープの各セルが可能な値の 1 つになり得ることを意味しhます。すべてのテープの間にセルの合計があり、それぞれ独立して値の 1 つになることができます。したがって、考えられる組み合わせの合計は、このアドレス (1) です。この式は文字通り、(可能なアルファベット記号の数) ^ (セルの最大数 * テープの数) を意味します。kσhkσσ^(h*k)

(2) については、qテープ セルのすべての組み合わせに対して有効な状態の追加の組み合わせがあります。qこれにより、理論上の最大値に追加の係数が与えられます。

(3) の場合、各マシン ヘッドは、テープhごとに可能なセル位置の 1 つに独立して配置することもできます。これにより、可能な状態kの別の要素が追加されます。h^k

したがって、可能な状態の総数は次の積になります。q * σ^(h*k) * h^k

于 2013-11-04T04:31:20.813 に答える
1

チューリング マシンを、h*k の範囲内で機能する線形有界オートマトン (LBA) と考えてください。まず、単一のテープ マシンについて考えてみましょう。

単一のテープ LBA の場合、LBA に以下がある場合:

1)q状態 2)gテープ アルファベットの記号、および 3) 長さ の入力n、

その場合、可能な構成の数はq * n * g^n、単一のテープ LBA に対するものです。 LBA での停止問題の証明

簡単に言うと、単一のテープ LBA の場合、g^n可能なテープがありn、ヘッドが指し示す可能性のある位置がありq、マシンが存在する可能性のある状態があります。したがって、q * n * g^n構成があります。

k-tape マシン用に一般化すると、(g^n)^k考えられるテープ構成があります。すべてのテープ ヘッドに可能な構成がありn ^ k(一部またはすべてのテープ ヘッドを同時に移動できるため)、qマシンが可能な状態になります。したがって、個別の構成の数は次のようになります。q * (n ^ k) * g^(nk)

文字通り単一テープ LBA の長さである に変更nし、に変更すると、答えがあります。hgσ

于 2013-11-04T04:37:21.253 に答える