11.6. Частично рекурсивные функции

Операторы примитивной рекурсии и подстановки не выводят нас из класса всюду определённых функций. Не так обстоит дело с оператором минимизации, о кото­ром мы уже упоминали. Он применяется к (к + ^-мест­ной функции / и даёт к-местную функцию д, определя­емую так: д(х\,.. .,хк) есть наименьшее у, для которо­го f(xl,. ..,хк,у)=0.

Смысл выделенных слов ясен, если функция / всюду определена. Если нет, то понимать их надо так: значение д(х\,..., хк) равно у, если /(х\,..., хк, у) определено и равно нулю, а все значения /(х\,..., ук, у1) при у1 < у определены и не равны нулю.

Часто используется обозначение

д(хг,..., хк) = цу ^(х1,.. .,хк,у) = Щ,

и потому оператор минимизации также называют /1-опе-ратором.

Ясно, что такое определение обеспечивает вычисли­мость д, если вычислима / (мы перебираем в порядке возрастания все у, ожидая появления нулевого значения).

86. Покажите, что если изменить определение и разре­шить /(х1, . . . , Хк, у') быть не определённым при у' < у, то функция д может быть невычислимой при вычислимой /.

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

Такая странная терминология, видимо, сложилась в ре­зультате переводов с английского. По-английски были "prim­itive recursive functions" (примитивно рекурсивные функции). Затем было дано более общее (general) понятие вычислимой всюду определённой функции, и такие функции были назва­ны "general recursive functions". Затем стали рассматривать и частичные (partial) вычислимые функции, называя их "partial recursive functions". В русском же языке слово "partial" попа­ло не туда, и вместо частичных рекурсивных функций стали говорить о частично рекурсивных функциях. Та же участь постигла и слово "general", которое странным образом вошло в прилагательное «общерекурсивная» и означает, что функ­ция всюду определена.

Теорема 76. Всякая функция, вычислимая с помощью машины Тьюринга, является частично рекурсивной.

<] Пусть / — вычислимая с помощью машины Тью­ринга (обозначим эту машину через М) функция одного аргумента. Рассмотрим свойство T{x,y,i), состоящее в том, что машина М на входе х даёт ответ у за время не более чем i. Как мы видели выше, по входу машины Тью­ринга и по времени i можно примитивно рекурсивно вы­числить её состояние в момент i; ясно, что можно также узнать, закончила ли она работу, и если да, то был ли от­вет равен у. Итак, свойство Т примитивно рекурсивно.

Теперь объединим аргументы у и i в пару с помощью примитивно рекурсивной нумерации; получится прими­тивно рекурсивная функция Т", для которой Т'(х, [у, t]) = = Т(х, у, i); теперь можно написать f(x) = р\ (fizT''(х, z)), где pi даёт по номеру пары её первый член, а //.: озна­чает «наименьшее z, для которого...». Таким образом, функция / является частично рекурсивной. >

Верно и обратное:

Теорема 77. Всякая частично рекурсивная функция вычислима на машине Тьюринга.

<] Легко написать программу с конечным числом пе­ременных, вычисляющую любую частично рекурсивнуюфункцию (подстановка сводится к последовательному выполнению программ, рекурсия — к циклу типа for, минимизация — к циклу типа while; оба вида циклов легко реализуются с помощью операторов перехода).

После этого остаётся только сослаться на то, что вся­кая функция, вычисляемая программой с конечным чи­слом регистров, вычислима на машине Тьюринга (как мы видели в разделе 10.2, теорема 66). >

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

На самом деле история здесь сложнее и примерно мо­жет быть описана так. Определение примитивно рекурсив­ной функции было дано великим логиком Куртом Гёделем и использовано как техническое средство при доказательстве теоремы Гёделя о неполноте, в начале 1930-х годов. Он же дал определение общерекурсивной функции (не совпадающее с приведённым нами, но эквивалентное ему). Американский логик Алонзо Чёрч сформулировал свой тезис для всюду опре­делённых функций, предположив, что всякая вычислимая всю­ду определённая функция является общерекурсивной. Затем американский математик Клини предложил распространить этот тезис на функции, не являющиеся всюду определёнными.

Параллельно английский математик Тьюринг и американ­ский математик Пост предложили свои модели абстрактных вычислительных машин (машины Тьюринга и Поста), отлича­ющиеся лишь некоторыми деталями, и высказали предположе­ние о том, что такие машины покрывают весь класс алгорит­мических процессов. Вскоре стало ясно, что вычислимость функции на таких машинах равносильна частичной рекур-сивности. (Исторические подробности можно узнать из книги Клини [4].)

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

(Заметим в скобках, что ещё одна вычислительная мо­дель — нормальные алгорифмы, или алгоритмы Маркова, бы­ли предложены Андреем Андреевичем Марковым-младшим (сыном старшего, в честь которого названы марковские цепи и марковские процессы). Это было уже в 1950-ые годы. Мар­ков писал слово алгорифм через «ф». Соответствующий прин­цип (всякий алгорифм эквивалентен нормальному) он назы­вал принципом нормализации. В его работах нормальные ал­горифмы использовались для построения неразрешимого ас­социативного исчисления (см. раздел 9.4). Кроме того, Мар­ков реально выписал во всех деталях конструкцию универ­сального алгоритма и провёл точное доказательство его кор­ректности; кажется, это достижение остаётся никем не по­вторённым — ни у кого больше не хватило настойчивости, чтобы для какого-то языка программирования написать на этом языке его интерпретатор и формально доказать его кор­ректность.)

Наше доказательство теорем 76 и 77 позволяет также получить такое следствие, называемое иногда теоремой Клини о нормальной форме:

Теорема 78. Всякая частично рекурсивная функция / представима в виде

f(x) = а{цг{Ъ{х, г) = 0)),

где а и Ь — некоторые примитивно рекурсивные функ­ции.

<] В самом деле, любая частично рекурсивная функция вычислима на машине Тьюринга, а следовательно, пред­ставима в нужном нам виде, как видно из доказательства теоремы 76 (в качестве а берётся функция, дающий пер­вый член пары по её номеру). >

Мы сформулировали эту теорему для случая одно­местной функции /, но аналогичное утверждение верно и для функций нескольких аргументов (и доказательство почти не меняется).

87. Покажите, что одним ju-оператором, применяя его по­следним, не обойтись: не всякая частично рекурсивная функ­ция представима в виде

f(x) = цг(Ъ(х, z) = 0)

где Ь — некоторая примитивно рекурсивная функция.

Из теоремы Клини о нормальной форме вытекает та­кое утверждение:

Теорема 79. Всякое перечислимое множество есть про­екция примитивно рекурсивного множества.

<] Перечислимое множество есть область определения рекурсивной функции; представив её в нормальной фор­ме, видим, что область определения есть проекция мно­жества {(х, z) | Ь{х, z) = 0}. >