The Turing Machine in the proof of Time Hierarchy Theorem

Question

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?

Answer 1

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})$.)