11 - Рекурсивные функции. Примитивно рекурсивные функции. Предикаты, простые числа и возвратная рекурсия. Частично рекурсивные функции (Конспект лекций), страница 4

, xn , y) равно нулюнезависимо от значения переменной y. Тогда оператор минимизации дает неопределенное значение. Внешне это выглядит как бесконечная проверка y = 1, 2, 3, . . . , которая никогда незаканчивается — ситуация, аналогичная неприменимости нормального алгорифма или машины Тьюринга.Если частично рекурсивная функция определена при любых значениях аргументов, ее называют общерекурсивной.ÌÃÒÓÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓ120ÌÃÒÓÌÃÒÓÌÃÒÓ121gn2?Z0gnmZ0?fm??gn1ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-1211. Рекурсивные функции¹¤бA2DlDlSl+11ÔÍ-12SlZ0Z02gn+ÌÃÒÓаZ0вРис.

11.2ÌÃÒÓÔÍ-12ÌÃÒÓDlÔÍ-12ÔÍ-12Z0SlÔÍ-12ÔÍ-12A2ÌÃÒÓfL1A1ÌÃÒÓ=¤DlÔÍ-12idA3ÌÃÒÓA1ÔÍ-12Перейдем к оператору примитивной рекурсии, который определяет функцию hn+1 по функциям f n и g n+2 . Чтобы вычислить функцию hn+1 для аргументов x1 , x2 , . . . , xn , y, необходимомногократно вычислять функцию g n+2 , а функцию f n использовать как начальное значение. Врезультате наш алгоритм реализуется как повторение с предусловием (рис. 11.2, а). АлгоритмA1 формирует γ-систему 01x1 0 . . . 01xn 01i 01z 01y 0, где i — текущее значение последнего аргумента функции hn+2 , z — текущее значение самой функции hn+2 , y — счетчик рекурсии.

Начальноезначение i нулевое, а начальное значение z есть f n (x1 , x2 , . . . , xn ). Далее на каждом шаге мыпроверяем условие y = 0 (алгоритм L1 ). Если оно выполняется, выделяем из γ-системы словоz и предъявляем как результат (алгоритм A3 ). Если же y > 0, то в γ-системе заменяем z наg n+2 (x1 , x2 , . . .

, xn , y, z), а y на y − 1 (алгоритм A2 ).Алгоритм A1 можно представить как соединение нескольких алгоритмов (рис. 11.2, б). Вэтом соединении алгоритм Dl удаляет последний элемент γ-системы, алгоритм Sl , наоборот,извлекает из γ-системы последний элемент, алгоритм id пустой, алгоритм f реализует вычисление функции f , алгоритм Z0 удаляет лидирующий нуль в γ-системе. Структура алгоритмаA2 представлена на рис. 11.2, в, алгоритмы, обозначенные +1“ и −1“, соответственно при””бавляют к числу 1 и вычитают. Алгоритм L1 реализуется как композиция двух алгоритмов:первый алгоритм Sl извлекает из γ-системы параметр y, второй проверяет условие y = 0 исостоит из одной подстановки 00 →· Λ. Наконец, алгоритм A3 есть композиция алгоритмов Dl(удаляет счетчик y) и Sl (извлекает z).Оператор минимизации также реализуется как повторение с предусловием. Формируем γ-систему 01x1 0 .

. . 01xn 01y 0. Начальное значение y нулевое. На каждом шаге проверяем значениеÌÃÒÓÌÃÒÓРис. 11.1ÌÃÒÓn(X) = js + js−1 ∗ m + j1 ∗ ms−1 .i = 1, 4,где u0 = (u01 , u02 , u03 , u40 ). Это похоже на примитивную рекурсию, но все четыре функцииперевязаны.

Выход: упаковать все четыре функции в одну так, что каждая извлекается изÔÍ-12ui (u0 , 0) = u0i , ui (u0 , t + 1) = u0i (u1 (u0 , t), u2 (u0 , t), u3 (u0 , t), u4 (u0 , t)),ÌÃÒÓТаким образом, один шаг машины Тьюринга описывается четырьмя функциями, которыев силу их представления являются примитивно рекурсивными. Для описания многошаговойработы нужно ввести еще один аргумент, играющий роль времени: t = 0 соответствует начальной конфигурации машины Тьюринга, t = k — конфигурации, полученной после k-го шага.В результате получим функции ui (t), которые определяются следующим образом:ÔÍ-12Каждому состоянию qi ставим в соответствие число i. Представленная числовая интерпретация элементов машины Тьюринга называется ее арифметизацией. Арифметизация машиныТьюринга позволяет любую конфигурацию Xqj ai Y представить как совокупность четырех чисел: n(X), j, i, n(Y ), Y — слово Y в обратном порядке. Инверсия слова Y позволяет пустыесимволы неограниченной ленты интерпретировать как незначащие разряды числа.

Каждыйшаг машины Тьюринга состоит из трех действий, зависящих от внутреннего состояния qjи обозреваемого символа ai : смене внутреннего состояния, замене обозреваемого символа исдвиге читающей головки. Каждое из этих действий описывается соответствующей функцией:внутреннее состояние q̂(j, i), печатаемый символ â(j, i), сдвиг ŝ(j, i), который можно описатьтремя значениями 0 (сдвига нет), 1 (влево), 2 (вправо). Каждая из этих функций определенана конечном множестве пар натуральных чисел.

