Частичная функция f называется частично рекурсивной, если она может быть получена из простейших

функций о, S, Im конечным числом операций подстановг ки, примитивной рекурсии и минимизации.

На языке термов это определение мояет быть выражено следу10П1;им образом: частичная функция / называется частично рекурсивной относительно системы частичных функций @, если / есть значение (операторного) терма, записанного с номоп1;ыо операторных символов R, М, S, предметных символов о, s, Im простейших функций и предметных символов для функций из системы @.

Частичная функция / называется частично рекурсивной, если она является значением (операторного) терма, записанного с помощью операторных символов JS, М, 8 и символов о, S, 1т простейших функций.

Из указанного основного определения неносредственно вытекают следующие свойства относительно частично рекурсивных функций.

1) Каждая частичная функция, примитивно рекурсивная относительно системы функций @, является и частично рекурсивной относительно @. В частности, все примитивно рекурсивные функции частично рекурсивны.

2) Класс частично рекурсивных функций шире класса примитивно рекурсивных функций, так как все примитт-но рекурсивные функции всюду определены, а среди частично рекурсивных функций встречаются и не всюду определенные функции, например функции sg~•,

а также нигде не определенная функция

/ (а;) = [хЛг; -Ы -Ь г = 0).

3) Операции подстановки, примитивной рекурсии и минидшзации, произведенные над функциями, частично рекурсивными относительно систеьш @, дают в результате функции, снова частично рекурсивные относительно ©. В частности, каждый (функциональный) терм, записанный с помощью символов функций, частично рекурсивных относительно ©, п предметных переменных .т, . . ., х„, представляет функцию от х-, . . ., х„, частично рекурсивную относительно @.

Уже из примеров, приведенных в п. 2.2, видно, что ьшогие числовые функции примитивно рекурсивны. Чтобы получить первое, грубое представление о связи между примитивно рекурсивными и частично рекурсивными функциями, введем следующие понятия.

Характеристической функцией %а. какого-нибудь множества натуральных чисел А называется одноместная функция, равная О в точках множества А и равная 1 в точках, не принадлежащих А. Частичной характеристической функцией множества А называется функция, равная О в точках множества Л и не определенная в точках, не принадлежащих А.

Например, характеристическая функция пустого множества есть функция, равная 1 для любого значения аргумента, а частичная характеристическая функция пустого множества есть нигде не определенная функция. Вообще легко понять, что характеристическая и частичная характеристическая функции совпадают лишь для множества всех натуральных чисел.

Множество натуральных чисел А называется примитивно рекурсивным, если его характеристическая функция примитивно рекурсивна. Множество А называется частично рекурсивным, если его частичная характеристическая функция частично рекурсивна. Аналогично определяются понятия примитивно рекурсивного и частично рекурсивного множеств относительно системы функций ©.

Покажем, что каждое {относительно) примитивно рекурсивное множество является {относительно) частично рекурсивным. Действительно, пусть % () - характеристическая функция какого-нибудь множества натуральных чисел А. Тогда функция %ч {х), определяемая равенством

Хч {х) = О - % {х).

будет частичной характеристической функцией множества А. Так как операция вычитания частично рекурсивна, то из формулы (5) следует, что функция %ч {х) такяе частично рекурсивна.

Детальное изучение свойств частично рекурсивных функций составляет центральную задачу теории рекурсивных функций. Оно будет проведено в главе III. В качестве предварительной информации о свойствах частично рекурсивных функций может служить следующая очевидная

Теорема 1. Пусть / {х) - какая-нибудь примитивно рекурсивная функция и А - произвольное при.чи-тивно рекурсивное множество натуральных чисел. Тогда

частичная функция (ж), определенная схемой -f{x), если х(А,

не определено, если хА,

является частично рекурсивной.

В самом деле, по доказанному выше частичная характеристическая функция (х) множества А частично рекурсивна. Из схемы (6) вытекает, что для всех значений х

и {Х) = / (ж) -Ь 14 {Х)

И, значит, функция /ч {х) частично рекурсивна.

Теорема 1 дает возможность строить многочисленные примеры частично рекурсивных функций.

Понятие частично рекурсивной функции - одно из главных понятий теории алгоритмов. Значение его уже было указано во введении. Кратко говоря, это значение состоит в следуюхцем. С одной стороны, каждая стандартно заданная, например, посредством указанного выше операторного терма частично рекурсивная функция вычислима путем определенной процедуры механического характера, которая несомненно отвечает нашему интуитивному представлению об алгоритмах. С другой стороны, какие бы классы точно очерченных «алгоритмов» до сих пор фактически ни строились, во всех случаях неизменно оказывалось, что числовые функции, вычислимые посредством алгоритмов этих классов, были частично рекурсивными. Поэтому ныне обп];епринятой является следуюп];ая естественнонаучная гипотеза, обычно формулируемая как

Тезис Чёрча. Класс алгоритмически {или ма-шинно) вычислимых частичных числовых функций совпадает с классом всех частично рекурсивных функций.

Этот тезис дает алгоритмическое истолкование понятия частично рекурсивной функции. Несколько сложнее дело обстоит с пстолкованием понятия частичной рекурсивности относптельно заданной системы функций @. Такое истолкование было впервые указано Тьюрингом. Для простоты предположим, что система © состоит лишь из одной функции h {х). Если значения этой функции вы-числтш посредством некоторого алгоритма и, значит, ввиду тезиса Чёрча функция h {х) частично рекурсивна, то каждая функция /, частично рекурсивная относительно h, бзлет просто частично рекугрсивной. Если заданная функция h не является частично рекурсивной, то единого

