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