Разрешимо ли множество кодов < M > таких машин Тьюринга M, что при всех n ∈ N на любом входе длины n машина M останавливается не более чем за 100n^2 + 100 шагов?

задан 25 Июн '19 13:57

10|600 символов нужно символов осталось
1

Специфика функции f(n)=100n^2+100 здесь не важна -- вместо неё можно взять любую вычислимую.

С каждой машиной Тьюринга M, работающей на пустой ленте, свяжем машину M'(n) с входом n, которая работает следующим образом: она запускает машину M на f(n) шагов (можно на n шагов), и если за это время M останавливается, то мы загоняем программу M' в бесконечный цикл, или заставляем работать достаточно долго (более f(n) шагов). Если же M за это время не останавливается, то мы досрочно останавливаем M'.

Таким образом, если бы мы располагали разрешающим алгоритмом для множество кодов из условия, мы применили бы его к программе M'(n). Если ответ будет, что M'(n) на любом входе работает не более f(n) шагов, это означало бы, что M, по которой строили M'(n), никогда не останавливается. Если же на каком-то входе n работа будет происходить дольше f(n) шагов, это означало бы остановку M за конечное время. Тем самым, мы от противного доказали неразрешимость проблемы из условия, так как проблема остановки неразрешима.

ссылка

отвечен 25 Июн '19 19:18

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

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

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

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

отмечен:

×273

задан
25 Июн '19 13:57

показан
227 раз

обновлен
25 Июн '19 19:18

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

по почте:

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

по RSS:

Ответы

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

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