問題タブ [decidable]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
90 問題
0
投票する
3
に答える
148
参照
algorithm - 「n は 23 で割り切れるか」の決定可能性
次の問題があります。
n を自然数、n > 10^100 とします。n は 23 で割り切れますか?
この問題は半決定可能ですか、それとも決定可能ですか?
常に停止するように、答えを見つけるアルゴリズムを作成することは可能です。半決定可能と決定可能の違いについて、私はかなり混乱しています。私が理解している限り、問題の解決策を受け入れ、それ以外の場合は拒否するチューリング マシン (アルゴリズム) を構築できれば、問題は決定可能です。ただし、解ではない入力の場合にマシンが決して停止しない場合、それは問題が半決定可能であることを意味します。
したがって、上記の問題は決定可能であると言えますが、私が言ったことが正しいかどうかはわかりません。答えとその理由を教えてください。ありがとうございました。