It's well-known that the Kolmogorov complexity is uncomputable, essentially because of the halting problem: you can list all programs of length less than one known to generate a given string, but you don't know how long you need to let them run before disqualifying them. But this strikes me as uninteresting, since you might not want to use a program that would take $10^{1000}$ operations to output your string.
It seems that a simple modification gives a complexity which is not only more reasonable (in terms of data compression) but which is computable: count not just space but time. Say, take a model of computation (a programming language and its semantics, together with rules for determining time of execution) and a constant $k>0$. Then the complexity of a(n input-free) program is the size of the program plus $k$ times its execution time, and the complexity of a finite string is the minimum complexity of a program generating it.
This seems too obvious of an idea to be original. Does this have a name? What results are known? (For example, clearly the complexity is in PSPACE, assuming the model allows a fixed string to be printed in time linear in the length of the string.) Are there references?
