"Is n divisible with 23?" 的可判定性
Decidability of "Is n divisible with 23?"
我有以下问题：
Let n be a natural number, n > 10^100. Is n divisible with 23?
这个问题是半可判定的还是可判定的？
可以创建一种算法来找到答案，使其始终停止。我对半可判定和可判定之间的区别感到很困惑。据我所知，如果我可以构建一个图灵机（算法）来接受问题的解决方案并拒绝，则问题是可确定的。但是，如果机器在输入不是解决方案的情况下永远不会停止，则意味着问题是半可判定的。
所以，我想说上面的问题是可以确定的，但我不知道我说的是否正确。你能帮我找出答案吗？为什么？谢谢。
return (n % 23 == 0)
这不算算法？对我来说似乎是可决定的。
请参阅您不想假设模数的可计算性。
是的，它是可判定的。给出比 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，则有 none 并且 n 不能 被 23 整除。完成。
由于23*n比n大，最晚k=n时会走到最后一步，即本程序结束
你是对的。如果您可以编写一种算法，对于任何输入，最终都会始终做出决定，那么问题就是可判定。对于 "is n divisible by 23?" 的问题，考虑以下（坏的）算法：从 i = 1 开始，然后检查 23 * i 是否小于、大于或等于 n。
- 如果小于
n，递增i。
- 如果等于
n,returntrue.
- 如果大于
n,returnfalse.
不管n有多大，这个算法最终总会吐出一个答案，因为在23 * i大于之前你只能递增i有限的次数n。这可能会花费大量时间，但出于可判定性的目的，我们不在乎。所以这个算法总是做出决定；因此，问题是可判定的。
将此与 半可判定 问题进行对比。这些问题存在一种算法，如果这是正确答案，它将始终回答 true，但如果正确答案是 false[=47=， 可能永远 运行 ].
最著名的半可判定问题是停机问题：给定一个程序，确定该程序是否曾经停止 运行ning。假设您尝试通过编写一个执行其输入的程序来解决这个问题。如果该执行终止，那么您可以 return true：您知道程序终止，因为您只是看着它这样做。但是如果你等了一段时间它还没有终止，你永远无法确定它是否会终止如果你只是让它 运行 稍微长一点，所以你只需要等待。因此，如果输入程序没有终止，您的程序也不会终止。
因此，对于停机问题有一个算法，如果实际答案为真，则总是 returns true，但如果实际答案为假，则永远 运行s。因此，停机问题是半可判定的。
我有以下问题：
Let n be a natural number, n > 10^100. Is n divisible with 23?
这个问题是半可判定的还是可判定的？
可以创建一种算法来找到答案，使其始终停止。我对半可判定和可判定之间的区别感到很困惑。据我所知，如果我可以构建一个图灵机（算法）来接受问题的解决方案并拒绝，则问题是可确定的。但是，如果机器在输入不是解决方案的情况下永远不会停止，则意味着问题是半可判定的。
所以，我想说上面的问题是可以确定的，但我不知道我说的是否正确。你能帮我找出答案吗？为什么？谢谢。
return (n % 23 == 0)
这不算算法？对我来说似乎是可决定的。
请参阅
是的，它是可判定的。给出比 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，则有 none 并且 n 不能 被 23 整除。完成。
由于23*n比n大，最晚k=n时会走到最后一步，即本程序结束
你是对的。如果您可以编写一种算法，对于任何输入，最终都会始终做出决定，那么问题就是可判定。对于 "is n divisible by 23?" 的问题，考虑以下（坏的）算法：从 i = 1 开始，然后检查 23 * i 是否小于、大于或等于 n。
- 如果小于
n，递增i。 - 如果等于
n,returntrue. - 如果大于
n,returnfalse.
不管n有多大，这个算法最终总会吐出一个答案，因为在23 * i大于之前你只能递增i有限的次数n。这可能会花费大量时间，但出于可判定性的目的，我们不在乎。所以这个算法总是做出决定；因此，问题是可判定的。
将此与 半可判定 问题进行对比。这些问题存在一种算法，如果这是正确答案，它将始终回答 true，但如果正确答案是 false[=47=， 可能永远 运行 ].
最著名的半可判定问题是停机问题：给定一个程序，确定该程序是否曾经停止 运行ning。假设您尝试通过编写一个执行其输入的程序来解决这个问题。如果该执行终止，那么您可以 return true：您知道程序终止，因为您只是看着它这样做。但是如果你等了一段时间它还没有终止，你永远无法确定它是否会终止如果你只是让它 运行 稍微长一点，所以你只需要等待。因此，如果输入程序没有终止，您的程序也不会终止。
因此，对于停机问题有一个算法，如果实际答案为真，则总是 returns true，但如果实际答案为假，则永远 运行s。因此，停机问题是半可判定的。