Is there a theory to answer "the simplest program to solve a problem"?

Question

To answer "what problems can be solved by computing", we developed the theory of computability. For the problems that are computable, is there a theory to answer the question "is the program I get the simplest one"?

I do not think computational complexity answer the question. I think it considers how long we need (though measured abstractly).

I am not sure whether algorithmic information theory answer the question. It seems that the theory talks about size, where the equivalence of minimal size and simplest is not obvious to me (well, at least they feel different to me).

I think the theory should at least define "simple" or "simpler than" relation.

---

I am now convinced that I should look into Kolmogorov Complexity. However, I would like to explain what was in my mind when I was asking the question.

When I improve a program, I try to reduce unnecessary connections between different parts of the program (maybe re-dividing parts so that there can be less or weaker connections). Since the connections are reduced, the program feels "simpler". Hence the choice of the word "simple" when I am phrasing the question. It is very likely the size of the program also decreases, but that is a good side effect, not the main goal. Obviousely, the improving process cannot go forever. There is a point that I should stop. If, only by considering the "structure" (sorry for another undefined concept) or "relation", can I convince myself that nothing more can be done?

Here contains better description of my notion of complexity.

Olaf Sporns (2007) Complexity. Scholarpedia, 2(10):1623

Answer 1

This problem is studied in Algorithmic Information Theory. What you're defining is called Kolmogorov-Chaitin complexity.

http://en.wikipedia.org/wiki/Kolmogorov_complexity

And it seems that the notion of simplicity that you're requiring can be formalized via the notion of complexity measure, which is formalized by Blum's axioms.

http://en.wikipedia.org/wiki/Blum_axioms

It seems also that it is possible to generalise Kolmogorov's complexity to take other complexity measures into consideration. See reference below. (Wikipedia's article on Kolmogorov complexity addresses this issue.)

Burgin1990- Generalized kolmogorov complexity and other dual complexity measures Cybernetics and Systems Analysis Volume 26, Number 4, 481-490

Answer 2

The answer for the first question is Yes there is a theory, it's Algorithmic information theory and those are called Elegant Programs (by Gregory Chaitin).

For the second question about "is the program I get the simplest one"?

There is no answer, because it's an uncomputable question, it's not posible to prove that a program is an Elegant program.

I've put an answer to add the mention about elegant programs.

Answer 3

There are different kind of approach to decide what is a simple code and what is not.

But sadly, there are not a automatic way to determine it, for example, Kolmogorov Complexity fail with recursive functions, some recursive functions (logical deep) are simple but the understanding about it is not so simple.

In my experience, our team was working in a system and we found a "simple" procedure in Oracle (no more than 50 lines)... and we tried to understand it, it took 2 months (and several meetings) for fully understand it, not by the complexity of the code but in the logic behind every variable.

I think the way to determine how simple is a code is :"read a code and consider the time used to understand it."

So "The simplest program to solve a problem?" can be divided in:

a) simplicity of the code (clear code) but it is too subjective.

b) overcomplexity of the function, if i have X problem then i must solve DX (Delta X) task to solve it, where DX must trend to X.

For example, if my problem is (one) "to peel an apple" and i must do it in PHP (and language) then

if i am extremely lucky and PHP have the function function_peel_apple() then it is the simplest code ever X=1 DX=1, just call the function and that's it!.

In opposite, if i am not so lucky but exist the function function_peel() and function_get_apple() then X=1 (one problem) and DX=2 (two task).

If, in the worst case, does not exist any function, then i must create one (or more than one) by myself and it add several task prior to solve the problem, now that's is a complex program.