Abstract:
Cost functions were introduced as a framework for constructions
of c.e. incomputable sets that are close to computable. We
carry out a systematic study of cost functions. We relate their algebraic
properties to their expressive strength. We show that additive cost functions
correspond to the K-trivial sets. We prove a cost function basis
theorem, and give a general construction for building c.e. sets that are
close to being Turing complete.
