Арифметическая функция y=j(x1, х2, ...,хn) - это целочисленная функция, зависящая от целочисленных значений аргументов, т.е. это функция, построенная на множестве {0, 1, 2, ...}. Под jпонимается суперпозиция операций сложения, вычитания, умножения и деления, операций определения абсолютного значения результата при вычитании и целой части - при делении, а также некоторых специальных операций, например
.
Заметим здесь же, что логические функции являются частным случаем арифметических функций, a"мостом", связывающим арифметику и логику, являются предикаты.
Арифметические функции, значения которых можно вычислять посредством некоторого алгоритма, называются вычислимыми функциями. Понятие вычислимой функции, основанное на интуитивном смысле алгоритма, также является интуитивным. Однако между ними имеется существенная разница: совокупность вычислительных процессов, удовлетворяющих признакам 1-5 алгоритма (п. В.1), очень обширна; напротив, совокупность вычислимых функций для самых разных процессов, удовлетворяющих признакам 1-5, оказалась одной и той же, и при том легко описываемой в обычных математических терминах. Точно описанная совокупность арифметических функций, совпадающая с совокупностью всех вычислимых функций при самом широком до сих пор известном понятии алгоритма (см. признаки 1-5), носит название совокупности рекурсивных функций.
