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

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

2. Если на вход алгоритма A поступил вектор x, не принадлежащий области определения
D
f
, то алгоритм A никогда не заканчивается.
Несколько замечаний по поводу этого определения:
1. Понятие вычислимости определяется здесь для частичных функций (областью
определения которых является некоторое подмножество натурального ряда).
Например, нигде не определенная функция вычислима, в качестве A надо взять
программу, которая всегда зацикливается.
2. Можно было бы изменить определение, сказав так: «если f(x) не определено, то
либо
алгоритм A не останавливается, либо останавливается, но ничего не печатает на
выходе». На самом деле от этого ничего бы не изменилось (вместо того, чтобы
останавливаться, ничего не напечатав, алгоритм может зацикливаться).
3. Входами и выходами алгоритмов могут быть не только натуральные числа, но и
двоичные строки (слова в алфавите {0, 1}), конечные
последовательности слов и
вообще любые, как говорят, «конструктивные объекты».
4. Множество эффективно вычисляемых функций мы не отождествляем с множеством
«практически вычисляемых» функций, так как не накладываем на первое множество
никаких ограничений, связанных с современными вычислительными машинами. Хотя
каждое входное натуральное число должно быть конечным, тем не менее не
предполагается верхняя
граница размера этого числа, так, например, количество цифр
числа может быть больше числа электронов во Вселенной. Точно так же нет никакой
верхней границы на число шагов, которые может сделать алгоритм для конкретных x
из области определения.
Рассматривая теорию алгоритмов, мы можем ссылаться на программистский опыт,
говоря об алгоритмах, программах, интерпретаторах и
т. д. Это позволяет нам
игнорировать детали построения тех или иных алгоритмов под тем предлогом, что
читатель их легко восстановит (или хотя бы поверит). Но в некоторых случаях этого
недостаточно, поэтому мы собираемся дать строгое определение нового множества
функций, которое в некотором смысле будет совпадать с множеством вычислимых
функций. Мы
дадим три различные формализации понятия вычислимой функции.
1.2 Частично-рекурсивные функции
Определения
Этот подход к формализации понятия алгоритма
принадлежит Гёделю и Клини (1936).
Основная идея Гёделя состояла в том, чтобы получить все
вычислимые функции из существенно ограниченного множества
базисных функций с помощью простейших алгоритмических
средств.
Множество исходных функций таково:
постоянная функция 0(x) = 0; •
•
•
•
одноместная функция следования s(x) = x+1;
функция проекции pr
i
, 1 ≤ i ≤ k, pr
i
(x) = x
i
.
Нетривиальные вычислительные функции можно получать с
помощью композиции (суперпозиции) уже имеющихся функций.
Этот способ явно алгоритмический.
Стивен Коул
Клини
Оператор суперпозиции. Говорят, что k-местная функция f(x)
получена с помощью суперпозиции из m-местной функции ϕ(y
1
, y
2
, ..., y
m
) и k-местных
функций g
1
(x), g
2
(x), ..., g
m
(x), если f(x) = ϕ(g
1
(x), g
2
(x), ..., g
m
(x)).
Второй (несколько более сложный) способ действует так.

Страницы