Alternative to Ackermann Function

[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).

 

[jedishrfu]

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

 

[SSequence]

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.

 

[jedishrfu]

Ok so is there some question you want answered?

 

[SSequence]

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).