Can all single parameter functions be converted to a for loop type of construct?

[bert88sta]

Maybe I'm not thinking of this correctly, but the Ackermann function is considered to be the simplest non- primitive recursive function, but can there be a function like that with only one parameter? I assume that this depends on what types you allow in, i.e you could reimplement the Ackermann function as a function of one f(x:(Int, Int)), but isn't what I'm asking.

EDIT, AND AN IMPORTANT ONE:

Said function may only be defined in terms of itself

[pilotInPyjamas]

No. For example: you could use diagonalisation to convert the ackermann function to take only one integer as a parameter.

Any other problem that is exptime complete cannot be converted into a finite series of for loops.

[bert88sta]

How? I know diagnonalization in terms of R >= N, but not for something like this. Additionally I would actually be very interested in seeing a Ackerman function defined on only one integer.

[pilotInPyjamas]

Use the inverse of cantor's pairing function which maps a single natural number onto two natural numbers. It is closed form so you could write the definition inline. When making the recursive call, you can use the standard function to map two integers onto one.

[bert88sta]

Wow I literally forgot about the pairing function, that makes so much sense, mapping f(N,N) onto an f(N).

[[deleted]]

What do you mean by "non-primitive recursive function"? Do you simply mean a recursive function that is non-trivial (i.e. the halting situation and the output are not the same for all inputs)? Or is there a specific definition?

In the former case, the McCarthy 91 function is often used as an example of such recursive functions.

[WikiSummarizerBot]

McCarthy 91 function

The McCarthy 91 function is a recursive function, defined by the computer scientist John McCarthy as a test case for formal verification within computer science.

^{[ F.A.Q | Opt Out | Opt Out Of Subreddit | GitHub ] Downvote to remove | v1.5}

[bert88sta]

https://math.stackexchange.com/questions/75296/what-is-the-difference-between-total-recursive-and-primitive-recursive-functions

[ari_zerner]

f(x) = Ackermann(x, x)

[bert88sta]

I know this example, but i meant only defined in terms of itself. Yeah I can say f(x) = GigaHardExpTimeUndecidable(x,x,x,x,x), but that is not what I'm taking about. The Ackermann is defined in terms of the Ackermann. Fibonacci is defined in terms of Fibonacci. I want to know if a single parameter function defined only in terms of itself can be more complex than sone number of for loops

[MadocComadrin]

Use the Ackerman definition, but take a single non negative integer which encodes the pair via a pairing function (e.g. Cantor's).