Cтраница 1
Проблема эквивалентности слов для ассоциативных исчислений была сформулирована еще в 1914 г. норвежским математиком Туэ. Им же был предложен алгоритм для распознавания эквивалентности слов в некоторых ассоциативных исчислениях специального вида. С тех пор предпринимались многие попытки построить такой общий алгоритм, который для любого ассоциативного исчисления я для любой пары слов в нем позволил установить, эквивалентны эти слова или нет. [1]
Проблема эквивалентности слов для ассоциативных исчислений ( см. § 4) была сформулирована еще в 1914 г. норвежским математиком Туэ. Им же был предложен алгоритм для распознавания эквивалентности слов в некоторых ассоциативных исчислениях специального вида. С тех пор предпринимались многие попытки построить такой общий алгоритм, который для любого ассоциативного исчисления и для любой пары слов в нем позволили бы установить, эквивалентны эти слова или нет. [2]
Так как проблема эквивалентности слов в полугруппе & алгоритмически неразрешима, то проблема эквивалентности слов в полугруппе ф также алгоритмически неразрешима. [3]
Требуется найти разрешающий алгоритм для проблемы эквивалентности слов в этом исчислении. [4]
Из построения алгебры т видно, что проблема эквивалентности слов в т равносильна проблеме тождественных соотношений ранга т на классе К. [5]
Из этой леммы непосредственно вытекает невозможность алгоритма для решения проблемы эквивалентности слов в ассоциативных исчислениях. Действительно, такой алгоритм решал бы одновременно и проблему переводимости слов посредством ориентированных подстановок в заключительные слова. Теорема 2 утверждает невозможность такого алгоритма. [6]
Так как проблема эквивалентности слов в полугруппе & алгоритмически неразрешима, то проблема эквивалентности слов в полугруппе ф также алгоритмически неразрешима. [7]
Пост, независимо один от другого, построили конкретные примеры ассоциативных исчислений, для каждого из которых проблема эквивалентности слов алгоритмически неразрешима. Тем более не существует алгоритма для распознавания эквивалентности слов в любом ассоциативном исчислении. [8]
Позднее советским математиком Г. С. Цейтиным был построен пример ассоциативного исчисления, насчитывающего всего лишь семь допустимых подстановок, для которого проблема эквивалентности слов была также алгоритмически неразрешима. [9]
В 1946 и 1947 гг. советский математик Андрей Андреевич Марков и американский математик Эмиль Пост независимо один от другого построили конкретные примеры ассоциативных исчислений, для каждого из которых проблема эквивалентности слов алгоритмически неразрешима. Тем более не существует алгоритма для распознавания эквивалентности слов в любом исчислении. [10]
Общая) проблема Туэ - найти алгоритм для решения, при произвольно данных алфавите и словаре, вопроса о том, являются ли два данных слова эквивалентными. Эта проблема известна также как проблема эквивалентности слов, или проблема тождества для полугрупп. [11]
При доказательстве алгоритмической неразрешимости проблемы распознавания самоприменимости был использован метод от противного. С помощью этого метода доказана алгоритмическая неразрешимость множества различных проблем, в том числе и проблема эквивалентности слов для ассоциативных исчислений. [12]
Была поставлена задача построения по возможности более простых примеров. В этом направлении блестящий успех был достигнут ленинградским математиком Г, С. Цейтиным и насчитывающего всего лишь семь допустимых подстановок, проблема эквивалентности слов также алгоритмически неразрешима. В течение последних тридцати лет были выявлены и многие другие алгоритмические проблемы, для которых невозможен разрешающий алгоритм. Для некоторых из них это очень долго не удавалось установить, хотя они уже давно числились в списке кандидатов на алгоритмически неразрешимые проблемы. Лишь в конце 1969 г. молодому ленинградскому математику Ю. В. Мати-ясевичу удалось доказать, что эта знаменитая проблема алгоритмически неразрешима. [13]
R и S называют смежными словами, если они могут быть преобразованы друг в друга однократным применением допустимой подстановки. Последовательность смежных слов называют дедуктивной цепочкой. Слова R и 5 называют эквивалентными и обозначают R - S, если существует дедуктивная цепочка, ведущая от слова R к слову S. Проблема эквивалентности слов состоит в том, что для любых двух слов требуется узнать, эквивалентны они или нет. [14]