АССОЦИАТИВНОЕ ИСЧИСЛЕНИЕ это:

АССОЦИАТИВНОЕ ИСЧИСЛЕНИЕ

название, установившееся за исчислениями нек-рого точно охарактеризованного типа, хорошо приспособленными для задания конечно определенных ассоциативных систем ( полугрупп). Термин "А. и." введен А. А. Марковым. Им же было осуществлено построение развернутой теории А. и. (см. [2], гл. VI).

Всякое А. и. определяется указанием нек-рого алфавита А и конечного списка соотношений в А - пар слов в этом алфавите. Слова, входящие в состав соотношений, обычно наз. их частями - левыми и правыми. Допустимым относительно действием над словами в Аназ. любая подстановка одной из частей к.-л. соотношения, принадлежащего а, вместо любого вхождения другой части того же соотношения. А. и. представляет собой разрешение лроизводить, исходя из любого слова Рв А, любые допустимые относительно действия. Обо всех словах , к-рые при этом получаются (в том числе и о самом исходном слове Р), говорят, что они эквивалентны в А. и. (в символич. записи : ). Отношение для любого А. и. рефлексивно, симметрично и тран-зитивно. Кроме того, из следует, что . Это позволяет естественным образом сопоставить всякому А. и. нек-рую конечно определенную ассоциативную систему , взяв в качестве ее элементов классы слов, эквивалентных друг другу в , а в качестве операции умножения в - операцию, естественно индуцируемую операцией соединения слов в А. Так построенная ассоциативная система будет иметь единицу (элемент, представленный пустым словом); элементы , представленные буквами алфавита А, будут составлять для систему порождающих элементов, а список соотношений а будет представлять собой полную систему соотношений между упомянутыми порождающими элементами в том смысле, что элементы , представленные словами и , тождественны в тогда и только тогда, когда и эквивалентны в Таким образом, распознавание тождества элементов в сводится к распознаванию эквивалентности слов в . Отсюда становится понятной важность исследования разрешимости алгоритмической проблемы распознавания эквивалентности слов в произвольном А. и. Эта проблема была впервые сформулирована А. Туз [1]; она заключается в том, что для произвольного А. и. ,. требуется построить алгоритм, к-рый для любой пары слов в алфавите А. и. позволял бы за конечное число шагов выяснить, эквивалентны ли в слова, составляющие эту пару. В алгебраич. интерпретации эта проблема есть проблема тождества для ассоциативной системы . Самому А. Туэ удалось решить ее лишь в весьма частных случаях. В современной интерпретации (после 30-х гг. 20 в.) этой проблемы алгоритм ищется в к.-л. точном смысле слова, напр, частично рекурсивная функция, Тьюринга машина или нормальный алгорифм. При такой модернизации этой проблемы уже становится осмысленным вопрос о том, нельзя ли указать такое конкретное А. и., для к-рого искомый алгоритм оказался бы невозможным. А. А. Марковым [3] и Э. Постом [4] одновременно и независимо были построены неразрешимые А. и., то есть А. и. с неразрешимой алгоритмич. проблемой распознавания эквивалентности слов. Эти результаты дают отрицательное решение модернизированной проблемы А. Туэ. Однако, принимая Чёрча тезис или к.-л. другое, эквивалентное ему предложение считать произведенное в теории алгоритмов уточнение понятия алгоритма адекватным, мы с необходимостью приходим к заключению, что и в начальной постановке проблема Туэ для нек-рого конкретного А. и. решается отрицательно.

Первоначальные примеры А. А. Маркова и Э. Поста были чрезвычайно сложными. В дальнейшем предложены более простые неразрешимые А. и.; напр., А. и. с семью весьма простыми соотношениями (см. [5]), с всего лишь тремя соотношениями (см. [6]); почти полностью решена проблема Туэ в случае А. и. с одним соотношением (см. [7]).

