3
$\begingroup$

SK, BCKW, and BAMT combinator systems are known to be Turing-complete and convertible into each other. (BAMT is mentioned in this blog post)

Sxyz ~> xz(yz)
Kxy  ~> x

Bxyz ~> x(yz)
Cxyz ~> xzy
Kxy  ~> x
Wxy  ~> xyy

Bxyz ~> x(yz)
Axy  ~> y
Mx   ~> xx
Txy  ~> yx

Here, B, C, and S take three arguments.

Interestingly, the fixed point combinator can be expressed using only two-argument combinators:

Y' = (\xy. xyx) (\yx. y(xyx))
Theta = (\xy. y(xxy)) (\xy. y(xxy))

My question is: Is there any Turing-complete basis that only consists of one- or two-argument combinators? More specifically, is it possible to construct B or S with such combinators?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ It is known such two-variable combinators don't form the complete basis (MathOverflow question, Statman R. "Two variables are not enough"). This page lists computability of the word problem as an open problem as of 2014. $\endgroup$ Commented Jul 7, 2024 at 10:40
  • $\begingroup$ @pcpthm shouldn't you comment be an answer? $\endgroup$ Commented Oct 22, 2024 at 13:37
  • $\begingroup$ Thanks for bringing up BAMT, deriving BCKW from it was fun! $\endgroup$ Commented Oct 22, 2024 at 13:38

0

Reset to default

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.