Изменения
Нет описания правки
# Докажите или опровергните, что любые два бесконечных разрешимых множества являются вычислимо изоморфными.
# Докажите или опровергните, что любые два бесконечных перечислимых множества являются вычислимо изоморфными.
# Множество $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 N \setminus A$? ($N$ - множество всех натуральных чисел/слов)
# Пусть $A$ перечислимо и $N \setminus A \le_m A$. Что можно сказать про $A$?
# Пусть $A$ перечислимо и $A \le_m N \setminus A$. Что можно сказать про $A$?
# Существует ли множество натуральных чисел $A$, к которому m-сводится любой множество натуральных чисел?
# Множество называется $m$-полным, если к нему m-сводится любое перечислимое множество. Докажите, что универсальное множество является $m$-полным.
# Докажите, что диагональ универсального множества (множество $\{u | (u, u) \in U\}$ является m-полным.
# Шень 52
# Шень 53
</wikitex>
