Изменения

# Используя теорему о рекурсии, докажите, что язык программ, которые останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым? Как по-другому можно доказать неразрешимость этого языка?# Используя теорему о рекурсии, докажите, что язык программ, которые не останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым? Как по-другому можно доказать неразрешимость этого языка?# Используя теорему о рекурсии, докажите, что язык программ, которые допускают бесконечное число слов, является неразрешимым. Как по-другому можно доказать неразрешимость этого языка?# Покажите, что существует счётное число непересекающихся перечислимых множеств, никакие два из которых нельзя отделить разрешимым множеством. (Шень, задание 28)# Шень, задание 29# Шень, задание 30# Шень, задание 31# Докажите, что существуют две различные программы $p$ и $q$, такие что программа $p$ печатает текст программы $q$, а программа $q$ печатает текст программы $p$.# Докажите, что существует бесконечная последовательность различных программ $p_i$, такая что $p_i$ печатает текст программы $p_{i+1}$.# Докажите, что существует бесконечная последовательность различных программ $p_i$, такая что $p_1$ печатает пустую строку, а $p_i$ печатает текст программы $p_{i-1}$.# Докажите, что для любого конечного $n$ существует последовательность программ $p_1, p_2, \ldots, p_n$, что $p_i$ печатает текст $p_{i+1}$, а $p_n$ печатает текст $p_1$.# Рассмотрим два множества $A$ и $B$. Назовём их вычислимо изоморфными, если существует всюду определенная вычислимая биекция $\varphi$, такая что $x \in A$ тогда и только тогда, когда $\varphi(x) \in B$. Приведите пример бесконечных вычислимо изоморфных множеств.# Докажите или опровергните, что любые два бесконечных разрешимых множества являются вычислимо изоморфными.# Докажите или опровергните, что любые два бесконечных перечислимых множества являются вычислимо изоморфными.# Множество $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# ХМУ 9.22 (а)# ХМУ 9.22 (б)# ХМУ 9.22 (в)# ХМУ 9.22 (г)# ХМУ 9.22 (д)# ХМУ 9.22 (е)# ХМУ 9.5.1