|
On the Recursive Enumerability of Fixed-Point Combinators
Mayer Goldberg January 2005 |
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
Available as PostScript, PDF, DVI. |