Бильгаева Н.Ц. - Теория алгоритмов, формальных языков, грамматик и автоматов, страница 3

Оператор примитивной рекурсииОператор примитивной рекурсии Rn позволяет определить (n+1) - местную функцию fпо двум заданным функциям, одна из которых является n- местной функцией g, а другая(n+2) - местной функцией h.Функция f(x1, x2, ..., xn, y) получается оператором примитивной рекурсии из функцийg(x1, x2, ..., xn) и функции h(x1, x2, ..., xn, y, z), если:f(x1, x2, ..., xn, 0) = g(x1, x2, ..., xn);(2)f(x1, x2, ..., xn, y+1) = h(x1, x2, ..., xn, y, f(x1, x2, ..., xn, y)).Приведенная пара равенств (2) называется схемой примитивной рекурсии. Дляпонимания операции примитивной рекурсии необходимо заметить, что всякую функцию отменьшего числа аргументов можно рассматривать как функцию от большего числааргументов.

Существенным в операторе примитивной рекурсии является то, что независимоот числа переменных в f рекурсия ведется только по одной переменной у. Остальные nпеременных x1, x2, ..., xn на момент применения схемы (2) зафиксированы и играют рольпараметров.2.2.3. Оператор минимизацииОтношение P(x1, x2, ..., xn) называется примитивно-рекурсивным, если примитивнорекурсивна его характеристическая функция:1, если P( x 1 , x 2 ,..., x n ) - " истина" ,χ( x 1 , x 2 ,..., x n ) =  0, если P( x 1 , x 2 ,..., x n ) - " ложь".Предикат называется примитивно-рекурсивным, если его характеристическая функцияпримитивно-рекурсивна.Функция f(x1, x2, ..., xn) получается посредством оператора минимизации из предикатаP(x1, x2, ..., xn, z), если в любой точке значением функции f(x1, x2, ..., xn) являетсяминимальное значение z, обращающее предикат P(x1, x2, ..., xn, z) в значение «истина»:f(x1, x2, ..., xn) = µz (P(x1, x2, ..., xn, z)),где µz – оператор минимизации.2.2.4.

Ограниченный оператор минимизацииФункция f(x1, x2, ..., xn) получается ограниченным оператором минимизации изпредиката P(x1, x2, ..., xn, z) и функции U(x1, x2, ..., xn), если в любой точке значение этойфункции определено следующим образом:1) для любого z < U(x1, x2, ..., xn) такого, что P(x1, x2, ..., xn, z) = "истина", значениефункции f(x1, x2, ..., xn) = µz(P(x1, ..., xn, z)),2) не для любого z < U(x1, x2, ..., xn) такого, что P(x1, x2, ..., xn, z) = "истина", значениефункции f(x1, x2, ..., xn) = U(x1, x2, ..., xn).Данное определение записывается следующим образом:f(x1, x2, ..., xn) = µ z < U(x) (P(x1, x2, ..., xn, z)).Ограничение z в ограниченном операторе минимизации дает гарантию окончаниявычислений, поскольку оно оценивает сверху число вычислений предиката P. Возможностьоценить сверху количество вычислений является существенной особенностью примитивнорекурсивных функций.2.3.

Примитивно-рекурсивные и частично-рекурсивные функцииБольшинство вычислимых функций относится к классу примитивно-рекурсивныхфункций.Функция называется примитивно-рекурсивной, если она может быть получена изпростейших функций с помощью конечного числа операторов суперпозиции и примитивнойрекурсии.Если некоторые функции являются примитивно-рекурсивными, то в результатеприменения к ним операторов суперпозиции или примитивной рекурсии можно получитьновые примитивно-рекурсивные функции.Существует три возможности доказательства того, что функция является примитивнорекурсивной:а) показать, что заданная функция является простейшей;б) показать, что заданная функция построена с помощью оператора суперпозиции;в) показать, что заданная функция построена с помощью оператора примитивнойрекурсии.Тем не менее примитивно-рекурсивные функции не охватывают все вычислимыефункции, которые могут быть определены конструктивно.

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

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

Утверждение о несуществовании частично-рекурсивнойфункции эквивалентно несуществованию алгоритма решения соответствующей задачи.2.4. Типы рекурсивных алгоритмовЭффективность разработки рекурсивного алгоритма определяется наличием некоторыхусловий:1) если исходные данные имеют рекурсивную структуру, то процедуры анализа такихструктур будут более эффективны, если они сами рекурсивны;2) если алгоритм обработки некоторого набора данных построить, разбивая данные начасти и обрабатывая в отдельности каждую часть, то из частичных решений можно получитьобщее;3) если по условию задачи необходимо выбрать оптимальный вариант из некоторогомножества решений, то искомое решение может быть найдено через конечное число шагов.При этом на каждом шаге удаляется часть информации, и далее задача решается на меньшемобъеме данных.

Поиск решения завершается после окончания данных либо при нахожденииискомого решения на текущем наборе данных.2.5. Методика решения задач2.5.1. Использование оператора примитивной рекурсииПример 1. Доказать примитивную рекурсивность функции f(x, y) = x + y.Решение. Рассмотрим способ рекурсивного определения данной функции:f(x, 0) = x,f(x, y+1) = x + y + 1 = f(x, y) +1.Чтобы показать соответствие данной рекурсивной схемы схеме примитивной рекурсии,воспользуемся функциями выбора и следования:f(x, 0) = x = I(x),f(x, y+1) = f(x, y) + 1 = S(f(x, y)) = S(I3(x, y, f(x, y))).Пример 2. Доказать примитивную рекурсивность функции f(x, y) = x ⋅ y.Решение.

