Файл: Дискретная мат-ка_Ч.2_УП.pdf

21 

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

Если для некоторых систем чисел x

1

,…, x

n

, y

1

 значение 

ƒ не оп-

ределено,  то  неопределенными  будут  и  значения 

ƒ(x

1

,…, x

n

, y) для 

всех y > y

1

. 

Если функции g и h всюду определены, то и 

ƒ = R (g , h) – всю-

ду определенная функция. 

 
Пример. Пусть g = 0, h = 2x + y, тогда 
ƒ (0) = 0, 
ƒ (1) = h (0, g) = 0, 
ƒ (2) = h(1, ƒ (1)) = 2, 
ƒ (3) = h (2, ƒ (2)) = 2·2 + 2 = 6, 
ƒ (4) = 2·3 + 2·2 + 2 = 12, 
ƒ (x + 1) = 2x + 2(x - 1) + … +  2·2 + 2 = x(x+1), 

то есть функция 

ƒ (x + 1) = x(x + 1) возникает примитивной рекур-

сией из постоянной g = 0 и функции h = 2x + y. 

При  задании  номера  переменной,  по  которой  осуществляется 

рекурсия, функция 

ƒ однозначно определяется видом функций g и h. 

Переход к рекурсии по другой переменной в общем случае приводит 
к изменению функции. 

Оператор минимизации 

Этот оператор часто называют оператором наименьшего числа, 

а  иногда – оператором  построения  по  первому  нулю.  Последнее 
название лучше отражает суть рассматриваемого оператора и сопут-
ствующего ему алгоритма. 

Рассмотрим какую-нибудь n-местную (n 

≥ 1) частичную число-

вую  функцию 

ƒ.  Допустим,  что  существует  алгоритм  для  вычисле-

ния значений этой функции во всей области определения. Зафикси-
руем значения      x

1

,…, x

n-1

 первых (n-1) аргументов функции и рас-

смотрим уравнение 

ƒ (x

1

,…, x

n-1

, y) = x

n

. 

22 

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

ƒ (x

1

,…, x

n-1

, y) после-

довательно для y = 0, 1, 2, … . Найденное в процессе такого вычис-
ления наименьшее значение a, для которого 

ƒ (x

1

,…, x

n-1

, a) = x

n

, 

обозначим через 

μ

y 

(

ƒ (x

1

,…, x

n-1

, y) = x

n

). 

Данный  процесс  нахождения a не  дает  результатов,  т.е.  будет 

продолжаться бесконечно, в следующих случаях: 

1)

значение 

ƒ (x

1

,…, x

n-1

, 0) не определено; 

2)

значения 

ƒ (x

1

,…, x

n-1

, y) при y = 0, 1, … k определены, но 

не равны x

n

 , а значение 

ƒ (x

1

,…, x

n-1

, k+1) не определено; 

3)

значения 

ƒ (x

1

,…, x

n-1

, y) определены для всех y = 0, 1, 2,…, 

но отличны от x

n

. 

В этих случаях значение 

μ

y

 считается неопределенным. 

μ

y

 явля-

ется  частичной  функцией  от n переменных  x

1

,…, x

n

.  Обозначим  ее 

через  M

ƒ.  Здесь M – символ  оператора  минимизации,  преобра-

зующего функцию 

ƒ в Mƒ. 

Иными  словами  этот  оператор  по  заданной  функции,  завися-

щей  от n аргументов,  строит  новую  функцию  от  (n-1) аргументов. 
Исчезающий  аргумент  является  вспомогательным  и  используется 
при  выполнении  оператора.  Алгоритм,  сопутствующий  оператору 
минимизации  гласит: «Придавать  вспомогательному  аргументу  по-
следовательные  значения,  начиная  с  нуля,  до  тех  пор,  пока  не  ока-
жется, что функция 

ƒ стала (в первый раз) равной нулю. Полученное 

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

Пример 1. Пусть 

ƒ (y) = 2

y

, тогда M

ƒ (x) = μ

y 

(2

y

 = x). Функция 

M

ƒ(x) определена для значений x = 2

n

, где n = 0, 1, 2,…. В этих слу-

чаях   M

ƒ(x) = log

2

x = n. В частности, 

M

ƒ (1) = 0, 

M

ƒ (2) = 1. 

Значения функции M

ƒ при x = 0 и x = 3 не определены. 

Пример 2. Пусть 

ƒ (x, y) = y - x, тогда Mƒ (x, z) = μ

y

(y - x = z). 

Значение  этого  выражения  не  определено,  так  как  уже  при                     
y = 0 (x > 0) функция   

ƒ (x, y) = y - x не  определена. Но, с другой 

стороны, уравнение y - x = z имеет решение y = z + x. 

23 

Этот пример показывает, что значение функции M

ƒ не является 

в общем случае решением уравнения 

ƒ (x

1

,…, x

n-1

, y) = x

n

. Значение 

M

ƒ совпадает с минимальным решением уравнения ƒ (x

1

,…, x

n-1

, y) = 

=x

n

,  если  функция 

ƒ (x

1

,…, x

n-1

, y) для  данного  набора  значений 

x

1

,…, x

n-1

 определена при всех y  

≤ Mƒ (x

1

,…, x

n

). 

Если функция 

ƒ одноместная, то функция Mƒ называется обра-

щением  функции 

ƒ,  или  обратной  функцией,  ее  обозначают  часто 

через 

ƒ

-1

: 

