33

非決定性チューリングマシンの概念がわかりません。非決定性アルゴリズムという用語を理解していると思います:(非決定性アルゴリズムは、決定論的アルゴリズムとは対照的に、さまざまな実行でさまざまな動作を示すことができるアルゴリズムです）。したがって、アルゴリズムは次のようになります。

a = fromSomeAlgo();

if(a > foo)
   stateA();
else
   stateB();

しかし、私が読んだ非決定性チューリングマシンの場合、一度に複数の状態になる可能性があります。また、ウィキペディアの記事は、 「非決定性チューリングマシン（NTM）には、特定の状況に対して複数のアクションを規定する一連のルールがある場合がある」と示唆しています。

どういう意味ですか ？..特定の状況に対する複数のアクション...複数の状態...私は単にこれを理解していません。

4

1 に答える 1

47

非決定性チューリングマシンでは、各ブランチで（両方の可能性を実行します）、完了したときにのみ、ソリューションに必要なもの（存在する場合）を「選択」します。

たとえば、でサブセット和問題を見てみましょうS = {a,b,c... }。非決定性チューリングマシンには線形ソリューションがあります。

for each element:
   "guess" if it is in the subset
check if the subset has the specified sum

生成されるツリーは次のようになります。

                                       start
                 with a                                      without a
               /         \                                   /          \
              /           \                                 /            \
             /             \                               /              \
      with b               without b                  with b              without b
      /     \               /       \                 /     \             /        \
  with c    without c    with c     without c     with c    without c    with c     without c

アルゴリズムが「true」を生成するには、1つの計算（ツリー内のパス）が正しいだけで十分です。そのような計算がない場合にのみ、「false」が生成されます。

非決定性チューリングマシンの概念は純粋に理論的なものであり、非決定性チューリングマシンはありません。

ボーナス：
非決定性チューリングマシンで実行できるすべてのこと（およびその逆）は、決定性チューリングマシンで実行できることに注意してください。たとえば、停止問題はどちらでも決定できません。ただし、NPCの問題は、非決定性チューリングマシンで多項式で実行でき、決定性チューリングマシンで多項式で実行する方法がわかりません（不可能であると想定しています）。

于 2012-11-23T06:53:30.687 に答える