Читать онлайн «Кибернетический сборник. Новая серия. Выпуск 11»

Кибернетический сборник НОВАЯ СЕРИЯ ВЫПУСК 11 Сборник переводов Под редакцией О. Б. ЛУПАНОВА ИЗДАТЕЛЬСТВО „МИР" Москва 1974 УДК 519. 95 Научный совет по кибернетике Академии наук СССР Продолжение новой серии кибернетических сборников, публика- публикация которой начата издательством «Мир» в 1965 г. В данном вы- выпуске большой интерес представит обзорная статья известных уче- ученых Хартманиса и Хопкрофта по теории сложности вычислений, а также статья Сэлтона, в которой излагаются некоторые новые ре- результаты из области информационного поиска. В сборник вошли также работы зарубежных авторов по теории кодирования, теории автоматов и по различным приложениям кибернетики. Сборник рассчитан на научных работников, инженеров, аспиран- аспирантов и студентов различных специальностей, занимающихся и интере- интересующихся кибернетикой в ее теоретическом аспекте. Н. *Вазынина. Художник Н. К. Сапожников. Художественный редактор В. И. Шаповалов. Технический редактор 3. И. Резник. Корректор Т. С. Лаврова Сдано в набор 5/V 1974 г. Подписано к печати 2/Х 1974 г. Бумага № 2 60X907ie. €,25 бум. л. 12,5 печ. л. Уч. -изд. л. 12,19. Изд. № 1/7806. Цена 1 р. 43 к. Зак. 210 ИЗДАТЕЛЬСТВО €МИР» Москва, 1-й Рижский пер. , 2 Ордена Трудового Красного Знамени Ленинградская типография № 2 имени Евгении Соко- Соколовой Союзполиграфпрома при Государственном комитете Совета Министров СССР по де- делам издательств, полиграфии и книжной торговли. 198052, Ленинград, Л-52, Измайловский проспект, 29 математические вопросы Базисы для эквациональных теорий полугрупп0 /7. Перкинс 1. ВВЕДЕНИЕ Удивительно трудными могут оказаться некоторые вопросы о конечных алгебраических структурах, даже с одной бинарной опе- операцией и всего с несколькими элементами. В [4] Линдон поставил вопрос: всякая ли конечная алгебра (в смысле Г. Биркгофа) обла- обладает конечным множеством тождеств, из которых выводимы все остальные? В той же работе он показал, что для всех двуэлемент- ных алгебр ответ положительный. Затем, однако, он доказал [5], что в общем случае ответ отрицательный, указав конкретный семи- элементный группоид. Позднее четырехэлементный группоид, тож- тождества которого не имеют конечного базиса, описал В. В. Вишин [11] 2). Этот же вопрос о конечном базисе рассматривался в связи с группами. В 1937 г. было доказано (Б. Нейман [7]), что тождества любой абелевой группы имеют конечный базис. Такой же резуль- результат для нильпотентных групп был получен Линдоном [6] и обобщен Хигманом [3]. Самый, вероятно, значительный результат на сегод- сегодняшний день — это положительное решение вопроса для всех ко- конечных групп, данное Оутс и Пауэллом в их весьма «теоретико- групповой» статье [8]. Интересный вопрос о том, существует ли группа, не имеющая конечного базиса тождеств, все еще открыт3). Цель настоящей статьи — получить положительный ответ на вопрос о конечной базируемости тождеств для всех коммута- коммутативных полугрупп и всех равномерно периодических полугрупп, 1) Peter Perkins, Bases for equational theories of semigroups, Journal of Al- Algebra, 11 A968), № 2, 298—314. 2) Трехэлементный группоид с этим свойством построен В.