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

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

Определим теперь новую функцию g формулой
g(n) = f
n
(n)+1.
Она не входит в нашу последовательность, поскольку при n=1 она отличается от f
1
,
при n=2 – от f
2
и т. д. Следовательно, она не вычислима.
С другой стороны, ясно, что она вычислима, так как f
n
(n) вычислима, а прибавив 1
к f
n
(n), мы получим g(n).
Этот парадокс можно объяснить. На самом деле мы здесь используем две
формальные системы. В рамках одной системы (скажем, элементарной арифметики EA),
мы описываем вычислимые функции f, а то, что g является вычислимой функцией мы
получаем в рамках другой формальной системы, в которой уже используется возможность
упорядочить
f. Вторая формальная система является надсистемой или метасистемой
относительно первой.
2.2 Теорема о рекурсии
После изучения эффективно вычислимых операций на множестве чисел,
естественно рассмотреть вопрос о том, существует ли понятие подобного рода и для
операций над функциями. Существенная разница между функциями и числами (если их
рассматривать как множества основных объектов) состоит в том, что первые являются,
как правило, бесконечными объектами, а вторые – конечными.
Для простоты
изложения мы будем рассматривать частичные функции только
одного аргумента, но все определения и полученные результаты обобщаются и на случай
функций от нескольких аргументов.
Обозначим через F класс всех частичных функций из N в N. Словом оператор мы
будем обозначать функцию Φ: F→F, причем будем рассматривать лишь такие операторы
Φ, область
определения которых совпадает со всем классом F.
Основная проблема при попытке дать определение понятию вычислимого (или
эффективного) оператора Φ: F→F состоит в том, что как вводимая функция f, так и
выводимая функция Φ(f) являются, скорее всего, бесконечными объектами и,
следовательно, не могут быть заданы за конечное время. В то
же время, согласно нашему
интуитивному представлению об алгоритмических процессах, мы должны в некотором
смысле уметь проводить их за конечное время.
Чтобы разобраться, как можно преодолеть эту трудность, рассмотрим следующие
операторы из F в F:
1) Φ
1
(f) = 2f,
2) Φ
2
(f) = g, где g(x) = .
∑
≤xy
yf )(
Эти операторы, несомненно, очень естественны и записаны в явном виде. На интуитивном
уровне их вполне можно было бы считать вычислимыми. Попытаемся сейчас разобраться,
почему. Пусть f∈F. Рассмотрим случай g
1
= Φ
1
(f). Заметим, что любое конкретное
значение g
1
(x) (если оно определено) может быть вычислено за конечное время по одному
единственному значению f(x) функции f. В случае g
2
= Φ
2
(f) для вычисления значения g
2
(x)
(если оно определено) необходимо знать конечное число значений f(0), f(1), …, f(x). Тем
самым в обоих случаях любое определенное значение выводимой функции (Φ
1
(f) или
Φ
2
(f)) может быть эффективно вычислено за конечное время при использовании лишь
конечной информации о вводимой функции f. В этом и состоит суть приведенного ниже
определения рекурсивного оператора.
Для того чтобы дать определению точный смысл, условимся о некоторых
технических деталях. Если f, g – функции, то будем говорить, что g продолжает f,
если D
f
⊆D
g
и f(x) = g(x) для всех x∈D
f
. Это отношение функций f, g записывается как f⊆g.

Страницы