See "Logical Depth" as defined by Charles Bennett: http://researcher.ibm.com/researcher/files/us-bennetc/UTMX.p... as well as Chapter 7, "Resource-Bounded Complexity", from "An introduction to Kolmogorov complexity and its applications".