“n可除以23?”的可判定性

Question

我有以下问题：

设n是一个自然数，n> 10^100。N可以用23整除吗？

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

可以创建一个算法来找到答案，这样它就会始终停止。我对半可决定和可判定之间的区别感到很困惑。据我所知，如果我能够构建一个图灵机(算法)来接受问题的解决方案，并以其他方式拒绝，那么问题是可以判定的。然而，如果机器永远不会停止在输入不是解决方案的情况下，这意味着问题是半决定性的。

因此，我想说，上述问题是可以解决的，但我不知道我所说的是否正确。你能帮我找出答案吗?为什么？谢谢。

Answer 1

你是对的。如果您可以编写一个算法，对于任何输入，最终都会做出决策，那么问题是可以确定的。对于“n可被23除吗？”的问题，请考虑以下(坏的)算法:从i = 1开始，检查23 * i是否小于、大于或等于n。

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

无论n有多大，这个算法最终都会给出一个答案，因为在23 * i大于n之前，只能将i增量有限次。这可能需要大量的时间，但为了决定的目的，我们不在乎。因此，该算法总是做出决策，因此问题是可判定的。

将此与半可判定的问题进行对比。如果有一个算法，如果答案是正确的，那么总是会回答false.，但是如果正确的答案是，可能会永远运行

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

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

Answer 2

return (n % 23 == 0)

这不算一种算法吗？在我看来是可以决定的。

请看answer by Hermann Döppes，你不想假设模数的可计算性。

Answer 3

是的，它是可决定的。给出一个比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时到达最后一步，这意味着这个过程终止。