Изменения
Нет описания правки
# Докажите, существует конкретное множество правил двустороннего исчисления $P$, что для него множество пар $(x, y)$, где $x$ эквивалентно $y$ с точностью до $P$ неразрешимо. (Это задание можно переформулировать в терминах полугрупп так: докажите, что существует полугруппа с конечным множеством образующих и конечным множеством соотношений, что проверка равенства слов в этой полугруппе неразрешима)
# Предыдущее задание можно обобщить на группы: докажите, что существует группа с конечным множеством образующих и конечным множеством соотношений, что проверка равенства слов в этой группе неразрешима. Отличие от предыдущего задания: вместе с каждым символом $c$ существует также символ $c^{-1}$ и соотношения $cc^{-1}\leftrightarrow\varepsilon$, $c^{-1}c\leftrightarrow\varepsilon$..
# Докажите, что следующее свойство перечислимых языков является перечислимым: язык содержит палиндром.
# Докажите, что следующее свойство перечислимых языков является перечислимым: язык содержит два слова одинаковой длины.
# Докажите, что следующее свойство перечислимых языков является перечислимым: язык содержит два слова разной длины.
# Докажите, что следующее свойство перечислимых языков не является перечислимым: все слова языка имеют различную длину.
# Докажите, что следующее свойство перечислимых языков не является перечислимым: язык не содержит заданное слово $x$.
# Является ли что следующее свойство перечислимых языков перечислимым: язык содержит пару $(p, x)$, для которой $p(x) = 1$?
# Является ли что следующее свойство перечислимых языков перечислимым: язык содержит пару $(p, x)$, для которой $p(x) \ne 1$?
