← 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 -combinator is: Given two ground terms build only of the constant 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 -combinator
Is the word-problem for the -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 ( is of order 3), see
RTALooP entry smallorder-combinators-word.
