Complexity of complexity and strings with maximal plain and prefix Kolmogorov complexity

Bruno Bauwens, Alexander Shen

Peter Gacs showed (Gacs 1974) that for every n there exists a bit string x of length n whose plain complexity C(x) has almost maximal conditional complexity relative to x, i.e., C(…