Пусть задана некоторая главная универсальная нумерация вычислимых функций. Докажите, что множество номеров машин Тьюринга, которые вычисляют последовательность Каталана, неперечислимо и некоперечислимо

задан 11 Май 18:03

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

Серия искусственных однотипных задач на тему вычислимости, если честно, уже порядком надоела :) Там набор используемых приёмов примерно один и тот же. Ничего нового при этом нет -- приходится только "изобретать" каждый раз нечто вполне стандартное.

Берём алгоритмически неразрешимую проблему -- например, проблему остановки машин Тьюринга на пустой ленте. Поскольку нумерация главная, мы по номеру программы можем "прогнать" её на заданное число шагов.

Для заданной машины M рассматриваем такой процесс: на вход подаётся число n, и мы прогоняем машину M на n шагов. В случае, если машина не остановилась, печатаем n-е число Каталана (оно вычислимо по формуле (2n)!/(n!(n+1)!). Если остановилась, печатаем 0. Номер соответствующей программы принадлежит множеству из условия <=> машина M никогда не останавливается. Если бы мы умели перечислять все программы из условия, то имели бы свидетельство о том, что машина никогда не останавливается. Поскольку множество останавливающихся за конечное время машин перечислимо, это давало бы алгоритм решения проблемы остановки.

В другую сторону (по поводу некоперечислимости): рассмотрим произвольную программу. Подадим на её вход число (можно подать n=0), и начнём делать вычисления. Если она на данном входе останавливается, мы это за конечное время увидим. Если нет, то она точно не входит в число программ, вычисляющих последовательность Каталана. Тогда её номер будет напечатан при перечислении дополнения. Получится решение проблемы остановки программы на данном входе.

ссылка

отвечен 11 Май 20:15

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

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

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

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

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

отмечен:

×883
×52

задан
11 Май 18:03

показан
80 раз

обновлен
11 Май 20:15

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

по почте:

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

по RSS:

Ответы

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

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