3.1. Главные универсальные функции

Очевидно, композиция двух вычислимых функций вы­числима. При этом это утверждение кажется «эффектив­ным» в том смысле, что по программам двух функций можно алгоритмически получить программу их компо­зиции. В разумном языке программирования она будет состоять из двух подпрограмм, соответствующих двум вычислимым функциям, и главной программы с един­ственной строкой «return (f(g(x)))».

Однако мы хотим говорить не о программах (что­бы не вдаваться в детали языка программирования), а о номерах функций. Для этого у нас есть средства. Имен­но, всякая универсальная функция U для класса вычисли­мых функций одного аргумента задаёт нумерацию это­го класса: число п является номером функции Un : х н->-i->- U(п, х).

Вообще нумерацией (более точно, натуральной ну­мерацией) произвольного множества J- называют всюду определённое отображение v: N —5- J~, область значе­ний которого есть всё множество J-. Если v(n) = /, то число п называют номером объекта /. Таким образом, всякая функция двух аргументов задаёт нумерацию не­которого класса функций одного аргумента (и является универсальной для этого класса).

Наша цель — сформулировать и доказать такое ут­верждение: (при некоторых условиях на нумерацию вы­числимых функций) существует алгоритм, который по любым двум номерам вычислимых функций даёт неко­торый номер их композиции.

Прежде всего мы потребуем, чтобы универсальная функция, задающая нумерацию, была вычислимой. (Та­кие нумерации называют вычислимыми.) Однако этого условия мало: нам потребуется, чтобы нумерация была, как говорят, главной (гёделевой).

Пусть U — двуместная вычислимая универсальная функция для класса одноместных вычислимых функ­ций (термин «fc-местная функция» означает «функция к аргументов»). Её называют главной универсальной функцией, если для любой двуместной вычислимой функ­ции V существует всюду определённая вычислимая функ­ция s(m), для которой

V(m, х) = U(s(m), х)

при всех т и х (равенство понимается, как обычно, в том смысле, что либо оба значения не определены, либо определены и равны).

Другими словами, Vm = t/s(m), то есть функция s даёт по V-номеру некоторой функции некоторый U-номер той же функции.

Теорема 15. Существует главная универсальная функ­ция.

<] (Первый способ.) Покажем, что описанное в дока­зательстве теоремы б (с. 17) построение универсальной функции даёт главную универсальную функцию. Напо­мним, что мы перечисляли все программы ро,р\,р2, ■ ■ ■ какого-то естественного языка программирования в по­рядке возрастания их длин и полагали U(n,x) равным результату применения программы рп к входу х. Пусть теперь есть какая-то другая вычислимая функция V двух аргументов. Нам надо по любому натуральному т по­лучить программу функции Vm, то есть функции, ко­торая получится, если в V зафиксировать первый аргу­мент равным т. Ясно, что такую программу (в большин­стве языков программирования) получить легко — надо только в программе для V заменить первый аргумент на определение константы (или использовать программу для V в качестве подпрограммы, а в основной программе вызывать V с фиксированным первым аргументом).

(Второй способ.) Но можно и не вдаваться в детали построения универсальной функции, а воспользоваться лишь фактом её существования.

Заметим сначала, что существует вычислимая функ­ция трёх аргументов, универсальная для класса вычи­слимых функций двух аргументов, то есть такая функ­ция Т, что при фиксации первого аргумента среди функ­ций Tn(u,v) = T(n,u,v) встречаются все вычислимые функции двух аргументов.

Такую функцию можно построить так. Фиксируем некоторую вычислимую нумерацию пар, то есть вычи­слимое взаимно однозначное соответствие (и, v) <->• [и, v] между N xN и N; число [и, v], соответствующее паре (и, v), мы будем называть номером этой пары. Если теперь R — двуместная вычислимая универсальная функция для вы­числимых одноместных функций, то вычислимая функ­ция Т, определённая формулой Т(п, u,v) = R(n, [и, v]), бу­дет универсальной для вычислимых двуместных функ­ций. В самом деле, пусть F — произвольная вычисли­мая функция двух аргументов. Рассмотрим вычислимую одноместную функцию /, определённую соотношением f([u,v]) = F(u,v). Поскольку R универсальна, найдёт­ся число п, для которого R(n,x) = f(x) при всех х. Для этого п выполнены равенства T(n,u,v) = R(n,\u,v\) = = f([u,v]) = F(u,v), и потому n-ое сечение функции Т совпадает с F. Итак, универсальная функция трёх аргу­ментов построена.

