An Extended Ackermann function?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

tricky77puzzle
Will take "No Tresspassing Signs" for 500
Posts: 488
Joined: Thu Feb 28, 2008 11:02 pm UTC

An Extended Ackermann function?

Postby tricky77puzzle » Tue Dec 09, 2008 1:12 am UTC

This idea came out of the forum game, "My number is bigger than yours".

From the post:

I wrote:Let a({xn}) be the "extended Ackermann function" of the set of numbers {xn}.

a(x) = x+1.
a({xn},0,0...0) = a({xn}). Any trailing zeroes are cut off.

Let {m,n} be two natural numbers that are the arguments of the extended Ackermann function.

When {xn} has 2 terms, the function is the standard Ackermann function, with the exception that the terms are reversed. I.e.

1. a(0,0) = 1
2. a(m,0) = m+1
3. a(0,n) = a(1, n-1)
4. a(m,n) = a(a(m-1, n), n-1)

Now, let {x,y,z} be three natural numbers that are the arguments on the second function:

1. a(0,0,0) = 1
2. a(x,0,0) = x+1
3. a(0,y,0) = a(1, y-1, 0)
4. a(0,0,z) = a(0, 1, z-1)
5. a(x,y,0) = a(a(x-1, y, 0), y-1, 0)
6. a(x,0,z) = a(a(x-1, 0, z), 1, z-1)
7. a(0,y,z) = a(1, y, z-1)
8. a(x,y,z) = a( a( a(x-1,y,z), y-1, z-1 ), a(x, y-1, z), z-1)

You can see how quickly this gets complicated. In fact, the formula for a(m, n, p, q, r) (where m, n, p, q, r are natural numbers) is:

a( a( a( a( a(m-1, n, p, q, r), n-1, p-1, q-1, r-1), a(m, n-1, p, q, r), p-1, q-1, r-1), a( a(m-1, n, p, q, r), n-1, p-1, q-1, r-1), a(m, n, p-1, q, r), q-1, r-1), a(a(a(m-1, n, p, q, r), n-1, p-1, q-1, r-1), a(m, n-1, p, q, r), p-1, q-1, r-1), a(a(m-1, n, p, q, r), n-1, p-1, q-1, r-1), a(m, n, p, q-1, r), r-1)

I know it's not rigorously defined, but I'm guessing that you can interpolate. Actually, the equation can be rigorously defined if all the terms are greater than zero, but it's the complex situations of zero terms that I'm most worried about.

The rigorous definition for a({xn}) is as follows:
Imagine a "tower size" property. That is, f(f(f(f(f(n))))) has 5 layers of brackets, so is of tower size 5. The "e" in f(f(f(f(f(a, b), c), d), e), n) is in a function of tower size 4. Any expression that is not inside a function has tower size 0.
For the extended Ackermann function, the tower size is expressed as follows: the tower layout of a[n] (where n is the tower size) is a[a[n-1], a[n-2], ..., a[1], a[0]], where a[0] is a constant.
If any arguments are missing, fill them in with the arguments that are in the same position as the missing arguments, minus one. (e.g. a(m,n) = a(a(m-1,n),n-1), where n-1 is the fill-in argument.)
If an a() is of tower size 1, only one argument is subtracted by 1 (the rest are left alone), and that argument is in the same position as the position that the entire a() function of tower size 1 is at, in the tower directly below it. (e.g. a(x,y,z) = a( a( a(x-1,y,z), y-1, z-1 ), a(x, y-1, z), z-1). The y-1 in a(x,y-1,z) is there because the entire function is in position 2 of the function directly below it.)

Basically, the extended Ackermann function is a fractal.

To give you an example, let me show you the calculation process of a(1,1,1).

a(1,1,1) = a( a( a(0, 1, 1), 0, 0), a(1, 0, 1), 0)
a(0,1,1) = a(1,1,0) = a(1,1) = 3

therefore, a(1,1,1) = a(a(3, 0, 0), a(1,0,1), 0)

a(3,0,0) = a(3) = 4
a(1,0,1) = a(a(0,0,1), 1, 0)
a(0,0,1) = a(0,1,0) = a(1,0,0) = 2, so:
a(2,1,0) = a(2,1) = 4

therefore, a(1,1,1) = a(4,4,0) = a(4,4) = 72 - 3, which is already a big-ass number.


The definitions for a(0, {xn}) are also pretty clear, any term whose first term is zero does not recur at all, but instead, redefines itself. E.g.:

a(0,0,3,0,0,0,5) = a(0,1,2,0,0,1,4). Each term greater than zero gives up 1 to the term to its left, unless the term was zero in the previous iteration. If that is the case, then it stays one. Note that there cannot be any trailing zeroes because they are eliminated from the sequence.

