Первоначальной целью теории алгоритмов является классификация всех задач на алгоритмически разрешимые и неразрешимые, т.е. на те, для которых существуют решающие их алгоритмы, и те, для которых таких алгоритмов нет. Неформально под алгоритмом
Начиная с тридцатых годов ХХ века, был предпринят ряд исследований для формализации понятия алгоритма. Перечислим некоторые из предложенных разными авторами в разное время формальных моделей: машины Тьюринга-Поста, частично-рекурсивные функции (Гедель, Клини), ?-исчисление (Черч, Клини), итеративные автоматы Неймана, нормальные алгорифмы Маркова, счетчиковые автоматы Минского, автоматы на графах Колмогорова-Барздиня и др. Заложенные в них идеи в значительной степени повлияли затем на архитектуру и языки программирования реальных компьютеров (например, на базе ?-исчисления построен широко применяемый в задачах искусственного интеллекта язык ЛИСП, а из нормальных алгорифмов Маркова произошел хорошо подходящий для текстовой обработки язык РЕФАЛ). Каждый из многочисленных языков программирования также задает некоторую формальную модель алгоритмов. Мы вначале рассмотрим один из простейших таких языков - простые структурированные программы.