Definition
The last equation can be equivalently written as
- . [4]
In the theory of computation, the Sudan function is an example of a function that is recursive, but not primitive recursive. This is also true of the better-known Ackermann function.
In 1926, David Hilbert conjectured that every computable function was primitive recursive. This was refuted by Gabriel Sudan and Wilhelm Ackermann — both his students — using different functions that were published in quick succession: Sudan in 1927, [1] Ackermann in 1928. [2]
The Sudan function is the earliest published example of a recursive function that is not primitive recursive. [3]
The last equation can be equivalently written as
These equations can be used as rules of a term rewriting system (TRS).
The generalized function leads to the rewrite rules
At each reduction step the rightmost innermost occurrence of F is rewritten, by application of one of the rules (r1) - (r3).
Calude (1988) gives an example: compute . [5]
The reduction sequence is [6]
Concrete implementations can be found on Rosetta Code. [7]
F0(x, y) = x + y
| y \ x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 2 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 3 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 4 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 5 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 6 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 7 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| 8 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| 9 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| 10 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
F1(x, y) = 2y · (x + 2) − y − 2
| y \ x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 |
| 2 | 4 | 8 | 12 | 16 | 20 | 24 | 28 | 32 | 36 | 40 | 44 |
| 3 | 11 | 19 | 27 | 35 | 43 | 51 | 59 | 67 | 75 | 83 | 91 |
| 4 | 26 | 42 | 58 | 74 | 90 | 106 | 122 | 138 | 154 | 170 | 186 |
| 5 | 57 | 89 | 121 | 153 | 185 | 217 | 249 | 281 | 313 | 345 | 377 |
| 6 | 120 | 184 | 248 | 312 | 376 | 440 | 504 | 568 | 632 | 696 | 760 |
| 7 | 247 | 375 | 503 | 631 | 759 | 887 | 1015 | 1143 | 1271 | 1399 | 1527 |
| 8 | 502 | 758 | 1014 | 1270 | 1526 | 1782 | 2038 | 2294 | 2550 | 2806 | 3062 |
| 9 | 1013 | 1525 | 2037 | 2549 | 3061 | 3573 | 4085 | 4597 | 5109 | 5621 | 6133 |
| 10 | 2036 | 3060 | 4084 | 5108 | 6132 | 7156 | 8180 | 9204 | 10228 | 11252 | 12276 |
| y \ x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| x | ||||||||
| 1 | F1 (F2(0, 0), F2(0, 0)+1) | F1 (F2(1, 0), F2(1, 0)+1) | F1 (F2(2, 0), F2(2, 0)+1) | F1 (F2(3, 0), F2(3, 0)+1) | F1 (F2(4, 0), F2(4, 0)+1) | F1 (F2(5, 0), F2(5, 0)+1) | F1 (F2(6, 0), F2(6, 0)+1) | F1 (F2(7, 0), F2(7, 0)+1) |
| F1(0, 1) | F1(1, 2) | F1(2, 3) | F1(3, 4) | F1(4, 5) | F1(5, 6) | F1(6, 7) | F1(7, 8) | |
| 1 | 8 | 27 | 74 | 185 | 440 | 1015 | 2294 | |
| 2x+1 · (x + 2) − x − 3 ≈ 10lg 2·(x+1) + lg(x+2) | ||||||||
| 2 | F1 (F2(0, 1), F2(0, 1)+2) | F1 (F2(1, 1), F2(1, 1)+2) | F1 (F2(2, 1), F2(2, 1)+2) | F1 (F2(3, 1), F2(3, 1)+2) | F1 (F2(4, 1), F2(4, 1)+2) | F1 (F2(5, 1), F2(5, 1)+2) | F1 (F2(6, 1), F2(6, 1)+2) | F1 (F2(7, 1), F2(7, 1)+2) |
| F1(1, 3) | F1(8, 10) | F1(27, 29) | F1(74, 76) | F1(185, 187) | F1(440, 442) | F1(1015, 1017) | F1(2294, 2296) | |
| 19 | 10228 | 15569256417 | ≈ 5,742397643 · 1024 | ≈ 3,668181327 · 1058 | ≈ 5,019729940 · 10135 | ≈ 1,428323374 · 10309 | ≈ 3,356154368 · 10694 | |
| 22x+1·(x+2) − x − 1 · (2x+1·(x+2) − x − 1) − (2x+1·(x+2) − x + 1) ≈ 10lg 2 · (2x+1·(x+2) − x − 1) + lg(2x+1·(x+2) − x − 1) ≈ 10lg 2 · 2x+1·(x+2) + lg(2x+1·(x+2)) ≈ 10lg 2 · (2x+1·(x+2)) = 1010lg lg 2 + lg 2·(x+1) + lg(x+2) ≈ 1010lg 2·(x+1) + lg(x+2) | ||||||||
| 3 | F1 (F2(0, 2), F2(0, 2)+3) | F1 (F2(1, 2), F2(1, 2)+3) | F1 (F2(2, 2), F2(2, 2)+3) | F1 (F2(3, 2), F2(3, 2)+3) | F1 (F2(4, 2), F2(4, 2)+3) | F1 (F2(5, 2), F2(5, 2)+3) | F1 (F2(6, 2), F2(6, 2)+3) | F1 (F2(7, 2), F2(7, 2)+3) |
| F1(F1(1,3), F1(1,3)+3) | F1(F1(8,10), F1(8,10)+3) | F1(F1(27,29), F1(27,29)+3) | F1(F1(74,76), F1(74,76)+3) | F1(F1(185,187), F1(185,187)+3) | F1(F1(440,442), F1(440,442)+3) | F1(F1(1015,1017), F1(1015,1017)+3) | F1(F1(2294,2297), F1(2294,2297)+3) | |
| F1(19, 22) | F1(10228, 10231) | F1(15569256417, 15569256420) | F1(≈6·1024, ≈6·1024) | F1(≈4·1058, ≈4·1058) | F1(≈5·10135, ≈5·10135) | F1(≈10309, ≈10309) | F1(≈3·10694, ≈3·10694) | |
| 88080360 | ≈ 7,04 · 103083 | ≈ 7,82 · 104686813201 | ≈ 101,72·1024 | ≈ 101,10·1058 | ≈ 101,51·10135 | ≈ 104,30·10308 | ≈ 101,01·10694 | |
| longer expression, starts with 222x+1 an, ≈ 101010lg 2·(x+1) + lg(x+2) | ||||||||
| 4 | F1 (F2(0, 3), F2(0, 3)+4) | F1 (F2(1, 3), F2(1, 3)+4) | F1 (F2(2, 3), F2(2, 3)+4) | F1 (F2(3, 3), F2(3, 3)+4) | F1 (F2(4, 3), F2(4, 3)+4) | F1 (F2(5, 3), F2(5, 3)+4) | F1 (F2(6, 3), F2(6, 3)+4) | F1 (F2(7, 3), F2(7, 3)+4) |
| F1 (F1(19, 22), F1(19, 22)+4) | F1 (F1(10228, 10231), F1(10228, 10231)+4) | F1 (F1(15569256417, 15569256420), F1(15569256417, 15569256420)+4) | F1 (F1(≈5,74·1024, ≈5,74·1024), F1(≈5,74·1024, ≈5,74·1024)) | F1 (F1(≈3,67·1058, ≈3,67·1058), F1(≈3,67·1058, ≈3,67·1058)) | F1 (F1(≈5,02·10135, ≈5,02·10135), F1(≈5,02·10135, ≈5,02·10135)) | F1 (F1(≈1,43·10309, ≈1,43·10309), F1(≈1,43·10309, ≈1,43·10309)) | F1 (F1(≈3,36·10694, ≈3,36·10694), F1(≈3,36·10694, ≈3,36·10694)) | |
| F1(88080360, 88080364) | F1(10230·210231−10233, 10230·210231−10229) | |||||||
| ≈ 3,5 · 1026514839 | ||||||||
| much longer expression, starts with 2222x+1 an, ≈ 10101010lg 2·(x+1) + lg(x+2) | ||||||||
| y \ x | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 |
| x | |||||
| 1 | F2 (F3(0, 0), F3(0, 0)+1) | F2 (F3(1, 0), F3(1, 0)+1) | F2 (F3(2, 0), F3(2, 0)+1) | F2 (F3(3, 0), F3(3, 0)+1) | F2 (F3(4, 0), F3(4, 0)+1) |
| F2(0, 1) | F2(1, 2) | F2(2, 3) | F2(3, 4) | F2(4, 5) | |
| 1 | 10228 | ≈ 7,82 · 104686813201 | |||
| No closed expressions possible within the framework of normal mathematical notation | |||||
| 2 | F3 (F4(0, 1), F4(0, 1)+2) | F3 (F4(1, 1), F4(1, 1)+2) | F3 (F4(2, 1), F4(2, 1)+2) | F3 (F4(3, 1), F4(3, 1)+2) | F3 (F4(4, 1), F4(4, 1)+2) |
| F3 (1, 3) | F3 (10228, 10230) | F3 (≈104686813201, ≈104686813201) | |||
| No closed expressions possible within the framework of normal mathematical notation | |||||
Jbuch 53, 171
In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive. All primitive recursive functions are total and computable, but the Ackermann function illustrates that not all total computable functions are primitive recursive.
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. Primitive recursive functions form a strict subset of those general recursive functions that are also total functions.
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. In computability theory, it is shown that the μ-recursive functions are precisely the functions that can be computed by Turing machines. 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.
Graham's number is a large number that arose as an upper bound on the answer of a problem in the mathematical field of Ramsey theory. It is much larger than many other large numbers such as Skewes's number and Moser's number, both of which are in turn much larger than a googolplex. As with these, it is so large that the observable universe is far too small to contain an ordinary digital representation of Graham's number, assuming that each digit occupies one Planck volume, possibly the smallest measurable space. But even the number of digits in this digital representation of Graham's number would itself be a number so large that its digital representation cannot be represented in the observable universe. Nor even can the number of digits of that number—and so forth, for a number of times far exceeding the total number of Planck volumes in the observable universe. Thus Graham's number cannot be expressed even by physical universe-scale power towers of the form .
A longest common subsequence (LCS) is the longest subsequence common to all sequences in a set of sequences. It differs from the longest common substring: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. The problem of computing longest common subsequences is a classic computer science problem, the basis of data comparison programs such as the diff utility, and has applications in computational linguistics and bioinformatics. It is also widely used by revision control systems such as Git for reconciling multiple changes made to a revision-controlled collection of files.
In compiler construction, strength reduction is a compiler optimization where expensive operations are replaced with equivalent but less expensive operations. The classic example of strength reduction converts strong multiplications inside a loop into weaker additions – something that frequently occurs in array addressing.(Cooper, Simpson & Vick 1995, p. 1)
In mathematics, tetration is an operation based on iterated, or repeated, exponentiation. There is no standard notation for tetration, though and the left-exponent xb are common.
In the field of mathematical optimization, stochastic programming is a framework for modeling optimization problems that involve uncertainty. A stochastic program is an optimization problem in which some or all problem parameters are uncertain, but follow known probability distributions. This framework contrasts with deterministic optimization, in which all problem parameters are assumed to be known exactly. The goal of stochastic programming is to find a decision which both optimizes some criteria chosen by the decision maker, and appropriately accounts for the uncertainty of the problem parameters. Because many real-world decisions involve uncertainty, stochastic programming has found applications in a broad range of areas ranging from finance to transportation to energy optimization.
In commutative algebra, a regular sequence is a sequence of elements of a commutative ring which are as independent as possible, in a precise sense. This is the algebraic analogue of the geometric notion of a complete intersection.
In computability theory, the μ-operator, minimization operator, or unbounded search operator searches for the least natural number with a given property. Adding the μ-operator to the primitive recursive functions makes it possible to define all computable functions.
In mathematical analysis, and applications in geometry, applied mathematics, engineering, and natural sciences, a function of a real variable is a function whose domain is the real numbers , or a subset of that contains an interval of positive length. Most real functions that are considered and studied are differentiable in some interval. The most widely considered such functions are the real functions, which are the real-valued functions of a real variable, that is, the functions of a real variable whose codomain is the set of real numbers.
In computability theory the S m
n theorem, written also as "smn-theorem" or "s-m-n theorem" is a basic result about programming languages. It was first proved by Stephen Cole Kleene (1943). The name S m
n comes from the occurrence of an S with subscript n and superscript m in the original formulation of the theorem.
In computability theory, course-of-values recursion is a technique for defining number-theoretic functions by recursion. In a definition of a function f by course-of-values recursion, the value of f(n) is computed from the sequence .
Gabriel Sudan was a Romanian mathematician, known for the Sudan function, an important example in the theory of computation, similar to the Ackermann function.
In proof theory, the Dialectica interpretation is a proof interpretation of intuitionistic logic into a finite type extension of primitive recursive arithmetic, the so-called System T. It was developed by Kurt Gödel to provide a consistency proof of arithmetic. The name of the interpretation comes from the journal Dialectica, where Gödel's paper was published in a 1958 special issue dedicated to Paul Bernays on his 70th birthday.
In formal language theory, an LL grammar is a context-free grammar that can be parsed by an LL parser, which parses the input from Left to right, and constructs a Leftmost derivation of the sentence. A language that has an LL grammar is known as an LL language. These form subsets of deterministic context-free grammars (DCFGs) and deterministic context-free languages (DCFLs), respectively. One says that a given grammar or language "is an LL grammar/language" or simply "is LL" to indicate that it is in this class.
In mathematics, the hyperoperation sequence is an infinite sequence of arithmetic operations (called hyperoperations in this context) that starts with a unary operation (the successor function with n = 0). The sequence continues with the binary operations of addition (n = 1), multiplication (n = 2), and exponentiation (n = 3).
LOOP is a simple register language that precisely captures the primitive recursive functions. Of see The language is derived from the counter-machine model. Like the counter machines the LOOP language comprises a set of one or more unbounded registers, each of which can hold a single ppnon-negative integer. A few arithmetic instructions operate on the registers. The only control flow instruction is 'LOOP x DO...END'. It causes the instructions within its scope to be repeated x times.
In theoretical computer science, in particular in term rewriting, a path ordering is a well-founded strict total order (>) on the set of all terms such that
Buchholz's psi-functions are a hierarchy of single-argument ordinal functions introduced by German mathematician Wilfried Buchholz in 1986. These functions are a simplified version of the -functions, but nevertheless have the same strength as those. Later on this approach was extended by Jäger and Schütte.
