Some examples of non-existent combinators
type: Item
instance of: scholarly article
title: Some examples of non-existent combinators
zbMATH Open document ID: 0795.03022
DOI: 10.1016/0304-3975(93)90096-C
published in: Theoretical Computer Science
publication date: 1994-09-01T00:00:00Z
review text: This note discusses some interesting properties that combinators may or may not have. First, the author mentions an open problem: is there a fixed point combinator \(Y\) such that \(Y= Y(SI)\)? Next, he proves that no fixed point combinator can be defined in terms of the combinators \(B\) and \(WI\). He defines hypercreative and hypereasy combinators and shows none exist and also shows that there is no universal generator \(M\) for which there exists an \(N\) such that for all combinators \(P\), \(M\twoheadrightarrow NP\).
Mathematics Subject Classification ID: 03B40
zbMATH DE Number: 501176
zbMATH Keywords: combinatory logic
zbMATH Keywords: combinators
zbMATH Keywords: fixed point combinator
zbMATH Keywords: universal generator
author: Richard Statman
reviewed by: Martin W. Bunder
MaRDI profile type: Publication
cites work: Q3728878
cites work: Some new results on easy lambda-terms
cites work: Q5565113
cites work: On sets of solutions to combinator equations
cites work: Q3922646
description: scientific article; zbMATH DE number 501176