algorithm - “n 能被 23 整除吗？”的可判定性

Question

我有以下问题：

设 n 为自然数，n > 10^100。n 能被 23 整除吗？

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

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

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

Answer 1

return (n % 23 == 0)

这不算算法吗？对我来说似乎可以决定。

请参阅Hermann Döppes 的答案，您不想假设模数的可计算性。

Answer 2

是的，这是可以决定的。给出比 Lakshay Garg 更基本的论点：

• 您可以枚举所有数字 k = 0, 1, 2, 3, 4, 5, ...</li>
• 您可以将它们依次乘以 23。
• 现在到了有趣的一步：
  • 如果 23*k 小于 n，则尝试下一个 k。
  • 如果 23*k = n，则 n 可被 23 整除。完成。
  • 如果 23*k 大于 n，我们可以停止，因为任何进一步的 k 我们只会进一步超过 n。如果到那时我们没有找到 k = n/23，那么就没有 k = n/23，并且 n不能被 23 整除。完成。

由于 23*n 比 n 大，所以我们最迟会在 k = n 时到达最后一步，这意味着这个过程终止。

Answer 3

你是对的。如果您可以编写一个算法，对于任何输入，该算法最终总是会做出决定，那么问题就是可判定的。对于“是否能被 23 整除？”的问题，考虑以下（坏）算法：从 开始，并检查是否小于、大于或等于。ni = 123 * in

• 如果小于n，则递增i。
• 如果等于n，则返回true。
• 如果大于n，则返回false。

不管有多大n，这个算法最终总会吐出一个答案，因为在大于i之前你只能增加有限的次数。这可能需要大量时间，但出于可判定性的目的，我们不在乎。所以这个算法总是做出决定；因此，这个问题是可以判定的。23 * in

将此与半可判定问题进行对比。在这些问题中，存在一种算法，true如果这是正确答案，它总是会回答，但如果正确答案是 ，则可能永远运行false。

最著名的半可判定问题是停机问题：给定一个程序，确定该程序是否停止运行。假设您尝试通过编写一个执行其输入的程序来解决这个问题。如果该执行终止，那么您可以返回true：您知道程序终止，因为您只是看着它这样做。但是，如果您已经等待了一段时间并且它还没有终止，那么您永远无法确定如果让它运行更长的时间它是否不会终止，所以您只需要等待。因此，如果输入程序没有终止，您的程序也不会终止。

因此，对于停止问题有一个算法，true如果实际答案为真，则该算法总是返回，但如果实际答案为假，则永远运行。因此，停机问题是半可判定的。