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

Покажем, что для произвольна* целых чисел S , t , г имев* место эквивалентность Iе $ ( о 5, а * , а г ) * - ? г - s t . В самом деле, если ^ Л ( а 3, a l, а 1) , то пусть X , i t , 2 - такие элементы группы Fz , что F 2 и Г ( а к X ) £ У а Ч -- а Ч У » 2 - у х ’ 1а Ч Ч’ 1 ( г ) ; 1 $ Гг /, то X : 6 f и существует такое целое число X: , что У = ( u s 6 ) K , тогда 2 - ( а 1 6 ) к 6 ~‘ а ~ * и равенство V ' s t Z ) - ! влечет равенство k - t % а равенство У? ( z ) - 1 дает в свою очередь нужное равен­ ст в о z = i ' k - s t Истинность на формулы i f f l * й / й 11) полагая • _ + x z 6 *, y - - ( a s 8 ) , i - ( a s 8 f 6 ха устанавливаем, - s t Хорошо известно следующее непосредственное следствие резуль­ та т а Ю.В.Магиясевича о диофантносги рекурсивно перечислимых мно­ жеств» /1*1. Для произвольного рекурсивно перечислимого множества А натуральных чисел можно построить такую формулу 4 ^ ' f a , ) вида ( З х г ,..., Х р ) Ф . где ¥ '-< £ * , У*/ и каждая формула ^ имеет один из следующих видов: Хс /-Ху - Ц , Хр X j - х у , Xg - Xj , X g - С у , где Ct - целое число, что для произвольного натурального числа к имеем: к&А тогда и только то гд а, когда формула Ф д 1 к) истинна на кольце целых чисел. По формуле Ф ^ ’(Хг) построим формулу Ф ^ 2 ( х , ) оледуюцим образом: Ф а '( х ,) = ( З х „ . . . , х р ) ( ф , & f a -' x i <з -- а х , » , где У) получается из Ф заменой каждой формулы вида X g t X j z X ^ на X f X j - Х к , формулы W вида Xg х у - Х * на &(Х/, Ху, х К) , формулы Fi вида х е = на Хе -<* С* > формулы же вида Z ( - X j не меняются. Подходящим образом переименовав переменные в полученной фор­ муле и заменив обычным образом в свободной группе систему равенотв равносильны)/ ей одним равенством, получим формулу Фц fx) вида ( В х , Хя , у „ . . . , у т ) Щ Х , х ? \ , . . , Х ? . х * Х л * У » " " У "1’ а’ 6^ 1 такую, что для произвольного натурального числа к : к £ п ^ > 6 ( В х „ . ..,х я , у п - , z * . ..,Хп2, у * л 6 ) - - 1 Но