プログラムが常に停止することが知られているプログラム等価

おそらく無限の状態空間を持つ2つのプログラムがあり、いくつかのオラクルは両方とも常に停止していると主張しています。彼らが文脈上同等であるかどうか私はいつでも決めることができますか?はいの場合は、既知の効果的なアルゴリズム(またはケースバイケースまたは言語ごとに適用して効果的なアルゴリズムを提供するアプローチ)がありますか?

答えは、有限入力ドメインでははい/はいですが、無限入力ドメインでは:入力ドメインが無限大(例えば、数えることと数えられない)に依存しますか?

ベストアンサー

この逆の例として、Context-Free
Equivalenceの問題を考えてみましょう.2つのコンテキストフリー言語が同じセットを受け入れるかどうかを決定することは決定できません。

CFLを常に停止中のチューリングマシンにすることは常に可能であるため、問題が解決できない場合は、CFLの等価性を判断するためにこの問題を使用できます。

したがって、無限の入力を数えるだけでも、問題は決めることができません。

また、標準的なチューリングマシンでは、すべての入力ドメインが有限の文字列のセットであるため、無限に無限大であることにも言及する価値があります。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です