In Sipser's Introduction to the Theory of Computation, the definition of time-constructible function is,
a funciton $f:\mathbb{N}\to \mathbb{N}$, where $f(n)$ is at least $O(n\lg n)$, is called time constructible if the function that maps the string $1^n$ to the binary representation of $f(n)$ is computable in time $O(f(n))$
In this definition, $f(n)\geq O(n\lg n)$. I found someone discussed why $f(n)\geq O(n\lg n)$ is sensible from the viewpoint of the time hierarchy theorem here. But I want to know, if I remove this restriction, is there any $f(n) = o(n\lg n)$ time constructible?
For $f(n) = n$, I have a proof that $f$ is not time constructible below.
First, as the exercise 7.49 in Sipser's Introduction to the Theory of Computation, if $f(n)=o(n\lg n)$, then any $L\in \mathrm{TIME}(f(n))$ is a regular language. A proof sketch is here.
And then, if $f(n) = n$ is time constructible, I can get the binary representation of $1^n$ in $O(n)$, then I can decide whether $n$ is the power of $2$ by simply checking the binary representation.
But, $L=\{1^{n}\mid n=2^k, k=0,1,...\}$ is not a regular language, so there is a contradiction. This means that $f(n)=n$ is not time constructible.
So I have two questions.
- Is my proof above correct? In fact I did not find any proof of $f(n)=n$ time constructible or not, so I am not sure.
- Is it possible to prove any $f(n)=o(n\lg n)$ is not time constructible?
Thank you for your help.