| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
The Ackermann function is:
A(0,n) = n+1,
A(m+1,0) = A(m,1), and
A(m+1,n+1) = A(m,A(m+1,n)).
As I recall, the values of A(n,n) increase too quickly for any program
with only bounded loops to compute. A bounded loop is one for which
the number of iterations is calculated before the loop begins.
Is that correct? Does anybody recall the proof? And would somebody
like to recommend a textbook that includes this, along with discussion
of recursive and recursively enumerable functions? I'm looking for
something good to keep in my library, since I didn't keep my college
textbook.
-- edp
Public key fingerprint: 8e ad 63 61 ba 0c 26 86 32 0a 7d 28 db e7 6f 75
To find PGP, read note 2688.4 in Humane::IBMPC_Shareware.
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 2082.1 | BEGIN::YODER | It's 999,943 to 1 but it just might work | Thu May 15 1997 10:35 | 14 | |
The proof is that the Ackermann function isn't a "primitive recursive
function." My old text is Rogers, "Theory of Recursive Functions and
Effective Computability," which gives a definition of primitive
recursive functions on p.8 and then doesn't bother with them. It does
mention that a proof that the 3-argument Ackermann function isn't
primitive recursive is given in Pe'ter, Ro'sza, "Rekursive funktionen,"
Academiai Kiado, Budapest.
The proof I read when in college consisted, as I recall, of proving
that primitive recursive functions couldn't grow faster (as a function
of their arguments) faster than a certain rate which was slower than
the rate of growth of Ackermann's function.
| |||||
| 2082.2 | Correct, but try Altavista for Ackermann | HERON::BLOMBERG | Trapped inside the universe | Thu May 15 1997 10:43 | 8 |
Try Altavista. Several hits on Ackermann's function. And I think
you are correct, at Univ of Erlangen I found the statement
"Sie w�chst schneller als alle primitiv-rekursiven", growing faster
than all primitive recursive functions.
/Ake
| |||||
| 2082.3 | SPECXN::DERAMO | Dan D'Eramo | Thu May 15 1997 12:08 | 7 | |
If the function n -> f(n) is primitive recursive, then there
will be an integer k such that f(n) < A(k, n) for all but at
most finitely many n. One of my books at home outlines a
proof. There will be a relationship between k and the maximum
nesting depth of the bounded loops.
Dan
| |||||
| 2082.4 | AMCFAC::RABAHY | dtn 471-5160, outside 1-810-347-5160 | Fri May 16 1997 10:19 | 8 | |
A(0,n) = n+1 A(1,n) = n+2 A(2,n) = 2n+3 A(3,n) = A(2,A(3,n-1)) = 2*A(3,n-1)+3 = 2**(n+3)-3 A(4,n) = A(3,A(4,n-1)) = 2**(A(4,n-1)+3)-3 What's the closed form of A(4,n)? | |||||
| 2082.5 | as much of the table as I can handle | AMCFAC::RABAHY | dtn 471-5160, outside 1-810-347-5160 | Fri May 16 1997 10:38 | 31 |
A(0,n) = n+1 A(1,n) = n+2 A(2,n) = 2n+3 A(3,n) = 2**(n+3)-3 A(m+1,0) = A(m,1) A(m+1,n+1) = A(m,A(m+1,n)) A | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ---+--------+-----------------------+-------------+-----------------+-------------+-------------+-----+------+------+ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ---+--------+-----------------------+-------------+-----------------+-------------+-------------+-----+------+------+ 1 | A(0,1) | A(0,A(1,0)) | A(0,A(1,1)) | A(0,A(1,2)) | A(0,A(1,3)) | A(0,A(1,4)) | | 2 | A(0,2) | A(0,3) | A(0,4) | A(0,5) | A(0,6) | | | 3 | 4 | 5 | 6 | 7 | ---+--------+-----------------------+-------------+-----------------+-------------+-------------+ 2 | A(1,1) | A(1,A(2,0)) | A(1,A(2,1)) | A(1,A(2,2)) | | 3 | A(1,3) | A(1,5) | A(1,7) | | | 5 | 7 | 9 | ---+--------+-----------------------+-------------+-----------------+-------------+-------------+-----+------+------+ 3 | A(2,1) | A(2,A(3,0)) | A(2,A(3,1)) | A(2,A(3,2)) | A(2,A(3,3)) | | | | | | 5 | A(2,5) | A(2,13) | A(2,29) | A(2,61) | A(2,124) | | | | | | 13 | 29 | 61 | 125 | 253 | 509 | 1021 | 2045 | ---+--------+-----------------------+-------------+-----------------+-------------+-------------+-----+------+------+ 4 | A(3,1) | A(3,A(4,0)) | A(3,A(4,1)) | A(3,A(4,2)) | | 13 | A(3,13) | A(3,65533) | A(3,2**65536-3) | | | 65533 | 2**65536-3 | 2**2**65536-3 | ---+--------+-----------------------+-------------+-----------------+ 5 | A(4,1) | A(4,A(5,0)) | A(4,A(5,1)) | | 65533 | A(4,65533) | | | 2**2**...**2**65536-3 | | | 65532 | ---+--------+-----------------------+ 6 | A(5,1) | ---+--------+ | |||||
| 2082.6 | JAMIN::OSMAN | Eric Osman, dtn 226-7122 | Thu May 22 1997 14:39 | 6 | |
I've often wondered, is there any rhyme or reason to Ackermann's choice of function ? It seems like an intentionally obscure definition, almost as though it were merely picked to "demonstrate" recursion. /Eric | |||||
| 2082.7 | SPECXN::DERAMO | Dan D'Eramo | Thu May 22 1997 17:56 | 27 | |
Eric, see topic 640 here for a little more background.
The variation given in .0 of Ackermann's function,
A(0,n) = n+1,
A(m+1,0) = A(m,1), and
A(m+1,n+1) = A(m,A(m+1,n))
is set up so that
A(m+1, 1) = A(m, A(m+1,0)) = A(m, A(m, 1))
A(m+1, 2) = A(m, A(m+1,1)) = A(m, A(m, A(m, 1)))
A(m+1, 3) = ... = A(m, A(m, A(m, A(m, 1))))
etc. Basically the function n -> A(m+1, n) is defined via
primitive recursion over the function n -> A(m, n). For each
fixed m the function n -> A(m, n) is primitive recursive, but
each increment to m requires one more nested loop of the
programming language in topic 640 to compute it. The overall
function m,n -> A(m,n) and the function n -> A(n,n) both fail
to be primitive recursive. [They need unbounded loops to
compute.]
In one sense it is one of the simplest ways to directly define
a computeable but not primitive recursive function.
Dan
| |||||