The proof is by the “diagonalization” method. We assume for the sake of contradiction that TM code \(A\) deciding \(\textbf{Accepts}\) exists. We now describe “diagonalizing TM code” \(D\). In brief: \[D(\langle M \rangle) \text{ runs } A(\langle M, \langle M \rangle\rangle) \text{ and does the opposite}.\] In more details:

• The TM code \(D\) first interprets its input string in \({\{\mathtt{0},\mathtt{1}\}}^*\) as the encoding of a TM \(M\). (Recall that by GUIDO, every possible string input to \(D\) counts as a TM. Garbage strings are interpreted as some default standard TM, say the one that immediately rejects every input.)

• \(D\) then copies its input string over, adding a little punctuation if necessary, thereby arranging for the string \(\langle M, \langle M \rangle \rangle\) to be on its tape. This will be an input for the TM \(A\).

• \(D\) now enters into a subroutine that contains the exact “code” of \(A\), except with \(A\)’s accept/reject states swapped.

Notice that \(D\) is definitely a decider TM: it halts on every input, because \(A\) (by assumption) is a decider and thus halts on every input.

We can now obtain a contradiction by considering the question of whether \(D(\langle D \rangle)\) accepts or not. When \(D\) is given \(\langle D \rangle\) as input, it ends up running \(A(\langle D, \langle D \rangle \rangle)\) and doing the opposite. But by assumption, \(A(\langle D, \langle D \rangle \rangle)\) gives the correct answer to the question, “Does \(D(\langle D \rangle)\) accept?” So we have a contradiction; if \(D(\langle D \rangle)\) accepts then it means that \(D(\langle D \rangle)\) does not accept, and vice versa.

Therefore we conclude that the initial assumption was false; the TM \(A\) deciding \(\textbf{Accepts}\) cannot exist.

