Some Absolute Properties of A-Computable Numberings

详细

For an arbitrary set A of natural numbers, we prove the following statements: every finite family of A-computable sets containing a least element under inclusion has an Acomputable universal numbering; every infinite A-computable family of total functions has (up to A-equivalence) either one A-computable Friedberg numbering or infinitely many such numberings; every A-computable family of total functions which contains a limit function has no A-computable universal numberings, even with respect to Areducibility.