Open AccessOn the Recursive Enumerability of Fixed-Point Combinators
Author(s) -
Mayer Goldberg
Publication year - 2005
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v12i1.21867
Subject(s) - combinatory logic , fixed point , set (abstract data type) , recursively enumerable language , context (archaeology) , mathematics , discrete mathematics , computer science , point (geometry) , algorithm , programming language , mathematical analysis , paleontology , geometry , biology
We show that the set of fixed-point combinators forms a recursively-enumerable subset of a larger set of terms we call non-standard fixed-point combinators. These terms are observationally equivalent to fixed-point combinators in any computable context, but the set of on-standard fixed-point combinators is not recursively enumerable.