What would be an intuitive notion of time-constructible functions ? Is there a function which is not time-constructible?
In my own words I would say a function is time-constructible when:
- it is computable on a TM and
- it is computed in time which itself calculates.
So, $2^n$ might be time-constructible if there is a TM calculating $2^n$ (for any given n) and the calculation ends in at most $2^n$ time (steps, seconds, some other time measure, etc.).
I'm reading the book CC by Arora and Barak. I got stuck on page 16 where the definition for Time-constructible functions is given, which, in my words says:
f is time-constructible when there is a TM that computes
For me, this is about writing a program (for a TM) that computes a value
f(n) where the calculation itself may not exceed
f(n) time which is the value to be calculated by the TM. So there is some kind of tricky self-reference.
I would like to know where the notion of time and space complexity comes from, i.e. what it is good for, and some counterexample for it - some function that is not time constructible. This would help grasp the concept better, which seems to me to be really fundamental for all the rest (in the book).
I'm having difficulties understanding this concept and its rational, since it is kind of self-referential; it is defining itself by means of its own output. Some examples and counterexamples would be really useful. Thank you.