We will say what \(L\) is in a roundabout way. We will first describe a decider TM called \(D\). Then we will say, \[L \text{ is whatever language is decided by $D$; \quad that is, } L = \{x : D(x) \text{ accepts}\}.\] (As you will see, the \(L\) we produce might be called something like \(\textbf{Doesn'tBoundedAcceptSelf}_{2^\bullet}\).)

As suggested, the proof is very similar to Turing’s, but using the decider \(B\) for \(\textbf{BoundedAccepts}_{2^\bullet}\). TM algorithm \(D\) takes as input the description of a TM \(M\) and does the following: \[D(\langle M \rangle) \text{ runs } B(\langle M, \langle M \rangle\rangle) \text{ and does the opposite}.\] Let \(L\) be the language decided by \(D\). The algorithm \(D\) basically copies its input string (time: \(O(n^2)\)) and then does \(B\), which as we know takes time \(O(3^n)\). Thus the running time of \(D\) is \(O(3^n)\), so \(L \in \mathsf{TIME}(3^n)\).

To complete the proof, suppose for the sake of contradiction that there is some (standard-alphabet) TM \(M\) deciding \(L\) with running time \(T_M(n) \leq 2^n\). Then for any input \(w\):

• \(M(w)\) gives the same answer as \(D(w)\) (because \(M\) and \(D\) decide the same language, \(L\)).

• Furthermore, \(M(w)\) gives this answer in at most \(2^{|w|}\) steps.

To get a contradiction, we consider the input \(w = \langle M \rangle\):

• \(M(\langle M \rangle) = D(\langle M \rangle)\), because of (i) above.

• \(D(\langle M \rangle) \neq B(\langle M, \langle M \rangle\rangle)\), by definition of \(D\).

• \(B(\langle M, \langle M \rangle\rangle) = M(\langle M \rangle)\) provided \(M(\langle M \rangle)\) runs in at most \(2^{|\langle M \rangle|}\) steps, by definition of “\(B\) decides \(\textbf{BoundedAccepts}_{2^\bullet}\)”.

• \(M(\langle M \rangle)\) does run in at most \(2^{|\langle M \rangle|}\) steps, by (ii) above.

Putting together (a)–(d), we get \(M(\langle M \rangle) \neq M(\langle M \rangle)\), a contradiction.

We just need to prove the second bullet point. Suppose for the sake of contradiction that there is some (standard-alphabet) TM \(M\) deciding \(L\) with running time \(T_M(n) \leq O(1.1^n)\). The idea is that this will always be smaller than \(2^n\) for “large enough” \(n\). Doing the math, \(T_M(n) \leq O(1.1^n)\) means that there exist \(C, n_0 \geq 1\) such that \(T_M(n) \leq C \cdot 1.1^n\) for all \(n \geq n_0\). Let \(n_1\) be large enough so that \(C \leq (\frac{2}{1.1})^{n_1}\). Now setting \(N = \max(n_0,n_1)\), we conclude \[n \geq N \quad\implies\quad T_M(n) \leq (\tfrac{2}{1.1})^{n} \cdot 1.1^n = 2^n.\] Similar to the previous proof, for any input \(w\) we conclude:

• \(M(w)\) gives the same answer as \(D(w)\).

• \(M(w)\) gives this answer in at most \(2^{|w|}\) steps provided \(|w| \geq N\).

Let \(w_0 = \langle M \rangle\). Since \(|w_0|\) might not be at least \(N\), we want to introduce “artificially longer” versions of \(w_0\). For \(i = 1, 2, 3, \dots\), let \(M_i\) denote a TM that consists of taking \(M\) and adding \(i\) extra “useless” states at the end, meaning states that are never transitioned into. (For concreteness, you can assume that such a state \(q_j\) writes back the symbol it reads, moves it head right, and transitions back to \(q_j\). It hardly matters, since no state transitions into \(q_j\).) Let \(w_i = \langle M_i \rangle\). The key points are:

• \(M_i\) behaves identically to \(M\) on every input;

• \(|w_i| = |\langle M_i \rangle| = |\langle M \rangle| + c \cdot i = |w_0| + c \cdot i\) for some fixed constant \(c\).

(The second point here depends a bit on our precise TM encoding format. For the format used in the Bevan universal TM, each extra useless state takes \(c = 12\) extra symbols. Since we’re technically encoding each symbol in Bevan’s alphabet by \(4\) bits, \(c\) should be \(48\).)

Thus the strings \(w_i\) get longer and longer, but they all encode a TM that is “functionally equivalent” to \(M\). Now there is some large enough value for \(i\), say \(i_* = \lceil N/c \rceil\), such that \(|w_{i_*}| \geq N\). Thus item (ii’) above implies that \[\text{$M(w_{i_*})$ takes at most $2^{|w_{i_*}|}$ steps.} \tag{\$}\]

Now we can get a contradiction almost identically to that in D-tier quality Time Hierarchy Theorem, by considering the input \(w_{i_*} = \langle M_{i_*} \rangle\):

• \(M(\langle M_{i_*} \rangle) = D(\langle M_{i_*} \rangle)\), because of (i) above.

• \(D(\langle M_{i_*} \rangle) \neq B(\langle M_{i_*}, \langle M_{i_*} \rangle\rangle)\), by definition of \(D\).

• \(B(\langle M_{i_*}, \langle M_{i_*} \rangle\rangle) = M_{i_*}(\langle M_{i_*} \rangle)\) provided \(M_{i_*}(\langle M_{i_*} \rangle)\) runs in at most \(2^{|\langle M_{i_*} \rangle|}\) steps, by definition of “\(B\) decides \(\textbf{BoundedAccepts}_{2^\bullet}\)”.

• \(M_{i_*}(\langle M_{i_*} \rangle) = M(\langle M_{i_*} \rangle)\), and both computations take the exact same number of steps, because \(M_{i_*}\) is functionally identical to \(M\).

• \(M_{i_*}(\langle M_{i_*} \rangle)\) runs in the same time \(M(\langle M_{i_*} \rangle) = M(w_{i_*})\) does, and this is indeed at most \(2^{|w_{i_*}|} = 2^{|\langle M_{i_*} \rangle|}\) steps, by \((\$)\).

Putting together (a)–(d), we get \(M(\langle M_{i_*} \rangle) \neq M(\langle M_{i_*} \rangle)\), a contradiction.

We mostly just need to repeat the proof of C-tier quality Time Hierarchy Theorem and D-tier quality Time Hierarchy Theorem, but with \(B\) being a decider for \(\textbf{BoundedAccepts}_{f(\bullet)}\) (rather than with the specific \(f(\bullet) = 2^\bullet\) version). Since we are assuming \(f(n)\) is clockable, Theorem (\(\textbf{BoundedAccepts}_{f(\bullet)}\) time complexity) from the previous chapter tells us that \(B\) — and hence \(L\) — is in \(\mathsf{TIME}(O(n^2 + \log f(n)) \cdot f(n))\). For simplicity we can be wasteful and say that \(n^2 + \log f(n) \leq n^2 \cdot \log f(n)\), and therefore we have proven the first bullet point in the theorem, \(L \in \mathsf{TIME}(n^2 \cdot f(n) \cdot \log f(n))\).

We move on to the second bullet point, \(L \not \in \mathsf{TIME}(\frac{f(n)}{\log f(n)})\). We can prove this almost exactly as in the proof of C-tier quality Time Hierarchy Theorem; there we only used that any \(O(1.1^n)\) function is smaller than \(2^n\) for large enough \(n\). In our general case here, we can use that any \(O(\frac{f(n)}{\log f(n)})\) function is smaller than \(f(n)\) for large enough \(n\).

There is one more technical detail. Looking carefully at C-tier quality Time Hierarchy Theorem, we find that we’ve only ruled that there is a standard-alphabet TM \(M\) solving \(L\) in \(O(\tfrac{f(n)}{\log f(n)})\) time, whereas to truly say that \(L \not \in \mathsf{TIME}(\tfrac{f(n)}{\log f(n)})\), we need to rule out an \(M\) solving \(L\) in \(O(\tfrac{f(n)}{\log f(n)})\) time using any (constant-sized) tape alphabet. But this is not hard; we saw in Proposition (Tape alphabet reduction) that an arbitrary-tape-alphabet \(M\) running in time \(O(\tfrac{f(n)}{\log f(n)})\) can be converted to a standard-alphabet \(M'\) deciding the same language and running in time \(O(n^2 + \tfrac{f(n)}{\log f(n)})\). But using our assumption \(n^2 \log n \leq O(f(n))\), we get that \(O(n^2) \leq O(\tfrac{f(n)}{\log f(n)})\), so \(M'\) just has running time \(O(\tfrac{f(n)}{\log f(n)})\). But we ruled out standard-alphabet TMs with this running time.

Consider the language \(L\) constructed in the proof of D-tier quality Time Hierarchy Theorem. We showed that it satisfies \(L \not \in \mathsf{TIME}(1.1^n)\). But this was actually somewhat sloppy; we could have actually showed it is not in \(\mathsf{TIME}(1.9^n)\), or even \(\mathsf{TIME}(\frac{2^n}{n})\).

Recall also from the proof that \(L\) could be named something like \[\textbf{Doesn'tBoundedAcceptSelf}_{2^\bullet};\] more carefully, we can see that \[\begin{aligned} L = \{\langle M \rangle: & M \text{ is a (standard-alphabet) TM such that} \\ & M(\langle M \rangle) \text{ does not accept within } 2^{|\langle M \rangle|} \text{ steps}\}. \end{aligned}\]

Suppose now by way of contradiction that there is a TM \(B\) deciding \(\textbf{BoundedAccepts}_{2^\bullet}\) with running time \(O(1.1^n)\). We will use it to construct a TM \(R\) that solves \(L\) in time \(O(1.21^n)\). This is indeed a contradiction, because as we said at the beginning of this proof, \(L\) is not even in \(\mathsf{TIME}(1.9^n)\).

The algorithm \(R\) is straightforward: On input \(w\) of length \(n\), algorithm \(R\) first interprets \(w = \langle M \rangle\) for some (standard-alphabet) TM \(M\). (Validating the input here surely takes at most \(\operatorname{poly}(n)\) time, much less than \(O(1.21^n)\) time.) Next, \(R\) copies the string \(\langle M \rangle\), forming the input \(x = \langle M, \langle M \rangle\rangle\) for \(B\); again, this takes minimal time, say \(O(n^2)\). More importantly, note that \(|x| \approx 2n\). (Perhaps \(2n + O(1)\) due to punctuation, but probably literally \(2n\) if we dig into our encoding conventions.) Finally, \(R\) performs the code of \(B\) on \(x\), and gives the opposite answer.

Overall, it is clear that \(R\) correctly decides \(L\). Further, its running time is \(\operatorname{poly}(n) + O(1.1^{2n})\). Here \(O(1.1^{2n})\) is the running time of \(B\) on an input of length \(2n\). Finally, \(\operatorname{poly}(n) + O(1.1^{2n}) \leq O(1.21^n)\), as claimed, giving the desired contradiction.