12.. Оператор минимизации, алгоритм его вычисления. Определение

класса частично-рекурсивных функций. Понятие алгоритма.

Пусть f- некоторая n-местная вычислимая функция, n ≥ 1, алгоритм вычисления f известен. Вычисление значения функции f для некоторого значения аргумента невозможно лишь тогда, когда алгоритм не может завершиться.

Зафиксируем некоторые значения первых n - 1 переменных х₁, х₂, ..., х_n-1. Рассмотрим уравнение:

f(х₁, х₂,..., х_n-1,y)=x_n (3)

Для его решения начнем вычислять последовательно значения функции f(х₁, х₂,..., х_n-1,y) для y=0,1,2,... . Наименьшее число k такое, что f(х₁, х₂,..., х_n-1,k)=x_n есть решение этого уравнения. Это решение обозначается μ_y(f(х₁, х₂,..., х_n-1,y)=x_n). Решения может и не оказаться, например, если:

1. значения f(х₁, х₂,..., х_n-1,k), k = 0, 1, 2, ... определены и отличны от x_n, а значение f(х₁, х₂,..., х_n-1,k+1) не определено,

2. значения f(х₁, х₂,..., х_n-1,k), k = 0, 1, 2, ... все определены и отличны от x_n.

В таких случаях значение μ_y(f(х₁, х₂,..., х_n-1,y) = х_n) считается неопределенным. Величина μ_y(f(х₁, х₂,..., х_n-1,y) = х_n) зависит от значений переменных х₁, х₂,..., х_n-1, х_n и потому она может рассматриваться как значение функции от аргументов х₁, х₂,..., х_n-1, х_n. Эта функция обозначается Mf, M называется оператором минимизации. Если f - одноместная функция, то очевидно, что f¹(х) = μ_y(f(y)=x).

Оператор минимизации очевидно вычислим, а значит, и функция Mf частично вычислима.

Функция f называется частично рекурсивной относительно простейших функций, если она строится конечным числом применений операторов суперпозиции, примитивной рекурсии и минимизации.

Перефразируя, можно сказать, что функция называется частично рекурсивной, если она представляется конечным операторным термом. В соответствии с тезисом Черча класс частично рекурсивных функций совпадает с классом всех вычислимых функций.

Как и для оператора примитивной рекурсии, для оператора минимизации можно построить представление в виде счетного множества функциональных термов. Введем предикат P(y_i):f(х₁, х₂,..., х_n-1, y_i) = х_n.

Т огда оператор минимизации представляется счетным множеством функциональных термов (рис. 2.4). Предикат Р(у_i) выделяет функциональный терм, который вырабатывает значение функции μ_y(f(х₁, х₂,..., х_n-1,y) = х_n).

Рис. 2.4

Из всех этих термов лишь один может выработать значение функции Mf, а именно тот, который выработает значение z_k = х_n для минимального k. Таким образом, и здесь, как и в случае оператора примитивной рекурсии, операторный терм Mf представляется счетным множеством функциональных термов. Одно из существенных отличий состоит в том, что конечное множество функциональных термов, представляющих оператор примитивной рекурсии, фиксируется для конкретных значений до начала вычислений. В случае оператора минимизации терм, вычисляющий значение функции, определяется динамически в ходе вычисления. Алгоритм – функциональный терм