これが決定可能かどうかに苦しんでいます：
A = {x は自然数の集合の要素 | x より大きいすべての y に対して、2y は 2 つの素数の和です}
チューリング マシンに供給されると、受け入れ状態に達することはなく、拒否しない限り無限にループするという事実を考えると、これは決定可能であると考える傾向があります。ただし、言語が決定可能であるためには、それを決定するためのアルゴリズムのみが存在する必要があることも知っています。必ずしもそれがどのように行われるかを知る必要はありません。これで、私の一部は決定可能だと思いますか？どちらかを証明する方法を知っている人はいますか？
この言語は決定可能ですが、証明は少し悪いです。
まず、この言語の特性について考えてみましょう。明らかに、n が言語に含まれる自然数である場合、n より大きいすべての数も言語に含まれます。したがって、この言語には次の 3 つの形式があります。
言語 (1) と (2) は、それぞれ {0, 1}* と空の言語であり、どちらも決定可能です (したがって、これらの言語を受け入れる常に停止する TM があります)。フォーム (3) のすべての言語も決定可能です。これは、任意の n に対して、入力が少なくとも n であるかどうかを単純にチェックする n をハードコードした TM を簡単に作成できるためです。したがって、いずれの場合 (1、2、または 3) に関係なく、常に停止する TM が存在し、その言語が指定した言語であるため、その言語は決定可能です。
しかし、そうは言っても、この証明は非構築的です。言語が決定可能でなければならないことを示すことはできますが、それを受け入れる常に停止する TM を実際に見つけることはできません! 実際、ゴールドバッハの予想(2 より大きいすべての偶数が 2 つの素数の和であるかどうか) は数学の未解決の問題であるため、それがどの TM であるかは誰にもわかりません。
お役に立てれば！