Wikipedia Article of the Day
Randomly selected articles from my personal browsing history
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 is fixed 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 particularly easy to devise a computable function that is not primitive recursive; some examples are shown in section § Limitations below. The set of primitive recursive functions is known as PR in computational complexity theory.
History
Jul 17
Bit error rate
Jul 16
Kullback–Leibler divergence
Jul 15
Mary Schmich
Jul 14
Regression testing
Jul 13
Wasserstein metric
Jul 12
Block cipher mode of operation
Jul 11
Wireless
Jul 10
Birds Aren't Real
Jul 9
Hyperacusis
Jul 8
Rip current
Jul 7
Primitive recursive function
Jul 6
Sudan function
Jul 5
Meow Mix
Jul 4
Tulsi Gabbard
Jul 3
AsciiDoc
Jul 2
Northwest Ordinance
Jul 1
Phylum
Jun 30
Taxonomic rank
Jun 29
Robbie (TV series)
Jun 28
Gödel's Loophole
Jun 27
Survival function
Jun 26
Commitment scheme
Jun 25
Lighthouse of Alexandria
Jun 24
Limonene
Jun 23
United States Department of Energy
Jun 22
PETSCII
Jun 21
The Game (mind game)
Jun 20
Audie Murphy
Jun 19
Base64
Jun 18
Isaac Saul