Example Turing Machine for a time-constructible function

Question

I am currently reading "Computation Complexity: A Modern Approach" by Arora and Barak and have a question about time-constructible functions. In particular, I can't construct a turing machine for a simple function $f(n)=n$ using the definitions in the book.

The authors start by introducing $k$-tape turing machines: 1ドル$ read-only input tape and $k-1$ read/write work tapes with the last one being the output tape. The tapes are one-directional and they are initialized in the leftmost cell via a special start symbol $\triangleright$. The input tape also contains the input $x$ after the $\triangleright$ symbol, in binary notation. All remaining cells contain the blank symbol $\square$. The tape-heads start on the $\triangleright$ symbol.

A TM $M$ computes a function $f$ in $T(n)$-time if for every $x,ドル after $M$ is initialized in start configuration on input $x,ドル using at most $T(|x|)$ steps, $M$ halts with $f(x)$ written on its output tape.

They then define time-constructible functions

A function $T \colon \Bbb N \to \Bbb N$ is time-constructible if $T(n) \geq n$ and there is a TM $M$ that computes the function $x \mapsto \llcorner T(|x|)\lrcorner$ ($\llcorner T(|x|)\lrcorner$ denotes the binary representation of $T(|x|)$) in time $T(n)$.

I have a problem constructing TMs $M$ for the functions $F(n)=n$ and $G(n)=n^2$. Let's say $x = 3,ドル so $|x|=2$. The machine for $F$ will have to halt after $F(|x|)=|x|=2$ steps and output $\llcorner x \lrcorner$. How is this possible if the machine heads start on the $\triangleright$ symbols?

In 2ドル$ steps, the machine can't even read the input, since the first step is wasted by moving right from the $\triangleright$ symbol.

Shouldn't the definition make use of asymptotic notation?

• Raphael: Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you!
• Raphael: "Shouldn't the definition make use of asymptotic notation?" -- why?
• Raphael: (Where you looking for \floor and \ceil?)
• Riyil: @Raphael: If you're talking about $\llcorner T(|x|)\lrcorner,ドル that is the notation that the authors use. By using asymptotic notation the authors could say that a $T(n)$-time TM uses at most $\mathcal{O}(T(n))$ steps, or the time-constructible function $T(n)$ could be computed in time $\mathcal{O}(T(n))$.

Answer 1

I think you're right, we should use asymptotic notation, for the reason you mention, but maybe somebody more knowledeable than me can weigh in if that's wrong. Here are my thoughts: A function $T$ works as a function of the number of bits on the tape, with $|x|=\lfloor\log(x)\rfloor$. Consider the function $T(n)=n$. This function maps $x\mapsto T(|x|) = T(\lfloor\log(x)\rfloor)=\lfloor\log(x)\rfloor$. This means is must count the number of bits on the tape, erase the input, and write the number, but it has only exactly enough time to read the input, and then it must halt. But since $\log(x)<x$ for some $x,ドル this means the machine must, on most inputs, also move back on the tape, at least to the beginning. With a multitape Turing Machine, I can think of a $(3n+\log(n))$-time machine which computes $T(n)=n,ドル so I think it makes more sense to use asymptotic notation.

Note that in order to make a Turing Machine, if you have trouble when $n$ is small because $T$ doesn't grow fast enough for you, you can just hardcode the first billion values into your TM, and run an honest algorithm on the remaining numbers. This is how you overcome the problem of computing, for example, $n\cdot \log(\log(\sqrt{n})),ドル which requires a lot of computation but grows very slowly.

A machine which computes $x\mapsto 2^{|x|}$: read the first 1ドル$ on the tape, then replace all subsequent numbers by 0ドル$ and add one 0ドル$ to the end. And you did it in $n+1$ steps exactly! That is exponentially faster than the available time.

According to this question (link), there is an alternative source of Arora and Barak which does use asymptotic notation and one by Sipser, although it doesn't provide any explicit references. As far as I know, all other definitions (like $\text{TIME}(n)$ and $\text{SPACE}(n)$) are built around asymptotic notation anyway, so it should be perfectly legal to use asymptotic notation here.

• Wei-Cheng Liu: I think $\lfloor \log(x) \rfloor$ should be $\lceil \log(x) \rceil$.
• Wei-Cheng Liu: I don't understand why "since $\log(x)<x$ for some $x,ドル this means the machine must, on most inputs, also move back on the tape, at least to the begining." Could you please explain it to me? Thank you in advance.