алгоритма для вычисления произвольного значения функции h нет, и вьгаислить какое-нибудь значение функции (а;) это математическая проблема. Пусть теперь нам задана какая-нибудь функция /, частично рекурсивная относительно h. Это значит, что функция / может быть представлена в виде значения операторного терма, содер-жап];его символ функции h и символы простейших функций. Мы предположим, что этот терм а нам известен. В таком случае, просматривая определения операций JS, М, S, легко убен{даемся, что вместе с термом а опеределен и алгоритм, который позволяет вычислять значения функции / при условии, что мы можем находить те значения функции h (путем решения соответствуюш;их проблем), которые указывает алгоритм.

Говорят, что функция / алгоритмически вычислима относительно функции h, если суш;ествует алгоритм, позволяющий вычислять значения функции / при условии, что мы можем находить те значения функции h, которые указываются алгоритмом. При этом значения функции h, необходимые на более поздних шагах алгоритма, могут зависеть от значений h, требовавшихся на предыдущих шагах алгоритма.

Это определение относительной алгоритмической вычислимости, конечно, не полное. Смысл его зависит от того, какой смысл мы вкладываем в понятие обычного (не относительного) алгоритма, и других обстоятельств. Как и понятие алгоритма, понятие относительного алгоритма можно уточнять различными способами. Однако при всех фактически испробованных уточнениях оказывалось, что относительно вычислимые функции являлись относительно частично рекурсивными. Поэтому по аналогии с тезисом Чёрча обычно принимается в качестве естественнонаучной гипотезы и

Тезис Тьюринга. Класс функций, алгоритмически вычислимых относительно какой-либо функции h {и.ги класса функций ©), совпадает с классом частичных функций, частично рекурсивных относительно h {соответственно относительно системы ©).

Из тезиса Тьюринга вытекает тезис Чёрча. Обратное, по-видимому, нельзя считать справедливым. Конечно, здесь речь идет не о строгой логической зависимости, а скорее о зависимости в некотором философском смысле.

2.4. Общерекурсивные функции. Как уже говорилось, для каждой частично рекурсивной функции / существует

§ 2. ОСНОВНЬ№ ВЫЧИСЛИМЫЕ ОПЕРАТОРЫ

механический процесс, посредством которого любое натуральное число X перерабатывается в значение / (ж) . функции /. Этот процесс продолжается бесконечно, не давая окончательного результата, тогда и только тогда, когда значение функции / в точке а; не определено. Таким образом, всюду определенные частично рекурсивные функции - это функции, для вычисления значений которых существует алгоритм, обрывающийся через конечное число шагов для любого начального числа. Алгоритмы, которые перерабатывают любое заданное число в определенное число, играют особую роль в теории алгоритмов. Вместе с ними особое полояение в теории рекурсивных функций занимают и всюду определенные частично рекурсивные функции.

Следующий способ получения всюду определенных частично рекурсивных функций вполне очевиден. Операция минимизации, введенная в п. 2.3, ставит в соответствие любой заданной функции / определенную частичную функцию Ж/. Введем теперь еще одну операцию, которую временно будем обозначать символом Ж" и называть слабой минимизацией. Ло определению положим

ж/ = Ж/,

если функция Ж/ всюду определена. Если ясе эта функция определена не всюду, то значение Ж/ будем считать неопреде ленньпи.

Функции, которые можно получить из простейших функций О, S, 1т конечным числом операций подстановки, примитивной рекурсии и слабой минимизации, называются общерекурсивными.

Так как операции JK, Ж, S, выполненные над всюду определенными функциями, либо ничего не дают, либо дают снова всюду определенные фшкции, то все общерекурсивные функции всюду определены.

С другой стороны, если результат операции слабой минимизации определен, то он совпадет с результатом операции обычной минимизации. Поэтому все общерекурсивные функции яв.гяются всюду onределенньши частично рекурсивныш функци.чми.

Обратное тоже верно: каждая всюду определенная частично рекурсивная функция общерекурсивна. Однако этот результат является следствием довольно тонкой теоремы, которая будет доказана лишь в п. 6.1. Заметим пока, что

согласно определению каждая примитивно рекурсивная функция является общерекурсивной.

В п. 5.2 будут построены общерекурсивные функции, не являющиеся примитивно рекурсивными. Таким образом, класс общерекурсивных функций шире класса примитивно рекурсивных функций.

Примеры и задачи

1. Операция подстановки одноместной фгнкции в одиоместную функцию дает снова одиоместную функцию. Эту операцию мы будем обозначать символом *. Таким образом, по определению

f*g=S if, g), (/ * g) = / (g (X)). Операция * ассоциативна, но не коммутативна: / * (g * 7г) = (/ * g) * h, s * sg фз§ * s. Показать, что для любой одноместной функции /

Если/-1 всюду определена, то /*/~= Если выражение/- (х) оиределепо для некоторого х, то

Показать, что суя;ествуют одноместные функции /, для которых всюду определена и в то же время f- * f ф 1.

2. Для двзместных функций вводим операцию т, полагая

f (X, у) = / {у, X). Операция т удовлетворяет следующим соотношениям:

f = (/, ll, ll), lxif {X, y) = z) = {Mf) {y,z).

3. Если X - вещественное число, то символом [х] будем обо-•шачать целую часть х, т. е. наибольшее целое число, не превосходящее X. Показать, что функция

q{x)==x~ \]fT

удовлетворяет соотношениям

<7-1 {2х) = х2 -Ь 2х, «-1 [2х + 1) = х2 -Ь 4х -Ь 2.

4. Пусть g - 5шожество всех частичных функции на N от лю-иого числа переменных. Рассмотрим частичную алгебру

2( = <5; М, R, S2, S3, . . . >.