Комбинаторная теория групп - Линдон Р.
Скачать (прямая ссылка):
Совершая резкий переход к новым для читателя вещам, рассмотрим некоторые понятия, связанные с многочленами с целыми коэффициентами. Пусть P(X1, Xn) — целочисленный многочлен (от нескольких переменных). Строчка целых чисел (zu .. .,гя) называется корнем многочлена Р, если
P(Z1.....zk)=0.
Определение. Подмножество S из Z" называется диофантовым, если существует многочлен P(X1, Xn; Y1, Ym), такой, что
(si, ..., Sn)QS тогда и только тогда, когда P (sb . ..,sn; Yu ... F7n) имеет целый корень. Будем говорить, что P перечисляет S.
296 Гл. IV. Свободные произведения и HNN-расширения
Нетривиальным примером диофантова множества является множество N всех натуральных чисел. Действительно, по знаменитой теореме Лагранжа целое число неотрицательно в том и только том случае, когда оно представимо в виде суммы четырех квадратов. Таким образом, s?N тогда и только тогда, когда многочлен P(s; Yu У4)=Yl+.. .-T-Yl-S имеет корень.
Заметим, что диофантово множество естественным образом интуитивно эффективно перечислимо. В самом деле, пусть P(Xi, . ., Xn; Yu Yn) — некоторый многочлен, перечисляющий S. Перенумеруем эффективным образом все (п+т)-ки (su sn; du ..., dm) целых чисел. При выборе каждой такой строки вычислим P(Su sn; du dm) и посмотрим, равно ли полученное
число 0. Если да, то поместим (si.....Sn) в список элементов MHfljj
жества 5. Если нет, перейдем к следующей (п+т)-ке. Щ
Одной из самых известных алгоритмических проблем являете 10-я проблема Гильберта. Гильберта интересовало нахождение ал! горитма, определяющего по данному многочлену P(Xu X1n) с целыми коэффициентами, имеет P целый корень или нет. Ю. В. Ma-^ тиясевич [1970] показал, что такого алгоритма не существует. При решении 10-й проблемы Гильберта Матиясевичем было доказано на самом деле много большее. Именно он установил, что все рекурсивно перечислимые множества диофантовы! Этот резуль-; тат в настоящее время является основным в теории рекурсивный функций. Для наших целей удобно рассматривать диофантовосш как определение рекурсивной перечислимости. Такой подход може быть обоснован двояко. Во-первых, он позволит нам объясните некоторые основные факты о рекурсивно перечислимых множеся вах с минимумом логического формализма. Во-вторых, при докЯ зательстве теоремы Хигмана о вложении мы сможем следовая работе м. К. Валиева [1968], в которой весьма изобретательно ищ пользуется диофантов характер рекурсивно перечислимых мн<Я жеств. 1
Читатель, предпочитающий стандартное определение «рекуЯ сивности», может иметь в виду теорему Матиясевича, устанавлит Вающую эквивалентность этого определения и определения, предлагаемого ниже. Точно так же мы не собираемся доказывать, что некоторые очевидным образом «эффективно перечислимые» множества, которые встретятся нам в дальнейшем, являются диофан-товыми. Достаточно сказать, что это можно сделать. Мы настоятельно рекомендуем читателю статью Дейвиса [1973], в которой можно найти отличное изложение результата Матиясевича.
Определение. Множество S=Z" называется рекурсивно пере-числимым, ести оно диофантово. Множество S называется рекурсивным, если как оно, так и его дополнение Z"—5 рекурсивно перечислимы.
7. Теорема Хигмана о вложении
297
Для начала нам необходимо продемонстрировать рекурсивно перечислимые, но не рекурсивные множества. Подход к этому дает ^нумерация», т. е. сопоставление натуральных чисел всему, что может встретиться. Поскольку это впервые было сделано Гёделем, получаемые числа называются «гёделевскими номерами». Введем нумерацию для многочленов следующим образом. Определим функцию a: Z->-N, полагая
а (z) = j2\Z\+1' если г<°>
к ' \2|г|, если г > 0.
Эта функция, разумеется, взаимно однозначна.
Зафиксируем X0, X1, ..., Xn, ... в качестве бесконечного множества переменных. Поставим в соответствие каждому одночлену
T = cX't\...Xt"n,
где 0 Ф с Q Z, каждое е{ больше или равно 1 и J1 < i2 < i3 <., < in, число
? (7-) = 2« top». De„
•де рф есть /-oe простое число. (Так, ? (5X1X1) = 21033132.)
Каждый ненулевой многочлен P от X,- единственным образом записывается в виде суммы одночленов
P = T1+...+Тк,
где T1 различаются не только коэффициентами из ZhP(T1) <... ... < ? (Тк). Сопоставим каждому многочлену P такого вида число
у (P) ^ р^
Понятно, что по данному многочлену его гёделевский номер y(P) вычисляется эффективно.
Теорема 7.5. Существует рекурсивно перечислимое нерекурсивное множество натуральных чисел.
? Рассмотрим
S{у(P(Xi1.....Хіпїї' Р(е' Х''' •"' XlJ имееткоРень«
где е = у (P)}.
Иначе говоря, S — множество гёделевских номеров многочленов, таких, что если в этот многочлен, вместо первой из встречающихся переменных подставить его гёделевский номер, то полученный многочлен имеет корень. Интуитивно ясно, что множество S эффективно перечислимо. С другой стороны, его дополнением яц-
298 Гл. IV. Свободные произведения и HNN-расширения
1) В оригинале «benign».— Прим. ред.
2) В оригинале «the Higman rope trick»,— Прим, pedt
ляется множество S*=Z—5= {г; 2 не принадлежит множес значений функции у или z=y(P(Xi,, X1n)), но многочл P(у(P), Xi2, Xin) не имеет корней}.
