decidable

-1熱

1答えて

再帰的に決定可能な言語は、その言語の入力wが与えられたときにチューリングマシンを構築できる言語であり、チューリングマシンは常に受け入れ、停止または拒否する停止します。私が混乱しているのは無限に成長する言語です。たとえば、L = {0^p | pは素数です}。したがって、数が線形空間で素数であるかどうかを決定するアルゴリズムを書くことができます。だから私の理解は、このアルゴリズムは素数であるか、素数

3熱

4答えて

なぜOWL Fullは決まりませんか？

私はOWL Fullがなぜ決めることができないのかを見てきましたが、わかりやすい例が見つかりませんでした。「Entailment Closure」に起因するものであり、OWL FullがPropertiesであり、同時にIndividualでもあるクラスを持つことができるという事実と関連していることを説明しました。しかし、私はそれらのステートメントの関係を理解していません。

9熱

3答えて

NPハードとundecidable問題の関係

undecidable問題とNPハード問題の関係について少し混乱しています。 NP困難な問題が決定不能な問題のサブセットであるか、それとも単に同じで均等であるか、それとも同等ではないのか？私にとって、私は、決定不能な問題はNPの難しい問題のスーパーセットであると私の友人と主張してきました。 NPではなく、決めることのできない問題がいくつか存在します。しかし、私はこの議論が弱いと思っていて、ちょっ

0熱

1答えて

この言語が決定可能かどうかを証明する

この問題のために私のメモを検討していますが、この問題の仕組みを理解できていないようです。私たちはMを持っているとし、Mはすべての非停止状態を訪れる入力を受け入れます。私はこの問題が決定可能だと確信しましたが、私は問題を証明しています。私の答えの大まかな概要は次のようなものです：TM Tが1つの停止状態しかないと仮定し、すべての状態を通過する必要がある場合は、この停止状態を通過する必要があり、どの

0熱

1答えて

チューリングマシンの停止は何ですか？

私は決定性には新しいです。私は問題を止めるという問題を止めたが、実際に何を意味しているのかは分からなかった。私はすでに説明をしています。誰でも私に何か音の説明や少なくともいくつかの詳細を教えてもらえますか？多くの助けになるでしょうか？

2熱

1答えて

EPR断片のプレノックス定量の順序は重要ですか？

1次論理の効果的命題（EPR）フラグメントは、しばしば∃X.∀Y.Φ(X,Y)という形式のプレノックスで数量化された式のセットとして定義されます。XとYは（おそらくは空の）可変シーケンスです。定量化の順序、つまり∃*∀*はEPRの決定可能性に関係しますか？定量化の順序が入れ替わった場合、決定性を失うか？特に、私は決定可能なロジックで集合モナドのバインド操作のセマンティクスをキャプチャすることに興

1熱

1答えて

{<M> | MはTMであり、| L（M）| = n}を決定する決定者が決定したら、決定者はn-1を決定する

これは可能ですか？ {| MがTMであり、| L（M）| = n}が決定されたとすると、{MはTMであり、| L（M）| = n-1} 可能であれば、どうですか？

26熱

2答えて

Haskell/GHC UnndecidableInstances - 非終了型チェックの例？

コンパイルするために-XUndecidableInstancesが必要なHaskellコードを書いています。私はそれがなぜ起こるか、違反された特定の条件があり、それゆえGHCが叫ぶことを理解しています。しかし、タイプチェッカーが実際にハングアップしたり、無限ループに巻き込まれたりすることはありません。終了しないインスタンス定義はどのようなものですか？例を挙げてください。例えば

-1熱

1答えて

証明方法E_tm = {M | Mは何も受け入れないチューリングマシンです}はNP-Hardですか？

私は始める方法もわかりません。私の考えは、いくつかのNP完全な問題から多時間短縮を提供することです。 E_tm 私が理解できないことは、E_tmは決定できないが、NP-Hardクラスは決定可能であることを知っていることです。

9熱

2答えて

何らかのメモリが必要かどうかを知るのはなぜ難しいのですか？

私はMozillaのJavascriptチュートリアルを元に戻していました。ハイレベル言語は、ジョブに割り当てられたメモリの一部が場合にはもはや必要ないとき見つけるメモリ割り当てを追跡し、するために使用することがある「ゴミコレクタ」と呼ばれるソフトウェアを埋め込みます自動的に解放されます。この処理は、のメモリが必要かどうかを知るという一般的な問題は決めることができないため（アルゴリズムで