次の問題があります。
n を自然数、n > 10^100 とします。n は 23 で割り切れますか?
この問題は半決定可能ですか、それとも決定可能ですか?
常に停止するように、答えを見つけるアルゴリズムを作成することは可能です。半決定可能と決定可能の違いについて、私はかなり混乱しています。私が理解している限り、問題の解決策を受け入れ、それ以外の場合は拒否するチューリング マシン (アルゴリズム) を構築できれば、問題は決定可能です。ただし、解ではない入力の場合にマシンが決して停止しない場合、それは問題が半決定可能であることを意味します。
したがって、上記の問題は決定可能であると言えますが、私が言ったことが正しいかどうかはわかりません。答えとその理由を教えてください。ありがとうございました。