On the Recursive Enumerability of Fixed-Point Combinators

Authors

  • Mayer Goldberg

DOI:

https://doi.org/10.7146/brics.v12i1.21867

Abstract

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.

Downloads

Published

2005-01-11

How to Cite

Goldberg, M. (2005). On the Recursive Enumerability of Fixed-Point Combinators. BRICS Report Series, 12(1). https://doi.org/10.7146/brics.v12i1.21867