10
$\begingroup$

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

$\endgroup$
14
  • 12
    $\begingroup$ en.wikipedia.org/wiki/Kolmogorov_complexity $\endgroup$ Apr 3, 2011 at 10:34
  • 4
    $\begingroup$ You may be interested in Bennett's concept of Logical Depth. Li and Vitanyi's have devoted chapter 7.7 in their book on Kolmogorov Complexity to it. $\endgroup$ Apr 3, 2011 at 11:40
  • 2
    $\begingroup$ @YuNing: What do you mean by "simplest", if not size? $\endgroup$
    – Rob
    Apr 3, 2011 at 12:29
  • 1
    $\begingroup$ @Yu Ning: How about, rather than the simplest being the smallest program to produce an output, it is the Turing machine with the best Minimum Description Length - so that there is a balance between 'smallness' and 'structure'? $\endgroup$ Apr 3, 2011 at 15:20
  • 3
    $\begingroup$ I think the question is a bit ill-defined. Also note that there are algorithms that are very simple, but it is difficult to prove that they are correct. And there are algorithms that are simple and clearly correct, but it is difficult to prove that they are fast. $\endgroup$ Apr 3, 2011 at 21:51

3 Answers 3

16
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ As @Jukka Suomela says, the question is a bit ill-defined. Thus I wonder I can hardly get a complete answer for the question. However, since this answer is quite informative, and does hit an important part of the question, I still tag it as the answer. $\endgroup$
    – Yuning
    Apr 17, 2011 at 9:58
  • $\begingroup$ By the way, can you point me further on the application of the topic, specifically if one has a formal specification of a program, can she find the smallest size from the specification? $\endgroup$
    – Yuning
    Apr 17, 2011 at 10:05
1
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$

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.