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

<p>For the second question about "is the program I get the simplest one"?  </p>

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

<p>I've put an answer to add the mention about <strong>elegant programs</strong>.</p>

CC BY-SA 3.0
2012-01-19T13:45:50.760Z
2012-01-19T13:45:50.760Z
Hernán Eche
<p>This problem is studied in Algorithmic Information Theory. What you're defining is called Kolmogorov-Chaitin complexity.</p>

<p><a href="http://en.wikipedia.org/wiki/Kolmogorov_complexity" rel="nofollow">http://en.wikipedia.org/wiki/Kolmogorov_complexity</a></p>

<p>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.</p>

<p><a href="http://en.wikipedia.org/wiki/Blum_axioms" rel="nofollow">http://en.wikipedia.org/wiki/Blum_axioms</a></p>

<p>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.)</p>

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

CC BY-SA 3.0
2011-04-17T09:58:28.820Z
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.
Yuning
CC BY-SA 3.0
2011-04-17T10:05:23.023Z
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?
Yuning
CC BY-SA 2.5
2011-04-03T19:37:59.877Z
2011-04-03T19:59:18.850Z
2011-04-03T19:59:18.850Z
Mateus de Oliveira Oliveira
<p>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"?</p>

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

<p>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).</p>

<p>I think the theory should at least define "simple" or "simpler than" relation.</p>

<hr>

<p>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.</p>

<p>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?</p>

<p>Here contains better description of my notion of complexity.</p>

<p>Olaf Sporns (2007) <a href="http://www.scholarpedia.org/article/Complexity">Complexity</a>. <a href="http://www.scholarpedia.org">Scholarpedia</a>, 2(10):1623</p>

CC BY-SA 2.5
2011-04-03T10:34:50.680Z
http://en.wikipedia.org/wiki/Kolmogorov_complexity
Dave Clarke
CC BY-SA 2.5
2011-04-03T11:40:48.927Z
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.
Martin Schwarz
CC BY-SA 2.5
2011-04-03T12:29:35.737Z
@YuNing: What do you mean by "simplest", if not size?
Rob
CC BY-SA 2.5
2011-04-03T14:08:09.930Z
@Rob, I do not have a precise idea for that.
Yuning
CC BY-SA 2.5
2011-04-03T14:16:28.550Z
@Rob, I think programs of non-trival size will show some kind of structure. A better structured/well organized program will feel "simpler" than a badly organized one.
Yuning
CC BY-SA 2.5
2011-04-03T15:20:21.460Z
@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'?
Ross Snider
CC BY-SA 2.5
2011-04-03T15:56:52.200Z
@Yu Ning: as @Ross Snider suggested, Kolmogorov Complexity takes that order into account. I like to think of it as the compressed size of the source (which is an upper bound on KC), the order and patterns should allow better compresion than a badly designedm erratic program.
tobyodavies
CC BY-SA 2.5
2011-04-03T18:16:23.147Z
Something simple to someone might not be simple for some other person. It is difficult to find person independent notion of simplicity. Good question!
Pratik Deoghare
CC BY-SA 2.5
2011-04-03T18:22:06.290Z
Often the 'simplest' way to solve a lot of problems (say NP problems for instance) is to enumerate all the cases until you get your answer. Such procedures are often easy to describe and correspond to small TMs... and yet such an answer is rather unsatisfying... so I think divorcing 'simple' from some measure of 'good' provided by complexity theory is dangerous. Of course you can just start to qualify you statements by saying stuff like "simples algorithm that performs better than O(f(x))".
Artem Kaznatcheev
CC BY-SA 2.5
2011-04-03T20:22:46.873Z
As a programmer, I would like to ask this: in a high level language model (unlimited integer vars,arrays,math ops,boolean ops,if,while,[recursive]functions/subs) can we define a measure for "the most human readable" progam?
Marzio De Biasi
CC BY-SA 2.5
2011-04-03T21:51:46.280Z
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.
Jukka Suomela
CC BY-SA 2.5
2011-04-04T19:04:32.010Z
You may want to look at the following, which looks rooted in Algorithmic Information Theory. Speed Prior, a new simplicity measure:

