Пусть задана некоторая главная универсальная нумерация вычислимых функций. Классифицируйте множество пар (n, m), таких что n-ая вычислимая функция определена на m, а m-ая вычислимая функция не определена на n, в арифметической иерархии, доказав в том числе оценку снизу, и докажите или опровергните его m-полноту на соответствующем уровне.

(Возможно, надо как-то использовать тот факт, что множество пар (m, n) - неперечислимо и некоперечислимо)

задан 17 Июн 20:18

Возможное решение: К - множество номеров самоприменнимых программ. М - множество пар номеров программ, удовлетворяющих условию Нужно доказать, что ¬К m-сводится М. Для этого достаточно доказать, что К м-сводится к ¬М. (как это делать можно посмотреть тут: https://lectoriy.mipt.ru/lecture/Maths-MathemLogic-L22-Musatov-150325.02 51:46) Знаем, что К принадлежит Σ1 и м-полно в нем. Следовательно, ¬К принадлежит П1 и м-полно в нем. (Ответ на вопрос почему это так, возможно, можно найти в Шене) ¬К <=m M значит M m-полно в классе П1.

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

Ваш ответ

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

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

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

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

отмечен:

×778
×42

задан
17 Июн 20:18

показан
53 раза

обновлен
19 Июн 21:52

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

по почте:

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

по RSS:

Ответы

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

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