Stochastic processes as computational resource

In An Intelligent paradox I speak about the interesting paradox of the Kolmogorov complexity strings.

I don’t believe in the existence of really stochastic processes but if I am wrong or if exist good approximations this open an interesting possibility.

I can use a stochastic process to construct with very high probability a Kolmogorov complexity bit string and this is uncomputable and in general very computational expensive to do in a deterministic domain.

Using a stochastic process I have something like an oracle let me to answer to the question “give me a Kolmogorov complexity bit string with length N” ( the answer can be only high probably correct ) and I can solve every problem have a computable reduction to a program that use an oracle like this.

I don’t know if algorithm like this exist , searching throw the randomized algorithms the use of random source seem more related to a statistical distribution and is not used the property of the random data as an algorithmic random source .

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s