A function $T: \mathbf{N} \rightarrow \mathbf{N}$ is time constructible if $T(n) \ge n$ and there is a Turing Machine $M$ that computes the function $x \mapsto \lfloor T(|x|) \rfloor$ in time $T(n).$

Here $\lfloor m \rfloor$ denotes the binary representation of $m$ for a natural number $m$.

I understand that $T(n) \ge n$ is required in order to give the $M$ sufficient time to read its input. About the mapping $x \mapsto \lfloor T(|x|) \rfloor$: since $x$ is a natural number, does this mean $|x|$ is the number of digits in the decimal representation of $x$?

As an example, let's forget about the the requirement that $T(n) \ge n$. Suppose $T(n) = \log_2 n$. Then, for example, $T(2^{100}) = 100$, but what is $T(|2^{100}|)$ in this case?


1 Answer 1


$|x|$ here means the length of the string $x$ over an alphabet $\Sigma$. Note that $x$ does not need to be a natural number.

So, $|2^{100}|$ is $100$ (but do remember that you MUST understand that you are encoding the natural number $2^{100}$ into string over finite alphabet) if we want to encode a natural number in binary. Therefore, $T(|2^{100}|) = T(100) = \log_2100$.

It would be type-safer to write $|\lfloor{2^{100}}\rfloor|$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.