Рассмотрим способ рекурсивного определения данной функции:f(x, 0) = 0,f(x, y+1) = x ⋅ (y + 1) = x ⋅ y + x = f(x, y) +x,из которого следует, что Z(x) = x ⋅ 0.Обозначим x ⋅ y = p(x, y), тогда:p(x, 0) = Z(x);p(x, y+1) = p(x, y) +x = S(p(x, y), x) = S( I 13 (x, y, p(x, y)), I 33 (x, y, p(x, y))).Пример 3. Доказать примитивную рекурсивность функции0, если x = 0,Sg ( x ) = 1, если x ≠ 0.Решение. Рассмотрим способ рекурсивного определения данной функции:Sg(0) = 0 = Z(x),Sg(x+1) = Z(x) +1 = 1 = S(Z(x)).Пример 4. Доказать примитивную рекурсивность функции f(x) = 2x.Решение.

Рассмотрим способ рекурсивного определения данной функции:f(0) = 1 = S(Z(x)),f(x+1) = 2 ⋅ 2x =2 ⋅ f(x) = S(S(Z(x))).Пример 5. Доказать примитивную рекурсивность функции f(x, y) = xy.Решение. Рассмотрим способ рекурсивного определения данной функции:f(x, 0) = 1 = S(Z(x));f(x, y+1) = xy+1 = xy ⋅ x = f(x, y) ⋅ I 12 (x, y) = p( I 33 (x, y, f(x, y)), I 13 (x, y, f(x, y))).2.5.2. Использование оператора минимизацииПример 1.

Пусть f(x, y) = µz( 2⋅x + z = y+1), откуда предикат P(x, y, z) = 2⋅x + z = y + 1.Покажем примитивную рекурсивность предиката P. Его характеристическая функцияможет быть представлена следующим выражением:Sg(Sg((2 ⋅ x + z) ÷( y + 1)) + Sg((y +1) ÷ (2 ⋅ x + z)).Найдем значение функции в точке (1, 5):При z = 0: P(1, 5, 0) = 2 ⋅ 1 + 0 = 5 + 1 - "ложь",z = 1: P(1, 5, 1) = 2 ⋅ 1 + 1 = 5 + 1 - "ложь",z = 2: P(1, 5, 1) = 2 ⋅ 1 + 2 = 5 + 1 - "ложь",z = 3: P(1, 5, 1) = 2 ⋅ 1 + 3 = 5 + 1 - "ложь",z = 4: P(1, 5, 4) = 2 ⋅ 1 + 4 = 5 + 1 - "истина".Таким образом, минимальное значение переменной z, обращающее предикат в "истину",дает значение функции в точке (1, 5), и оно равно 4.2.5.3.

Использование ограниченного оператора минимизацииОграниченный оператор минимизации является удобным средством для построенияобратных функций.Пример 1. C помощью ограниченного оператора минимизации определить функцию y(x,zz) =   - "целая часть от деления z на x" - как функцию, обратную умножению. xРешение.z / x = y, тогда y ⋅ x = z,z / x < y + 1, поэтому z < x(y + 1).С использованием ограниченного оператора минимизации запишем исходную функциючерез обратную:zy(x, z) =   = µ z ≥ y (P(x, y, z)), xпредикат P(x, y, z) = z < x(y + 1).zТогда   = µ z ≥ y (z < x( y+1)). xВычислим значение функции при z = 11, x = 2.При y = 0: P(2, 11, 0) = 2(0+1) < 11 - "ложь",y = 1: P(2, 11, 1) = 2(1+1) < 11 - "ложь",...y = 5: P(2, 11, 5) = 2(5+1) > 11 - "истина".zСледовательно,   = 5. xПример 2.

С помощью ограниченного оператора минимизации определить функциюf ( x ) = x - "целая часть от корня из х".Решение.Пусть x = z. Тогда x < z +1, а предикат P равен:P(x, z) = x < (z + 1)2.С использованием ограниченного оператора минимизации запишем исходную функциючерез обратную: x = µ z ≤ x (x < (z +1)2).Вычислим значение функции при x = 17.При z = 0: P(17, 0) = 17 < 1 - "ложь",z = 1: P(17, 1) = 17 < 4 - "ложь",...z = 4: P(17, 4) = 17 < 25 - "истина".[ ][ ][ ][ ]Следовательно, x = 4, что и требовалось доказать.Пример 3. С помощью ограниченного оператора минимизации определить функцию f(x,y) = [log y x ] - "целая часть от log y x".Решение.Пусть y z = x.

Тогда y z+1 > x.С использованием ограниченного оператора минимизации запишем исходную функциюкак:[log x ] = µ z < x (y z+1 > x).yПредикат P(x, y, z) = y z+1 > x.Вычислим значение функции при x = 8, y = 2.При z = 0: P(8, 2, 0) = 1 > 8 - "ложь",z = 1: P(8, 2, 1) = 2 > 8 - "ложь",z = 2: P(8, 2, 2) = 8 > 8 - "ложь",z = 3: P(8, 2, 3) = 16 > 8 - "истина".Следовательно, [log y x ] = 3.2.6. Задания для самостоятельной работыДоказать примитивную рекурсивность следующих функций.1. Усеченное вычитаниеx − x 2 , если x 1 > x 2 ,x1 ÷ x 2 =  1если x 1 < x 2 .0,2. Функция знака0, если x = 0,Sg ( x ) = 1, если x ≠ 0.3.