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
Is there a theory to answer the simplest program to solve a problem?
big picture;kolmogorov complexity
This problem is studied in Algorithmic Information Theory. What you're defining is called Kolmogorov-Chaitin complexity.http://en.wikipedia.org/wiki/Kolmogorov_complexityAnd 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_axiomsIt 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 measuresCybernetics and Systems Analysis Volume 26, Number 4, 481-490