Cтраница 3
Условимся называть ассоциативным исчислением совокупность всех слов в некотором алфавите вместе с какой-нибудь конечной системой подстановок. Чтобы задать ассоциативное исчисление, достаточно указать соответствующие алфавит и систему подстановок. [31]
ГРУППОВОЕ ИСЧИСЛЕНИЕ - ассоциативное исчисление, в к-ром эффективным образом выполнено естественное групповое требование существования обратной операции. Именно, ассоциативное исчисление 91 наз. [32]
Важно отметить, что выделение СОИС представляет собой переход на более высокий уровень абстракции. Использование языка ассоциативных исчислений обеспечивает рассмотрение задач, решаемых человеком, на определенном уровне абстракции. Большой класс конкретных задач из жизни человека может быть формально описан одним ассоциативным исчислением. При этом имеет место абстрагирование от всех несущественных для работы программы свойств, например от указания на то, что нужно получить черный или белый предмет, и выделение только существенных свойств. [33]
Пост, независимо один от другого, построили конкретные примеры ассоциативных исчислений, для каждого из которых проблема эквивалентности слов алгоритмически неразрешима. Тем более не существует алгоритма для распознавания эквивалентности слов в любом ассоциативном исчислении. [34]
Проблема эквивалентности слов для ассоциативных исчислений ( см. § 4) была сформулирована еще в 1914 г. норвежским математиком Туэ. Им же был предложен алгоритм для распознавания эквивалентности слов в некоторых ассоциативных исчислениях специального вида. С тех пор предпринимались многие попытки построить такой общий алгоритм, который для любого ассоциативного исчисления и для любой пары слов в нем позволили бы установить, эквивалентны эти слова или нет. [35]
Проблема эквивалентности слов для ассоциативных исчислений была сформулирована еще в 1914 г. норвежским математиком Туэ. Им же был предложен алгоритм для распознавания эквивалентности слов в некоторых ассоциативных исчислениях специального вида. С тех пор предпринимались многие попытки построить такой общий алгоритм, который для любого ассоциативного исчисления я для любой пары слов в нем позволил установить, эквивалентны эти слова или нет. [36]
В 1955 С. И. Адян [10] - [12] получил весьма общий результат, аналогичный результату А. А. Маркова для ассоциативных исчислений, давший отрицательное решение практически всех, известных в го время алго-ритмич. В частности, им было получено отрицательное решение третьей проблемы Дена - проблемы изо-морфии любой фиксированной конечно определенной группе. [37]
При доказательстве алгоритмической неразрешимости проблемы распознавания самоприменимости был использован метод от противного. С помощью этого метода доказана алгоритмическая неразрешимость множества различных проблем, в том числе и проблема эквивалентности слов для ассоциативных исчислений. [38]
Однако использование этого уровня абстракции неудобно при исследовании мозга. В самом деле, добавление одной новой допустимой подстановки, удовлетворяющей требованиям СОИС ( например, не меняющей числа букв А в слове), хотя и не влияет на эффективность алгоритма, требует использования другого исчисления. В ассоциативном исчислении можно выделить много свойств, не существенных для работ алгоритмов и эвристических программ. Вместе с тем каждая программа оказывается применимой не к одному, а к целому классу ассоциативных исчислений. В связи с этим целесообразно перейти на более высокий уровень абстракции, выделив класс ассоциативных исчислений, для которого будет применима эвристическая программа. Для этого во всех ассоциативных исчислениях, входящих в класс, необходимо выделить то, что существенно для работы программы, и отбросить те свойства, которые в данном случае несущественны. В этом случае мы приходим к использованию системы СОИС, так как именно ограничения определяют работу программ и они явятся хорошими критериями для классификации информационных задач. [39]
Итак, слова ас и ассс неэквивалентны. Приведенное в примере 4 подробное решение проблемы слов для конкретного ассоциативного исчисления во многом характеризует понятия и методы, возникающие и при исследовании проблемы слов для других исчислений. Нам остается еще пояснить содержательный смысл проблемы слов и ее значение в современной алгебре. Это удобно сделать не конкретном примере. [40]
Важно отметить, что выделение СОИС представляет собой переход на более высокий уровень абстракции. Использование языка ассоциативных исчислений обеспечивает рассмотрение задач, решаемых человеком, на определенном уровне абстракции. Большой класс конкретных задач из жизни человека может быть формально описан одним ассоциативным исчислением. При этом имеет место абстрагирование от всех несущественных для работы программы свойств, например от указания на то, что нужно получить черный или белый предмет, и выделение только существенных свойств. [41]
Проблема эквивалентности слов для ассоциативных исчислений ( см. § 4) была сформулирована еще в 1914 г. норвежским математиком Туэ. Им же был предложен алгоритм для распознавания эквивалентности слов в некоторых ассоциативных исчислениях специального вида. С тех пор предпринимались многие попытки построить такой общий алгоритм, который для любого ассоциативного исчисления и для любой пары слов в нем позволили бы установить, эквивалентны эти слова или нет. [42]
Проблема эквивалентности слов для ассоциативных исчислений была сформулирована еще в 1914 г. норвежским математиком Туэ. Им же был предложен алгоритм для распознавания эквивалентности слов в некоторых ассоциативных исчислениях специального вида. С тех пор предпринимались многие попытки построить такой общий алгоритм, который для любого ассоциативного исчисления я для любой пары слов в нем позволил установить, эквивалентны эти слова или нет. [43]
Однако использование этого уровня абстракции неудобно при исследовании мозга. В самом деле, добавление одной новой допустимой подстановки, удовлетворяющей требованиям СОИС ( например, не меняющей числа букв А в слове), хотя и не влияет на эффективность алгоритма, требует использования другого исчисления. В ассоциативном исчислении можно выделить много свойств, не существенных для работ алгоритмов и эвристических программ. Вместе с тем каждая программа оказывается применимой не к одному, а к целому классу ассоциативных исчислений. В связи с этим целесообразно перейти на более высокий уровень абстракции, выделив класс ассоциативных исчислений, для которого будет применима эвристическая программа. Для этого во всех ассоциативных исчислениях, входящих в класс, необходимо выделить то, что существенно для работы программы, и отбросить те свойства, которые в данном случае несущественны. В этом случае мы приходим к использованию системы СОИС, так как именно ограничения определяют работу программ и они явятся хорошими критериями для классификации информационных задач. [44]
Однако использование этого уровня абстракции неудобно при исследовании мозга. В самом деле, добавление одной новой допустимой подстановки, удовлетворяющей требованиям СОИС ( например, не меняющей числа букв А в слове), хотя и не влияет на эффективность алгоритма, требует использования другого исчисления. В ассоциативном исчислении можно выделить много свойств, не существенных для работ алгоритмов и эвристических программ. Вместе с тем каждая программа оказывается применимой не к одному, а к целому классу ассоциативных исчислений. В связи с этим целесообразно перейти на более высокий уровень абстракции, выделив класс ассоциативных исчислений, для которого будет применима эвристическая программа. Для этого во всех ассоциативных исчислениях, входящих в класс, необходимо выделить то, что существенно для работы программы, и отбросить те свойства, которые в данном случае несущественны. В этом случае мы приходим к использованию системы СОИС, так как именно ограничения определяют работу программ и они явятся хорошими критериями для классификации информационных задач. [45]