Значення ГРУППОВЕ ЗЛІЧЕННЯ в математичній енциклопедії
Значення ГРУППОВЕ ЗЛІЧЕННЯ в математичній енциклопедії:
асоціативне обчислення,в якому ефективним чином виконано природну групову вимогу існування зворотної операції. Саме, асоціативне літочислення зв. Р. в. (див. [1], с. 341), якщо для нього може бути побудований інвертуючий алгоритм, тобто такийалгоритм,що для всякого слова Рв алфавіті Обчислення виконуються такі умови :
1) визначено і також є словом А;
2) слова та еквівалентні в порожньому слові (алгоритм тут слід розуміти в к.-л. точному сенсі слова, напр, як нормальний алгоритм ).
Найбільш уживаними є Р. і. спеціального типу (так зв. інверсивні обчислення, див. [2]), у яких брало існування інвертуючого алгоритму забезпечується належним підбором їх алфавітів і списків співвідношень: алфавіт інверсивного обчислення має парну довжину, для кожної його літери явно вказується зворотна їй до списку співвідношень включається повний набір так зв. тривіальних співвідношень, т. е. співвідношень, праві частини яких брало суть порожні слова, а ліві мають вигляд .
Згаданий приклад П. З. Новікова дає негативне рішення і другий фундаментальної проблеми Дена - проблеми розпізнавання пар слів, пов'язаних у цьому Р. і. Пізніше П. С. Новіков [9] дав більш просте та незалежне від зазначеного прикладу негативне вирішення проблеми сполученості.
Великий інтерес з алгебраїч. точки зору представляє вивчення тих властивостей Р. і., які виявляються інваріантними щодо ізоморфізмів Р. і., - це властивості абстрактних звичайно певних груп. У 1955 С. І. Адян [10]-[12] отримав дуже загальний результат, аналогічний результату А. А. Маркова дляасоціативних обчислень, що дав негативне рішення практично всіх відомих на той час алго-ритміч. проблем, пов'язаних із основними класифікаціями Г. і. Зокрема, їм було отримано негативне вирішення третьої проблеми Дена - проблеми ізоморфії будь-якої фіксованої певної групи. Згодом аналогічні результати отримав М. Рабін [13].
Нерозв'язність згаданих алгоритміч. проблем, що стосуються Р. і., спричинила негативне рішення ряду алгоритмич. проблем топології
проблема гомотопії шляхів. Спираючись на результати С. І. Адяна, А. А. Марков отримав у 1958 р. негативне вирішення проблеми гомеоморфіну (див. [14]).
Лит.: [1] Марков А. А., Теорія алгорифмів, М., 1954; [2] його ж, "Ізв. АН СРСР. Сер. Матем.", 1963, т. 27, № 4, с. 907-36; [3] Dehn M., "Math. Ann.", 1911, Bd 71, S. 116; [4] Magnus W., "J. reine und angew. Math.", 1931, Brt 163 № 2, S. 141-65; [5] Новіков П. С., "Докл. АН СРСР", 1952, т. 85, с. 709-12; [6] його ж, Про алгоритмічну нерозв'язність проблеми тотожності слів у теорії груп, М., 1955; [7] Воone W. W., "Indagat. math.", 1954, v. 16, p. 231, 492; 1955, v. 17, p. 252-56; 1957, v. 19, p. 22-7, 227-32; [8] Вrill on JL, "Proc. London Math. Soc.", 3 ser., 1958, v. 8 № 32, p. 493-506; [9] Новіков П. С., "Ізв. АН СРСР. Сер. Матем.", 1954, т. 18, № 6, с. 485-524; [10] Адян С. І., "Докл. АН СРСР", 1955, т. 103, с. 533-35; [11] його ж, там-таки, 1957, т. 117, № 1, с. 9-12; [12] його ж, "Тр. моск. Мат. об-ва", 1957, т. 6, с. 231-98; [13] Rabin M. О., "Ann. Math.", 1958, v. 67, p. 172-94; [14] Марков А. А., "Докл. АН СРСР", 1958, т. 121 №2, с. 218-20. н.