RUS  ENG
Полная версия
ЖУРНАЛЫ // Чебышевский сборник // Архив

Чебышевский сб., 2020, том 21, выпуск 4, страницы 56–71 (Mi cheb952)

О «простых» алгоритмически неразрешимых фрагментах элементарной теории бесконечно порожденной свободной полугруппы

В. Г. Дурнев, О. В. Зеткина, А. И. Зеткина

Ярославский государственный университет имени П. Г. Демидова (г. Ярославль)

Аннотация: В статье доказана алгоритмическая неразрешимость $\exists \forall^2 \exists^3$-теории свободной полугрупп счетного ранга, что усиливает классический результат В. Куайна [1] 1946 года об алгоритмической неразрешимости элементарной теории любой нециклической свободной полугруппы.

Ключевые слова: свободные полугруппы, элементарные теории.

УДК: 512+512.5+512.54+512.54.03

Поступила в редакцию: 24.04.2020
Принята в печать: 22.10.2020

DOI: 10.22405/2226-8383-2018-21-4-56-71



© МИАН, 2024