Philosophy of Everything

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  K(s)  is the Kolmogorov complexity . We can define the compress-ibility C(s) of a string s  to be the smallest compression  K(s)  divided by the size of the original representation  size(s) : C(s) = K(s) / Size(s) - lower is better The smallest compressed size" for any given string is a function that cannot be calculated in general, however you can always find an upper bound to it as soon as you find a compression of that size. A compression of s is basically a program along with it's input that can generate s as output. If is always possible to find a program slightly bigger than s  (think: print " s "), therefore it is only interesting to find compression with size that is lower than size( s ).

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 look. It starts with an introduction of known facts, it continues with some less discussed properties and finishes with some philosophical considerations. Introduction Example of irrational numbers are numbers like √2 and ℼ (PI). Irrational numbers cannot be represented as a fraction like, 0.25 is represented by 25/100 or 1/4. Such numbers have an infinite number of decimals that are not repeating any groups we would take. Numbers like 0.(321) are not irrational, even if they have an infinite number of decimals, because they are repeating: 0.321 321 321 321 ... Such numbers with repeating decimal groups can be represented as a simple fraction: 0.321 = 321/999 an therefore are considered "rational". Rational numbers can be represented as fractions (like 234/789), and the...

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 new ideas: an example of a Kolmogorov compression that would require an arbitrary high amount of working memory before shrinking to the compressed string (conjecture). 1. Root cause why "Kolmogorov complexity" is uncomputable Kolmogororov complexity is uncomputable because Turing machines have a halting problem :) Let's start with the observation the the Halting problem of a Turing machine having a limited band is actually decidable, unlike the infinite band one. A "finite band Turing machine" is actually a finite state machine that will either stop without going through the same state, or will cycle infinitely. Having a limited number of possible states, it cannot run too much without repeating a previous state. As soon as the machine returns to...

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. You can think about it like measuring how small can you make a file (string of characters) by compressing it with ZIP or similar. A file storing a very redundant information (like "aaaaaaaaaaaaaaaa....") can be compressed in a much smaller size compared with a random one. For calculating the "Kolmogorov complexity", the "compressed" form is considered to be something like a self-extract archive: the shortest program that can output the initial string of characters (the "file/string to be compressed"). The Kolmogorov complexity is more general and includes classical compressing algorithms. For example a Huffman code is not very powerful in compressing a string like "123456789101112131415161718192021222324..." (concatenated consecut...

" 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 having solutions that can be proven in polynomial time once you "guess" the solution. This is analogous with the sorting problem: it's easier to check the correct sorting of a list than to actually sort a list. Of course, if you can fully solve the problem in polynomial time, you can also prove it in polynomial time, so P is included in NP. However, NP seems to contain some very hard problems that cannot be currently solved in polynomial time. It is believed that NP contains some problems that can never be possibly solved in P. I will not do a formal proof, more like an argument or a sketch. You might have more patience and skills to develop some of these ideas even if they might have flaws in the current form. You can take it a...

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 computer with more memory than the virtual machine, although it might be way slower. However, such virtual machine does not answer the problem because it normally simulates a computer with less memory. The question is, can a computer to simulate a virtual computer that has the same capabilities as itself? Before answering this, let's exclude some trivial (forbidden) cases of "simulations": A calculator will always do exactly what it does, it will be identical with itself, we will not call this a simulation of itself. Copying the exact state of another identical computer in a "twin brother" will not be considered simulation. Starting 2 identical computers with the same input will not be considered like one is simulating the other.

"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 basic assumption is that there are common laws that are universal and they function the same across the whole Universe. This is a leap of faith that we have to take if we believe that the Universe can be understood at all by humans.

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 the solution. The program does not need to run efficiently. Actually, it does not need to run in reasonable time. It just has to be very short. And to be proven to answer the requirement, eventually... No external random source is allowed and no input from user.

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 to put in competition a big, however finite, problem like chess with an arbitrary big problem like sorting n elements. Fair enough; the interesting thing is that sorting becomes inherently harder than chess for an "n" that is way smaller than you would expect, like sorting 3000 elements. At least in theory... Sorting takes a minimum of n* log 2 (n) comparisons,  more exactly  log 2 (n!) This is about sorting "by comparison only" and can be proven in 2 step. You can skip to the "chess" part if you already know this. 1. Sorting can be done in  log 2 (n!) comparisons, that is just slightly less than n* log 2 (n). We are used to consider sorting an O (n* log 2 (n)) problem. Actually there are algorithms that can do the sorting with little less t...

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 information very compressed, but still... I will approach the problem of describing life complexity based of information theory.

A friend told me once that we are living in an Universe full of unprovable truths. He was referring to the Gödel's incompleteness theorems . Without being very formal, this says that there are many mathematical propositions that might be true but we cannot prove them using a computer program or any predictive way of checking, no matter how huge amount of time we can spend. We can find the proof for some, by luck, but for most of them we cannot find either a proof or disproof. In fact this "unprovable" propositions are way more many than the provable propositions. The provable propositions are like the set of natural numbers "N" and the unprovable propositions are like the set of real numbers (R).