АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП 1990 г.

ТЕОРЕМА. Можно указать такое однопараметрическое се­ мейство уравнений (CC,X„...,Xf ,a t,QA) = ^ ( x , x t ....... 0ср , f i t , f i t ) с параметром сс , неизвестными act х Р и константами Д / , Д^ на свободной абелевой полугруппе ^ (такоз подмножество J3 множест­ ва /< !',/> р } , что не существует алгоритма, позволяю­ щего для произвольного натурального числа Ц определить, тлеет ли система I © _ А (*1 ■> • Г *^V* fit) ~ Ц ( 0 +. > X ]/,... , ОГр , d t , fit.) такое решение Jiu . . . t X p * А , . что при X- - степень В качестве следствия доказанной теореш получим алгоритми­ ческую неразрешимость одной задачи для линейных диофантовых сис­ тем. Будем говорить, что пара натуральных чисел t< e t d > V -кр а т- на паре натуральных чисел ( я , / ) , если существует такое натураль­ ное число ri . что <<?,/>= п< a , i > • Ясно, что понятие .W - кратности элементов это просто переформулировка понятия степени элемента при переходе от А ^ с операцией умножения к А / й с операцией слежения . Получаем следующую теорему. ТЕОРЕМА. .Молено указать такую однопараметрическую сис­ тему линейных уравнений с целыми коэффициентами Л Г л ~ . <Г.Р r^U) 0(0 * П а , гу'С!> 'i A w ( а х +£j~i л ^ ^ J и такое подмножество 3 множества | L й < , Р 1 > что не существует алгоритма, позволяющего для произвольного нату­ рального числа П определить, тлеет ли систеш / / л L n ( t ) и > . Р Л С1А Л Гб п * V a *'i * i i- А 5 ^ * 4 (-t <*i ) i (О такое решение < Ж , V* (О r^(X) V )■ oc, (if в натуральных теслах, что при 6 В j V - кратна <ar.f<’, £Г?->. а\ r i « й к o Список использованной литературы I.Бельтюков А.П. Разрешимость универсальной теории натуральных чисел со сложением и делимостью //Записки научи.семинаров ЛОМИ. 1976. Т . 6 Э. J* 7 . С.1Ь - За. . . . . . . ^ Z .iU fututi ц Jtu cfiq&xntiru р го б& т t t i a d d itio n a n d d < r itt6 ie iiy /f Tm,if Лти math Sec /97/. i’ гЗУ P 2 7i-2S3 52