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]
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.
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 algebra, a quartic function is a function of the form
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 Knuth's up arrow notation and the left-exponent xb are common.
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.
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do the job of the function, i.e. given an input of the function domain it can return the corresponding output. Computable functions are used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines. Any definition, however, must make reference to some specific model of computation but all valid definitions yield the same class of functions. Particular models of computability that give rise to the set of computable functions are the Turing-computable functions and the general recursive 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 computer graphics, the Liang–Barsky algorithm is a line clipping algorithm. The Liang–Barsky algorithm uses the parametric equation of a line and inequalities describing the range of the clipping window to determine the intersections between the line and the clip window. With these intersections it knows which portion of the line should be drawn. So this algorithm is significantly more efficient than Cohen–Sutherland. The idea of the Liang–Barsky clipping algorithm is to do as much testing as possible before computing line intersections.
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, a function is called limit computable if it is the limit of a uniformly computable sequence of functions. The terms computable in the limit, limit recursive and recursively approximable are also used. One can think of limit computable functions as those admitting an eventually correct computable guessing procedure at their true value. A set is limit computable just when its characteristic function is limit computable.
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.
Besides Euclid's formula, many other formulas for generating Pythagorean triples have been developed.
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. 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 non-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
