私はこれが決定可能かどうかと苦労しています：この言語は決定可能ですか？
A = {xは自然数の集合の要素です| xより大きいすべてのyについて、2yは2つの素数の和です。
チューリングマシンに入力すると、決して受け入れられない状態になり、ループすることはないと考えられますそれが拒否されない限り、無限大。しかし、私は、決定可能な言語については、それを決定するアルゴリズムしか存在してはならないことも知っています。必ずしもそれがどのように行われたのかを知る必要はありません。これで、私の一部は決定可能だと思いますか？どちらかを証明する方法を誰かが知っていますか？
この言語は判読可能ですが、証明は少し悪です。
まず、この言語のプロパティについて考えてみましょう。明らかに、nが言語に含まれる自然数である場合、nより大きいすべての数も言語に含まれます。この言語は、いくつかの自然数よりも、すべての自然数より大きい含まれている。この言語は、すべての自然数が含まれてい
言語（1）および（2）はそれぞれ{0,1} *および空の言語であり、両方とも決定可能である（したがって、これらの言語を受け入れるTMは常に停止する）。いずれのnについても、入力が少なくともnであるかどうかを単にチェックするハードコーディングされたnを持つTMを簡単に書くことができるので、フォーム（3）の各言語も決定可能である。したがって、どちらの場合（1,2、または3）に関係なく、言語があなたが提供した言語であることを常に止めるTMが存在するため、あなたの言語は決定可能です。
しかし、この証明は非構造的です。言語が決定可能でなければならないことを示すことはできますが、実際にはそれを受け入れることを止めるTMを見つけることはできません。実際には、Goldbach's Conjecture（2つ以上のすべての偶数が2つの素数の合計であるかどうかにかかわらず）が数学における未解決の問題であるため、TMがどれであるかを知る人はいません。
希望すると便利です。