On the Recursive Enumerability of Fixed-Point Combinators

Mayer Goldberg

November 2004


We show that the set of fixed-point combinators forms a recursively-enumerable subset of a larger set of terms that is (A) not recursively enumerable, and (B) the terms of which are observationally equivalent to fixed-point combinators in any computable context

Available as PostScript, PDF, DVI.


Last modified: 2004-12-08 by webmaster.