10.3. Арифметичность вычислимых функций

Сейчас мы докажем, что функции, вычислимые про­граммами с конечным числом переменных, арифметич-ны, то есть их графики являются арифметическими мно­жествами. В этом разделе мы вновь предполагаем неко­торое знакомство читателя с логическими обозначени­ями, и будем рассматривать арифметические формулы, содержащие переменные по натуральным числам, равен­ство, константы 0 и 1, операции сложения и умножения, логические связки (И, ИЛИ, НЕ) и кванторы «для всех» и «существует». Формально говоря, мы рассматриваем сигнатуру, содержащую единственный двуместный пре­дикатный символ (равенство), две константы 0 и 1 и два двуместных функциональных символа (сложение и умно­жение). Говоря об истинности таких формул, мы име­ем в виду их истинность в стандартной интерпретации, носителем которой является множество N натуральных чисел.

Множество А С N* называется арифметическим, если существует арифметическая формула а с параме­трами х\,..., хк, которая его представляет в следующем смысле: (п\,..., пк) 6 А тогда и только тогда, когда формула а истинна при значениях параметров х\ = щ, ... ,хк = пк.

Теорема 67. График любой функции, вычисляемой программой с конечным числом переменных, является арифметическим множеством.

<] Пусть /: N —5- N — функция, вычислимая некоторой программой Р с конечным числом переменных k\, . . . , kff. Будем считать, что входной переменной является к\, а выходной — &2- Нам нужно написать формулу с дву­мя переменными х, у, которая была бы истинна тогда и только тогда, когда у = f(x). Состояние программы с конечным числом переменных полностью описывается значениями переменных и номером текущей команды (в процессорах соответствующий регистр часто называют program counter, по-русски счётчик команд). Легко по­нять, что соответствие между двумя последовательны­ми состояниями программы с конечным числом перемен­ных арифметично. Мы имеем в виду, что можно написать арифметическую формулу

Step(sb .. .,sN,p, s[,. ..,s'N,p'),

с 2N + 2 переменными, которая утверждает, что дан­ная программа Р из состояния, где переменные рав­ны si,..., Sff, а счётчик команд равен р, за один шаг переходит в состояние, где переменные равны Sj,..., s'n , а счётчик команд равен р'. (Договоримся, что значе­ние р' = 0 соответствует остановке программы.) Та­кая формула является конъюнкцией отдельных утвер­ждений, соответствующих каждой строке программы. Пусть, например, строка 7 программы имеет вид кг :=кз. Тогда в конъюнкции будет член вида

(Р = 7) =>• ((4 = si) Л (4 = s3) Л (4 = s3) Л ...

...Л (4, = sN) Л (р' = 8)).

Для строки с условными переходами типа 3   if k5=0 then goto 17 else goto 33

в формуле будет два конъюнктивных члена (на два слу­чая перехода)

((р = 3) Л (*5 = 0))=>((4 = s,) Л.. .Л (s'N = sN)A (р' = 17))

((р = 3)Л(*5 ф 0))=>((4 = st)A.. .A(s'N = sN)A(p' = 33)).

Надо ещё добавить утверждение о том, что при р = О работа прекращается, то есть что переменные на следу­ющем шаге сохраняют свои значения, и р' остаётся рав-

Таким образом, арифметичность одного шага рабо­ты программы доказать несложно. Остаётся главный во­прос: как записать в виде формулы тот факт, что суще­ствует последовательность шагов, которая начинается с исходного состояния, заканчивается в данном и в кото­рой каждый шаг правилен. Трудность в том, что здесь нужно как бы написать переменное число кванторов су­ществования — или квантор «существует конечная по­следовательность натуральных чисел».

Это делается с помощью приёма, традиционно назы­ваемого /3-функцией Гёделя. Вот что имеется в виду.

Лемма 1. Для любого к можно найти сколь угодно большое целое положительное число Ь, при котором пер­вые к членов последовательности Ь + 1,25+ 1,36+ 1,... попарно взаимно просты.

Доказательство. Любой общий простой делитель двух из этих чисел будет делителем их разности, то есть чи­сла 1Ь при 0 < I < к; взяв Ь кратным к\, мы гарантируем, что он будет делителем числа Ь, но все члены нашей по­следовательности взаимно просты с Ь. Лемма доказана.

Лемма 2. Для любой последовательности хо, х\,..., хп натуральных чисел можно найти такие числа а и Ь, что Х{ есть остаток от деления а на Ь(г + 1) + 1.

Доказательство. Согласно предыдущей лемме, дели­тели Ь(г + 1) + 1 можно взять взаимно простыми (и скольным 0.угодно большими), остаётся воспользоваться «китайской теоремой об остатках». Эта теорема утверждает, что ес­ли целые положительные числа d\,..., dk взаимно про­сты, то при делении целого и на них может получить­ся любой заданный набор остатков. В самом деле, таких наборов будет d\d2 ...dk (поскольку при делении на d{ возможны остатки от 0 до rf; - 1). При делении чисел и = 0,1,..., d\d2 ... dk — 1 получаются разные наборы остатков (если два числа и' и и" дают одинаковые остат­ки, то их разность делится на все d{, что невозможно в силу взаимной простоты). Поэтому чисел столько же, сколько наборов остатков, и должны появиться все набо­ры. Лемма 2 доказана.

Эта лемма показывает, что последовательность про­извольной длины можно закодировать тремя числами а, Ь и п (последнее число — длина последовательности). Та­ким образом, условно говоря, можно заменить «формулу»

3{х0>. ..,хп)[Уг ^ п)[.. .Xi ...]

(которая на самом деле не является арифметической фор­мулой, так как содержит квантор по конечным последо­вательностям) на формулу

За 36 3n (Vi ^ п)[. . . (остаток от деления а на b(i + 1) + 1) . . . ].

Мы будем записывать остаток от деления а на 5(г + 1)-|-1 как fi(a,b,i) (отсюда и название «бета-функция»).

Возвращаясь к нашей программе Р с конечным чи­слом переменных к\,..., k?f и вычисляемой ей функ­ции /, можно записать утверждение вида f(x) = у так: существуют такое число шагов п и такие числа o-i > Ь\, а,2, 6oj • • • > on, bff, a, b, что

• fi(a\, b\, 0),..., p(aff, bff, 0) есть правильные началь­ные значения переменных (первое равно х, осталь­ные равны 0); р(а,Ь, 0) есть правильное начальное значения счётчика команд, то есть 1;

• для каждого г от 0 до п — 1 имеет место

Step(/3(al ,Ь\,г),..., /3(адг, бдг, г), /3(а, 5, г),

/9(а1, Ьг, г + 1),...,/3(адг, 5дг, г + 1),/3(а, 5, г + 1)),

то есть каждый переход соответствует программе;

• /?(а2, Ъ2,п) = у (значение выходной переменной &о в конце вычисления равно у) и р(а, Ь,п) = 0 (значение счётчика команд в конце вычисления равно 0, что по нашей договорённости соответствует остановке машины).

Итак, арифметичность вычислимых (на машинах с ко­нечным числом переменных) функций доказана. >

Вспоминая теорему 65, мы заключаем, что всякая вы­числимая на машине Тьюринга функция арифметична. Принимая тезис Тьюринга, можно сказать, что график любой вычислимой функции является арифметическим множеством.