задача по теории алгоритмов

[Greenbear]

У нас есть бесконечное вычислимое несобственное подмножество множества простых чисел, рассмотрим множество таких чисел в разложении которого участвуют только данные простые числа, может ли данное множество быть невычислимым?

[nikvic]

Greenbear в сообщении #660664 писал(а):

бесконечное вычислимое несобственное подмножество множества простых чисел

А это что за зверь? Есть ли алгоритм, дающий ответ да/нет для всякого простого числа?

[Greenbear]

По одной теореме множество вычислимо <=> когда одновременно и оно само и его дополнение вычислимо перечислимо, из этого следует что простые числа вычислимы, но у меня такое смутное сомнение, что этот алгоритм тут все равно не поможет, но он точно есть, однозначно!

[nikvic]

Greenbear в сообщении #660670 писал(а):

По одной теореме множество вычислимо <=> когда одновременно и оно само и его дополнение вычислимо перечислимо, из этого следует что простые числа вычислимы

Это скорее определение. Сойдёт

Тогда всё в порядке: достаточно проверить на принадлежность числа Вашему множеству простые множители данного числа - на принадлежность заданному множеству простых чисел.

[Greenbear]

Спасибо, попробуем