Кіріспе
Есептелетін функцияның бірнеше мағынасының бірі. Математикалық логика мен компьютерлік ғылымда жалпы рекурсивті функция, ішінара рекурсивті функция немесе μ-рекурсивті функция – табиғи сандардан табиғи сандарға дейінгі, интуитивті және формальды түрде "есептелетін" ішінара функция. Егер функция толық болса, онда ол жалпы рекурсивті функция деп те аталады (кейде рекурсивті функция деп қысқартылады). Есептеу теориясында μ-рекурсивті функциялардың Тьюринг машиналарымен есептелетін функциялармен сәйкес екені дәлелденген (бұл Church-Turing тезисін қолдайтын теоремалардың бірі). μ-рекурсивті функциялар примитивті рекурсивті функциялармен тығыз байланысты, ал олардың индуктивті анықтамасы (төменде) примитивті рекурсивті функциялардың негізінде салынған. Дегенмен, барлық жалпы рекурсивті функциялар примитивті рекурсивті функциялар емес – ең белгілі мысалы Акерманн функциясы. Басқа баламалы функциялар кластары – лямбда-есептеу функциялары және Марков алгоритмдерімен есептелетін функциялар. - мәндері бар барлық толық рекурсивті функциялар жиыны есептеу күрделілігі теориясында R күрделілік класы ретінде танымал.
In mathematical logic and computer science, a general recursive function, partial recursive function, or μ recursive function is a partial function from natural numbers to natural numbers that is "computable" in an intuitive sense – as well as in a formal one. If the function is total, it is also called a total recursive function (sometimes shortened to recursive function). In computability theory, it is shown that the μ recursive functions are precisely the functions that can be computed by Turing machines (this is one of the theorems that supports the Church–Turing thesis). The μ recursive functions are closely related to primitive recursive functions, and their inductive definition (below) builds upon that of the primitive recursive functions. However, not every total recursive function is a primitive recursive function—the most famous example is the Ackermann function. Other equivalent classes of functions are the functions of lambda calculus and the functions that can be computed by Markov algorithms. The subset of all total recursive functions with values in is known in computational complexity theory as the complexity class R.
Жалпы рекурсивті функция
Жалпы рекурсивті функция, егер ол кез келген кіріс үшін анықталса немесе, балама ретінде, егер оны толық Тьюринг машинасы есептесе, толық рекурсивті функция деп аталады. Берілген жалпы рекурсивті функцияның толық екенін анықтаудың есептеу арқылы шешімі жоқ – қараңыз, тоқтау мәселесі.
Басқа есептеу модельдерімен баламалық
Есептеуге қабілеттілік модельдерінің эквиваленттілігінде, кейбір кірістер үшін тоқтамайтын Тьюринг машиналары мен сәйкес келетін ішінара рекурсивті функцияда сол кіріс үшін анықталмаған нәтиже арасында салмақтау жүргізіледі. Шексіз іздеу операторы примитивті рекурсия ережелерімен анықталмайды, себебі олар "шетсіз циклдар" (анықталмаған мәндер) үшін механизмді ұсырмайды.