Изменения
Нет описания правки
# Множество $A$ называется иммунным, если оно бесконечно, но не является эффективно бесконечным. Множество называется простым, если оно перечислимо, а его дополнение иммунно. Докажите, что существует простое множество. Указание: рассмотрите множество $T = \left\{\langle p, x\rangle | p(x) = 1, x > 2p\right\}$.
# Докажите, что множество является иммунным тогда и только тогда, когда оно не содержит бесконечных разрешимых подмножеств.
# Два перечислимых множества $A$ и $B$, где $A \cup cap B = \varnothing$ называются неотделимыми, если не сущестует разрешимых множеств $X$ и $Y$, таких что $A \subset X$, $B \subset Y$, $X \cup Y = \varnothing$. Покажите, что существуют неотделимые множества. Указание: рассмотрите множества пар $\langle p, x\rangle$, где $p$ - программа, возвращающая целое число, для некоторого условия.
# Обобщите определение неотделимых множеств на счетное семейство множеств. Докажите, что существует счетное семейство неотделимых множеств.
# Докажите, что существует вычислимая функция $f$, у которой не существует всюду определенного вычислимого продолжения.
