- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: <hal.domain.name.hidden>

Date: Thu, 4 Nov 1999 09:01:14 -0800

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

Received on Thu Nov 04 1999 - 09:18:52 PST

Date: Thu, 4 Nov 1999 09:01:14 -0800

Juergen Schmidhuber writes:

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

Received on Thu Nov 04 1999 - 09:18:52 PST

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:06 PST
*