Length of the shortest program on a fixed universal machine U outputting x. Invariant up to O(1) across choices of U. Uncomputable: if K were computable, the 'smallest x of complexity > n' would have a short description, contradiction.
Length of the shortest program on a fixed universal machine U outputting x. Invariant up to O(1) across choices of U. Uncomputable: if K were computable, the 'smallest x of complexity > n' would have a short description, contradiction.