Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Any string generated from a PRNG clearly has a very short description. You need the code for the random number generator, the seed, and then the number of times to iterate. So, it seems that all such strings have low KC complexity.

If the above it true, then what is an example of a "complex" string, in the Kolmogorov-Chatin sense?

share|improve this question

migrated from cstheory.stackexchange.com Feb 12 '13 at 23:18

This question came from our site for theoretical computer scientists and researchers in related fields.

    
You can pick a bunch of bits from random.org –  Vor Feb 11 '13 at 9:15
5  
A͇̠̭͕̙̻̍̈́͗ͩ͠ ̉̔ͤ̓͌̉̽͠"͍͉̰͎ͨ̓̃c͕̟̈́ͧ̒̽̚͟o̰͈̠ͭm͔̭̳͙͉̪͌̅̔ͦp̷̺̱̠ͪ͂͌ͨ͂̚l̡̓̄̐ê̚͞x̖̟̝̻̫̻̙ͧͩ̎̆"̜͈ͪͤͥ͡ ̩̫͓ͭͯ̀s̥̼͂̃̿ͮ͊ṭ̫̺̬ͯͤ͛r̗̯͊ͣ̄̓ͪi͕̟̲̝̖͎ͨ̋̓̉̈́ͦn̹̟̗͚͒̋̏͂̂g̜ͫ̄̐̔͒ͤ,͈̫̟̬͊̔̑̐͐ ̪̝̟̼̜̩͒ͩ̈͌̓ȋ̹̟̺̪͉̺ͩͥ͋̅͂̏̕n̜͆ ̯̭t̖ͩ͛h̺͓͚̹ͯ̒̽ͮͫ͠e̪̹̓̇͌̒̎ͥ̋ ̫ͤ́ͦ͂̒͗̃͢K̍҉̘͔̭̪̰̦̺o̱͚̰͙̺̥̒͆͒̀l̺͉̬̤̬̊̕m̨͖̦̻̥ͮͦ̏͊͆o͈͒͂ͩ͆g̭͙̼̦o̞̤̮̲͑ͩ͞r̺͕̩͓̊ͭ͂̍̇̋̓‌​̜̯͇o̙͉͍̭̟͖v̦̏ͭ̀̔̅̈ͧ-͗̑҉͉C͚̱̣͎͚͔͆̕h̖̽͗ͧͨͤ͘a̞͐͌͆̅̍̾ṭ̻̗̺̫̖̭ͬ͑̍ͤͪ͊̂i̼͎̻̹̲̟͎ͬ̾̄̉̐ͥn̐ͧ‌​̗̀ ̔͒̇ͤͪ͊̎͡s̶̳̖̥̥̊ͪͦ͑̐̐e̝̖͓̺̤̰̗̍ͯ̓̈́̋͡n҉̻̮s͉͈̣̫͍͂̕e͔̜͓ͬ̒̂̐ͅ –  JeffE Feb 11 '13 at 17:10
    
I think what you want to ask is not just an example, you are probably confusing Kolmogorov random strings (i.e. strings with high Kolmogorov complexity) with pseudorandomness. If that is the case please clarify the question and ask for example "is there a relation between strings with high Kolmogorov complexity and pseudorandomness?". –  Kaveh Feb 12 '13 at 23:37

3 Answers 3

It is impossible to give a specific example of a string with high Kolmogorov complexity. If I was to give an example in this answer, then the following piece of code would retrieve it:

wget http://cs.stackexchange.com/q/9721

(plus some O(1) post-processing).

A string of high Kolmogorov complexity is as elusive as a random number:

Random number

There is in fact a connection between randomness and Kolmogorov complexity: a random string has maximal complexity for its length. (At least for one definition of randomness, appropriately called Kolmogorov randomness.)

This observation that it is impossible to exhibit a string of high Kolmogorov complexity can be put into a mathematical form and proved: it is called Chaitin's theorem.

The high-complexity strings are all the ones that you cannot describe.

share|improve this answer

The infinite string that has a 1 at the $i$-th position if the $i$-th Turing machine (in some fixed enumeration of TMs) halts on all inputs has a very high complexity.

share|improve this answer

Here is one example of a random string in the Kolmogorov sense:

kejrjtokplarkoprl[paxes,0owp,itro,se0ofiespoKWP[OLAOINJ-O2CLKSEJOPOS[P3VTOIIOIopqwiodhriuropdiorpdioieurfpoiopdioiuoidurodpiwoptdopirtois02-9980uhoititoci0ieioq34u0-40brnjvhw09a3=-rjchgo0ewir

share|improve this answer
7  
In my programming language, that string is exactly the result of a builtin function PrintGarbage(). –  Tsuyoshi Ito Feb 11 '13 at 13:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.