Основная терминология теории алгоритмов.

Областью применимости алгоритманазывается совокупность тех объектов, к которым он применим. Про алгоритмUговорят, что он:

1. «Выявляет функцию f», коль скоро его область применимости совпадает с областью определенияf, иUперерабатывает всякий х из своей области применимости вf(x);

2. «Разрешает множество А относительно множества Х», коль скоро он применим ко всякому х из Х и перерабатывает х из ХА в слово «да», а всякий х из Х\А в слово «нет»;

3. «Перечисляет множество В», коль скоро его область применимости есть натуральный ряд, а совокупность результатов есть В.

Функция называется вычислимой, если существует вычисляющий ее алгоритм. Множество называетсяразрешимым (рекурсивным)относительно Х, если существует разрешающий его относительно Х алгоритм. Множество называетсяперечислимым (рекурсивно-перечислимым), если либо оно пусто, либо существует перечисляющий его алгоритм.

Замечания:

1. Область возможных исходных данных и область применимости любого алгоритма суть перечислимые множества;

2. Для любой пары вложенных одно в другое перечислимых множеств можно подобрать алгоритм, у которого большее множество служит областью возможных исходных данных, а меньшее областью применимости.

3. Разрешимые и перечислимые множества являются множествами, строение которых задается с помощью тех или иных алгоритмических процедур.

4. Процесс выполнения алгоритма называется алгоритмическим процессом.