В теоретических подходах к построению строгого определения понятия алгоритма исторически выделились три основные направления.
Первое направление связано с рассмотрением алгоритмов, позволяющих вычислить значение числовых функций, зависящих от целочисленных значений аргументов - такие функции получили название вычислимых. Понятие вычислимой функции не является строгим, как и понятие алгоритма. Однако, благодаря работам А. Черча, К. Геделя, С. Клини, была обоснована тождественность класса всюду определенных вычислимых функций с классом частично рекурсивных функций, который определяется строго. Это позволило свести проблему алгоритмической разрешимости к
доказательству возможности (или невозможности) построения рекурсивной функции, решающей задачу. Именно этим путем А. Черчу удалось доказать неразрешимость одной из проблем математической логики - исчисления истинности предикатов.
Второе направление связано с машинной математикой. Основная идея этого направления состоит в том, что алгоритмические процессы - это процессы, которые может совершать соответствующим образом устроенная «машина». В соответствии с этой идеей ими были описаны в точных математических терминах довольно узкие классы машин, однако при этом было доказано, что посредством этих машин можно осуществить или имитировать все алгоритмические процессы, которые фактически когда-либо описывались математиками. Данный подход развивался в работах Э. Поста и А. Тьюринга одновременно с упомянутым выше подходом. Доказательство алгоритмической разрешимости задачи сводится к доказательству существования машины, ее решающей.
Третье направление связано с понятием нормальных алгоритмов, введенным и разработанным российским математиком А. А. Марковым в начале 50-х гг. XX в.
В последующих разделах все три направления будут рассмотрены подробнее. Но прежде чем перейти к этому, хотелось бы отметить то обстоятельство, что строго формализованный подход в определении понятия «алгоритм» используется лишь непосредственно в самой математической теории алгоритмов, где исследуются общие свойства алгоритмов, проводится доказательство алгоритмической разрешимости и пр. В практических же приложениях, в том числе в информатике, строгая формализация может привести к значительному усложнению задачи; в то же время, можно указать ряд ситуаций, в которых допустимо отступление от нее.
1. Применение исполнителей, способных выполнять сложные команды. Определение термина «исполнитель алгоритма» достаточно очевидно:
Исполнитель алгоритма - это субъект или устройство способные правильно интерпретировать описание алгоритма и выполнить содержащийся в нем перечень действий.
Указания по выполнению действий для каждого исполнителя формулируются посредством некоторого языка, включающего набор служебных слов, обозначающих действия (команды), а также синтаксические правила их объединения. Совокупность допустимых команд образует систему команд исполнителя (СКИ). Различаться СКИ разных исполнителей могут детальностью описания действий. Как будет показано ниже, элементарным (простейшим) действием при обработке дискретной информации является замена одного знака другим. Однако можно построить абстрактное или реальное устройство, которое будет способно выполнять целую цепочку подобных элементарных действий по заложенному в него правилу - некое комплексное (интегральное) действие. При построении алгоритма для такого исполнителя разработчику достаточно указать последовательность интегральных команд, а их преобразование в цепочку истинно элементарных шагов будет производиться самим исполнителем. Такая «многоступенчатая» алгоритмизация широко применяется при управлении компьютером.
Истинно элементарными следует считать действия процессора (хотя их общее число у современных процессоров достигает нескольких сотен и даже тысяч) - их называют машинными командами, а их обозначения - машинными кодами. Первым (низшим) уровнем, на котором происходит отход от машинных кодов, является код ассемблера - внутренний (т.е. аппаратно-зависимый) язык. Объединения элементарных действий в сложные команды на этом уровне еще не происходит и общее количество команд ассемблера совпадает с числом команд процессора, однако, используется символьная форма представления машинных кодов и регистров процессора - мнемоники, что удобнее для пользователя, чем двоичный машинный код.
Перевод мнемоник в машинные команды осуществляет программа - ассемблер; именно с ней имеет дело программист как с исполнителем. Команды, объединяющие ряд элементарных действий, появляются в языках программирования высокого уровня, например, в тексте программы достаточно написать «Write», а уже транслятор языка переведет ее в последовательность элементарных шагов: прерываний, пересылок и пр. По отношению к программисту исполнителем в этом случае оказывается транслятор языка программирования. Еще большую степень интеграции элементарных команд может обеспечить прикладная программа, которая является исполнителем по отношению к конечному пользователю. СКИ такого исполнителя включает все команды управления, представленные в виде меню, экранных кнопок, окон настройки и других элементов интерфейса. Использование одной команды может вызвать цепочку сложных действий, например, выравнивание многих строк текста.
Таким образом, при записи алгоритмов возможны ситуации, когда язык представления алгоритма является формальным, но в нем используются сложные команды, которые самим исполнителем переводятся на уровень истинно элементарных действий.
Допустимость нестрогой формализации представления алгоритмов, если исполнителем является человек. Человек обладает собственным мышлением и знаниями, опираясь на которые он может компенсировать неточности алгоритма, выполнить действия и добиться результата. Подобные алгоритмы следует считать еще менее строгими, чем те, что были рассмотрены в начале параграфа, поскольку они, как правило, не обладают всеми перечисленными свойствами. Примерами могут служить кулинарные рецепты, инструкции по применению бытовых приборов, алгоритмы решения школьных задач.
Расширение применимости понятия алгоритма на последовательность любых дискретных действий. По определению алгоритм должен быть обязательно связан с обработкой дискретной информации. Однако этот же термин используется и для обозначения действий по управлению исполнителем, напрямую не производящим
преобразование информации. Например, в школьном курсе информатики широко применяются учебные исполнители «Чертежник», «Паркетчик», «Черепашка», СКИ которых включает перемещение по экрану и выполнение некоторых операций («начертить линию», «положить плитку» и т.п.). То же относится к инструкциям по управлению какими-либо агрегатами и устройствами.
