[Submit a comment] [RTALooP home] [Index] [Previous] [Next] | [Postscript] [PDF] [BibTeX Source] [LaTeX Source] |
Originator: Henk Barendregt [Bar75]
Date: 1975
Summary: Is the word problem for the S-combinator decidable?
The word problem for the S-combinator is: Given two ground terms build only of the constant S 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 S-combinator
S x y z → (x z) (y z) |
Is the word-problem for the S-combinator decidable? See also [Wal98b] and [Wal98a] for more background.
A related problem is the word problem for proper combinators of order smaller than 3 (S is of order 3), see Problem #96.
[Submit a comment] [RTALooP home] [Index] [Previous] [Next] | [Postscript] [PDF] [BibTeX Source] [LaTeX Source] |