<p>It is well-known that the <a href="https://en.wikipedia.org/wiki/SKI_combinator_calculus" rel="noreferrer">SKI combinators</a> are enough to get universal computation, though the original version of combinatory calculus used <a href="https://en.wikipedia.org/wiki/B,_C,_K,_W_system" rel="noreferrer">BCKW</a>. However, it is possible to get a fixed-point combinator from just the B and W combinators (by a construction of Statman: <code>(B(WW))((BW)((BB)B))</code> is a fixed-point combinator). Given that fixed-points are used in some instances to compute, I was wondering how much of computation one can get at this point. I would be quite surprised if one could get universal computation, so I ask the more modest question about how much computation we get. Or, to put it another way, what do we lack?</p>
<p>I would be interested in knowing either what we get from just a fixed-point combinator, or else what we get from B and W, taking into account the fact we get a fixed-point combinator from these.</p>
<p>I'm aware of Wolfram's recent <a href="https://writings.stephenwolfram.com/2021/06/1920-2020-and-a-20000-prize-announcing-the-s-combinator-challenge/" rel="noreferrer">S combinator challenge</a> to prove that universal computation can arise from just S, but this is something of a different flavour.</p>

CC BY-SA 4.0
2021-11-04T18:15:06.003Z
It is claimed on IRC (Libera Chat, #esolangs) that BCW is Turing-complete, although large amounts of garbage are built up during reduction and cannot be discarded. This suggests that BW has trouble swapping pairs of arguments.
Corbin
CC BY-SA 4.0
2021-11-04T21:38:35.197Z
I don't expect it to be able to swap!
David Roberts
CC BY-SA 4.0
2021-11-06T10:45:05.573Z
Deleted my previous comment, since I made a calculation mistake. Still just wanted to say that this is a nice question, which I don't know the answer to, and that the question of what we can get from just B and I (definitely not universal computation) was considered by Statman in [Combinators and the theory of partitions](https://kilthub.cmu.edu/articles/journal_contribution/Combinators_and_the_theory_of_partitions/6477062/1).
Noam Zeilberger
CC BY-SA 4.0
2021-11-06T13:26:21.237Z
@NoamZeilberger thanks! I missed the first comment :-) That reference looks interesting. I think I'd be quite happy if there was some kind of undecideability already in BW combinatory logic, even if not universal computation. But I may be misunderstanding what Statman is claiming
David Roberts
CC BY-SA 4.0
2021-11-07T08:24:55.393Z
@DavidRoberts I ran a computation and was confused about how `(B(WW))((BW)((BB)B))` could give a fixed-point combinator, but I had a pair of misplaced parentheses. :-) In the paper I referenced about B+I, Statman proved that the *unification* problem is undecidable (given two B,I combinations with free variables, is there a substitution making them equal?).  However, the word problem can be solved in polynomial time by interpretation in $\lambda$-calculus, since every step of $\beta$-reduction reduces the size of the term. This is of course very different when you have $W = \lambda xy.(xy)y$.
Noam Zeilberger
CC BY-SA 4.0
2021-11-07T09:13:14.257Z
@NoamZeilberger Ah, ok, so not quite so fancy. I could tell it wasn't much more serious undecideability, but wasn't sure how big the specified problem was. I myself also checked Statman's combinator when I learned of it, albeit by hand :-)
David Roberts
<universal-computation><combinatory-logic><fixed-points>
Is it known how much computation a fixed-point combinator gets you?
David Roberts
# Is it known how much computation a fixed-point combinator gets you?

(Asked by: username_0 on 2021-11-04)

It is well-known that the [SKI combinators](https://en.wikipedia.org/wiki/SKI_combinator_calculus) are enough to get universal computation, though the original version of combinatory calculus used [BCKW](https://en.wikipedia.org/wiki/B,_C,_K,_W_system). However, it is possible to get a fixed-point combinator from just the B and W combinators (by a construction of Statman: `(B(WW))((BW)((BB)B))` is a fixed-point combinator). Given that fixed-points are used in some instances to compute, I was wondering how much of computation one can get at this point. I would be quite surprised if one could get universal computation, so I ask the more modest question about how much computation we get. Or, to put it another way, what do we lack?

I would be interested in knowing either what we get from just a fixed-point combinator, or else what we get from B and W, taking into account the fact we get a fixed-point combinator from these.

I'm aware of Wolfram's recent [S combinator challenge](https://writings.stephenwolfram.com/2021/06/1920-2020-and-a-20000-prize-announcing-the-s-combinator-challenge/) to prove that universal computation can arise from just S, but this is something of a different flavour.

**Tags:** universal-computation, combinatory-logic, fixed-points
> **Comments:**
> **username_1**: It is claimed on IRC (Libera Chat, #esolangs) that BCW is Turing-complete, although large amounts of garbage are built up during reduction and cannot be discarded. This suggests that BW has trouble swapping pairs of arguments.  
> **username_0**: I don't expect it to be able to swap!  
> **username_2**: Deleted my previous comment, since I made a calculation mistake. Still just wanted to say that this is a nice question, which I don't know the answer to, and that the question of what we can get from just B and I (definitely not universal computation) was considered by Statman in [Combinators and the theory of partitions](https://kilthub.cmu.edu/articles/journal_contribution/Combinators_and_the_theory_of_partitions/6477062/1).  
> **username_0**: @NoamZeilberger thanks! I missed the first comment :-) That reference looks interesting. I think I'd be quite happy if there was some kind of undecideability already in BW combinatory logic, even if not universal computation. But I may be misunderstanding what Statman is claiming  
> **username_2**: @DavidRoberts I ran a computation and was confused about how `(B(WW))((BW)((BB)B))` could give a fixed-point combinator, but I had a pair of misplaced parentheses. :-) In the paper I referenced about B+I, Statman proved that the *unification* problem is undecidable (given two B,I combinations with free variables, is there a substitution making them equal?).  However, the word problem can be solved in polynomial time by interpretation in $\lambda$-calculus, since every step of $\beta$-reduction reduces the size of the term. This is of course very different when you have $W = \lambda xy.(xy)y$.  
> **username_0**: @NoamZeilberger Ah, ok, so not quite so fancy. I could tell it wasn't much more serious undecideability, but wasn't sure how big the specified problem was. I myself also checked Statman's combinator when I learned of it, albeit by hand :-)  

---

## 0 answers

