Re: Turing vs math

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