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