Примитивная рекурсия

способ определения функций от натуральных аргументов с натуральными значениями. Говорят, что (n+1)-местная функция f(x1,..., х п, у). получена примитивной рекурсией из n-местной функции g(х 1,..., х п).и (п+2).местной функции h(х 1,..., х n у, z), если для всех натуральных значений x1..., х п, у имеет место [img: http://localhost:8080/file/041747-67.jpg] и [img: http://localhost:8080/file/041747-68.jpg] Для данных gи hтакая функция f всегде существует и единственна. При n=0 определяющие равенства для f записываются в виде [img: http://localhost:8080/file/041747-69.jpg] Фундаментальным свойством П. р. является то, что при любом разумном уточнении понятия вычислимости функция f, полученная из вычислимых функций gи h с помощью П. р., сама вычислимая. П. р.- одно из основных правил порождения из исходного набора простейших функций всех примитивно рекурсивных и всех частично рекурсивных функций.