Cтраница 2
Так просто решал он проблему равенства разных народов в составе России. [16]
Не известно, разрешима ли проблема равенства в группе с двумя соотношениями. [17]
Теорема 6.36. Проблема изоморфизма и проблема равенства рядов Гильберта двух мономиалъных подалгебр матричных алгебр алгоритмически неразрешимы. [18]
Конечно порожденная группа О имеет разрешимую проблему равенства тогда и только тогда, когда существует инъективный гомоморфизм ф / О - S, где S - простая подгруппа конечно определенной группы ( см. А В. [19]
К данной проблеме нетрудно свести проблему равенства языков, порожденных контекстно-свободными грамматиками. Однако известен более сильный результат: проблема слабой эквивалентности неразрешима в классе унарных рекурсивных схем. [20]
Следовательно, в группе G разрешима проблема равенства. [21]
Связь между финитной аппроксимируемостью и разрешимостью проблемы равенства получается из следующих соображений. Пусть ФА-группа G задана конечным кодом. Тогда множество a ( TV) является рекурсивно перечислимым множеством. [22]
Связь между финитной аппроксимируемостью и разрешимостью проблемы равенства получается из следующих соображений. Пусть ФА-группа G задана конечным кодом. Тогда множество a ( N) является рекурсивно перечислимым множеством. [23]
Для построения машины Тьюринга, решающей проблему равенства слов для бесконечной группы, требуется больше усилий, что связано с тем, что ее основные операции слишком примитивны. Несмотря на свою кажущуюся элементарность, машины Тьюринга столь же мощны, как любой другой вид идеализированного компьютера, который был до сих пор придуман. [24]
Алгебра с конечной полной системой соотношений имеет разрешимую проблему равенства. [25]
В алгебрах Ли с одним определяющим соотношением разрешима проблема равенства. [26]
Перед тем, как перейти к приложениям неразрешимости проблемы равенства слов в некоторых представлениях, мы опишем другой подход к построению групп с неразрешимой проблемой слов, принадлежащий Хигману [98]; этот подход вскрывает глубокую связь между идеями вычислимости и конечной представимостью групп. Множество А слов над SB называется эффективно перечислимым, если существует некоторая эффективная процедура, перечисляющая элементы А. Следует подчеркнуть, что это вовсе не означает, что элементы множества А перечисляются таким образом, что для произвольного слова возможно за конечное число шагов установить, лежит оно в А или нет. Мы оставим интуитивным понятие эффективной процедуры и заметим только, что его точное определение аппелирует к понятиям наподобие машины Тьюринга. [27]
Таким образом, эквивалентность схем сводится к изучению синтаксической проблемы равенства языков определенного вида. [28]
Относительно недавно были найдены алгебраические характеризации групп с разрешимой проблемой равенства. [29]
Для группы Я ( ф) может оказаться неразрешимой проблема равенства слов, а также может не быть выполненным условие максимальности для нормальных подгрупп. [30]