Значение на ГРУПОВО СЧИТАНИЕ в математическата енциклопедия
Значение на ГРУПОВО СЧИТАНИЕ в математическата енциклопедия:
асоциативно смятане,в което изискването за естествена група за съществуване на обратна операция е ефективно изпълнено. А именно асоциативното смятане се нарича. G. i. (виж [1], стр. 341), ако за него може да бъде конструиран алгоритъм за обръщане, т.е. такъвалгоритъм,, че за всяка дума P в азбуката на Acalculus са изпълнени следните условия:
1) е дефинирана и също е дума в A;
2) думите и са еквивалентни в празната дума (тук алгоритъмът трябва да се разбира в точния смисъл на думата, например катонормален алгоритъм).
Най-често срещаните са G. и. от специален тип (т.нар. обратно смятане, вижте [2]), за които съществуването на инвертиращ алгоритъм се осигурява чрез правилен подбор на техните азбуки и списъци от съотношения: азбуката на обратното смятане има четна дължина, за всяка от буквите й е изрично посочена нейната обратна буква, а списъкът от съотношения включва пълния набор от т.нар. тривиални отношения, т.е. отношения, чиито десни части са празни думи, а левите части имат формата .
Споменатият пример на П. С. Новиков също дава отрицателно решение на втория основен проблем на Дан - проблемът за разпознаване на двойки думи, спрегнати в даден G. и. По-късно П. С. Новиков [9] дава по-просто отрицателно решение на проблема за конюгацията, независимо от горния пример.
Голям интерес към алгебриката. от гледна точка е изучаването на онези свойства на G. и., които се оказват инвариантни при изоморфизмите на G. и., - това са свойствата на абстрактни крайно дефинирани групи. През 1955 г. С. И. Адян [10]-[12] получава много общ резултат, подобен на резултата на А. А. Марков заасоциативно смятане, което даде отрицателно решение на почти всички известни по това време алгоритми. проблемите, свързани с основните класификации на Г. и. По-специално, той получи отрицателно решение на третия проблем на Dehn, проблема за изоморфността за всяка фиксирана ограничено представена група. Впоследствие подобни резултати са получени от M. Rabin [13].
Неразрешимостта на споменатите алгоритми. проблеми, свързани с G. и., доведоха до отрицателно решение на редица алгоритмични. топологични проблеми.
проблем с хомотопията на пътя. Въз основа на резултатите от С. И. Адян, А. А. Марков получава през 1958 г. отрицателно решение на проблема с хомеоморфина (виж [14]).
Спр.: [1] Марков А. А., Теория на алгоритмите, Москва, 1954 г.; [2] собствен, "Изв. АН СССР. Сер. мат.", 1963, том 27, бр. 907-36; [3] Dehn M., "Math. Ann.", 1911, Bd 71, S. 116; [4] Magnus W., "J. reine und angew. Math.", 1931, Brt 163, № 2, стр. 141-65; [5] П. С. Новиков, „Доклади на Академията на науките на СССР”, 1952 г., т. 85, с. 709-12; [6] негов, За алгоритмичната неразрешимост на проблема за идентичността на думите в теорията на групите, Москва, 1955 г.; [7] Boone W. W., „Indagat. math.“, 1954, v. 16, стр. 231, 492; 1955 г., с. 17, стр. 252-56; 1957 г., с. 19, стр. 22-7, 227-32; [8] Brill on J.L., "Proc. London Math. Soc.", 3 ser., 1958, v. 8, № 32, стр. 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. O., "Ann. Math.", 1958, v. 67, стр. 172-94; [14] А. А. Марков, "Доклади на Академията на науките на СССР", 1958 г., т. 121, № 2, с. 218-20. Н.