211
правок
Изменения
Нет описания правки
# Пусть для любой строки $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(g(p))$.# Рассмотрим произвольные всюду определенные вычислимые функции $f, g : \Sigma^* \to \Sigma^*$. Докажите или опровергните, что существует программа $p$, что $L(f(g(p))) = L(g(f(p)))$.
