这种语言是可判定的吗？
我正在努力解决这是否是可判定的：
A = {x 是自然数集的元素 |对于每个大于x的y，2y是两个素数的和}
我倾向于认为这是可以判定的，因为当输入图灵机时，它永远不会达到接受状态并无限循环，除非它拒绝。然而，我也确实知道，对于一种可判定的语言，必须只存在一种算法来判定它；我们不一定要知道它是如何完成的。有了这个，我的一部分认为这是可以决定的？有谁知道如何证明吗？
I'm struggling with whether or not this is decidable:
A = {x is an element of the set of Natural Numbers | for every y greater than x, 2y is the sum of two primes}
I'm inclined to think that this is decidable given the fact that when fed into a Turing Machine, it will never reach an accept state and loop for infinity unless it rejects. However, I also do know that for a language to be decidable, there must only exist an algorithm to decide it; we don't necessarily have to know how it's done. With this, part of me think that it is decidable? Does anyone know how to prove either?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这种语言是可判定的，尽管证明有点邪恶。
首先，让我们考虑一下这种语言的属性。显然，如果 n 是语言中包含的自然数，则每个大于 n 的数字也在该语言中。因此，该语言可以采用三种可能的形式：
语言 (1) 和 (2) 分别是 {0, 1}* 和空语言，两者都是可判定的（因此存在总是停止接受这些语言的 TM）。 (3) 形式的每种语言也是可判定的，因为对于任何 n，我们可以轻松地编写一个将 n 硬编码到其中的 TM，简单地检查输入是否至少为 n。因此，无论哪种情况成立（1、2 或 3），都存在一些 TM 总是停止，其语言就是您提供的语言，因此您的语言是可判定的。
但话虽如此，这个证明是没有建设性的。我们可以证明该语言必须是可判定的，但我们实际上无法找到总是停止接受它的 TM！事实上，没有人知道它是哪一个 TM，因为哥德巴赫猜想（无论是每个偶数大于二的是两个素数之和）是数学中的一个悬而未决的问题。
希望这有帮助！
This language is decidable, though the proof is a bit evil.
For starters, let's think about the properties of this language. Clearly, if n is a natural number contained in the language, then every number greater than n is also in the language. Thus there are three possible forms this language can take:
Languages (1) and (2) are, respectively, {0, 1}* and the empty language, both of which are decidable (so there are TMs that always halt that accept those languages). Every language of form (3) is also decidable, because for any n we can easily write a TM with n hardcoded into it that simply checks whether the input is at least n. Consequently, no matter which case is true (either 1, 2, or 3), there exists some TM that always halts whose language is the language you've provided, so your language is decidable.
But that said, this proof is nonconstructive. We can show that the language has to be decidable, but we can't actually find the TM that always halts that accepts it! In fact, no one knows which TM it is, because Goldbach's Conjecture (whether every even number greater than two is the sum of two primes) is an open problem in mathematics.
Hope this helps!