# The Turing Machine in the proof of Time Hierarchy Theorem

In the proof of the Time Hierarchy Theorem, Arora and Barak writes:

Consider the following Turing Machine $$D$$: “On input $$x$$, run for $$|x|^{1.4}$$ steps the Universal TM $$U$$ of Theorem 1.6 to simulate the execution of $$M_x$$ on $$x$$. If $$M_x$$ outputs an answer in this time, namely, $$M_x(x)\in \{0,1\}$$ then output the opposite answer (i.e., output $$1−M_x(x)$$). Else output $$0$$.” Here $$M_x$$ is the machine represented by the string $$x$$.

What if we give the encoding of $$D$$ as input to $$D$$? Then $$D$$ will accept exactly when $$D$$ will reject. So such a $$D$$ cannot even exist. Am I missing something?

• Arora and Barak are two different people. Oct 6, 2021 at 19:54

There will be no contradiction, since $$D$$ doesn't run in time $$n^{1.4}$$. In fact, what the proof of the time hierarchy theorem shows is that no equivalent Turing machine can run in time $$n^{1.4}$$, precisely because this will result in a contradiction. In other words, the language computed by $$D$$ lies outside of $$\mathrm{DTIME}(n^{1.4})$$. On the other hand, $$D$$ can be computed in time $$O(n^{1.4} \log n)$$. This shows that $$\mathrm{DTIME}(n^{1.4}) \subsetneq \mathrm{DTIME}(O(n^{1.4} \log n)).$$
(Usually $$\mathrm{DTIME}(f(n))$$ is defined as the class of problems which can be solved in time $$O(f(n))$$ rather than $$f(n)$$, the latter being the intended interpretation above. In that case the separation is between $$\mathrm{DTIME}(f(n))$$ and $$\mathrm{DTIME}(n^{1.4} \log n)$$ for any $$f(n) = o(n^{1.4})$$.)
• In the proof in the book, this $D$ was defined to actually prove that $DTIME(n)\subset DTIME(n^2)$. So $D$ indeed lies in $DTIME(n^{1.4})$. Here is the link to the book: Page 84 in google.com/… Oct 6, 2021 at 19:50
• Yes it can. But my question was what would happen when we give the string encoding of $D$ as input to $D$. Oct 6, 2021 at 19:58
• It would output $0$, since $D$ takes more than $n^{1.4}$ time. Oct 6, 2021 at 19:59
• Could you please explain why it would take more than $n^{1.4}$ time? Oct 6, 2021 at 20:15