210
правок
Изменения
Нет описания правки
# Множество называется m-полным, если к нему m-сводится любое перечислимое множество. Докажите, что универсальное множество является $m$-полным.
# Докажите, что диагональ универсального множества (множество $\{u | (u, u) \in U\}$ является m-полным.
# Используя теорему о рекурсии, докажите, что язык программ, которые останавливаются на пустом любом вводе, является неразрешимым. Является ли этот язык перечислимым?
# Используя теорему о рекурсии, докажите, что язык программ, которые не останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым?
# Используя теорему о рекурсии, докажите, что язык программ, которые допускают бесконечное число слов, является неразрешимым.
# Докажите, что для любой всюду определенной вычислимой функции $f$ найдется бесконечно много значений $n$, для которых $BB(n) > f(n)$.
# Пусть для любой строки $s$ выполнено $K(s) \ge f(s)$, где $f$ — всюду определенная вычислимая функция. Докажите, что найдется константа $C$, такая что $f(s) \le C$ для любой $s$.
# Рассмотрим функцию $S(n, x)$, равную максимальной длине строки, выводимой программой длины $n$ на пустом входе$x$. Докажите, что $S(n, x)$ невычислима.# Рассмотрим произвольную произвольные всюду определенную вычислимую функцию определенные вычислимые функции $f , g : \Sigma^* \to \Sigma^*$. Докажите, что существует программа $p$, что $L(f(p)) = L(fg(p))$.
