Are fixed-point combinators general recursive?

77 Views Asked by At

I'm not even sure if I'm asking the right way, but here's what I'd like to know:

If your language has fixed-point combinators, is it automatically Turing complete?

1

There are 1 best solutions below

2
On

The answer will be trivially "no". We need other basic functions to use as a starting point. For example, if the language just has a fixed point combinator, you can't actually use that to construct any functions, so the resulting language will not be able to express any function at all.

Of course, it does not take much to be Turing complete; the $\lambda$ calculus is already Turing complete.