> > 2g i и g j < xg/2. Поэтому

числа

- г/д р . . ., -• попарно несравнимы по mod х.

Остается проверить, что г/д ф + i/i mod Жд для t<5 и j/g s ф - Уд mod а;. Первое следует из того, что Уа±Уг = x i + гу. i ± г/i < а;д. Если уд = -уд mod .г,, т. е. 2i/g = О mod xq, то 2zg j + + 4!/g j = Жд + = О mod и г/д = О mod xq, что невозможно ввиду Уд 1 < Ig < Жд.

Итак, для чисел у, . . . абсолютно наименьшие вычеты по mod Жд сначала возрастают от = О до yq (на q), затем убывают до -уд (на Зд) и снова возрастают до j/q = О (на 45).

Отсюда несложно выводится заключение предложения 7.

3. Диофантовость отношения у= х". Все дальнейшее рассуждение разбивается на два этана. На первом этапе строится диофантов предикат для у = -а (п), а i, пу > О, на втором с его по-мош,ью устанавливается диофантовость отношения у = ж". Все изложение построено на идеях 10. В. Матиясевича [2*] и Ю.Робинсон [2] и [5*]*).

Теорема. Пусть я > 1, i/ > О, ге > 0. Тогда г/ = "фо (п) в том и только в том случае, когда система Матиясевича - Робинсон

1) у= п + к, 5) Ь = я -Ь g2 (g2 - а),

2) ж2 = (а2 1) 2 1 6) и = (Ь2 - 1) + 1,

3) g2 = (а2 1) ft2 -1- 1, 7) 1; = у -Ь cg2,

4) /г = 2 (t -I- 1) xY, 8) и = re 4- 2ej/

разрешима в натуральных числах относительно ж, g, h, i, b, и, i;, с, e, A:.

Доказательство. Пусть при данных я > 1, г/ > О, ге > О система 1) - 8) разрешима в натуральных числах относительно остальных переменных. Тогда немедленно видим, что числа ж. Л, g, V, и, Ъ будут положительны&ш (так как = (д (д

- 1) ft2 -[- 1 > а ввиду я > 1, то g2 а> 0). Из 2), 3) и 6) выводим согласно предлончеппю 1 п. 2, что суш;ествуют натуральные р, q и г такие, что

x = ta (Р), У =а (Р); g = 1а (з), Л = Фа (з); " = (), ! = (О-Искусный выбор числа Ь обеспечивает ocoojao роль числа v (оно встречается трижды в системе). Именно, v будет играть роль связы-ваюш,его мостпка, с одной стороны, между г и ге, с другой - между г и р. Это позволит нам сделать заключение, что р = ге и, значпт, У = а (п).

Так как h =0 mod 2у в силу 4), то g=l mod 2у в сплу 3) и Ь = 1 mod 2у в сплу 5). Отсюда согласно предложению 4 п. 2 = ib (") = " niod 2у.

Из 8) имеел! v = п mod 2у и, следовательно, г = ге mod 2у. Далее в силу 5) Ь = я mod g". Согласно тому же предложению 4 п. 2 V = трь (>) = "Фо {г) mod g-. Так как в силу "i) v = у mod g-, то г/ = % (р) = а [г) mod г, а значит, % (р) = la {г) mod Ха (д). Отсюда согласно предложенпю 7 п. 2 (вторая передаточная лемма) г = ±р mod 2g. Из 4) вндпы, что г/ Л, т. е. -ф (р) (д). Тогда согласно предложению 6 п. 2 (первая передаточная лешш) i)n (р) q,

*) См. сноску на с. 355.

т. е. г/ I д. Поэтому г = +р mod 2у. Таким образом, п = г = Jp mod 2у ъ п~ +р mod 2у. Из 1) видим, что п у. Наконец, в предложении 5 п. 2 отмечено, что р т)а (р) = У- Отсюда ге = р и У = -фа (ге).

