You're looking at Less Wrong's discussion board. This includes all posts, including those that haven't been promoted to the front page yet. For more information, see About Less Wrong.

Kawoomba comments on PSA: Eugine_Nier evading ban? - Less Wrong Discussion

17 Post author: Dahlen 07 December 2014 11:23PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (68)

You are viewing a single comment's thread. Show more comments above.

Comment author: gwern 09 December 2014 08:00:48PM *  3 points [-]

There can't be, since KC isn't computable (could be mistaken on that in itself precluding a bounded error).

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?

Comment author: Kawoomba 09 December 2014 08:14:29PM *  0 points [-]

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!