# Alternative to Ackermann Function

• SSequence
In summary, the conversation discusses the concept of a function that dominates every primitive recursive function, and how it can be defined using a collection of do-times programs. The function is denoted as f(n) and its properties are described, including its strict domination over primitive recursive functions and the potential use of an "oracle" command in Loop programs to further dominate the Ackermann function. The conversation also mentions the potential difficulty in calculating this function for larger values of n.
SSequence
Perhaps "alternative" isn't the best word here. What I meant is a function that dominates every PR (primitive recursive) function for which it is very easy to see that property.

Every PR function is calculated by some "do-times" program. Define the collection W1 to be the set of all do-times programs that take only one variable as input.

So define a function f : N → N as follows:
f(n) = the minimum number of steps on which all W1-programs of length ≤ n halt when they are given n as input

We could also use the function g(x)=f(x)+1 but it wouldn't be very elegant perhaps.

It would not be particularly difficult to show that f itself is not primitive recursive.

I think it could also be shown (haven't thought about the argument carefully but it seems quite likely) that the domination is strict (in the sense that the domination is based on "less than" relation and not on "less than or equal to" relation).

If someone wanted to implement this function using a concrete programming language it wouldn't be that hard. I do wonder what would be the values of n (roughly) at which the values of this function would just become too large to calculate feasibly.

Edit:
"f(n) = the minimum number of steps on which all W1-programs of length ≤ n halt when they are given n as input"
Possibly (with careful argument) one could also relax the condition above from "≤ n" to "=n"? Wouldn't be surprising if that was the case.

P.S.
Of course one would also make sure of basic stuff such as not having any commands of type "c=100" etc. to make sure that there are finite number programs of a given length (also other stuff such as variable re-naming to avoid redundancy for the same/equivalent programs).

Last edited:
What are you looking for? An alternative function? Or are you musing about the theory behind primitive recursion?

I described a function g(x)=f(x)+1 which by its definition:
(a) Grows strictly faster than any primitive recursive function (after a finite values*** is strictly greater than any given primitive recursive function (of one argument) for all values) by its definition.
(b) By (a) it follows g isn't primitive recursive function itself.

My original post seemed slightly fragmentary because I was talking about f instead of g. Proving the properties (a) and (b) for f would require a few further (though fairly easy) arguments.

To program this function one just needs to write an interpreter for do-times/Loop programs (in any language of course). Also by length of program I meant number of instructions (instead of number of characters which would just be harder to maintain).

Indeed writing this function would be a bit long (not that much but still), but partly ackermann function is also so short because it uses a higher level construct of function calling itself.

*** the first value where it will definitively start dominating some given primitive recursive function h (of one variable) would be when the input is equal to the length of smallest do-times/Loop program which calculates h.

Last edited:
Ok so is there some question you want answered?

Not as such :p ... of course unless someone has enough time to spend to actually write it and report when the value of this functions starts becoming too difficult to calculate (in terms of time) :p.

I can think of one or two interesting questions though (in case someone wants to answer). For example, suppose we added another "oracle" command to Loop programs which can use this function g. Then does there exist an "oracle Loop program" which would dominate the ackermann function?

My guess would be yes (unless the ackermann function dominates PR functions in a very crude/overwhelming way ... which would be a bit weird).

## What is the alternative to Ackermann function?

The alternative to Ackermann function is the primitive recursive function, which is a simpler and more well-behaved function.

## Why is an alternative to Ackermann function needed?

An alternative to Ackermann function is needed because the Ackermann function grows extremely quickly and is not computable for large inputs, making it impractical for use in many applications.

## How does the primitive recursive function compare to Ackermann function?

The primitive recursive function is much simpler and more well-behaved than the Ackermann function. It grows much slower and is computable for all inputs, making it a more practical choice for many applications.

## What are the benefits of using a primitive recursive function over Ackermann function?

The benefits of using a primitive recursive function over Ackermann function include simpler computation, faster growth rate, and the ability to compute for all inputs.

## Are there any downsides to using a primitive recursive function instead of Ackermann function?

One downside to using a primitive recursive function instead of Ackermann function is that it may not be able to solve certain problems that require the extremely fast growth rate of the Ackermann function. Additionally, some problems may be harder to express using primitive recursion compared to the more powerful Ackermann function.

• Programming and Computer Science
Replies
1
Views
1K
• Programming and Computer Science
Replies
16
Views
1K
• Programming and Computer Science
Replies
17
Views
2K
• Programming and Computer Science
Replies
11
Views
908
• Programming and Computer Science
Replies
20
Views
2K
• Programming and Computer Science
Replies
13
Views
2K
• Programming and Computer Science
Replies
2
Views
988
• Programming and Computer Science
Replies
29
Views
2K
• Programming and Computer Science
Replies
12
Views
1K
• Programming and Computer Science
Replies
9
Views
2K