Изменения
Нет описания правки
# Покажите, что для всякой вычислимой функции $f$ существует вычислимая функция, являющаяся «псевдообратной» к $f$ в следующем смысле: область определения $g$ совпадает с областью значений $f$, и при этом $f(g(f(x))) = f(x)$ для всех $x$, при которых $f(x)$ определено.
# Докажите, что существует вычислимая функция $f$, у которой не существует всюду определенного вычислимого продолжения.
# Два перечислимых множества $A$ и $B$, где $A \cap B = \varnothing$ называются неотделимыми, если не сущестует разрешимых множеств $X$ и $Y$, таких что $A \subset X$, $B \subset Y$, $X \cup cap Y = \varnothing$. Покажите, что существуют неотделимые множества. Указание: рассмотрите множества пар $\langle p, x\rangle$, где $p$ - программа, возвращающая целое число, для некоторого условия.
# Обобщите определение неотделимых множеств на счетное семейство множеств. Докажите, что существует счетное семейство неотделимых множеств.
# Докажите, что множество программ, допускающих заданное конечное множество слов $x_1, \ldots, x_n$, перечислимо, но не разрешимо.
