algorithm - "Is n divisible with 23?"的可判定性

Question

我有以下问题:

Let n be a natural number, n > 10^100. Is n divisible with 23?

这个问题是半可判定的还是可判定的？

可以创建一种算法来找到答案，使其始终停止。我对半可判定和可判定之间的区别感到很困惑。据我所知，如果我可以构建一个图灵机(算法)来接受问题的解决方案并拒绝，则问题是可确定的。但是，如果机器在输入不是解的情况下永远不会停止，则意味着问题是半可判定的。

所以，我会说上面的问题是可判定的，但我不知道我说的是否正确。你能帮我找出答案吗？为什么？谢谢。

Answer 1

是的，它是可判定的。给出比 Lakshay Garg 更基本的论点:

• 你可以枚举出所有的数字 k = 0, 1, 2, 3, 4, 5, ...
• 您可以将它们连续乘以 23。
• 现在是有趣的步骤:
  • 如果23*k小于n，尝试下一个k。
  • 如果 23*k = n，则 n 可以被 23 整除。完成。
  • 如果 23*k 大于 n，我们可以停止，因为再多 k 个，我们只会超过 n 个。如果到那时我们发现没有 k = n/23，则没有，并且 n 不能被 23 整除。完成。

由于23*n大于n，最晚k=n时，我们会到达最后一步，这意味着该过程终止。