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




rene-dekart-razmishleniya-o-pervoj-filosofii-stranica-4.html
rene-dekart-rodilsya-v-imenii-svoih-aristokraticheskih-predkov-v-yuzhnoj-tureni-31-marta-1596-g-s-1604-po-avgust-1612-g.html
Лекция 13.

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

Рекурсивные функции и невозможность их эффективного перечисления.
Теорема: рекурсивные функции не поддаются эффективному перечислению.
Док-во
На уровне тезисов:

Из тезиса Чёрча: всякая арифметическая функция, вычислимая в обычном смысле(ВАФ) есть рекурсивная функция (РФ), а всякая частичная арифметическая функция (ЧАФ) вычислимая в обычном смысле есть частично рекурсивная функция(ЧРФ) . Известно (теорема Тьюринга) что ВАФ эффективно не перечислимы. Отсюда следует что и РФ эффективно не перечислимы (так как ВАФ эффективно не перечислимы, а ВАФ есть РФ).
Строгое (по сути копия док-ва теоремы Тюринга)

Допустим, что множество рекурсивных функций n-переменных эффективно перечислимо.

Тогда существует алгоритм, по которому их можно перечислить. Применим этот алгоритм. Получим последовательность

F0(x1,…,xn), F1(x1,…,xn),.. Fn(x1,…,xn),..

Построим диагональную функцию:




Fx1(x1,…,xn)+1, при x1=…=xn
G(x1,…,xn)=
0, в противном случае
Процедура вычисления G. Для любых значений x,y,z мы можем сначала провести операцию сравнения, и затем, если x=y=z, отыскать функцию Fx. Далее применить к ней алгоритм вычисления функции Fx(x,x,x) в заданной точке. Такой алгоритм существует в силу рекурсивности функций вида Fi(x1,…,xn). Прибавление к результату вычисления единички есть тривиальная рекурсивная функция операция. Т.о. видно, что эта диагональная функция будет тоже рекурсивной.

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

Возьмем рекурсивную но не примитивно-рекурсивную функцию f(x). Построим  g(x) след образом:
g(x)=f(x) если машина Тx не остановится за первые x+1 тактов
g(x)=0 во всех иных случаях

Функция g(x) тоже рекурсивна (в силу того, что она вычислима). Но на самом деле если Тх все таки остановится, то g(x) будет являться также примитивно-рекурсивной (потому что функция, отличная от нуля в конечном числе точек всегда примитивно-рекурсивна). Пусть мы умеем (знаем какой то алгоритм) распознавать примитивно-рекурсивные функции среди рекурсивных. Применим этот алгоритм к произвольной рекурсивной фунции – если удастся сказать является ли она примитивно-рекурсивной, значит окажется решенной и задача об остановке машины Тьюринга., что противоречит ранее доказанной теореме.

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

Невозможность эффективной распознаваемости рекурсивных функций среди частично рекурсивных функций.
Теорема: Рекурсивные функции не поддаются эффективному распознаванию среди частично рекурсивных функций.
Док-во
на уровне тезисов:

Понятие рекурсивных функций совпадает с ВАФ, а понятие частично рекурсивной функции совпадает с ВЧАФ. А так как ВАФ не распознается среди ВЧАФ, то рекурсивные функции не поддаются эффективному распознаванию среди частично рекурсивных функций.
строгое:

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


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

Итак, мы хотим найти по возможности простые, но очень быстрорастущие функции. Опыт показывает, что произведение растет быстрее суммы, степень быстрее произведения. Называя сложение, умножение и возведение в степень действиями 0-й, 1-й и 2-й ступени и вводя для них в целях единообразия обозначения:

P0 (a, x)=a+x, P1 (a, x)=a*x, P2(a, x)=ax,

приходим к знакомой всем идее о продолжении этой последовательности путем введения действий высших ступеней. При этом действие высшей ступени должно возникать из действия предыдущей ступени так же, как умножение возникает из сложения, возведение в степень из умножения. Функции Р0, Р1, Р2 связаны следующими соотношениями:

P1(a, x+1)=P0(a, P1(a, x)), P1(a, 1)=a, (1)

P2(a, x+1)=P1(a, P2(a, x)), P2(a, 1)=a.

Продолжим эту цепочку, полагая по определению для n=2, 3,…

Pn+1(a, 1)=a, (2)

Pn+1(a, x+1)=Pn(a, Pn+1(a, x)). (3)

Чтобы функции Pn(a, x) были определены всюду, положим Pn+1(a, 0)=1 (n=1, 2,…) и соотношения (2), (3) будем считать определениями функций Pn(a, x) для n=2, 3,… Ясно, что равенства (1) вытекают из соотношений (2), (3) и соотношения P1(a,0)=0. В силу (2), (3), например, имеем:

P3(a, 0)=1, P3(a, 1)=a, P3(a, 2)=aa, P3(a, 3)=(aa)a.

Вводим новые функции B(n, x)=Pn(2,x), A(x)=B(x, x).

Функции B(n, x) часто называют функциями Аккермана, а функцию A(x) – диагональной функцией Аккермана.

Итак, следующая система уравнений определяет рекурсивно неко­торую функцию А (х)
A(0, y) = y’,

A(x’, 0) = A(x, 1),

A(x’, y’) = A(x, a(x’, y)),

A(x) = A(x, x)

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

Например, зададим функцию f(x) следующим образом
f(x)=1 если машина Тьюринга Tx останавливается на чистой ленте

f(x)=0 если машина Тьюринга Tx никогда не остановится на чистой ленте
Значения везде определены (0 или 1), но вычислены быть не могут, иначе бы это означало что решена задача об остановке произвольной машины Тьюринга. алгоритм

mpedagog.ru