Logic and Foundations Commons^™

Enumerations Of The Kolmogorov Function, Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet

Peter Fejer

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.

We determine exactly how hard it is to enumerate the Kolmogorov function, which assigns to each string x its Kolmogorov complexity:

• For every underlying universal machine U, there is a constant a …