Обратно, пусть я>1, j/>0, ге>Оиу = % (ге). Мы должны показать, что возможен выбор значений для остальных переменных так, что равенства 1) - 8) выполняются.

Так как п \а (п) = у, то у = пк для Л; е 2V и 1) верно. Полагаем х = уа {п) и получаем 2). Берем g = 2п-а (2ге) и полагаем g = Ха (д)> = Фа (д)- Согласно Предложению 6 п. 2 (см. эквивалентность (11)) (2ге) 1(д). Но

V (2п)= (2Ха (ге),л1)„(ге))2 = 4V.

Поэтому 4x2;/ /г. Так осуществляются равенства 3), 4). Число Ь строим согласно 5). Так как g > а, то Ь > я. Полагаем = Хь (") и у = (")• Получаем 6). Так как b = а mod , то -фь (ге) = = -фа (ге) mod ф, т. в. V = у mod g и ввиду b > я согласно предло-лению 5 п. 2 у. Отсюда v = у сф. Наконец, как выше, имеем b = 1 mod 2у. Отсюда (предложение 4 п. 2) фь (ге) = ге mod 2у. Так как (ге) > ге, то i; = ге -[- 2ei/ для подходящего е. Итак, 7) и 8) выполнены.

Таким образом, при указанном выборе значений для других неизвестных вся система 1) - 8) удовлетворяется.

Следствие. Существует многочлен D с целыми коэффициентами такой, что если а>1,г/>0, ге>>0, то у = а {п) тогда и только тогда, когда

Bxghibuvcek (D (а, у, ге, ж, g, h, i, b, и, v, с, в, к) = 0).

Действительно, все уравнения 1) - 8) имеют вид равенств f = g. Однако, / = g (/ - g) = 0. Конъюнкция равенств Д = = О, . . ., /;с = О равносильна равенству /i -Ь •••+••• + /t = = 0. На основании этих замечаний по системе 1) - 8) ьюжпо построить требуемый многочлен D (я, у, ге, ж, g, h, i, Ъ, и, v, с, е, к) с целы1Ш коэффициентами,

В работе [5*] дается очень изящное и экономное диофантово представление г/ = "фо (ге). Но там преследуются и другие цели, которых мы здесь не ставим.

Далее нам нужна

Лемм а. Для а>?г>0 и х О имеет место

п .......

<

Доказательство. Согласно формуле (2) п. 1

3 нечетно

Отсюда

жХ (я + 1) =

2 ( " + ) (яж)"+1- (аЧ - ж»)<-«/2.

J нечетно

Отсюда

•1)= S

j нечетно

re-f 1 V /

,У-1)/а

Так как г > 1, то о-г - < а?х- - 1. Поэтому x% {п + 1) <фа (1+ 1)

п левая часть доказываемого нераненства установлена. Согласно предложению 5 п. 2 пмеем оценки

