# Why if for any computable function f(n) that is less than n, then Time Hierarchy Theorem wouldn't hold?

First let's have some definition (you can find these in any complexity's textbook)

Theorem. [Gap Theorem] There is a computable time bound $$t(n)$$ such that DTIME[ $$t(n)$$ ]= DTIME[ $$r(t(n))$$ ] for any computable function $$r$$.

This theorem says that even if you have more time resources, then you cannot do more. We have another theorem that says.

Theorem. [Time Hierarchy Theorem (THT)] if f and g are time-constructible functions and f(n)=o(g(n)), then DTIME[ $$f(n)$$ ] $$\subsetneq$$ DTIME[ $$g(n)$$ ].

It is clear that if $$f$$ and $$g$$ are not time-constructible, then THT wouldn't hold. Time-constructible ensures that we read the whole input in the input tape of the TM.

Question: If $$f$$ and $$g$$ are not time-constructible, why then THT cannot hold? What makes THT cannot hold even if f and g are not time-constructible?

Thanks

• Take a look at the proof of the time hierarchy theorem. Apr 17 at 17:37
• Thank you Yuval. Is it because UTM runs on at most $O(n log n)$ steps? because I took an example such that $f(n)=\log n$ and $g(n)=n$ (Now, we have $f(n)$ is not time-constructible). Now if I run UTM U with input $M$ and $<M>$ in $g(n)$ steps (this is the first step of the simulation in the THT and M is a TM such that $L(M) \in$ DTIME[$g(n)$]), then U will take n log n where $n=|<M>|$ and this is more than $g(n)=n$ steps. Therefore, the simulation will always interrupt and return reject. So we will never have a diagonalization method in this case. Is this true Yuval? Apr 18 at 12:19
• Presumably the proof of the time hierarchy theorem uses time-constructibility somewhere. Apr 18 at 14:02
• I don't understand Yuval! So are you saying that my idea is not true and I should rethink again? Apr 18 at 14:11
• I'm saying that the reason that the time hierarchy theorem requires time-constructibility, is that this assumption is used somewhere in the proof. Apr 18 at 14:12