← All problems
Unverified

Is the word problem for the S-combinator decidable?

The source page states the original problem together with its recorded qualifications and progress updates as follows.

The word problem for the SS-combinator is: Given two ground terms build only of the constant SS in combinatory logic (that is with an application operator written as juxtaposition, and parantheses), are they convertible in the system consisting only of the definition of the SS-combinator

Sxyz→(xz)(yz) S x y z \rightarrow (x z) (y z)

Is the word-problem for the SS-combinator decidable? See also [Barendregt, 1975] and [Barendregt, 1975] for more background.

A related problem is the word problem for proper combinators of order smaller than 3 (SS is of order 3), see RTALooP entry smallorder-combinators-word.

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu