Шаг 2.
Классические формализации понятия "алгоритм".
Подходы к формализации понятия "алгоритм"

    На этом шаге мы рассмотрим подходы к формализации понятия "алгоритм".

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

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

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

    На следующем шаге мы рассмотрим принципы работы машины Поста.




Предыдущий шаг Содержание Следующий шаг