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

£ \u,\ t I t / i H I t i jU l ^ j ) А последняя формула приводится к предваренной позитивной формуле с приставкой типа 3 V Э для некоторых натуральных чисел m и к . ЛЕММА. По произвольному многочлену Р ( х , , . . . , х „ ) с целыми коэффициентами можно построить формулу Фр вида где i/' г i/.f 1 (wL a ’ 6 ) r i & £ ( t , s ) e f y ^ ^ ^ такую, что уравнение Р (Х), ■■■,Xri ) - 0 имеет решение в целых неот­ рицательных числах тогда и только то гд а, когда формула Ф р ис­ тинна на группе F г . ДОКАЗАТЕЛЬСТВО, По уравнению Р ( Х , ....... Хп) г@ стандартным образом строим равносильную ему систему вида V* , где каж­ дое уравнение У7,' имеет один из следующих типов: Х} + Хр - X f , X) - Xt , Xj ~X g , X j - c , где С - натуральное число. Система <£, |f t I получается из предыдущей заменой каждой фор­ мулы f ; вида X j t X p - X { т - l i r l , вода Xj х ( - X t на l i / H X e U l t t t , вида X / = Х ( на I t а вида Z j - С на | l ^ U l a c l . Легко понять, что исходное уравнение Р (Х ,,...,Х п) - 0 имеет ре­ шение в целых неотрицательных числах тогда и только то гд а, когда построенная система I У*. I имеет решение в группе F ? « Используя введенные выше эквивалентности по системе <£/ i f ; ! - строим формулу Фр требуемого вида и с нужными свойствами. Это можно легко сд ел ать, если переименовывать по мере необходимости переменные, связанные квантором существования, и вспомнить, что формулы ( У а )М # Л ) и [ \ /х ) Д & (Vx)& эквивалентны (это позво­ ляет сохранить в формуле Ф р лишь один квантор общности), ТЕОРЕМА, Не существует алгоритма, позволяющего по произ­ вольной позитивной формуле вида ( В у , г - , Ц к Х ^ * М ^ ( / * - > г > " ^ о 1)Ф , где V - V * ( Щ ( ч , ....... У т , а , б ) - - 1 & £ ( f , s ) e & ( ty e l,= lj/s h , определить, истинна ли она на свободной группе Рг . Доказательство следует из предыдущей леммы и отрицательного решения 10-Й проблемы Д .Гильберта. 152