Как опровергнуть или доказать, что $%K\le_m Empty$% ?

$%K=\{p\in N: U(p,p)\downarrow\}$% множество номеров программ, которые всегда останавливаются при запуске на себе

$%Empty=\{p\in N:U(p,x)\uparrow \forall x\}$% множество номеров программ, которые определяют нигде не определенную функцию

При этом известно, что $%K\le_mEmpty^c$% (c=complement)

задан 30 Июл 2:38

изменен 30 Июл 2:38

И вдогонку:почему $%K\not\le_m K^c$% ?

(30 Июл 4:41) logic

Нашел такое доказательство К с чертой = дополнение к К = К с индексом с в моих обозначениях. https://i.stack.imgur.com/xqhHT.png Но мне кажется тут используется разрешимость дополнения к К. Разве оно разрешимо?

(4 Авг 21:31) logic
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×886

задан
30 Июл 2:38

показан
39 раз

обновлен
4 Авг 21:31

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

по почте:

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

по RSS:

Ответы

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

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