Can a language with some set of higher-order functions like map, fold and filter but without recursion or iteration be Turing complete?

I was reading this article and was wondering if there is any finite set of higher-order functions like map, fold or filter such that they could empower a language to be Turing complete even without having explicit constructs for recursion or iteration. Obviously the higher-order functions would be implemented with recursion or iteration, but the requirement is that recursion or iteration could not be directly exposed to the programmer. That is to say, recursion or iteration can be baked in a finite set of pre-defined, built-in higher-order functions, but the language must not have an explicit construct for iteration or recursion. The set of higher-order functions can be arbitrarily large, but must be finite.

Alternatively, if the answer is no, which is the biggest set of problems that could be computed by such a language? Is that set a known set (eg. equivalent to pushdown automaton)?

A functional language such as (a fragment of) Agda has:

• inductive types (lists, trees, numbers, etc.)

• higher-order functions

• structural recursion (a generalization of fold and map)

However, such a language is not Turing complete. If we add the fix-point operator, which is a higher-order function

fix_t : (t -> t) -> t

then we can use that to implement general recursion and we have a Turing-complete language. Conversely, in Turing-complete functional language it is possible to implement fix_t, at least in the case t = nat.

So the obstruction to Turing completeness of functional languages is whether they can implement the fixed-point operator. (Partial combinatory algebras from another answer to this question also have the fixed-point operator.)

StackExchange Computer Science Q#106995, answer score: 3