(2a-lf<,\{n + l) < (2а)".

Отсюда

7" \ га)

Используем следуюпще легко устанавливаемые неравенства: (1 - а)" > 1 - геа для О < а < Нп, (1 - а)-1 < 1 + 2а для О < а < 1/2.

To™.(ll)">.-i..« ..„i-<l,„(l-±)-4l +

+ = 1 -I- iL , так как -<с -. Отсюда получаем правую часть

2о а 2а 2

доказываемого неравенства.

Теорема. Имеем эквивалентность

J/ = (и = О & J/ = 1) V (1 > О & I = О & ;/ = 0) V

V (хуп > О & ЭаЬцу {апу & Ъ= ах &и = ь{п + 1) &

& у = г1)а(ге+ 1)& = ["/])•

Доказательство. Пусть хуп > О п существуют а, Ь, и, V с указанными свойствами. Тогда а > 1 п Ь > 1. Имеем для у

Так как а > гаг/ > ге, а > ?г, то согласно леьше

V \ а j

Отсюда г" < + 1 н < I/. С другой стороны,

yЧi+±]x + <x + 1L<x+i, У<х\ \ а / а а

Поэтому = х".

Пусть при хуп > О имеем у = г". Надо указать а, Ь, и, v с требуемыми свойствами. , , is

Берем а > ге, 6=02:, и = tfe (ге -Ь 1), v = % (п + I)- Остается показать, что у = [ufv].

Согласно лемме, учитывая, что у = г", имеем

x±<xl+y.

= аГ+<х+\.

Отсюда у uh < у -\- i и у = [uh]. Поскольку отношения и = = ojjb (ге -- 1) и у = фп (ге -Ь 1) имеют диофантовы представления (а, 6 > 1, га -Ь 1 > О, ц, у > 0) (см. следствие), а отношения а > > 71!/, b = ах, у = [ц/у] диофантовы, то видим, что правая часть эквивалентности построена из диофантовых отношений с помощью логических связок &, V и навешивания кванторов суп;оствования. Поэтому отношение у = х диЪфантово. 4. Некоторые следствия и дополнения.

а) Покажем, что десятая проблема Гпльберта алгоритмически неразрешпма. Пусть М - рекурсивно перечислимое, но не рекурсивное множество, 31 Q N. Тогда согласно основной теореме М диофантово н для некоторого полинома Р с целыми коэффициентами имеем

аеМ{Зуи..Ук){Р{а, Уи Уц) = 0).

Если бы существовал алгоритм для распознавания разрешимости в Л(даже одного только) уравнения F (а, уу, . . ., yj) = О при различных значениях параметра а, то проблема вхождения а М для множества М была бы алгоритмически разрешимой и М было бы рекурсивным множеством. Однако, М не рекурсивно и потому нет алгоритма для распознавания разрешимости диофантовых уравнений.

См. ссылки в книге на с. 15, 324, 339.

б) То же множество М, что и вьппе, дает пример перекурсивного диофантова множества (с. 326).

в) Всякая общерекурсивная функция / диофантова, так как отношение у = f {ху, . . ., х) рекурсивно иеречислимо. Область значений р/ любой общерекурсивной (н частшшо рекурсивной) функции диофантова, так как р/ рекурсивно перечислимо. В частности, диофантовыми являются множество всех степеней числа 2, множество всех простых чисел и др. (с. 327, 346, задача 1).

г) Согласно основной теореме множество А дважды диофантово тогда и только тогда, когда А рекурсивно (с. 329).

д) Всякое диофантово (а значит, и рекурсивно перечпслпмое) множество М <N является областью неотрицательных значений некоторого полинома с целыьш коэффициентами. Действительно, если

а S М (Э!/1. . . у) (G (а, уи . . ., у) = 0),

то берем Е (в, . . ., уц) = а - (а + I) (а, у, . . ., ут;}. Тогда М = N f] рЙ, рН - область значений полинома Л. В частности, существугэ йоЛйНОМЫ с целыми коэффициентами, у которых область HeofpKnatenbBbtx значений состоит в точности из всех простых чисел, в точности из всех степеней числа 2 и т. д.

б) Пусть iaxK {а, х) - клпниевская частично рекурсивная функция, уййверсальная для класса всех одноместных частично ре-курсивйШс функций. Яд (*) = К {а, х) п Wa - область определения функции «а- Тогда Wa - рекурсивно перечислимое множество, "а- В последовательности TFq, W, . . ., TF„, . . . содер-

С другой стороны,

жатся все рекурсивно неречислимые множества из N (так как каждое такое множество является областью определения некоторой частично рекурсивной функции).

Пусть М - область определения функции К. М рекурсивно перечислимо и потому диофантово. Очевидно, Wa = {х \ (а, х) е е М), т. е. является а-сечением множества М. Итак, существует диофантово множество М такое, что каждое рекурсивно перечислпмое множество из N является его а-сечеипем для подходящего д..

