Life is very compressible
An information representation (or string) s is very compressible if the size of it's smallest possible compression K(s) is very small compared with it's observed size(s). The smallest compression size...
Tag
#Kolmogorov
Explore (search, categories, archive)
Irrational numbers
This article contains my personal reflections on irrational numbers, especially the informational property of their infinite strings of decimal - strings that often look close to random at a shallow l...
Why Kolmogorov complexity is not computable - root cause
Please check my informal introduction to "Kolmogorov complexity" if you are not familiar with the subject. In this article I will approach some less discussed ramifications of it and hopefully some ne...
Kolmogorov complexity - short, informal introduction
I want to give you an intuition about Kolmogorov complexity, without being very formal. Basically, Kolmogorov complexity defines a measure of how small can you compress a certain string of characters....
P=NP is undecidable (conjecture)
"P equals NP?" is a million dollars unsolved problem. Introduction "P" is the class of problems where we have algorithms that solves the problem in polynomial time. "NP" is the class of problems havin...
Can a computer (or human) simulate itself?
A virtual machine is a common example of simulation. It can take the description of a (virtual) "computer" state and continue the execution from that point on. You can simulate a huge computer given a...
We believe in a compressible Universe
"Believe" is often associated with religion. However, even for using the "scientific method", we are forced to assume certain qualities of the Universe that we cannot prove nor fully verify. The most...
Shortest program that prints the play "Othello" by William Shakespeare
We have this requirement: "Create the smallest program that will print the full text of the play Othello by William Shakespeare". I should warn you that the requirement hides a trick and you will hate...
Sorting is computationally harder than playing chess
I will argue below that sorting of a big array, using only comparison, is inherently harder than solving the problem of choosing the best next move on a chess game. One could say that it is not fair t...
DNA and the fabric of the Universe
The genetic code seems to not be enough to describe the complexity of a human being. In fact, it seems too small to describe most of the life forms. We could assume that the genetic code has all the i...