All these are very well defined. It's cases like a(m, 0, n, p, 0, q) that I'm worried about, where the first term is not zero and there are zero terms in between. It's easy to manually define each case [e.g. in the previous case mentioned, the answer is a( a( a(m-1, 0, n, p, 0, q), 1, n, p-1, 1, q-1), 1, a(m, 0, n-1, p, 0, q), p-1, 1, q-1 )], but I want to create a general definition.

Can anybody help?

User avatar
Actaeus
Posts: 606
Joined: Thu Jan 10, 2008 9:21 pm UTC
Location: ZZ9 Plural Z Alpha

Re: An Extended Ackermann function?

Postby Actaeus » Sun Dec 14, 2008 6:51 pm UTC

Well, if this helps, the Ackermann function is the fastest-growing recursive function for two arguments that only calls the successor function (x+1) and itself.
If you find an n-argument function with that property, that's the best extension I can think of...]

EDIT: http://tunes.org/~nef//logs/esoteric/06.03.20 gives a possible extension.
I'm going to choose not to reverse the arguments here, so we're cutting 0's off the beginning.

A(a)=a+1

A(0,b)=A(b)
A(a,0)=A(a-1,1)
A(a,b)=A(a-1,A(a,b-1))

A(0,b,c)=A(b,c) //including b=0 or c=0
A(a,0,c)=A(a-1,1,c) //including c=0
A(a,b,0)=A(a,b-1,1)
A(a,b,c)=A(a-1,A(a,b-1,c),A(a,b,c-1))

Of course, the recursion here isn't as immediately deeply nested as with your version, but it's a bit clearer, and you get so much recursion anyway that I doubt a few more levels to start with makes a fundamental difference.

EDITEDIT: http://www3.interscience.wiley.com/journal/113462524/abstract?CRETRY=1&SRETRY=0; no actual document, but it seems we've been beaten to the punch by "real" mathematicians.

tricky77puzzle
Will take "No Tresspassing Signs" for 500
Posts: 488
Joined: Thu Feb 28, 2008 11:02 pm UTC

Re: An Extended Ackermann function?

Postby tricky77puzzle » Sun Dec 14, 2008 11:51 pm UTC

Nice, thanks for letting me check it out.

Wow, their B(1,1,1) evaluates to a meager 61.

Anyway, all that's different from their function and mine is that in mine, a(x,y,z) evaluates to a(a(a(x-1, y, z), y-1, z-1), a(x, y-1, z), z-1), and that theirs evaluates to a(a(x-1, y, z), a(x, y-1, z), z-1). Mine grows more quickly, but still...

And yes, those few levels of recursion do make a fundamental difference if the arguments are large enough.
Last edited by tricky77puzzle on Sun Dec 14, 2008 11:56 pm UTC, edited 1 time in total.

User avatar
Actaeus
Posts: 606
Joined: Thu Jan 10, 2008 9:21 pm UTC
Location: ZZ9 Plural Z Alpha

Re: An Extended Ackermann function?

Postby Actaeus » Sun Dec 14, 2008 11:53 pm UTC

We really need to get a math professor or someone to help us...
Any on the fora? :wink:

User avatar
ATCG
Posts: 471
Joined: Sat Aug 18, 2007 3:44 am UTC
Location: Straight up the jω axis

Re: An Extended Ackermann function?

Postby ATCG » Mon Dec 15, 2008 1:00 am UTC

I'm no math professor, but you just might find some useful guidance here. The following excerpt seems particularly revelant to your quest:

[All links are taken directly from the original.]

Exponentiation is repeated multiplication, so it does not take much imagination to define an operation of repeated exponentiation, and so on. Repeating this idea gives the class of primitive recursive functions. These are roughly the functions that can be defined by starting with the successor function and allowing functions to be defined by recursion over the integers. A typical example of a number produced with such functions is Graham’s number, which seems to be the largest number that has turned up “naturally” in mathematics (rather than by someone deliberately trying to produce a large number).

The next step is functions such as Ackermann’s function, one of the simplest functions that is not primitive recursive. Primitive functions allow one to define functions by recursion over the first countable ordinal ω, but Ackermann’s function allows one to use recursion over the ordinal ω×ω=ω2. To define bigger functions, one can use larger (countable, constructive) ordinals. Some obvious ways of constructing these are ordinal addition, multiplication, and exponentiation.

The smallest ordinal one cannot form in this way is called ε0, the limit of [imath]\omega, \omega^\omega, \omega^{\omega^\omega}, \omega^{ \omega^{\omega^\omega}}...[/imath] which is the ordinal measuring the strength of Peano arithmetic, in the sense that it is the smallest ordinal that Peano arithmetic cannot prove to be well ordered (Gentzen’s theorem). A reasonably natural function at this level, related to Ramsey’s theorem, was found by Paris and Harrington as part of the proof of the Paris-Harrington theorem. [For another, check out Goodstein's theorem and the Goodstein sequence.]
"The age of the universe is 100 billion, if the units are dog years." - Sean Carroll


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 6 guests