Понятие алгоритма

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

Таким образом, можно считать, что алгоритм - это преобразование слов из заданного алфавита: исходное слово перерабатывается (переписывается) алгоритмом в результирующее слово. Каким бы ни был конечный алфавит, любой его символ может быть закодирован с помощью двоичного алфавита. Иначе говоря, входные данные алгоритма могут быть представлены конечной цепочкой битов. То же самое можно сказать и о выходных данных. Конечная цепочка битов может интерпретироваться как целое неотрицательное число.

Из этого можно сделать важный вывод: любому алгоритму может быть поставлена в соответствие функция, отображающая множество неотрицательных целых чисел в себя. Однако мы не утверждаем обратного. Более того, существуют функции, не вычисляемые никаким алгоритмом. Вычислимой функцией будем называть функцию, вычисляемую некоторым алгоритмом.

Теперь нужно предложить способ описания шагов алгоритма. Известно несколько подходов к формализации понятия «алгоритм»:

Все эти возникшие исторически независимо друг от друга подходы оказались впоследствии эквивалентными. Главная цель формализации понятия алгоритма такова: подойти к решению проблемы алгоритмической разрешимости различных математических задач, т.е. ответить на вопрос, может ли быть построен алгоритм, приводящий к решению задачи. Вместе с тем, формально определенный любым из известных способов алгоритм не может в практическом программировании заменить то, что мы называли алгоритмами в предыдущем параграфе. Основная причина состоит в том, что формальное определение резко сужает круг рассматриваемых задач, делая многие практически важные задачи недоступными для рассмотрения.