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

А *»= Т ( а * , ах* ) . Теперь покажем, что для любых натуральных чисел A t Y 5 ( о Л « Л а?) В самом деле, если A t Y $ ( й * , й * , ) такие X Л , 2 e i j . что М д : то возылем 41= Т( а* , Х) Л о/4 л 2 =яДХ л Г(у,2;. Тогда для некоторого натурального числа I имеем С1* C lf= = ( а * <Х1 У , но тогда 1= 1 и 1 = $ l = $ i . Остается заметить, что A ^ Y $ СО / , (X*L , О.**). Имеет место следующее непосредственное следствие результата Ю.В.Матиясевича о диофантовости перечислимых множеств: H*i, СЛЕДСТВИЕ. Для произвольного рекурсивно перечис­ лимого множества о I натуральных чисел можно построить такую фор­ мулу вида . где р = Л*«<. Д и каждая формула тлеет один из следующих видов; 0 £ + 0 ^ = ССд f ОТ, СГ, = Х д , <r = Хд , X = С , <? - натуральное число, что для произвольного натурального числа ц имеем: тогда и только тогда, когда формула ( п ) истшша на множестве натуральных чи сел .^ м ■ По формуле ( x t ) строшл формулу ) следупцш образом: где 4 получено из Ч заменой каждой формулы вида X + на вида Х( = Од "на вида O C j-aj на Oj = Хд , вида зс^ - С на о т - ^ ^ . Подходящим образом переименовав переменные в формуле ф > ^ можем считать, что в формулу ’( XL ) входят лишь перемешшс Т 1, . . . , Х Р . Приведем ) к виду С3х4,..., ix p) (С л*а1^ )л ( CioC; XU, где В - некоторое подмножество множества всех упорядоченных пар , где <,£= 1 , Я } р I - слова в алфавц- те { O t , Р * » X* , . . . , огр! . w Получаем: Ц € d <«=» 4 )= ф * (Й< X • Взяв в качестве d рекурсивно перечислимое, но нерекурсивное множество, получим доказательство следующей теоремы. 51