Учебно-методический комплекс дисциплины ОПД. В.1.1 Дополнительные главы дискретной математики (стр. 10 )

А(m+x) = В(m+x, m+x) > В(m, m+x) > f(m+x),

т. е. А(y) > f(y), начиная по крайней мере с y=m+x=m+2.
§ 8. Общерекурсивные и частично-рекурсивные функции

Функция Аккермана А(x) является примером вычислимой, но не примитивно-рекурсивной функции. Этот пример говорит о том, что средства построения вычислимых функций нуждаются в расширении.

Функция называется частично-рекурсивной, если она может быть построена из простейших функций 0, x’ и Imn с помощью конечного числа применений суперпозиции, примитивной рекурсии и неограниченного m-оператора. (Так как в дальнейшем будет упоминаться только неограниченный m-оператор, прилагательное “неограниченный” будем опускать).

По определению m-оператор применяется к предикатам. Поскольку в теории рекурсивных функций истинность предиката Р(х) всегда связана со справедливостью некоторого равенства и, наоборот, всякое равенство является предикатом от содержащихся в нем переменных, то m-оператору можно придать стандартную форму, например,

f(x1, ..., xn) = my (g(x1, ..., xn-1, y) = xn) или f(x1, ..., xn) = my (g(x1, ..., xn-1, xn, y) =0).

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

Действительно, для вычисления функции f(x1, ..., xn) = my (g(x1, ..., xn-1, xn, y) =0) на наборе x1, ..., xn существует следующая простая процедура: вычисляем g на наборах (x1, ...,xn, 0), (x1, ...,xn, 1), ... до тех пор, пока не получим значение НОЛЬ.

Понятно, что такая процедура может и не привести к результату; это произойдет в случае, когда на данном наборе x1, ..., xn уравнение g(x1, ..., xn-1, xn, y) = 0 не имеет решения. В таком случае функция f(x1, ..., xn) считается неопределенной.

НЕ нашли? Не то? Что вы ищете?

Пример. Обратная к х+1 функция х-1 = my (y+1=х) не определена при х=0.

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

Таким образом, среди рекурсивных функций появляются не полностью определенные, т. е. частичные функции; операторы над частичными функциями порождают новые частичные функции. При этом характер неопределенности может оказаться довольно сложным, а именно: для данного набора значений x1, ..., xn не найдется способа установить, определена ли функция f на этом наборе, и придется продолжать процесс вычисления неопределенное время, не зная, остановится он или нет.

В случае, когда функция g, к которой применяется m-оператор, сама является частичной, функция f(x1, ..., xn) = my (g(x1, ..., xn-1, xn, y) = 0) вычисляется с учетом следующего условия: если для y = 0, 1,..., i-1: g(x1, ..., xn-1, xn, y) ¹ 0, а g(x1, ..., xn-1, xn, i) не определена, то и f(x1, ..., xn) не определена.

Пример. Функция f(x) = my ( 4/(y-2)-x=0 ) при х=4 не определена (хотя уравнение 4/(y-2)-x=0 имеет решение y=3), т. к. функция 4/(y-2)-x=0 не определена при y=2.

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

Связь рекурсивных функций с машинами Тьюринга

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

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

РАЗДЕЛ 4. Словарь терминов (глоссарий)

Производящие функции и их применение

Алгебра

биномиальная

отношений

Композиция

Ньютона

бином

Паскаля

преобразование

треугольник

Разбиение

Размещение

с повторениями

Сочетание

с повторениями

Формальный степенной ряд

Функция

производящая

экспоненциальная производящая

Рекуррентные уравнения

Решение

общее

частное

Уравнение

однородное

рекуррентное

с постоянными коэффициентами

характеристическое

Условие

начальное

Фибоначчи

задача

Теория алгоритмов

Алгоритм

Оператор

неограниченный минимизации

ограниченный минимизации

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

суперпозиции

Проблема

алгоритмическая

неразрешимая

остановки

распознавания нетривиального инвариантного свойства

Свойство

инвариантное

нетривиальное

Тьюринга

машина

Функция

Аккермана

вычислимая по Тьюрингу

общерекурсивная

примитивно-рекурсивная

частично-рекурсивная

Чёрча-Тьюринга

тезис

РАЗДЕЛ 5. Практикум по решению задач (практических ситуаций) по темам лекций (одна из составляющих частей итоговой государственной аттестации)

Производящие функции и их применение

Таблица простейших производящих функций

№ п/п	аn	а(x)	аe(x)
1	1	1 / (1−x)	ex
2	a n	1 / (1−ax)	eax
3	1 / n!	ex	−
4	a n / n!	eax	−
5	Can	(1+x) a	−
6	C n n+ b −1	(1−x) −b	−
7	a n C n n+ b −1	(1−ax) −b	−
8	n	x / (1−x)2	x ex

Задание 1.1. Используя бином Ньютона, вычислить: (2-)6.

Решение. В формулу

(a+b)n = Cnk an−kbk

подставим: a = 2, b = −; n = 6, получим:

(2 −)6 = C60 26 + C61 25 (−) + C62 24 (−)2 + C63 23 (−)3 + C64 22 (−)4 +

+ C65 21 (−)5 + C66 (−)6 = 64 – 192 + 720 – 480 + 540 – 108 + 27 =

= 1351 – 780.

Ответ: 1351 – 780.

Задание 1.2. Не раскрывая скобок, определить коэффициент при x9 в многочлене:

(1+ x)9 + (1+ x)10 + … + (1+ x)14.

Решение. Искомый коэффициент равен: C99 + C109 + C119 + C129 + C139 + C149. Упростим это выражение, используя равенство: Cnk + Cnk−1 = Cn+1 k, а также тот факт, что C99 = 1 = C1010:

(C1010 + C109) + C119 + C129 + C139 + C149 = (C1110 + C119) + C129 + C139 + C149 =

= (C1210 + C129) + C139 + C149 = (C1310 + C139) + C149 = (C1410 + C149) = C1510 = 3003.

Ответ:3003.

Задание 1.3. Даны числовые последовательности: a(n) = 2n+1 и b(n) = n + 5. Составить производящие функции a(x) и b(x) этих последовательностей. В произведении a(x)×b(x) найти коэффициент при x5.