Изменения
Нет описания правки
# Докажите, что образ перечислимого множества под действием вычислимой функции перечислим.
# Докажите, что прообраз перечислимого множества под действием вычислимой функции перечислим.
# В этой и последующих задачах вместо разрешимых и перечислимых языков рассматриваются разрешимые и перечислимые множества натуральных чисел. Это на самом деле одно и то же, достаточно установить естественную биекцию между натуральными числами и словами в градуированном лексикографическом порядке. Теорема об униформизации. Пусть $F$ — перечислимое множество пар натуральных чисел. Докажите. что существует вычислимая функция $f$, определённая на тех и только тех $x$, для которых найдётся $y$, при котором $\langle x,y\rangle \in F$, причём значение $f(x)$ является одним из таких $y$
# Даны два перечислимых множества $X$ и $Y$. Докажите, что найдутся два непересекающихся перечислимых множества $X'$ и $Y'$, таких что $X' \subset X$, $Y' \subset Y$, $X' \cup Y' = X \cup Y$.
# Докажите, что если перечислимое множество перечислимо в возрастающем порядке, то оно является разрешимым.
# Докажите, что любое бесконечное перечислимое множество содержит бесконечное разрешимое подмножество.
# Покажите, что для всякой вычислимой функции $f$ существует вычислимая функция, являющаяся «псевдообратной» к $f$ в следующем смысле: область определения $g$ совпадает с областью значений $f$, и при этом $f(g(f(x))) = f(x)$ для всех $x$, при которых $f(x)$ определено.
