Этот язык разрешим?

Question

Я борюсь с тем, является ли это разрешимым:

A = {x является элементом набора натуральных чисел |для каждого y, большего x, 2y является суммой двух простых чисел}

Я склонен думать, что это разрешимо, учитывая тот факт, что при подаче в машину Тьюринга он никогда не достигнет состояния принятия ицикл на бесконечность, если он не отвергает.Однако я также знаю, что для того, чтобы язык был разрешимым, должен существовать только алгоритм для его определения;нам не обязательно знать, как это делается.При этом часть меня считает, что это разрешимо?Кто-нибудь знает, как это доказать?

Answer 1

Этот язык является надёжным, хотя доказательства немного злые.

Для начала давайте подумаем о свойствах этого языка.Ясно, что если n - это натуральное число, содержащееся в языке, то каждое число, большее n, также присутствует в языке.Таким образом, существует три возможных формы, которые может принимать этот язык:

1. Этот язык содержит все натуральные числа, или
2. Этот язык не содержит натуральных чисел, или
3. Этот языксодержит все натуральные числа, превышающие некоторое натуральное число n.

Языки (1) и (2), соответственно, {0, 1} * и пустой язык, оба из которых являются разрешимыми (такЕсть ТМ, которые всегда останавливаются и принимают эти языки).Каждый язык формы (3) также разрешим, потому что для любого n мы можем легко написать TM с жестко закодированным n, который просто проверяет, является ли ввод по крайней мере n.Следовательно, независимо от того, какой случай является истинным (1, 2 или 3), существует некоторая TM, которая всегда останавливает, чей язык является тем языком, который вы указали, так что ваш язык может быть решаемым.это доказательство неконструктивно.Мы можем показать, что язык должен быть разрешимым, но на самом деле мы не можем найти ТМ, который всегда останавливается и принимает его!На самом деле, никто не знает, что это за ТМ, потому что Гипотеза Гольдбаха (является ли каждое четное число, большее двух, суммой двух простых чисел) - открытая проблема в математике.

Надеюсь, этопомогает!