2
$\begingroup$

There is one example in Kolmogorov complexity books and related articles:

Consider we have a monkey at a typewriter and a monkey at a computer keyboard.

If the monkey types at random on a typewriter, the probability that it types out all the works of Shakespeare (assuming that the text is 1 million bits long) is about

p_typewriter (works of Shakespeare) ≈ 2^−1000000

If the monkey sits at a computer terminal, however, the probability that it types out Shakespeare is now related to the Kolmogorov complexity of the works of Shakespeare, which can be approximated by

K(works of Shakespeare) ≈ 250000 bits

using a program that compacts these works using 250000 bits. Then:

p_computer(works of Shakespeare)≈2^−K(works of Shakespeare) ≈2^−250000

The example indicates that a random input to a computer is much more likely to produce “interesting” outputs than a random input to a typewriter.

We all know that a computer is an intelligence amplifier...

What actually the computer does?

$\endgroup$
  • 1
    $\begingroup$ "Intelligent information" (as interpreted by humans) is compressible (it contains repetitions, patterns, and so on); so a computer is simply able to "uncompress" a short string to a larger one; and a short random string is more likely to contain a compressed intelligent content. For a bunch of references about compressibility vs meaning see wasdarwinwrong.com/kortho44a.htm $\endgroup$ – Vor Mar 27 at 11:32
  • $\begingroup$ The link is not working. I understand that a computer can compress information by finding hidden patterns. The question is why do you need fewer trials on the computer? For example, if I generate 01010101 than a computer can interpret some text as instructions ('for, if...'), but how it can help? $\endgroup$ – Oleg Dats Mar 27 at 12:09
1
$\begingroup$

Let's first clarify the scenario. What you're basically asking is why it is more likely to randomly write a computer program that outputs the works of Shakespeare than writing the works of Shakespeare directly.

The simple answer to this is that there are many ways to write a program that outputs a fixed string, but only one way to directly write this string. This may sound a bit strange, because there is clearly a mapping from strings that describe a computer program that outputs a string to another string (that is, the string outputted by the described program), and we could interpret a large amount of strings as descriptions of programs that outputs something. So why are the sizes different?

The reason is that these mappings are not bijective: the map from programs to strings outputted is clearly surjective, as we can output any string, but also clearly not injective, as there are multiple programs that output the same string. So, the set of programs must be larger than the set of strings outputted by them. That means if we sample over the set of programs, we need to sample over a much smaller set to get strings of a certain size, than if we were to sample over the strings directly.

$\endgroup$
  • $\begingroup$ We put a random program P (tape 01001...) in the Turing machine that can interpret some code as instructions ('for, if, *5...'). Do these instructions amplify the probability? $\endgroup$ – Oleg Dats Mar 27 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.