$%X$% - перечислимое множество, $%X \subset N$%
Верно ли, что существует машина Тьюринга печатающая элементы $%X$% в порядке возрастания?

задан 2 Ноя '16 19:00

Не обязательно. Если существует машина, печатающая элементы бесконечного множества в порядке возрастания, то оно разрешимо. Поэтому рассматриваем любой из примеров перечислимых, но не разрешимых множеств, и получаем контрпример.

(2 Ноя '16 22:07) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×113

задан
2 Ноя '16 19:00

показан
243 раза

обновлен
2 Ноя '16 22:07

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

по почте:

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

по RSS:

Ответы

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

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