Статья: ИЗЛОЖЕНИЕ ПОНЯТИЯ ВЫЧИСЛИМОЙ ФУНКЦИИ В ТЕХНИЧЕСКОМ УНИВЕРСИТЕТЕ

Широко известно сравнение значимости понятия вычислимой функции со значимостью понятия натурального числа (Э. Пост). Однако традиции преподавания в технических вузах не предусматривают знакомства с основами теории вычислимых функций, что затрудняет изучение сложности алгоритмов студентами таких специальностей, как «Информационная безопасноть», САПР, «Прикладная математика» и др. На основе опыта работы со студентами с различной математической подготовкой можно рекомендовать начинать изложение этой темы с формализации понятия алгоритма. В качестве таких конструкций предлагаются машины Тьюринга и нормальные алгорифмы Маркова. Изучение различных формализаций интуитивного понятия алгоритма, сравнение решений, полученных упомянутыми методами, помогает лучшему пониманию теории вычислимых функций и способствует формированию чёткого представления о том, что такое сложность вычислений.