Основные понятия А. т.
Областью применимости алгоритма наз. совокупность тех
объектов, к которым он применим. Про алгоритм Я говорят, что он: 1) "вычисляет
функцию f", коль скоро его область применимости совпадает с областью определения
f и Я перерабатывает всякий х из своей области применимости в f(x); 2)
"разрешает множество А относительно множества X", коль скоро он применим
ко всякому x из X и перерабатывает всякий x из
з слово "да", а всякий x из Х\Л в слово "нет"; 3)"пе-речисляет множество
В", коль скоро его область применимости есть натуральный ряд, а совокупность
результатов есть В. Функция наз. вычислимой, если существует вычисляющий
её алгоритм. Множество наз. разрешимым относительно X, если существует
разрешающий его относительно X алгоритм (см. Разрешимое множество). Множество
наз. перечислимым, если либо оно пусто, либо существует перечисляющий его
алгоритм (см. Перечислимое множество).
Детальный анализ
понятия "алгоритм" обнаруживает, что (I) область возможных исходных данных
и область применимости любого алгоритма суть перечислимые множества. В
свою очередь (II) для любой пары вложенных одно в другое перечислимых множеств
можно подобрать алгоритм, у к-рого больщее множество служит множеством
исходных данных, а меньшее - областью применимости. Имеют место следующие
основные теоремы: (III) функция f вычислима тогда и только тогда, когда
перечислим её график, т. е. множество всех пар вида <x,f(x)>. (IV) Подмножество
А перечислимого множества X тогда и только тогда разрешимо относительно
X, когда А и Х\А перечислимы. (V) Если Л и В перечислимы, то
также перечислимы.
(VI) В каждом
бесконечном перечислимом множестве X существует перечислимое подмножество
с неперечислимым дополнением [ в силу (IV) это перечислимое подмножество
будет неразрешимым относительно X].
(VII) Для каждого
бесконечного перечислимого множества X существует вычислимая функция, определённая
на подмножестве этого множества и не продолжаемая до вычислимой функции,
определённой на всём X. Утверждения (VI) и (II) в совокупности дают упоминаемый
в ст. Алгоритм пример алгоритма
с неразрешимой
областью применимости.
А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я