alt text

задан 17 Июн '19 21:02

Пусть (x,y) in B <=> машина Тьюринга с номером x останавливается не более чем за y шагов. Ясно, что такое свойство разрешимо. Проекция -- множество номеров останавливающихся машин. Оно неразрешимо.

(17 Июн '19 21:17) falcao

@falcao, а почему проекция - неразрешима?

(17 Июн '19 21:22) Matrix

@Matrix: какие примеры неразрешимых множеств Вам известны? Если их не знать, то такую задачу вряд ли можно решить. Мне казалось, что множество номеров машин Тьюринга, которые останавливаются за конечное время (или наоборот -- работают бесконечно долго) -- это наиболее стандартный пример неразрешимого множества. Это следует из неразрешимости проблемы остановки. Но вообще-то курсы теории алгоритмов могут строиться по-разному.

(17 Июн '19 22:29) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,113

задан
17 Июн '19 21:02

показан
138 раз

обновлен
17 Июн '19 22:29

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

по почте:

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

по RSS:

Ответы

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

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