ж) В работе [5*] доказано, что для каждого полинома Р существует полипом Р такой, что Р (а, . . ., а, Zp, Zj, . . ., z) = О для некоторых Zq, z, . . ., z тогда и только тогда, когда Р (а, . . ., а, Ь, с, d, е, /, g, h, i, j, к, I, m, n)= 0 для некоторых Ъ, с, d, е, f, g, k, I, }, k, I, m, 11. Здесь я,, . . ., - параметры, остальные переменные - неизвестные (сведение к 13 неизвестным).

список дополнительной литературы

Матнясевич Ю. В. Диофантовость иеречислимых множеств.- ДАН СССР, 1970, 191, № 2, с. 279-282. [2*] МатияВевич 10. В. Диофаитовы мноя{ества.- УМЕ,

1972, 27, № 5, с. 185-222. [3*] Davis М., Matijasevic Y., RobinsonJ. Hilberts tenth problem. Diophantine equations: positive aspects of a negative solution.- Proc. Symp. in Pure Math., 1976, 28, p. 323-377.

[4*] Davis M. Hilberts tenth problem is unsolvable.- Amer. Math. Monthly, 1973, 80, № 3, p. 233-269.

[5*] Matijasevic Y., Robinson J. Reduction of an arbitrary diophantine equation to one in 13 unknowns.- Acta Arithmetica, 1975, 27, p. 521-553.

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ

Алгебра 24, 26

- конечно порожденная 27 -, основное множество 24 -, основные операции 24

- Робинсон 112

- Робинсона 75 -, сигнатура 24

- частичная 24 Алгебры, изоморфизм 24

- однотипные 24 Алгоритм (алгорифм) 9-11 -, детерминированность 10 -, дискретность 10

-, интуитивное понятие И

-, массовость 10

-, направленность 10

- нормальный 289

- операторный 291 Алфавит 17

- бесконечный 29

- машины внешний 219 --внутренний 220

- редуцированный 225

Вуква 17

Гипотеза Клини 13

- Чёрча 12

График рекурсивно перечпслиыы;

- примптивно рекурсивный 88

- рекурсивный 88

- функции 88

Декартова степень 19 Декартово произведение 19

Значение терна 21 - функции 19

Иерархия арифметическая 280

- Клини 280 Изоморфизм алгебр 24

- нумерованных множеств 173

Канторовский номер пары 60 --п-ки 62

Квадратичный остаток числа 57 Класс алгебр 24

- моделей сигнатуры а 267

- нумерационный 172 Клпнпевский номер функции 136

Кодирование 27 Команда машинная 222

- подстановочная 223 Композит машин 233 Колшозиция бинарных отношений

- слов 18

Конфигурация машины 221

Лента 18, 219

Машина 14, 218

- Л (перенос нуля) 234

- Б- (левый сдвиг) 234

- В+ (правый сдвиг) 234

- В+В+ (двойной перенос) 237

- в (транспозиция) 234

- Г (удвоение) 236

- Гг (копирование) 237

- Минского 305

- многоленточная 302

- Тьюринга 14, 219 --универсальная 250

- Тьюринга - Поста 219

- Ц (циклический сдвиг) 237 Множества, креативная система 196

- нумерованные, гомоморфизм 172 --, изоморфизм 173

- рекурспвно неотделимые 199 --отделтше 199

-, сводимость 156

- сильно неотделимые 203

-, слабо креативная система 197

- эффективно неотделимые 201 -, тп-эквивалентные 158 Множество арифметическое 271

- гинергишериымунное 168

- гипергинерпростое 168

- пшеримыунное 168

- гнперпростое 168

- диофантово 325

- замкнутое относительно частичной операции 25

- иммунное 163

- креативное (творческое) 161

- максвшальное 164

- мезоичное 167

- нерекурсивное рекурсивно перечислимое 124

- номерное 172

- порожденное 25, 33

- примитивно рекурспвное (относительно...) 43, 77

- продуктивное 159

- простое 163