Необходимость формализации интуитивного понятия алгоритма. Понятие формальной алгоритмической системы. Алгоритмические системы Тьюринга и Поста

Введенного на интуитивном уровне понятия алгоритма и опытным путем установленных свойств алгоритмов вполне достаточно для решения широкого круга математических задач. Достаточно такого подхода и при решении практических задач программирования компьютеров.

Однако, в тех случаях, когда задача оказывается сложной и алгоритмическое решение задачи найти не удается, встает вопрос о ее алгоритмической разрешимости.

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

Задача точного определения понятия алгоритма была решена в 30-х годах прошлого века в работах Дж.Гильберта, А.Черча, С.Клини, Э.Поста, А.Тьюринга в двух формах: на основе понятия рекурсивной функции и на основе описания алгоритмического процесса.

Рекурсивная функция – это функция, для которой существует алгоритм вычисления ее значений по произвольному значению аргумента.

Другой подход заключался в том, что алгоритмический процесс определяется как процесс, осуществимый на конкретно устроенной машине (называемой «машиной Тьюринга»).

Был сформулирован тезис (называемый «тезис Тьюринга»), утверждающий, что любой алгоритм может быть реализован на подходящей машине Тьюринга.