1
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ You will likely get a better answer if you ask a more precise question. In particular, what counts as a "higher order function"? One simple criterion to use is that any Turing-complete model of computation must have non-terminating computations. In particular, map, fold, filter, sort and the like, all necessarily terminate (if the mappings used in them terminate). Thus those can never suffice. $\endgroup$
    – Mees de Vries
    Apr 15 '19 at 17:35
  • $\begingroup$ @MeesdeVries A function that takes another function as a parameter. I think your answer answers my question, it is not possible. $\endgroup$
    – Jose
    Apr 15 '19 at 17:49
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for putting the things in words I thought about, that's definitely a good explanation! $\endgroup$
    – univalence
    Apr 15 '19 at 18:10
  • $\begingroup$ Wow, excellent answer. "A generalization of fold and map" sounds very interesting. I will accept this answer, but perhaps will let the question open a few more hours in order to get additional comments. $\endgroup$
    – Jose
    Apr 15 '19 at 18:45
0
$\begingroup$

Have you heard about combinatory logic? It somewhat works like this, introducing three combinators ($\approx\,$functions) $S$, $K$, and $I$. Together with an infinite set of variables, those are turing complete using the following evaluation rules:

$(((Sx)y)z)$ evaluates to $((xy)(xz))$.

$((Kx)y)$ evaluates to $x$.

$(Ix)$ evaluates to $x$.

where $(xy)$ is $x$ applicated to $y$.

For example, we can define the natural numbers in a quite simple way:

$0 =_{def} (KI)$, $succ =_{def} (S((S(KS))K))$

Addition isn't that difficult then: $add =_{def} S(KS)(S(K(S(KS)K)))$ (I omitted parentheses such that $XYZ = ((X Y) Z)$).

When evaluating, you will see how those terms work and what simple systems still are capable of.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for your answer, very informative and interesting! However, I was thinking about perhaps higher level primitives (at the level of sort, reduce,...), but still thank you very much. $\endgroup$
    – Jose
    Apr 15 '19 at 17:28
  • $\begingroup$ @Jose I also thought about this for a moment, but I believe those can't be turing-complete, because they are well-typed. Sounds a bit strange, but all of those functions are definitely definable within most type theories, and those theories forbid nonterminating functions which are required for turing-completeness. It might be achievable using a recursion combinator though (for such a combinator Y, (Y f) would reduce to (f (Y f))), but this would probably be against this question's point. $\endgroup$
    – univalence
    Apr 15 '19 at 17:34
  • $\begingroup$ I see, that answers my question, then. Thank you. $\endgroup$
    – Jose
    Apr 15 '19 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.