[amluto]

I think that, if you are restricted to a finite list of n-ary functions, n>=2, each returning a single value, then you can’t do it, as you will only have finitely many valid expressions.

This may be easier to see in a stack machine / RPN model. An expression is a list of operations, drawn from a finite set, each of is either “push the number 2” or something that decreases the stack size by at least 1. And you need exactly 4 pushes. So a valid expression has four pushes and at most 3 other operations, because otherwise the stack would underflow. This gives a finite number of possible expressions, but there are an infinite number of integers, so it can’t work.

[throwway120385]

Are you sure the number of possible expressions is finite? Or is it countably infinite? I could in theory make an arbitrarily long expression out of the four fundamental operators, and because I can derive -1 from a finite set of operations it is possible to derive any integer from any even integer. You can also derive zero from the rules.

[lmm]

> I could in theory make an arbitrarily long expression out of the four fundamental operators

Not with only four inputs you can't. You can only have three operations, because you have no way of getting another input parameter.

[vesinisa]

I didn't mean to say that n would need to be 2 or more, unary functions (I even mentioned factorial) should be fine. 1-tuple is valid tuple :)

And yes I think your analysis that only allowing n-ary funcs with n>=2 would make general solution very much impossible since you can only have a limited number of inputs.