1632
правки
Изменения
м
rollbackEdits.php mass rollback
# Вещественное число $\alpha$ называют перечислимым снизу, если множество всех рациональных чисел, меньших $\alpha$, перечислимо. Перечислимость сверху определяется аналогично. Докажите, что число $\alpha$ перечислимо снизу тогда и только тогда, когда оно является пределом некоторой вычислимой возрастающей последовательности рациональных чисел.
# Докажите, что вещественное число вычислимо тогда и только тогда, когда оно перечислимо снизу и сверху.
# Покажите, что следующие три свойства множества $X$ равносильны: (1) $X$ можно представить в виде $A \setminus B$, где $A$ — перечислимое множество, а $B$ — его перечислимое подмножество; (2) $X$ можно представить в виде $A \setminus B$, где $A$ и $B$ — перечислимые множества; (3) $X$ можно представить в виде симметрической разности двух перечислимых множеств.
# Покажите, что множество $X$ можно представить в виде $A\setminus (B\setminus C)$, где $A \supset B \supset C$ — перечислимые множества, если и только если его можно представить в виде симметрической разности (суммы по модулю 2) трёх перечислимых множеств.
# Пусть $A(x,y)$ - вычислимая функция от двух аргументов. Докажите, что для любого $x$ функция $A_x(y)=A(x, y)$ как функция одного аргумента - вычислима.
# Пусть $A(x,y)$ - функция от двух аргументов и для любого $x$ функция $A_x(y)=A(x, y)$ как функция одного аргумента - вычислима. Значит ли это. что функция $A$ вычислима как функция двух аргументов?
# Функция $f$ называется продолжением функции $g$, если для любого $n$, такого что $g$ определена, $f$ также определена и $f(n) = g(n)$. Докажите, что существует вычислимая функция $d(n)$, такая что никакая всюду определенная вычислимая функция $f(n)$ не является ее продолжением.
# Пусть множество пар $A=\{(x, y)\}$ перечислимо. Можно ли утверждать, что множество $B$ минимальных парных для каждого $x$ ($B = \{(x, y)| (x, y) \in A \wedge (x, z)\in A \Rightarrow z \ge y\}$ перечислимо?
# Пусть множество пар $A=\{(x, y)\}$ разрешимо. Можно ли утверждать, что множество $B$ минимальных парных для каждого $x$ ($B = \{(x, y)| (x, y) \in A \wedge (x, z)\in A \Rightarrow z \ge y\}$ перечислимо? Разрешимо?
# Реализуйте на машине Тьюринга проверку, что слово является палиндромом
# Реализуйте на машине Тьюринга проверку, что слово является тандемным повтором
# Реализуйте на машине Тьюринга прибавление 1 к числу (получив на вход двоичное число x, МТ должна заменить его на x + 1 и завершить работу)
# Реализуйте на МТ сложение двух чисел (числа в двоичном формате) а) б)
# Реализуйте на МТ умножение двух чисел (числа в двоичном формате) а) б)
# Реализуйте на МТ сравнение двух чисел (числа в двоичном формате) а) б)
# Докажите, что если на МТ можно реализовать функцию f и функцию g, то можно реализовать функцию f(g)
# ХМУ 9.4.1 а
# ХМУ 9.4.1 б
# ХМУ 9.4.1 в
# ХМУ 9.4.2
# ХМУ 9.4.3
# ХМУ 9.4.4
# Пусть $a = (a_1, a_2, ..., a_n)$ - список слов над алфавитом $\Sigma$. Обозначим как $L_a$ множество слов над алфавитом $\Sigma \cup \{[1], [2], ..., [n]\}$, которые порождаются грамматикой $S \rightarrow a_i S[i]$, $S \rightarrow \varepsilon$. Докажите, что дополнения языку $L_a$ является КС-языком. Указание: постройте соответствующий МП-автомат
# Докажите, что проблема пустоты пересечения языков двух КС-грамматик неразрешима
# Докажите, что проблема равенства языков двух КС-грамматик неразрешима
# Докажите, что проблема равенства языка КС-грамматики и регулярного языка неразрешима
# Докажите, что проблема пустоты дополнения КС-языка неразрешима
# Докажите, что проблема включения одного КС-языка в другой неразрешима
# ХМУ, стр 418, 9.5.1
# ХМУ, стр 418, 9.5.2
# ХМУ, стр 418, 9.5.3
</wikitex>
