Примеры частично рекурсивных не всюду определенных функций

Оператор минимизации

Пусть задана некоторая 2-местная функция f (x, y). Зафиксируем значение х и выясним, при каком значении переменной y значение f (x, y) = 0. Эту задачу усложним: найти для функции f (x, y) при фиксированном значении хнаименьшее из тех значений y, при которых f (x, y) = 0.

Так как результат решения задачи зависит от х, то наименьшее значение y, при котором f (x, y) = 0, является функцией от х.

Принято для такой задачи следующее обозначение:

φ (x) = μy [ f (x, y) = 0]

(читается: наименьшее y такое, что f (x, y) = 0).

Аналогично определяется функция многих переменных:

φ (x ₁, x ₂,…, x_n)= μy [ f (x ₁, x ₂,…, x_n, y)=0].

Переход от функции f (x ₁, x ₂,…, x_n, y) к функции φ (x ₁, x ₂, …, x_n) называется применением μ – оператора минимизации.

Для вычисления функции φ можно предложить следующий алгоритм.

Вычислим f (x ₁, x ₂, …, x_n, 0). Если это значение равно нулю, то полагаем φ (x ₁, x ₂, …, x_n) = 0. Если f (x ₁, x ₂, …, x_n, 0) ≠ 0, то переходим к следующему шагу.

Вычислим f (x ₁, x ₂, …, x_n, 1). Если f (x ₁, x ₂, …, x_n, 1) = 0, то полагаем φ (x ₁, x ₂, …, x_n) =1.

Если же f (x ₁, x ₂, …, x_n, 1) ≠ 0, то переходим к следующему шагу и т. д.

Если окажется, что " y Є Ν функция f (x ₁, x ₂, …, x_n, y) ≠ 0, то функция φ (x ₁, x ₂, …, x_n) в этом случае считается неопределенной.

Но возможно, что существует такое y ₀, что f (x ₁, x ₂,…, x_n, y ₀) = 0 и, значит, есть и наименьшее y, при котором f (x ₁, x ₂, …, x_n, y) = 0; и в тоже время может случиться, что при некотором z (0< z < y ₀) значение функции f (x ₁, x ₂, …, x_n, z) не определено. Очевидно, что в этом случае процесс вычисления наименьшего y, при котором f (x ₁, x ₂, …, x_n, y) = 0 не дойдет до y ₀. И здесь функцию φ (x ₁, x ₂, …, x_n) считают неопределенной.

Иногда µ -оператор определяют с ограничением, полагая φ (x ₁, x ₂,…, x_n)= μy [ f (x ₁, x ₂, …, x_n, y) = z ] для y £ z, которое дает гарантию окончания вычислений. Это ограничение оценивает сверху количество шагов вычислений, и это является существенной особенностью примитивно рекурсивных функций.

µ -оператор (как ограниченный, так и неограниченный) является удобным средством для построения обратных функций.

Оператору минимизации можно придать привычную функциональную форму

f (x ₁, x ₂, …, x_n) = μy [ g (x ₁, x ₂, …, x_n, y) = 0].

Будучи применен к эффективно вычислимой функции, µ-оператор снова дает эффективно вычислимую функцию (т.е. сохраняет вычислимость).

Действительно, для вычисления функции

f (x ₁, x ₂, …, x_n) = μy [ g (x ₁, x ₂, …, x_n, y) = 0]

на наборе x ₁, x ₂, …, x_n существует следующая простая процедура: вычисляем g на наборах

(x ₁, x ₂, …, x_n, 0), (x ₁, x ₂, …, x_n, 1),...,

до тех пор, пока не получим значение 0. Однако в отличие от рассмотренных ранее процедур она может не привести к результату.

Это может произойти в том случае, когда на данном наборе x ₁, x ₂, …, x_n уравнение g (x ₁, x ₂, …, x_n, y)=0 не имеет решения. В таком случае функция f (x ₁, x ₂, …, x_n) считается неопределенной. Например, функция х –1= µу [ у+ 1 =х ], обратная к функции y = x +1,не определена при х =0, и в случае неопределенности процесс вычисления не останавливается (проблема остановки).

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

Частично рекурсивные, общерекурсивные функции и первое уточнение понятия алгоритма

Использование неограниченного µ -оператора (оператора минимизации), приводит к понятию частичнорекурсивнойфункции.

Определение 1. Частичная (то есть не всюду определенная) функция f называется частично рекурсивной (или просто рекурсивной), относительно системы частичных функций Ω, если она может быть получена из функций системы Ω и простейшихфункций 0, х’ и Iⁿ_m с помощью конечного числа применений операторов суперпозиции, примитивнойрекурсии и минимизации.

Свойства частично рекурсивных функций

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

Примеры частично рекурсивных не всюду определенных функций

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

Общерекурсивные функции

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

Определение 2. Частично рекурсивная функция называется общерекурсивной, если она определена для всех значений своих аргументов.

Понятие общерекурсивной функции может быть определено и независимо от понятия частично рекурсивной функции следующим образом.

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

g (x ₁, x ₂,…, x_n, y).

Из сказанного выше о неопределенности видно, что не всегда частично рекурсивную функцию можно эффективным образом доопределить до общерекурсивной функции. Более точно, существует такая частично рекурсивная функция f, что никакая общерекурсивная функция g не является ее доопределением.

Тезис Черча

Поделиться:

Воспользуйтесь поиском по сайту: