Теория алгоритмов. Зюзысов В.М. - 17 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

Под «конечной частью» функции f понимается некоторая конечная функция θ,
которая продолжается до f. (Функция θ называется конечной, если её область определения
есть конечное множество.)
Из приведенных выше соображений ясно, что в определении вычислимого
оператора должны участвовать эффективные вычисления с конечными функциями.
Придадим этому точный смысл, закодировав каждую конечную функцию
θ натуральным
числом g(θ). Удобный для наших целей кодирующий алгоритм определяется следующим
образом.
Пусть p
k
(k = 0, 1, 2,…) обозначает последовательность простых чисел 2, 3, 5, 7,
11, … Для данного θ∈F положим
g(θ) =
, где k ∈ D
∏
+
k
k
k
p
1)(
θ
θ
≠∅,
g(θ) = 0, если D
θ
= ∅.
Имеется простой алгоритм, с помощью которого можно для любого числа z определить,
верно ли z = g(θ) для некоторой конечной функции θ, и, если ответ на вопрос
положителен, выяснить, принадлежит ли некоторое заданное x множеству D
θ
, и если да,
то вычислить значение θ(x).
Сформулируем теперь наше определение.
Рекурсивный оператор
Оператор Φ: F→F называется рекурсивным (или вычислимым), если существует
вычислимая функция φ(z, x), такая, что для всех f ∈ F и x, y ∈ N
Φ(f)(x) = y тогда и только тогда, когда существует конечная функция θ ⊆ f, такая, что
φ(g(θ), x) = y.
Число g(θ) – кодовый номер функции θ.
Пример. Оператор Φ(f) = 2f является рекурсивным оператором. Чтобы убедиться в
этом, положим
2θ(x), если z = g(θ) и x∈D
θ
,
φ(z, x) =
не определена в остальных случаях.
В силу тезиса Чёрча функция φ вычислима. Далее, для любых f, x, y мы имеем Φ(f)(x) = y
⇔ x∈D
f
и y = 2f(x) ⇔ существует θ ⊆ f, для которой x∈D
θ
и y=2θ(x) ⇔ существует θ ⊆ f,
для которой φ(g(θ), x) =y. Отсюда Φ – рекурсивный оператор.
Важное свойство рекурсивных операторов состоит в том, что они непрерывны и
монотонны в следующем смысле.
Непрерывный оператор
Оператор Φ: F→F называется непрерывным, если для любой функции f∈F и любых x, y:
Φ(f)(x) = y тогда и только тогда, когда существует конечная функция θ ⊆ f, такая, что
Φ(θ)(x) = y.
Монотонный оператор
Оператор Φ: F→F называется монотонным, если для любых функций f, h∈F таких, что
f ⊆ h, выполняется условие Φ(f) ⊆ Φ(h).

Страницы