Изменения

Перейти к: навигация, поиск

Список заданий по ДМ 2к 2019 весна

62 байта добавлено, 23 апрель
Нет описания правки
# Множество $A$ называется m-сводимым к $B$, если существует вычислимая всюду определенная функция $f$, для которой $x \in A$ тогда и только тогда, когда $f(x) \in B$. Пишут $A \le_m B$. Докажите, что если $A$ неразрешимо и $A \le_m B$, то $B$ неразрешимо.
# Докажите, что если $A$ неперечислимо и $A \le_m B$, то $B$ неперечислимо.
# Верно ли, что для любого непустого $A$ с непустым дополнением выполнено $A \le_m \mathbb{N} \setminus A$?
# Пусть $A$ перечислимо и $\mathbb{N} \setminus A \le_m A$. Что можно сказать про $A$?
# Пусть $A$ перечислимо и $A \le_m \mathbb{N} \setminus A$. Что можно сказать про $A$?
Анонимный участник

Навигация