Изменения
Нет описания правки
# Пусть множество пар $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)
</wikitex>
