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

- V ( Q t , X i , . . . . l a > X , Xn . yrn, a t , l i t ) решение в TT2 , ТВОРША 2 . Можно указать такой эндоморфизм У* полугруппы Иг. и такую систему уравнений в словах и длинах У ( х , х и . .. ,Х т ) вида & l £ i i ) e B 1л,-| = |Х>1^ г / 1, i n , и - 1 — а ” ^ > что не существует алгоритма, позволяющего для произвольного на­ турального числа к определить, имеет ли система VCа 7 ,х ,,...,Х ,„ ) решение в ТГ2 , ДОКАЗАТЕЛЬСТВО теоремы I . Обозначим через У » ,^ следую­ щие эндоморфизмы полугруппы "ТТг i Ъ ( а ^ % { а , ) = 1 . ¥г ( * л ) * < Ь , Рассмотрим предикаты Т(Х ,ц) и S ( x , y , l ) Т ( х , у ) < = > ( х а , у а г = а г у & ( 3 2 ) ( г а , а г - - а-, а г г & % ( z ) = х k ' i g ( z ) - у )>■ . Легко понять, что для произвольных элементов у , А полу­ группы ТГг имеет место следующая вквивалентность: T T ^ T ( g , н)<=> ( З г п * о ) ( § = &■ h = a f ) . Далее полагаем $ ( х , у , 2 . ) <==> ( - $ 0 , 1 / ) ( Т ( у , и )№ с & г г х а 2 : x a z v & £ ул ( v ) = u ) . Покажем, что для произвольных неотрицательных целых чисел & , t ,Z имеет место эквивалентность ТП М ( a , 3, a ,* , i = s t . В самом д ел е, если ТГ2 t* & (diS, a * . < J*, то обозначим через U , V такие элементы полугруппы ЛТ?, что Ц, t= Т ( а ,* , u ) & l f a t % = 4 , 4 \ f & % ( v ) , # , г& f t ( г ) = а / . Тогда , 1 f : ( a f c k )k при некотором к * О . г Из равенства ^ I V I - а / получаем, что к - 1 , Тогда из получаем нужное равенсуво г -- S t . Чтобы д о к азать, чТо на полугруппе ТТг истинна формула &(й?.й?, 0 . , ) , достаточно положить U - d j , *<!/)• Воспользуемся следующим хорошо Известным непосредственным оледотвием результата С.В.Матиясевича о диофаитовоети рекурсив­ но перечислимых множеств. п “ 1 . Для произвольного рекурсивно перечислимого множест- . .ft) ва А натуральных чисел можно построить формулу ^ ( х ,) вида 1№