Enumerations of the Kolmogorov function

Abstract

Abstract A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x) . f is a k(n) -enumerator if for every input x of length n. h(x) is among the first k(n) elements enumerated by f . If there is a k(n) -enumerator for h then h is called k(n) -enumerable. We also consider enumerators which are only A -recursive for some oracle A .