Пусть S - разрешимое множество натуральных чисел. D - множество всех простых делителей множества S. Всегда ли верно, что D - разрешимо?

задан 18 Сен '19 14:05

возвращен 18 Сен '19 18:45

falcao's gravatar image


267k63751

@Masha0102: нельзя удалять условия задач (а тем более уже решённых) -- это нарушает правила форума. Я всё вернул на место; вопрос закрываю.

(18 Сен '19 18:46) falcao
10|600 символов нужно символов осталось

Вопрос был закрыт. Причина - "Проблема не актуальна". Закрывший - falcao 18 Сен '19 18:46

0

Занумеруем все машины Тьюринга и все простые числа. В множество S включаем все числа вида p(m)^n, если машина с номером m остановилась не более чем за n шагов. Других чисел в S нет. Оно разрешимо, так как по данному числу вида p^n, где p простое (другие числа не принадлежат S) мы находим номер m такой, что p=p(m) и запускаем m-ю машину на n шагов. Если она остановилась, ответ "да"; иначе ответ "нет".

Легко видеть, что простое число p=p(m) является делителем некоторого числа из S тогда и только тогда, когда m-я машина останавливается за конечное число шагов. Но эта проблема алгоритмически неразрешима, поэтому D неразрешимо.

ссылка

отвечен 18 Сен '19 15:50

10|600 символов нужно символов осталось
Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×685
×7

задан
18 Сен '19 14:05

показан
400 раз

обновлен
18 Сен '19 18:46

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru