Введение в схемы, автоматы и алгоритмы
с двумя другими моделями алгоритмов:
А затем сравним их с двумя другими моделями алгоритмов: описаниями частично рекурсивных функций и машинами Тьюринга.
Хотя алгоритмы в разных прикладных областях имеют дело с дискретными объектами различных видов: целыми и рациональными числами, строками, формулами, разного рода выражениями, графами, матрицами, таблицами, точечными изображениями и др., мы в этой части курса будем рассматривать только задачи вычисления функций от натуральных аргументов, принимающих натуральные значения. Такие функции часто называют арифметическими. Дело в том, что для любого естественного множества дискретных объектов (в частности, для всех перечисленных выше) имеется простое кодирование его элементов целыми числами. Поэтому задачи вычисления функций на этих множествах превращаются в задачи вычисления арифметических функций.
Напомним, что через N обозначается множество натуральных чисел, т.е. N={0,1,2,…}. Для частичной n- местной арифметической функции f: Nn
