Kolmogorov Complexity and Noncomputability
George Davie · Mathematical logic quarterly · 2002
We use a method suggested by Kolmogorov complexity to examine some relations between Kolmogorov complexity and noncomputability. In particular we show that the method consistently gives us more information than conventional ways of demonstrating noncomputability (e. g. by embedding in the halting problem). Also, many sets which are (at least) awkward to embed into the halting problem are easily shown noncomputable. We also prove a gap-theorem for outputting consecutive integers and find, for a given length n, a statement of length n with maximal (shortest) proof length.