На этом шаге мы рассмотрим подходы к формализации понятия "алгоритм".
Теперь нужно предложить способ описания шагов алгоритма. Известно несколько подходов к формализации понятия «алгоритм»:
- теория конечных и бесконечных автоматов;
- теория вычислимых (рекурсивных) функций;
- лямбда-исчисление Черча.
Все эти возникшие исторически независимо друг от друга подходы оказались впоследствии эквивалентными. Главная цель формализации понятия алгоритма такова: подойти к решению проблемы алгоритмической разрешимости различных математических задач, т.е. ответить на вопрос, может ли быть построен алгоритм, приводящий к решению задачи. Мы рассмотрим постановку этой проблемы и некоторые результаты теории алгоритмической разрешимости задач, но вначале обсудим формализацию понятия алгоритма в теории автоматов на примере машин Поста, Тьюринга, а также нормальных алгоритмов Маркова, а затем - основы теории рекурсивных функций. Идеи лямбда-исчислений Черча реализованы в языке программирования LISP.
Вместе с тем, формально определенный любым из известных способов алгоритм не может в практическом программировании заменить то, что мы называли алгоритмами в предыдущем параграфе. Основная причина состоит в том, что формальное определение резко сужает круг рассматриваемых задач, делая многие практически важные задачи недоступными для рассмотрения.
На следующем шаге мы рассмотрим принципы работы машины Поста.
