Пусть $%U$% - универсальная функция ( определение https://i.stack.imgur.com/McOa9.png )

Рассмотрим множество $%O=\{p:U(p,0) \text{ определена}\}$%. Есть такое доказательство того, что $%O$% неразрешимо:

Рассмотрим $%S=\{q:U(q,q)\text{ останавливается}\}$%. Докажем, что $%S\le_m O$% (этого достаточно). Построим вычислимое отображение $%f:N\to N$% такое что $%q\in S\iff f(q)\in O$%

Определим $%p=f(q)$% как (номер) программы, делающей сделующее:

  • принимает х
  • запускает $%U(q,q)$%
  • возвращает 1

Получается что если $%U(q,q)$% определена, то $%p$% останавливается на всех входах. В противном случае она не останавливается ни на одном входе. То есть выполнено $%q\in S\iff f(q)\in O$%. И $%f$% вычислима, поэтому всё доказано.

Вопрос. В этом видео говорится, что это доказательство неявно использует главную универсальную вычислимую функцию (определение в по ссылке выше) или на "свойство главной универсальной функции". Как именно?

задан 25 Май 8:12

изменен 25 Май 8:23

Смысл того, что универсальная функция является главной, состоит в том, что по номеру программы мы можем эффективно (то есть алгоритмически) восстановить её текст, и далее начать выполнять. Свойство просто быть универсальной несколько слабее, а реально -- есть нумерации со свойством быть главными, и именно они нужны для дальнейшей работы.

(25 Май 14:44) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×883

задан
25 Май 8:12

показан
59 раз

обновлен
25 Май 14:44

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

по почте:

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

по RSS:

Ответы

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

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