Введение. Точное понятие «алгоритм» было выработано лишь в тридцатых годах XX века

Точное понятие «алгоритм» было выработано лишь в тридцатых годах XX века. До этого математики довольствовались интуитивным понятием алгоритма. Это объясняется тем, что до середины XIX века математика имела дело в основном с числами и вычислениями. Понятие алгоритма отождествлялось с понятием метода вычислений. Все многообразие вычислений комбинировалось из четко определенных операций арифметики, тригонометрии и анализа. Поэтому понятие метода вычисления считалось интуитивно ясным и не нуждалось в специальных исследованиях.

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

Опыт парадоксов теории множеств научил математику крайне осторожно обращаться с бесконечностью и даже о бесконечности рассуждать с помощью финитных методов. Существо финитного подхода заключается в том, что он допускает только конечные комплексы действий над конечным числом объектов. Выяснение того, какие объекты и действия над ними следует считать точно определенными, какими свойствами и возможностями обладают комбинации элементарных действий, что можно и чего нельзя сделать с их помощью – все это стало предметом теории алгоритмов. Главным внутриматематическим приложением теории алгоритмов явились доказательства невозможности алгоритмического решения некоторых математических проблем. Такие доказательства неосуществимы без точного понятия алгоритма (для доказательства несуществования алгоритма решения того или иного класса задач, надо точно знать несуществование чего требуется доказать).