Теперь используем её для определения главной уни­версальной функции U двух аргументов. Неформально говоря, мы встроим внутрь U все другие вычислимые функции двух аргументов, и тем самым U станет глав­ной. Формально говоря, положим U([n,u],v) = T(n,u,v) и проверим, что функция U будет главной. Любая вычи­слимая функция V двух аргументов встречается среди сечений функции Т: можно найти такое п, что V(u, v) = = T(n,u,v) для всех и и v. Тогда V(u,v) = U([n,u],v) для всех и и v и потому функция s, определённая форму­лой s(u) = [п,и], удовлетворяет требованиям из опреде­ления главной универсальной функции. >

Нумерации, соответствующие главным универсаль­ным функциям, называют главными, или гёделевыми.

Теперь уже можно доказать точный вариант утвер­ждения, с которого мы начали.

Теорема 16. Пусть U — двуместная главная уни­версальная функция для класса вычислимых функцийодного аргумента. Тогда существует всюду определён­ная функция с, которая по номерам р и д двух функ­ций одного аргумента даёт номер е(р, q) их композиции:

^с(р,д) еСТЬ КОМПОЗИЦИЯ 1}р О 1/д, ТО еСТЬ

и(с(р,д),х) = и(р,и(д,х))

для всех р, д Ж X.

<] Рассмотрим двуместную вычислимую функцию V, для которой У([р, д], ж) = II(р,11 (д, х)). По определению главной универсальной функции, найдётся такая всюду определённая одноместная вычислимая функция в, что У(т,х) = и(8(т),х) для всех т и х. Тогда У([р, д], ж) = = С/(в([р, д]), ж) и потому функция с, определённая соот­ношением с(р, д) = в([р, д]), будет искомой. >

Повторим это доказательство неформально. Опреде­ление главной универсальной функции требует, чтобы для любого другого языка программирования, для кото­рого имеется вычислимый интерпретатор V, существо­вал бы вычислимый транслятор в программ этого языка в программы языка V. (Для краткости мы не различаем программы и их номера и рассматриваем число т как [/-программу функции 11т.)

Теперь рассмотрим новый способ программирования, при котором пара (р, д) объявляется программой компо­зиции функций с [/-программами р и д. По условию, та­кие программы можно алгоритмически транслировать в [/-программы, что и требовалось доказать.

Любопытно, что верно и обратное к теореме 16 утвер­ждение:

28. Пусть О — двуместная вычислимая универсальная функция для класса вычислимых функции одного аргумента. Если существует всюду определённая функция, которая но но­мерам р и д двух функции одного аргумента даёт какой-либо номер их композиции, то функция О является главной. (Ука­зание: покажите, что но к можно алгоритмически получать (/-номер функции х Н- [/г, ж].)

Естественный вопрос: существуют ли вычислимые универсальные функции, не являющиеся главными? Мы увидим дальше, что существуют.

29. Изменим определение главной универсальной функции и будем требовать существования «транслятора» л лишь для универсальных вычислимых функций V (а не для любых, как раньше). Покажите, что новое определение эквивалентно ста­рому. (Указание: любую функцию можно искусственно пере­делать в универсальную, «растворив» в ней любую другую универсальную функцию.)

30. Пусть О — главная универсальная функция. Докажи­те, что для любой вычислимой функции У(тга, и. х) существует такая всюду определённая вычислимая функция з(т,п), что У(т, п, х) = и(з(т,п),х) при всех т, п и х. (Указание: объ­единить т и п в пару.)