Primitive recursive function (original) (raw)
Primitivně rekurzivní funkce (PRF) je v teorii vyčíslitelnosti v jistém smyslu „jednoduchá“ funkce. Jejím rozšířením je částečně rekurzivní funkce (ČRF).
| Property | Value |
|---|---|
| dbo:abstract | Les funcions recursives primitives es defineixen usant com a operacions principals la recursió i la composició i formen un subconjunt estricte de les funcions recursives, que són les funcions computables. El terme el va proposar originalment en Rózsa Péter. En Teoria de la computabilitat, les funcions recursives primitives són una classe de funcions que formen un bloc important per la formalització completa de la computabilitat. Aquestes funcions també són importants en Teoria de la demostració. Moltes de les funcions estudiades a Teoria de nombres i les aproximacions a les funcions de valor real són recursives primitives. Per exemple, la suma, divisió, factorial, exponencial i l'n-èsim primer són funcions recursives primitives. De fet, és difícil definir una funció que sigui recursiva però que no es pugui definir amb recursió primitiva. El conjunt de funcions recursives primitives es coneix com a en Complexitat computacional. Tota funció recursiva primitiva és una funció recursiva general. (ca) Primitivně rekurzivní funkce (PRF) je v teorii vyčíslitelnosti v jistém smyslu „jednoduchá“ funkce. Jejím rozšířením je částečně rekurzivní funkce (ČRF). (cs) Primitiv-rekursive Funktionen sind totale Funktionen, die aus einfachen Grundfunktionen (konstante 0-Funktion, Projektionen auf ein Argument und Nachfolgefunktion) durch Komposition und (primitive) Rekursion gebildet werden können. Die primitive Rekursion lässt sich auf Richard Dedekinds 126. Theorem in Was sind und was sollen die Zahlen? (1888) zurückführen. Die primitiv rekursive Arithmetik geht auf Thoralf Skolem (1923) zurück. Der Begriff primitiv-rekursive Funktion wurde von der ungarischen Mathematikerin Rózsa Péter geprägt. Primitiv-rekursive Funktionen spielen in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine Rolle. Sie treten im Zusammenhang mit der Explikation des Berechenbarkeitsbegriffs auf. Alle primitiv-rekursiven Funktionen sind im intuitiven Sinn berechenbar. Sie schöpfen aber nicht alle intuitiv berechenbaren Funktionen aus, Beispiele dafür sind die Ackermannfunktion und die Sudanfunktion, welche beide berechenbar, aber nicht primitiv-rekursiv sind. Eine vollständige Erfassung des Berechenbarkeitsbegriffs gelingt erst durch die µ-rekursiven Funktionen. Für primitiv-rekursive Funktionen ist es möglich, ein Komplexitätsmaß zu definieren, d. h., es kann die Dauer der Berechnung eines ihrer Funktionswerte vorab ermittelt werden. Die Klasse der primitiv-rekursiven Funktionen und die der LOOP-berechenbaren (vgl. LOOP-Programm) Funktionen sind äquivalent. (de) En teoría de la computabilidad, la recursión primitiva permite definir una clase de funciones que forman un importante paso en la formalización de la noción de computabilidad. Se definen usando como principales operaciones la recursión y composición de funciones y forman un subconjunto estricto de las funciones recursivas, que son precisamente las funciones computables. Las funciones recursivas se definen agregándole a la recursión primitiva el operador de búsqueda no acotada que permite definir funciones parciales. Muchas de las funciones normalmente estudiadas en teoría de los números, y las aproximaciones a las funciones de valor real utilizan la recursión primitiva. Como ejemplo de ellas se tiene la suma, la división, el factorial, el enésimo primo, etc. De hecho, no es fácil definir una función que sea recursiva pero que no se pueda definir con recursión primitiva. (es) En théorie de la calculabilité, une fonction récursive primitive est une fonction construite à partir de la fonction nulle, de la fonction successeur, des fonctions projections et des schémas primitifs de récursion et de composition. Ces fonctions constituent un sous-ensemble strict des fonctions récursives. (fr) In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined before entering the loop). Primitive recursive functions form a strict subset of those general recursive functions that are also total functions. The importance of primitive recursive functions lies in the fact that most computable functions that are studied in number theory (and more generally in mathematics) are primitive recursive. For example, addition and division, the factorial and exponential function, and the function which returns the nth prime are all primitive recursive. In fact, for showing that a computable function is primitive recursive, it suffices to show that its time complexity is bounded above by a primitive recursive function of the input size. It is hence not that easy to devise a computable function that is not primitive recursive; some examples are shown in section below. The set of primitive recursive functions is known as PR in computational complexity theory. (en) Nella teoria della calcolabilità, le funzioni ricorsive primitive sono una classe di funzioni che possono essere definite applicando un numero finito di volte la ricorsione e la composizione a partire da particolari funzioni base (funzioni zero, funzione successore e funzioni selettive o proiettive) e costituiscono un passo fondamentale nella costruzione di una completa formalizzazione della calcolabilità. Le funzioni ricorsive primitive sono un sottoinsieme stretto delle funzioni ricorsive (queste ultime corrispondono esattamente alle funzioni calcolabili). La classe più ampia delle funzioni ricorsive è definita aggiungendo la possibilità di avere funzioni parziali e introducendo un operatore di ricerca non limitato. Molte delle funzioni solitamente studiate nella teoria dei numeri, e le approssimazioni di funzioni a valori reali, sono primitive ricorsive, come l'addizione, la divisione, il fattoriale, l'esponenziale, la ricerca dell'ennesimo numero primo, e molte altre (Brainerd and Landweber, 1974). Infatti è difficile progettare una funzione che sia ricorsiva totale ma non primitiva ricorsiva, anche se se ne conoscono alcune, come la funzione di Ackermann. Perciò studiando questo particolare tipo di funzioni è possibile scoprire proprietà che hanno conseguenza di ampia portata. Le funzioni ricorsive primitive possono essere calcolate dalle macchine che terminano sempre, mentre le funzioni ricorsive richiedono sistemi con la stessa potenza di calcolo delle macchine di Turing. (it) 계산 가능성 이론에서 원시 재귀 함수(영어: primitive recursive function)은 원시 재귀와 합성 연산으로 정의되는 함수이다. 원시 재귀 함수의 클래스는 μ-재귀 함수의 클래스의 부분집합이며, μ-재귀 함수와는 달리 전역적(total)이다. 원시 재귀 함수의 클래스는 PR로 표기되며, 이는 R의 일부이다. (ko) 原始再帰関数（げんしさいきかんすう、英: Primitive Recursive Function）とは、原始再帰と合成で定義される関数であり、再帰関数（計算可能関数）の部分集合である。原始帰納的関数とも。 再帰理論において原始再帰関数は、計算可能性の完全形式化のための重要な要素となる関数のクラスの1つである。このような関数は証明論においても重要である。 数論が扱う関数の多くや、実数を値とする関数の近似は原始再帰的であり、加法、除法、階乗、指数、n 番目の素数を求める関数などがある (Brainerd and Landweber, 1974年)。実際、原始再帰的でない関数を考案するのは難しいが、いくつかの例が知られている（の節を参照）。 計算複雑性理論では、原始再帰関数の集合をPRと呼ぶ。 原始再帰関数のクラスとは、while文を使用せずに計算できる（すなわちfor文のみで計算可能な）関数のクラスと一致する。原始再帰関数のクラスはグジェゴルチク階層と呼ばれる階層に分類される。 (ja) In de theoretische informatica vormen de primitief recursieve functies een klasse van totale, berekenbare functies. De klasse is gedefinieerd als de kleinste klasse van functies die de basisfuncties (constante functies, opvolgerfunctie en projectie) bevat, en afgesloten is onder compositie en primitieve recursie. Alle primitief recursieve functies zijn totaal en berekenbaar, maar er bestaan totale en berekenbare functies die niet primitief recursief zijn, zoals de Ackermannfunctie. Als we de klasse van primitief recursieve functies ook onder minimalisering afsluiten, ontstaat de klasse van μ-recursieve functies, die wel precies met de berekenbare functies overeenkomt. (nl) As funções recursivas primitivas são definidas através do uso da recursão primitiva e da Composição como operações centrais. Na teoria computacional, funções recursivas primitivas são uma classe de funções que formam um importante bloco de construção importante no caminho para chegar à total formalização da computabilidade. Essas funções são de grande importância para a teoria da prova. Muitas das funções que normalmente são estudadas na teoria dos números, são recursivas primitivas. Por exemplo: adição, divisão, fatorial e exponenciação são todas recursivas primitivas. (pt) Рекурсивні функції — клас функцій, введений як уточнення класу обчислюваних функцій. В математиці загальноприйнятою є теза про те, що клас функцій, для обчислення яких існують алгоритми, при найширшому розумінні алгоритму, збігається з класом рекурсивних функцій. У зв'язку з цим, рекурсивні функції грають важливу роль в математиці та її застосуваннях, в першу чергу, в математичній логіці, основах математики та кібернетиці, як ефективно обчислювані функції. Тільки такі функції можна обчислювати на електронних обчислювальних машинах та інших цифрових пристроях. При введенні класу ефективно обчислюваних функцій природним чином виникає питання уточнення конструктивних об'єктів, на яких визначено ці функції. Клас всіх таких об'єктів широкий. В той же час, з допомогою методу , запропонованого австрійським математиком Куртом Геделем, всі такі об'єкти легко зводяться до натуральних чисел. Тому рекурсивні функції було введено як функції, що визначені на множині натуральних чисел і набувають значення з тієї ж множини натуральних чисел. Перенесення понять і методів вироблених в теорії рекурсивних функцій на функції визначені на складніших конструктивних областях (множини слів деякого алфавіту, формул деякої теорії, графів тощо) не створює принципових ускладнень. (uk) 在可计算性理论中，原始递归函数（英語：primitive recursive functions）对计算的完全的形式化而言是形成重要构造板块的一类函数。它们使用递归和复合作为中心运算来定义，并且是递归函数的严格的子集，它们完全是可计算函数。通过补充允许偏函数和介入无界查找运算可以定义出递归函数的更广泛的类。 通常在数论中研究的很多函数，近似于实数值函数，比如加法、除法、阶乘、指数，找到第 n 个素数等等是原始递归的（Brainerd and Landweber, 1974）。实际上，很难设计不是原始递归的函数，尽管某些函数是已知的(比如阿克曼函数)。所以，通过研究它们，我们能发现有广泛影响的结论的那些性质。 原始递归函数可以用总是停机的图灵机计算，而递归函数需要图灵完全系统。 原始递归函数的集合在计算复杂性理论中叫做PR。 (zh) Термин рекурсивная функция в теории вычислимости используется для обозначения трёх классов функций: * ; * ; * . Последние совпадают с классом вычислимых по Тьюрингу функций. Определения этих трёх классов сильно связаны. Они были введены Куртом Гёделем с целью формализации понятия вычислимости. Множество частично рекурсивных функций включает в себя множество общерекурсивных функций, а общерекурсивные функции включают в себя примитивно рекурсивные функции. Частично рекурсивные функции иногда называют просто рекурсивными функциями. (ru) |
| dbo:wikiPageExternalLink | https://projecteuclid.org/euclid.jsl/1230396909 http://www.people.cs.uchicago.edu/~soare/History/compute.pdf https://arxiv.org/abs/cs/0603063v3 https://doi.org/10.1145/74074.74089 |
| dbo:wikiPageID | 24829 (xsd:integer) |
| dbo:wikiPageLength | 39124 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1121006288 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Monus dbr:Paris–Harrington_theorem dbr:Primality_test dbc:Recursion dbr:John_P._Burgess dbr:Peano_arithmetic dbr:Peano_postulates dbr:Richard_Dedekind dbr:Double_recursion dbr:Richard_Jeffrey dbr:Primitive_recursive_set_function dbr:Computability_theory dbr:Computable_function dbr:Course-of-values_recursion dbr:Negation dbr:GOTO dbr:General_recursive_function dbr:George_Boolos dbr:Mu_operator dbr:Thoralf_Skolem dbr:Total_recursive_function dbr:Arity dbr:Logical_conjunction dbr:Machine_that_always_halts dbr:Stephen_Kleene dbr:Computational_complexity_theory dbr:Computer_program dbr:PR_(complexity) dbr:Partial_function dbr:Primitive_recursive_arithmetic dbr:Sudan_function dbr:Mutual_recursion dbr:Time_complexity dbr:Total_function dbr:Truth_value dbr:Wilhelm_Ackermann dbr:Domain_of_a_function dbr:Gödel's_β_function dbr:Gödel,_Escher,_Bach dbr:Gödel_numbering dbr:Gödel_numbering_for_sequences dbr:Primitive_recursive_functional dbr:Addition dbr:Albert_R._Meyer dbc:Functions_and_mappings dbr:Exponential_function dbr:Exponentiation dbr:Field_(mathematics) dbr:First-order_logic dbr:For_loop dbr:Forcing_(mathematics) dbr:Number_theory dbr:Diagonal_lemma dbr:Recursive_definition dbr:Proof_theory dbr:Recursively_enumerable dbr:Goodstein_function dbr:Gödel's_incompleteness_theorem dbr:Halting_problem dbr:ACM_SIGACT dbr:Ackermann_function dbc:Computability_theory dbc:Theory_of_computation dbr:LOOP_(programming_language) dbr:BlooP_and_FlooP dbr:While_loop dbr:Division_(mathematics) dbr:Douglas_Hofstadter dbr:Axiom dbr:Grzegorczyk_hierarchy dbr:Identity_function dbr:If_and_only_if dbr:Indicator_function dbr:Natural_number dbr:Operation_(mathematics) dbr:Cantor's_diagonal_argument dbr:Rational_number dbr:Recursion_(computer_science) dbr:Recursively_enumerable_set dbr:Set_theory dbr:Turing_machine dbr:Rózsa_Péter dbr:Undecidable_problem dbr:Factorial dbr:Robert_I._Soare dbr:Finitism dbr:Subset dbr:Turing_completeness dbr:Turing-complete_language dbr:Disjunction dbr:Consistency_proof dbr:Partial_recursive_function dbr:If,_and_only_if dbr:Primitive_recursive_ordinal_function dbr:Gödel_number dbr:Dennis_M._Ritchie dbr:Loop_(programming) dbr:Mu-operator |
| dbp:wikiPageUsesTemplate | dbt:= dbt:Block_indent dbt:Cite_journal dbt:Cleanup dbt:Cn dbt:Doi dbt:Expert_needed dbt:Math dbt:Mvar dbt:Ordered_list dbt:Reflist dbt:Sfn dbt:Short_description dbt:Slink dbt:Unordered_list dbt:Isbn dbt:Su dbt:JSTOR dbt:Mathematical_logic |
| dct:subject | dbc:Recursion dbc:Functions_and_mappings dbc:Computability_theory dbc:Theory_of_computation |
| gold:hypernym | dbr:Functions |
| rdf:type | dbo:Software yago:Abstraction100002137 yago:Function113783816 yago:MathematicalRelation113783581 yago:Relation100031921 yago:WikicatFunctionsAndMappings |
| rdfs:comment | Primitivně rekurzivní funkce (PRF) je v teorii vyčíslitelnosti v jistém smyslu „jednoduchá“ funkce. Jejím rozšířením je částečně rekurzivní funkce (ČRF). (cs) En théorie de la calculabilité, une fonction récursive primitive est une fonction construite à partir de la fonction nulle, de la fonction successeur, des fonctions projections et des schémas primitifs de récursion et de composition. Ces fonctions constituent un sous-ensemble strict des fonctions récursives. (fr) 계산 가능성 이론에서 원시 재귀 함수(영어: primitive recursive function)은 원시 재귀와 합성 연산으로 정의되는 함수이다. 원시 재귀 함수의 클래스는 μ-재귀 함수의 클래스의 부분집합이며, μ-재귀 함수와는 달리 전역적(total)이다. 원시 재귀 함수의 클래스는 PR로 표기되며, 이는 R의 일부이다. (ko) 原始再帰関数（げんしさいきかんすう、英: Primitive Recursive Function）とは、原始再帰と合成で定義される関数であり、再帰関数（計算可能関数）の部分集合である。原始帰納的関数とも。 再帰理論において原始再帰関数は、計算可能性の完全形式化のための重要な要素となる関数のクラスの1つである。このような関数は証明論においても重要である。 数論が扱う関数の多くや、実数を値とする関数の近似は原始再帰的であり、加法、除法、階乗、指数、n 番目の素数を求める関数などがある (Brainerd and Landweber, 1974年)。実際、原始再帰的でない関数を考案するのは難しいが、いくつかの例が知られている（の節を参照）。 計算複雑性理論では、原始再帰関数の集合をPRと呼ぶ。 原始再帰関数のクラスとは、while文を使用せずに計算できる（すなわちfor文のみで計算可能な）関数のクラスと一致する。原始再帰関数のクラスはグジェゴルチク階層と呼ばれる階層に分類される。 (ja) In de theoretische informatica vormen de primitief recursieve functies een klasse van totale, berekenbare functies. De klasse is gedefinieerd als de kleinste klasse van functies die de basisfuncties (constante functies, opvolgerfunctie en projectie) bevat, en afgesloten is onder compositie en primitieve recursie. Alle primitief recursieve functies zijn totaal en berekenbaar, maar er bestaan totale en berekenbare functies die niet primitief recursief zijn, zoals de Ackermannfunctie. Als we de klasse van primitief recursieve functies ook onder minimalisering afsluiten, ontstaat de klasse van μ-recursieve functies, die wel precies met de berekenbare functies overeenkomt. (nl) As funções recursivas primitivas são definidas através do uso da recursão primitiva e da Composição como operações centrais. Na teoria computacional, funções recursivas primitivas são uma classe de funções que formam um importante bloco de construção importante no caminho para chegar à total formalização da computabilidade. Essas funções são de grande importância para a teoria da prova. Muitas das funções que normalmente são estudadas na teoria dos números, são recursivas primitivas. Por exemplo: adição, divisão, fatorial e exponenciação são todas recursivas primitivas. (pt) 在可计算性理论中，原始递归函数（英語：primitive recursive functions）对计算的完全的形式化而言是形成重要构造板块的一类函数。它们使用递归和复合作为中心运算来定义，并且是递归函数的严格的子集，它们完全是可计算函数。通过补充允许偏函数和介入无界查找运算可以定义出递归函数的更广泛的类。 通常在数论中研究的很多函数，近似于实数值函数，比如加法、除法、阶乘、指数，找到第 n 个素数等等是原始递归的（Brainerd and Landweber, 1974）。实际上，很难设计不是原始递归的函数，尽管某些函数是已知的(比如阿克曼函数)。所以，通过研究它们，我们能发现有广泛影响的结论的那些性质。 原始递归函数可以用总是停机的图灵机计算，而递归函数需要图灵完全系统。 原始递归函数的集合在计算复杂性理论中叫做PR。 (zh) Термин рекурсивная функция в теории вычислимости используется для обозначения трёх классов функций: * ; * ; * . Последние совпадают с классом вычислимых по Тьюрингу функций. Определения этих трёх классов сильно связаны. Они были введены Куртом Гёделем с целью формализации понятия вычислимости. Множество частично рекурсивных функций включает в себя множество общерекурсивных функций, а общерекурсивные функции включают в себя примитивно рекурсивные функции. Частично рекурсивные функции иногда называют просто рекурсивными функциями. (ru) Les funcions recursives primitives es defineixen usant com a operacions principals la recursió i la composició i formen un subconjunt estricte de les funcions recursives, que són les funcions computables. El terme el va proposar originalment en Rózsa Péter. En Teoria de la computabilitat, les funcions recursives primitives són una classe de funcions que formen un bloc important per la formalització completa de la computabilitat. Aquestes funcions també són importants en Teoria de la demostració. Tota funció recursiva primitiva és una funció recursiva general. (ca) En teoría de la computabilidad, la recursión primitiva permite definir una clase de funciones que forman un importante paso en la formalización de la noción de computabilidad. Se definen usando como principales operaciones la recursión y composición de funciones y forman un subconjunto estricto de las funciones recursivas, que son precisamente las funciones computables. Las funciones recursivas se definen agregándole a la recursión primitiva el operador de búsqueda no acotada que permite definir funciones parciales. (es) Primitiv-rekursive Funktionen sind totale Funktionen, die aus einfachen Grundfunktionen (konstante 0-Funktion, Projektionen auf ein Argument und Nachfolgefunktion) durch Komposition und (primitive) Rekursion gebildet werden können. Die primitive Rekursion lässt sich auf Richard Dedekinds 126. Theorem in Was sind und was sollen die Zahlen? (1888) zurückführen. Die primitiv rekursive Arithmetik geht auf Thoralf Skolem (1923) zurück. Der Begriff primitiv-rekursive Funktion wurde von der ungarischen Mathematikerin Rózsa Péter geprägt. Primitiv-rekursive Funktionen spielen in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine Rolle. Sie treten im Zusammenhang mit der Explikation des Berechenbarkeitsbegriffs auf. (de) In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined before entering the loop). Primitive recursive functions form a strict subset of those general recursive functions that are also total functions. The set of primitive recursive functions is known as PR in computational complexity theory. (en) Nella teoria della calcolabilità, le funzioni ricorsive primitive sono una classe di funzioni che possono essere definite applicando un numero finito di volte la ricorsione e la composizione a partire da particolari funzioni base (funzioni zero, funzione successore e funzioni selettive o proiettive) e costituiscono un passo fondamentale nella costruzione di una completa formalizzazione della calcolabilità. (it) Рекурсивні функції — клас функцій, введений як уточнення класу обчислюваних функцій. В математиці загальноприйнятою є теза про те, що клас функцій, для обчислення яких існують алгоритми, при найширшому розумінні алгоритму, збігається з класом рекурсивних функцій. У зв'язку з цим, рекурсивні функції грають важливу роль в математиці та її застосуваннях, в першу чергу, в математичній логіці, основах математики та кібернетиці, як ефективно обчислювані функції. Тільки такі функції можна обчислювати на електронних обчислювальних машинах та інших цифрових пристроях. (uk) |
| rdfs:label | Funcions recursives primitives (ca) Primitivně rekurzivní funkce (cs) Primitiv-rekursive Funktion (de) Recursión primitiva (es) Fonction récursive primitive (fr) Funzione ricorsiva primitiva (it) 原始再帰関数 (ja) 원시 재귀 함수 (ko) Primitief recursieve functie (nl) Primitive recursive function (en) Рекурсивная функция (теория вычислимости) (ru) Função recursiva primitiva (pt) Рекурсивні функції (uk) 原始递归函数 (zh) |
| owl:sameAs | freebase:Primitive recursive function dbpedia-ru:Primitive recursive function yago-res:Primitive recursive function wikidata:Primitive recursive function dbpedia-ca:Primitive recursive function dbpedia-cs:Primitive recursive function dbpedia-de:Primitive recursive function dbpedia-es:Primitive recursive function dbpedia-fr:Primitive recursive function dbpedia-he:Primitive recursive function dbpedia-it:Primitive recursive function dbpedia-ja:Primitive recursive function dbpedia-ko:Primitive recursive function dbpedia-nl:Primitive recursive function dbpedia-pt:Primitive recursive function dbpedia-sr:Primitive recursive function dbpedia-uk:Primitive recursive function dbpedia-zh:Primitive recursive function https://global.dbpedia.org/id/Z1t2 |
| prov:wasDerivedFrom | wikipedia-en:Primitive_recursive_function?oldid=1121006288&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Primitive_recursive_function |
| is dbo:wikiPageDisambiguates of | dbr:Recursive_function |
| is dbo:wikiPageRedirects of | dbr:Primitive_recursive dbr:Primitive_recursive_functions dbr:Primitive_recursion dbr:Primitive_recursive_fuctions |
| is dbo:wikiPageWikiLink of | dbr:Proof_sketch_for_Gödel's_first_incompleteness_theorem dbr:Monus dbr:Paris–Harrington_theorem dbr:Index_of_computing_articles dbr:Integer-valued_function dbr:List_of_mathematical_functions dbr:List_of_mathematical_logic_topics dbr:List_of_mathematical_proofs dbr:Primitive_recursive_set_function dbr:Computability_theory dbr:Computable_function dbr:Counter-machine_model dbr:Course-of-values_recursion dbr:Mathematical_logic dbr:Μ_operator dbr:Function_composition dbr:General_recursive_function dbr:Constructive_set_theory dbr:Andrzej_Grzegorczyk dbr:Arithmetical_hierarchy dbr:Choice_sequence dbr:Computable_real_function dbr:Computably_enumerable_set dbr:Kruskal's_tree_theorem dbr:PR_(complexity) dbr:Primitive_recursive_arithmetic dbr:Stack_overflow dbr:Successor_function dbr:Sudan_function dbr:Theory_of_computation dbr:McCarthy_Formalism dbr:Automated_theorem_proving dbr:Brouwer–Hilbert_controversy dbr:Gabriel_Sudan dbr:Gödel's_β_function dbr:Gödel_numbering dbr:Gödel_numbering_for_sequences dbr:Primitive_recursive_functional dbr:Algorithm_characterizations dbr:ELEMENTARY dbr:Pairing_function dbr:Fast-growing_hierarchy dbr:History_of_the_Church–Turing_thesis dbr:Recursive_function dbr:Gödel's_incompleteness_theorems dbr:Counter_machine dbr:Smn_theorem dbr:Ackermann_function dbr:John_McCarthy_(computer_scientist) dbr:LOOP_(programming_language) dbr:BlooP_and_FlooP dbr:Realizability dbr:Register_machine dbr:BIT_predicate dbr:Grzegorczyk_hierarchy dbr:Indicator_function dbr:On_Formally_Undecidable_Propositions_o...cipia_Mathematica_and_Related_Systems dbr:Random-access_machine dbr:Recursion_(computer_science) dbr:Kleene's_T_predicate dbr:Loop_variant dbr:Walther_recursion dbr:List_of_types_of_functions dbr:Switch_statement dbr:Outline_of_logic dbr:Turing_completeness dbr:Primitive_recursive dbr:Primitive_recursive_functions dbr:Primitive_recursion dbr:Primitive_recursive_fuctions |
| is foaf:primaryTopic of | wikipedia-en:Primitive_recursive_function |