Kawoomba comments on PSA: Eugine_Nier evading ban? - Less Wrong Discussion
You are viewing a comment permalink. View the original post to see all comments and the full post content.
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (68)
KC may not be uncomputable in general, but I'm pretty sure that doesn't preclude all possible proofs or constructions*, and it seems odd to say that there is no upper bounds when we have what sure look like such things.
* I have just invented a Scheme-like programming language in which all tokens except numbers are 2 alphanumeric characters long; what is the Kolmogorov complexity of the bitstring '1'? 'Who knows, KC is uncomputable -' Bzzt! The answer is that the KC is exactly 1, since the shortest program which emits the bitstring '1' is a program consisting of the constant '1' which evaluates to '1', which as you can see, is indeed of length 1, and all other programs emitting the bitstring '1' are longer by definition.
Or if you don't like that example, consider taking your favorite language and enumerating all possible programs in length order; consider the outputs of the programs you've just enumerated when evaluated up to the highest available Busy Beaver in steps (to avoid nontermination issues), and the respective lengths of outputs - have you not found the KC for those outputs? If you run gzip over the outputs to get estimated KCs, are those not upper bounds on the actual KCs you proved?
Yea, only talking about the general case. Even the Halting Problem is usually computable in daily life, just by running the program (ETA: and seeing it terminate).
Watch the program run
See it die before your eyes
Halting Problem? Solved!