На этом шаге мы рассмотрим точное понятие алгоритма.
Следующая задача заключается в том, чтобы ввести точное, формальное понятие алгоритма. Как заметил Э.Дейкстра в книге «Дисциплина программирования», преимущество формального способа записи состоит в том, что он дает нам возможность изучать алгоритмы как математические объекты; при этом формальное описание алгоритма служит основой, позволяющей нам интеллектуально охватить этот алгоритм. Благодаря этому сумеем доказать теоремы о классах алгоритмов.
Для того чтобы дать точное понятие алгоритма, необходимо определить, как задаются данные, с которыми будет работать исполнитель, и как задаются элементарные шаги, из которых состоит алгоритм. Уже было сказано, что в качестве данных будем рассматривать конструктивные объекты. Опыт использования математики показывает, что любой объект может быть описан некоторым набором фраз на некотором языке, иначе говоря, представлен (закодирован) цепочкой символов. Это достаточно общий подход. Если объект - число, то его можно записать в десятичной или двоичной форме, т.е. цепочкой символов алфавита {0,1}. Если объект - программа, то она является цепочкой символов в алфавите, содержащем буквы, цифры и специальные символы. Если объект - изображение, то он представляется массивом пикселей, а каждый пиксель - тремя числами (интенсивностями красного, зеленого и синего цветов), т.е. изображение также может быть закодировано строкой символов. Современные высококачественные системы цифровой записи звука показывают, что и этот объект может быть адекватно описан строкой символов. Хотя представление данных - самостоятельная проблема в компьютерных науках, а эффективное представление - это в значительной степени искусство программиста, тем не менее, можно утверждать, что существует универсальный способ представления данных - словами в некотором алфавите.
Таким образом, можно считать, что алгоритм - это преобразование слов из заданного алфавита: исходное слово перерабатывается (переписывается) алгоритмом в результирующее слово. Каким бы ни был конечный алфавит, любой его символ может быть закодирован с помощью двоичного алфавита. Иначе говоря, входные данные алгоритма могут быть представлены конечной цепочкой битов. То же самое можно сказать и о выходных данных. Конечная цепочка битов может интерпретироваться как целое неотрицательное число.
Из этого можно сделать важный вывод: любому алгоритму может быть поставлена в соответствие функция, отображающая множество неотрицательных целых чисел в себя. Однако мы не утверждаем обратного. Более того, существуют функции, не вычисляемые никаким алгоритмом. Вычислимой функцией будем называть функцию, вычисляемую некоторым алгоритмом.
На следующем шаге мы рассмотрим подходы к формализации понятия "алгоритм".
