3
$\begingroup$

I don't know if I'm using the vocabulary correctly, but what I'm interested in is this: If your language has fixed-point combinators, is it Turing-complete?

$\endgroup$
  • $\begingroup$ Nice question. Can you do anything interesting if all you have is fixed-point combinators? $\endgroup$ – David Richerby Nov 14 '14 at 9:28
2
$\begingroup$

Yes, fixed point combinators are sufficient for general recursion and Turing complete computations.

In my Awelon project languages, fixed point combinators are the only way to model recursion. In practice, working directly with fixed point is rather annoying. However, it isn't difficult to build more conventional loop primitives (while, until, repeat) and collections-oriented abstractions (fold, map, scan, foreach, etc.) above fixed points. I hope to build a big enough library of loop functions that I rarely need to directly use fixpoint.

And to answer David Richerby's follow-on question: Yes, there are some interesting things we can do if all we have is fixed point combinators.

  1. It is possible to name any function by use of secure hash, which can be convenient for content-addressable linking models. With name-based recursion, you cannot use the secure hash of a function's name to refer to itself. Besides myself, it seems Paul Chiusano aims to take advantage of this [2].
  2. The language is much more streamable, by which I mean that program execution can proceed by processing each element in a stream of instructions then forgetting it. This is a nice feature for mobile code or remote control applications. Conventional languages model loops by jumping backwards, which requires the computer hold onto the code (i.e. stored program computing).

Use of fixed point combinators is not a sufficient condition for these features. Other aspects of the language must also align. But fixed point combinators do not entangle program semantics with the namespace, which does simplify things.

$\endgroup$

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.