Applications
Time-constructible functions are used in complexity theory results such as the time hierarchy theorem. They are important because the time hierarchy theorem relies on Turing machines that must determine in O(f(n)) time whether an algorithm has taken more than f(n) steps. This is, of course, impossible without being able to calculate f(n) in that time. Such results are typically true for all natural functions f but not necessarily true for artificially constructed f. To formulate them precisely, it is necessary to have a precise definition for a natural function f for which the theorem is true. Time-constructible functions are often used to provide such definition.
Space-constructible functions are used similarly, for example in the space hierarchy theorem.
This article incorporates material from constructible on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.
Read more about this topic: Constructible Function