Juergen Schmidhuber writes: > Hal: > > >....Approximate probabilities based on approximations to the > >K. complexity of a string are no more computable than precise ones. > >There is no fixed bound B which allows you to compute the K. complexity > >of an arbitrary string within accuracy B. > > You should add "within a given fixed time interval." Within finite > (though unknown) time you can compute the K of finite string x. In > general you'll just never know whether your current lowest upper bound > on K is tight.
Right, but the fact that we observe probabilities means that they are being computed to within some bounds, right? And the bounds have to be low enough that we don't observe discrepancies from what probability theory would predict, it seems to me. Kolmogorov complexity is uncomputable to the same extent and for much the same reason that the halting problem is undecideable. Yes, if you had infinite time you could compute the K. complexity of any string, and you could also solve the halting problem for any program. Wouldn't you be uncomfortable with an ontology which required solving the halting problem in order to produce the observable universe? It seems that requiring evaluating K. complexity, even to within some specific bounds, raises the same difficulties. Hal