244
правки
Изменения
Нет описания правки
# Покажите, что множество $X$ можно представить в виде $A\setminus (B \setminus C)$, где $A \supset B \supset C$ — перечислимые множества, если и только если его можно представить в виде симметрической разности трёх перечислимых множеств.
# Покажите, что существует множество, которое можно представить в виде симметрической разности трёх перечислимых множеств, но нельзя представить в виде симметрической разности двух перечислимых множеств
# Докажите, что если $A$ неперечислимо и $A \le_m B$, то $B$ неперечислимо.
# Пусть $A$ перечислимо и $\mathbb{N} \setminus A \le_m A$. Что можно сказать про $A$?
# Пусть $A$ перечислимо и $A \le_m \mathbb{N} \setminus A$. Что можно сказать про $A$?
# Пусть дана функция $f : A \to \mathbb{N}$. Ее продолжением на множество $B \supset A$ называется функция $g:B \to \mathbb{N}$, что если $x\in A$, то $g(x) = f(x)$. Докажите, что существует вычислимая функция $f$, у которой не существует всюду определенного вычислимого продолжения.
# Два перечислимых множества $A$ и $B$, где $A \cap B = \varnothing$ называются неотделимыми, если не сущестует разрешимых множеств $X$ и $Y$, таких что $A \subset X$, $B \subset Y$, $X \cap Y = \varnothing$. Покажите, что существуют неотделимые множества. Указание: рассмотрите множества пар $\langle p, x\rangle$, где $p$ - программа, возвращающая целое число, для некоторого условия.
# Обобщите определение неотделимых множеств на счетное семейство множеств. Докажите, что существует счетное семейство неотделимых множеств.
# Докажите, что множество программ, допускающих заданное конечное множество слов $x_1, \ldots, x_n$, перечислимо, но не разрешимо.
# Докажите, что множество программ, допускающих бесконечное множество слов не разрешимо.
# Докажите, что множество программ, зависающих на любом входе, не разрешимо.
# Докажите, что множество программ, останавливающихся на своём собственном исходном коде, перечислимо, но не разрешимо.
# Язык ограниченной задачи останова (bounded halting) $BH = \{ (p, t) | p$ завершается на пустом входе за $t$ шагов $\}$. Докажите, что $BH$ разрешим.
# Докажите, что существует разрешимое множество пар, проекция которого на одну из осей не является разрешимой.
# Докажите, что существует разрешимое множество пар, проекция которого на каждую из осей не является разрешимой.
# Некоторое множество $S$ натуральных чисел разрешимо. Разложим все числа из $S$ на простые множители и составим множество $D$ всех простых чисел, встречающихся в этих разложениях. Можно ли утверждать, что множество $D$ перечислимо?
# Некоторое множество $S$ натуральных чисел разрешимо. Разложим все числа из $S$ на простые множители и составим множество $D$ всех простых чисел, встречающихся в этих разложениях. Можно ли утверждать, что множество $D$ разрешимо?
# Множество $A \subset \mathbb{N} \times \mathbb{N}$ разрешимо. Можно ли утверждать, что множество «нижних точек» множества $A$, то есть множество $B = \{\langle x,y\rangle | (\langle x,y\rangle \in A)$ и $(\langle x,z\rangle \not\in A$ для всех $z < y)\}$ является разрешимым?
# В предыдущем задании можно ли утверждать, что $B$ перечислимо, если $A$ перечислимо?
# Существует ли множество натуральных чисел $A$, к которому m-сводится любой множество натуральных чисел?
# Множество называется m-полным, если к нему m-сводится любое перечислимое множество. Докажите, что универсальное множество является $m$-полным.
# Докажите, что диагональ универсального множества (множество $\{u | (u, u) \in U\}$ является m-полным.
