Quasi‐completeness and functions without fixed‐points
Ilnur Ildarovich Batyrshin · Mathematical logic quarterly · 2006
Abstract We prove a completeness criterion for quasi‐reducibility and generalize it to higher levels of the arithmetical hierarchy. As an application of the criterion we obtain Q‐completeness of the set of all pairs (x,n) such that the prefix‐free Kolmogorov complexity ofxis less thann. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)