Естественным образом определяется изоморфизм одного А. и. в другое А. и., а также на другое А. и. (см., напр., |2], с. 331 - 34). С алгебраич. точки зрения особый интерес представляет рассмотрение таких свойств А. и., к-рые являются инвариантными относительно изоморфизмов: эти свойства суть свойства абстрактных ассоциативных систем. А. А. Марков (см. [2], с. 331 - 70), основываясь на своих исследованиях по проблеме распознавания эквивалентности слов в А. и., получил весьма общий результат, дающий отрицательное решение практически всех обсуждавшихся в то время алгоритмич. проблем, связанных с основными классификациями А. и. В частности, он показал, что если И - инвариантное свойство А. и. и имеется единичное А. и. со свойством И, а также - А. и., не включаемое ни в какое А. и. со свойством И, то для всякого алфавита с числом букв более трех алгоритмич. проблема распознавания А. и. со свойством Исреди прочих А. и. неразрешима. Из этого результата непосредственно вытекает неразрешимость (для всякого алфавита, содержащего более трех букв) алгоритмич. проблем распознавания единичности А. и., конечности А. и., полугрупповости А. и., включаемости в групповое А. и., изоморфии для пар А. и. Впоследствии было показано (см. [8]), что множество пар изоморфных А. и. является рекурсивно перечислимым; использованный при этом метод позволяет также установить рекурсивную перечислимость ряда инвариантных свойств А. и.

Лит.:[1] Тhue A., "Videnskapsselskapets Skrifter. t. Mat. Naturv. Kl.", 1914, № 10; [2] Mapков А. А., Теория алгорифмов, M., 1954 ("Тр. Матем. ин-та АН СССР", т. 42); [3] его же, "Докл. АН СССР", 1947, т. 55, № 7, с. 587-90; [4] Post Е. L., "J. Symb. Logic", 1947, v. 12, p. 1 - 11; [5] Цейтин Г. С., "Докл. АН СССР", 1956, т. 107, № 3, с. 370-71; [6] Матиясевич Ю. В., "Докл. АН СССР", 1967, т. 173, Mi 6, с. 1264-66; [7] Адян С. И., "Тр. Матем. ин-та АН СССР", 1966, т. 85, с. 1 - 123; [8] Нагорн. <ый Н. M., "Z. math. Logik und Grundl. Math.", 1960, Bd 6, S. 319-24. Н. М. Нагорный.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Смотреть что такое "АССОЦИАТИВНОЕ ИСЧИСЛЕНИЕ" в других словарях:

  • ГРУППОВОЕ ИСЧИСЛЕНИЕ — ассоциативное исчисление, в к ром эффективным образом выполнено естественное групповое требование существования обратной операции. Именно, ассоциативное исчисление наз. Г. и. (см. [1], с. 341), если для него может быть построен инвертирующий… …   Математическая энциклопедия

  • ТУЭ СИСТЕМА — ассоциативное исчисление, названное по имени А. Туэ, к рый впервые сформулировал проблему распознавания равенства слов в ассоциативных системах (проблема Туэ, см. [1]). Если при задании Т. с. допустимыми подстановками считать только подстановки… …   Математическая энциклопедия

  • НОРМАЛЬНЫЙ АЛГОРИФМ — название, закрепившееся за алгоритмами некоторого точно охарактеризованного типа. Наряду с рекурсивными функциями и Тьюринга машинами Н. а. получили известность в качестве одного из наиболее удобных уточнений общего интуитивного представления об… …   Математическая энциклопедия

  • Перцептрон — Логическая схема перцептрона с тремя выходами Перцептрон, или персептрон[nb 1] (англ. perceptron от …   Википедия

  • Персептрон — Логическая схема перцептрона с тремя выходами Перцептрон, или персептрон[nb 1] (англ. perceptron от лат. perceptio  восприятие; нем. perzeptron)  математическая и компьютерная модель восприятия информации мозгом (кибернетическая модель мозга),… …   Википедия

  • МАТРИЦА — прямоугольная таблица состоящая из тстрок и n столбцов, элементы к рой принадлежат нек рому множеству К. Таблица (1) наз. также матрицей над К, или мат рицей размера над K. Пусть совокупность всех матриц над К. Если т=п, то (1) наз. квадратной… …   Математическая энциклопедия

  • МЫШЛЕНИЕ — направленный процесс переработки информации в когнитивной системе живых существ. М. реализуется в актах манипулирования (оперирования) внутренними ментальными репрезентациями, подчиняющимися определенной стратегии и приводящими к возникновению… …   Философская энциклопедия

  • АЛГЕБРА — часть математики, посвященная изучению алгебраических операций. Исторический очерк. Простейшие алгебраич. операции арифметич. действия над натуральными и положительными рациональными числами встречаются в самых ранних математич. текстах,… …   Математическая энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»