ƒ

-1

 (x) = 

μ

y 

(

ƒ (y) = x). 

2.2.3 

Примитивно

-

рекурсивные

функции

Функция 

ƒ  называется  примитивно-рекурсивной,  если  она 

является  одной  из  простейших  функций s, C

0

1

, I

m

n

  или  может  быть 

получена из простейших функций с помощью конечного числа опе-
раторов  подстановки  и  примитивной  рекурсии.  Это  определение 
индуктивное: 

определены 

исходные, 

базовые 

примитивно-

рекурсивные функции s, C

0

1

, I

m

n

 и даны правила  построения любых 

других примитивно-рекурсивных функций. 

Операторы  подстановки  и  примитивной  рекурсии,  применен-

ные  ко  всюду  определенным  функциям,  дают  также  всюду  опреде-
ленные  функции,  поэтому  все  примитивно-рекурсивные  функции – 
всюду определенные. 

Пример  1.  Показать,  что n-местная  функция-константа  C

a

n

  яв-

ляется примитивно рекурсивной. Действительно, 

C

a

n 

(x

1

,…, x

n

) = s (s (…s (C

0

1 

(I

1

n 

(x

1

,…, x

n

)))…)), 

т.е.  функция  C

a

n

  выражается  с  помощью  подстановок  через  прими-

тивно-рекурсивные  функции s, C

0

1

, I

1

n

  и,  следовательно,  является 

примитивно-рекурсивной. 

Пример  2.  Функция 

ƒ (x, y) = x + y может быть построена по 

схеме примитивной рекурсии: 

ƒ (x, 0) = x = I

1

1 

(x), 

ƒ (x, y+1) = s (ƒ (x, y)) = h (x, y, ƒ (x, y)), 

т.е. 

ƒ (x, y) возникает  примитивной  рекурсией  из  примитивно-

рекурсивных функций g = I

1

1

(x) и h (x, y, z) = s (z). 

24 

Пример  3.  Назовем  сложение,  умножение  и  возведение  в  сте-

пень соответственно действиями нулевой, первой и второй ступеней 
и обозначим соответствено 

P

0 

(x, y) = x + y,  P

1 

(x, y) = xy,  P

2 

(x, y) = x

y

.

Нетрудно заметить, что при n = 1, 2 

P

n 

(x, 0) = g (x), 

где g (x) = 0 при n = 1 и g (x) = 1 при n = 2, 

P

n 

(x, y + 1) = P

n-1 

(x, P

n 

(x, y)). 

Отсюда видно, что функция P

n 

(x, y) (n = 1,2) возникает прими-

тивной рекурсией из функций g (x) и h (x, y, z) = P

n-1 

(x, z). Следова-

тельно, функции P

1

 и P

2

 –

примитивно-рекурсивные. 

Представление  примитивно-рекурсивной  функции  с  помощью 

операторов  подстановки  и  примитивной  рекурсии,  примененных  к 
функциям s, C

0

1

, I

m

n

,  по  существу,  определяет  способ  вычисления 

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

2.2.4 

Частично

рекурсивные

функции

Функция 

ƒ называется частично рекурсивной, если она может 

быть получена из s, С

0

1

, I

m

n

 с помощью конечного числа операторов 

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

-  каждая  примитивно-рекурсивная  функция  является  также  и 

частично рекурсивной; 

- класс частично рекурсивных функций шире класса примитив-

но-рекурсивных  функций,  так  как  все  примитивно-рекурсивные 
функции всюду определены, а среди частично рекурсивных функций 
есть функции, не всюду определенные. 

Примеры частично рекурсивных функций. 

1.

Частичная функция (x - y) может быть представлена в виде   

x - y = 

μ

z

 (y + z = x), 

функция (y + z) является  примитивно-рекурсивной,  следова-
тельно, функция  (x - y) – частично рекурсивная. 

2.

Функция x / y = 

μ

z

 (yz = x), yz – примитивно-рекурсивная функ-

ция, поэтому  x / y – частично-рекурсивная функция. 

25 

Понятие частично рекурсивной функции является одним из ос-

новных понятий теории алгоритмов. Какие бы классы алгоритмов до 
сих  пор  не  строились,  во  всех  случаях  оказывалось,  что  числовые 
функции, вычисляемые посредством этих алгоритмов, были частич-
но рекурсивными. 

Американский логик и математик Алонзо Черч в 1936 г. выска-

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

Для каждой частично рекурсивной функции  

ƒ существует  вы-

числительный  процесс,  посредством  которого  любое  натуральное 
число перерабатывается в значение 

ƒ (x) функции ƒ. Этот процесс не  

дает определенного результата в том и только том случае, если зна-
чение функции 

ƒ в точке x не определено. 

Рассмотрим  способ  получения  всюду  определенных  частично 

рекурсивных функций. Введем оператор слабой минимизации: 

M

l

ƒ = Mƒ, если функция Mƒ всюду определена; 

M

l

ƒ не определена, т.е. не существует, если функция Mƒ опре-

делена не всюду. 

Функции,  которые  можно  получить из простейших функций s, 

С

0

1

, I

m

n

    применением  конечного  числа  операторов  подстановки, 

примитивной  рекурсии  и  слабой  минимизации,  называются  обще-
рекурсивными.  

Так  как  операторы R, M

l

, S

i

 , примененные  ко  всюду  опреде-

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

Если  результат    применения  оператора  слабой  минимизации 

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