Cтраница 2
Относительно проблемы распознавания свойств ассоциативных исчислений, Докл. [16]
Цейтин доказывает, что для данного ассоциативного исчисления не может быть единого алгоритма для распознавания эквивалентности любой пары слов. [17]
Из нее сразу же следует существование неразрешимых двусторонних ассоциативных исчислений, которое и составляло утверждение основной теоремы этого раздела. [18]
Позднее советским математиком Г. С. Цейтиным был построен пример ассоциативного исчисления, насчитывающего всего лишь семь допустимых подстановок, для которого проблема эквивалентности слов была также алгоритмически неразрешима. [19]
Пост, независимо один от другого, построили конкретные примеры ассоциативных исчислений, для каждого из которых проблема эквивалентности слов алгоритмически неразрешима. Тем более не существует алгоритма для распознавания эквивалентности слов в любом ассоциативном исчислении. [20]
Так, в классе всех полугрупп конечно определенная полугруппа задается ассоциативным исчислением Туэ. В классе всех ассоциативных алгебр конечно определенная алгебра представляется в виде фактор-алгебры свободной ассоциативной алгебры. Однако такое задание вряд ли может быть полезным для эффективных вычислений. Дело в том, что при таком способе задания проблема равенства слов и проблема вхождения в идеал оказываются алгоритмически неразрешимыми. После этого трудно ожидать, что какие-либо разумные свойства алгебраических объектов будут эффективно распознаваемы. Действительно, известны марковские свойства, алгоритмическая нераспознаваемость которых доказана. [21]
Сейчас мы объясним, как только что доказанное утверждение о двусторонних ассоциативных исчислениях переводится на алгебраический язык. Ничего нового по существу при этом не утверждается, это просто перевод. [22]
Сопоставление равенств ( 1) - ( 5) с допустимыми подстановками ассоциативного исчисления примера 4 подсказывает следующее предложение, устанавливающее связь между этим исчислением и рассматриваемой системой преобразований квадрата. [23]
Из этой леммы непосредственно вытекает невозможность алгоритма для решения проблемы эквивалентности слов в ассоциативных исчислениях. Действительно, такой алгоритм решал бы одновременно и проблему переводимости слов посредством ориентированных подстановок в заключительные слова. Теорема 2 утверждает невозможность такого алгоритма. [24]
Для этого мы покажем, что работу любой машины Тьюринга можно в некотором смысле моделировать с помощью ассоциативного исчисления, а затем возьмем исчисление, соответствующее машине с неразрешимой проблемой остановки. [25]
Наряду с тензорами, компоненты которых суть числа, можно рассматривать тензоры, компонентами которых служат элементы любого линейного ассоциативного исчисления ( напр. В дальнейшем целесообразность такого расширения понятия тензор иллюстрируется на примерах, заимствованных из 1) теории поверхностей в трехмерном Евклидовом пространстве, 2) векторно-афинорного исчисления. [26]
В следующем параграфе приводится один из вариантов доказательства теоремы о невозможности алгоритма для распознавания эквивалентности слов в любом ассоциативном исчислении. [27]
Существуют, наконец, алгоритмически неразрешимые проблемы, примером которых может служить проблема распознавания эквивалентности слов в любом ассоциативном исчислении. [28]
Содержательный смысл этого требования становится понятным, если, по аналогии с примером 4 из § 4, истолковать слова в любом ассоциативном исчислении как некоторые сложные преобразования, получаемые путем умножения элементарных преобразований, задаваемых соответствующими буквами, образующими это слово. В таком случае пустое слово Д задает тождественное преобразование, ничего не изменяющее ( сравни с § 4), а наличие допустимых подстановок вида аа - Д означает, что для каждого элементарного преобразования ( задаваемого буквой а) существует элементарное преобразование ( задаваемое буквой а) такое, что последовательное их осуществление дает тождественное преобразование. Не вдаваясь в дальнейшие подробности, отметим лишь, что рассмотрение таких множеств преобразований, называемых группами преобразований, представляет исключительно большой теоретический и практический интерес, а само понятие группы является одним из самых основных понятий современной математики. [29]
В 1946 и 1947 гг. советский математик Андрей Андреевич Марков и американский математик Эмиль Пост независимо один от другого построили конкретные примеры ассоциативных исчислений, для каждого из которых проблема эквивалентности слов алгоритмически неразрешима. Тем более не существует алгоритма для распознавания эквивалентности слов в любом исчислении. [30]