Вычислимая функция. Общее понятие о том, что можно сделать “механически”, “алгоритмически”, “эффективно”, “поручить компьютеру”, сформировалось в математике достаточно поздно, более того, и потребность в нем была осознана только в XX в. Замечательно, что это понятие может быть описано весьма простыми средствами. Например, описание абстрактной вычислительной машины и класса программ для нее может быть дано без всяких ссылок на реальные компьютеры и связанные с ними технологии. Это описание могло бы быть дано и несколько веков назад, но тогда оно никому не понадобилось. В курсе информатики такой подход особенно полезен, поскольку он параллельно может решать вопрос и об описании основных принципов устройства и функционирования реальных компьютеров. Можно описать этот класс и иначе: с помощью индуктивного определения, начиная с очень простых арифметических функций и операций над ними.