http://www.idsia.ch/~juergen/speedprior.html
ShyPerson
CC BY-SA 2.5
2011-04-05T00:04:32.880Z
It seems to me you are thinking in the context of high-level programing languages. While Kolmogorov–Chaitin complexity can be defined for any language, it's probably best understood in terms of very simple languages such as universal Turing machines, Brainf*ck, etc. In these languages there is no notion of dependency between different parts of a program. If you want to capture what we informally consider as the complexity of a high-level program, you may define it as the length of its description in a simpler programming language.
Antonio Valerio Miceli-Barone
CC BY-SA 2.5
2011-04-05T06:11:35.367Z
@Ross Snider, it would be better, but I think it is balancing between effort of _description_ and effort of _explanation_, instead of description and _structure_ .
Yuning
<big-picture><kolmogorov-complexity>
Is there a theory to answer "the simplest program to solve a problem"?
Yuning
# Is there a theory to answer "the simplest program to solve a problem"?

(Asked by: username_0 on 2011-04-03)

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](http://www.scholarpedia.org/article/Complexity). [Scholarpedia](http://www.scholarpedia.org), 2(10):1623

**Tags:** big-picture, kolmogorov-complexity

> **Comments:**
> **username_1**: http://en.wikipedia.org/wiki/Kolmogorov_complexity  
> **username_2**: 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.  
> **username_3**: @YuNing: What do you mean by "simplest", if not size?  
> **username_0**: @username_3, I do not have a precise idea for that.  
> **username_0**: @username_3, I think programs of non-trival size will show some kind of structure. A better structured/well organized program will feel "simpler" than a badly organized one.  
> **username_4**: @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'?  
> **username_5**: @Yu Ning: as @username_4 suggested, Kolmogorov Complexity takes that order into account. I like to think of it as the compressed size of the source (which is an upper bound on KC), the order and patterns should allow better compresion than a badly designedm erratic program.  
> **username_6**: Something simple to someone might not be simple for some other person. It is difficult to find person independent notion of simplicity. Good question!  
> **username_7**: Often the 'simplest' way to solve a lot of problems (say NP problems for instance) is to enumerate all the cases until you get your answer. Such procedures are often easy to describe and correspond to small TMs... and yet such an answer is rather unsatisfying... so I think divorcing 'simple' from some measure of 'good' provided by complexity theory is dangerous. Of course you can just start to qualify you statements by saying stuff like "simples algorithm that performs better than O(f(x))".  
> **username_8**: As a programmer, I would like to ask this: in a high level language model (unlimited integer vars,arrays,math ops,boolean ops,if,while,[recursive]functions/subs) can we define a measure for "the most human readable" progam?  
> **username_9**: 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.  
> **username_10**: You may want to look at the following, which looks rooted in Algorithmic Information Theory. Speed Prior, a new simplicity measure:  http://www.idsia.ch/~juergen/speedprior.html  
> **username_11**: It seems to me you are thinking in the context of high-level programing languages. While Kolmogorov–Chaitin complexity can be defined for any language, it's probably best understood in terms of very simple languages such as universal Turing machines, Brainf*ck, etc. In these languages there is no notion of dependency between different parts of a program. If you want to capture what we informally consider as the complexity of a high-level program, you may define it as the length of its description in a simpler programming language.  
> **username_0**: @username_4, it would be better, but I think it is balancing between effort of _description_ and effort of _explanation_, instead of description and _structure_ .  

---

## 2 answers

### Answer by username_13 on 2011-04-03. Score: 16 | Accepted answer

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

> **Comments:**
> **username_0**: As @username_9 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.  
> **username_0**: 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?  

---

### Answer by username_12 on 2012-01-19. Score: 1

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**.


---

