Конспект установочных лекций по комплексному курсу Информатика, Теория информации




Рекурсивные функции - часть 5


Функция g, реализующая для универсальной функции указанное выше вычисление min по схеме m (см. ниже):

g(i) = min{x Î N: F(i, х) = 0},

является, очевидно, частичной и вычислимой. Заметим, однако, что функция g , доопределяющая функции g следующим образом:

g=[ g(i), если нулевое место существует; 1 в противном случае],

не является вычислимой (см. десятую проблему Гильберта).

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

Пример (недоказанная завершаемость). Пусть отображение ulam специфицировано через

Ulam(n)=[1,n<1;ulam(g(n)) в противном случае]

причем функция g специфицирована следующим образом:

g(n)=[n/2,n- четно;$*n+1  иначе]

Обратим внимание, что функция g примитивно-рекурсивна. Это можно показать следующим образом. Отображение

Even(n)=[1,n-четно; 0  иначе]

является примитивно-рекурсивным. Функция g специфицирована через различение двух примитивно-рекурсивных функций и тем самым сама является таковой.

В зависимости от вопроса, завершается ли вычислительное предписание ulam для всех аргументов, справедливы следующие высказывания:

(1)                Если предписание ulam завершается всегда, то для всех n Î N справедливо

ulam(n) = 1.  При этом предположении функция ulam примитивно-рекурсивна.

(2) Если для определенных входных значений ulam не завершается, то ulam есть частичная функция и потому определенно непримитивно-рекурсивна, так как примитивно-рекурсивная функция всегда тотальна. Форма описания функции ulam не позволяет сделать заключение, что эта функция является примитивно-рекурсивной.

До сих пор не удалось показать завершаемость функции ulam.

Очевидно, что формализм примитивной рекурсии не достаточно мощен.


Содержание  Назад  Вперед