以前、ステート マシンについて話し合っていたのですが、何らかの入力で停止しないのではないかという質問がありました。重要で頻繁に言及されるステート マシンのプロパティのように思えますが、そのプロパティの名前が何なのか、一生わかりません。そのような用語はありますか?それは「停止可能」、「無限ループではない」、または何か他のものですか?
2 に答える
9
常に停止するマシンはディサイダーと呼ばれます。
ディサイダーは、すべての入力で停止するマシンである必要があります。たとえば、DPDA と同様に、すべての DFA はディサイダーです。
于 2010-06-24T19:13:05.417 に答える
0
私の推測では、有名な「停止問題」から派生した「停止」であり、これはあなたの質問、つまり特定の入力で停止するかどうかに似ています。重要な考慮事項は、マシンは一般に「停止」するものとして定義されているのではなく、特定の入力に対して定義されているということです。一般的なケースは解決できないことが証明されています (チューリング自身によって)。
于 2010-06-24T19:10:32.053 に答える