Формализация понятия алгоритма
    Для глубокого, строгого изучения свойств алгоритма и его организации необходима формализация, хотя бы для того, чтобы иметь возможность делать доказательные утверждения о свойствах алгоритма. Подчеркнем, что цель математического уточнения понятия Алгоритма - изучение его свойств, а не создание практического инструмента для построения алгоритмов.
    Один из возможных путей формализации состоит в том, чтобы подобрать понятия, уже известные в математике, и для которых уже разработан формализм. Одним из таких понятий-претендентов является функция. Действительно, на первый взгляд между функцией и алгоритмом есть много общего. У функции есть область определения, у алгоритма есть область применимости; у функции есть область допустимых значений, у алгоритма есть определенное множество результатов.
    Рассмотрим взаимосвязь между функцией и алгоритмом. Сразу отметим, что основные свойства этой взаимосвязи мы будем здесь приводить без доказательства. Тому есть как минимум две причины. Первая - у читателя не предполагается знания необходимого математического аппарата; вторая - это увело бы нас в сторону от основной цели - формализации понятия алгоритма.
    Определение 2.1. Говорят, что алгоритм А вычисляет функцию f(x), если:
    Существует взаимно однозначное соответствие ? между областью определения f(х) и областью применимости А;
    Для любого х из области определения f верно: f(x)= А(?(x))
    В этом случае функция f(x) называется вычислимой функцией.
    Определение 2.2. Говорят, что Алгоритм А разрешает множество М относительно множества Х, где М?Х, если:
    Для любого х из множества М верно, что А(х) = "истина";
    Для любого у из Х, но у не принадлежит М, А(у) ="ложь".
    В этом случае говорят, что множество М разрешимое.
    Примеры разрешающих алгоритмов - признаки делимости на 2, на 3, на 5. Эти алгоритмы разрешают множество натуральных чисел, кратных 2 (соответственно 3 либо 5), относительно всего множества натуральных чисел.
    Определение 2.3. Говорят, что алгоритм А перечисляет множество В если область применимости А есть множество натуральных чисел N, а совокупность результатов есть множество В.
    В этом случае В называется перечислимым множеством. Другими словами, в перечислимом множестве все элементы занумерованы целыми числами. Любой элемент в перечислимом множестве может быть найден по его номеру.
    Изучение свойств вычислимой функции, а стало быть и алгоритма, показало, что:
    Область применимости любого алгоритма - перечислимое множество; Следствие: алгоритмы не могут работать на множестве вещественных чисел.
    Функция f(x) вычислима тогда и только тогда, когда перечислим ее график, т.е. множество {(x, f(x))} перечислимо.
    Множество M?X разрешимо относительно множества X, когда M и X\M перечислимы.
    Отсюда видно, что понятие алгоритма не сводимо к понятию функции. Множество функций мощнее множества алгоритмов.
    Самое важное различие между этими понятиями для нас состоит в том, что алгоритм определяет некоторый процесс, который мы называем вычислительным. Понятие функции не предполагает и не определяет никакого процесса. ............