Доопределив их нулевым значением вне этогомножества, получим примитивно рекурсивные функции.Каждую конфигурацию Xqj ai Y , как сказано, можно представить как совокупность четырехчисел u1 = n(X), u2 = j, u3 = i, u4 = n(Y ). Один шаг машины Тьюринга можно представить0как преобразование этих чисел в новую четверку u01 = n(X 0 ), u02 = j 0 , u03 = i0 , u04 = n(Y ). Этопреобразование описывается функциямиs(u2 , u3 ) = 0;u1 ,0s(u2 , u3 ) = 1;u1 = [u1 /m],u02 = q̂(u2 , u3 );u ∗ m + â(u , u ), s(u , u ) = 2;12323s(u2 , u3 ) = 0;â(u2 , u3 ), s(u2 , u3 ) = 0;u4 ,00u3 = u1 mod m, s(u2 , u3 ) = 1;u4 = u4 ∗ m + â(u2 , u3 ), s(u2 , u3 ) = 1;u mod m, s(u , u ) = 2;[u /m],s(u2 , u3 ) = 2.4234ÌÃÒÓÔÍ-12ÌÃÒÓJ В данной теореме мы будем ориентироваться на машины Тьюринга, учитывая, что вычислимость по Тьюрингу равносильна вычислимости по Маркову.

Конечно, и машины Тьюринга,и нормальные алгорифмы реализуют словарные функции; числовые функции трактуются какособый тип словарных функций. Но для доказательства теоремы такой трактовки недостаточно, поскольку в процессе работы алгоритм часто выходит за рамки двухбуквенного алфавита.Поэтому необходимо любой словарной функции придать смысл функции числовой.Пусть A = a0 a1 . . . am−1 — внешний алфавит машины Тьюринга, Q = q0 q1 .

. . qn−1 — еевнутренний алфавит. Каждое слово в алфавите A можно интерпретировать как запись числав системе исчисления с основанием m и цифрами a0 , a1 , . . . , an , т.е. слову X = aj1 aj2 . . . ajs мыставим в соответствие числоÔÍ-12ÔÍ-12Теорема 11.9. Любая функция, вычислимая по Тьюрингу (Маркову), частично рекурсивна.ÌÃÒÓÌÃÒÓпредиката P . Если значение 0, увеличиваем значение y на единицу и процедуру проверки повторяем. Если P = 0, выделяем из γ-системы последнее слово и завершаем работу алгоритма. IÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ИУ-9, МЛТА, 2009-10уч.г.ÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓ122ÌÃÒÓиз которых видно, что это преобразование есть примитивно рекурсивная функция. Второепреобразование обратное.

Его можно интерпретировать как пересчет числа в сумму его цифр.Можно показать, что она примитивно рекурсивна. С учетом этого факта заключаем, что функция f (x1 , x2 , . . . , xn ) частично рекурсивна. IТеорема 11.10 (теорема Клини о нормальной форме). Для каждого натуральногоn > 1 существуют такая примитивно рекурсивная функция F 1 и такой примитивно рекурсивный предикат Dn+2 , что для любой n-арной частично рекурсивной функции f n при некоторомзначении l имеет место представлениеКак видим, любая частично рекурсивная функция может порождаться только одним применением оператора примитивной рекурсии.Пусть F n — некоторое множество n-арных частично рекурсивных функций.

Скажем, чтофункция U n+1 является универсальной для множества F n , если оно совпадает с множествомÔÍ-12f n (x1 , x2 , . . . , xn ) ' F 1 (µyDn+2 (l, x1 , x2 , . . . , xn , y)). #ÌÃÒÓПусть дана (n + 1)-арная частично рекурсивная функция f (x0 , x1 , . . . , xn ). Ясно, что длялюбого конкретного числа l функция gl (x1 , x2 , . . . , xn ) = f (l, x1 , . . . , xn ) является частично рекурсивной. Другими словами, каждая частично рекурсивная функция от n + 1 аргументовпорождает счетное семейство частично рекурсивных функций от n аргументов. Может либыть такое, что это семейство накрывает множество всех частично рекурсивных функций отn аргументов? Существование универсального алгорифма наталкивает на мысль, что такоевполне возможно.Ключевым пунктом здесь является следующая теорема.ÔÍ-1211.4.

Универсальные рекурсивные функцииÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12n(X) = m + . . . + mxn + mxn +2 + mxn +3 + . . . + mxn +xn−1 +2 + . . . ,ÌÃÒÓÌÃÒÓупакованного варианта с помощью примитивно рекурсивной функции (например, используяхарактеристическую функцию как в возвратной рекурсии).Наконец, условие останова реализуется с помощью оператора минимизации. Сперва определяется t как функция начальной конфигурации: t = µτ (u2 (u0 , t) = 0). Затем эта функцияначальных условий подставляется в функции ui , и мы получаем ui как функции только начальных условий.Можно считать, что машина Тьюринга начинает и завершает работу в стандартном положении, т.е. с положением читающей головки перед первым символом.

Тогда в начале работыu01 = 0, u01 = 1, u02 = X mod m, u03 = [X/m], в конце работы Y = ue4 ∗ m + ue3 . Здесь X — исходноеслово, Y — результирующее слово, в которое машина Тьюринга преобразовала слово X. В результате мы получили интерпретацию работы машины как вычисление частично рекурсивнойфункции.Пусть задана функция f (x1 , x2 , . . .