The Primitive Recursive Functions appear quite attractive as a subset of all computable functions. They always terminate, so one can use an enumeration to get a computable upper bound on Kolmogorov complexity. They look like they are rich enough that the upper bound could be low enough to be interesting.