[proofplan] We diagonalize against every deterministic Turing machine together with every possible constant hidden in an $O(t(n))$ running-time bound. An input is interpreted as an encoding of a machine, a unary time multiplier, and padding; on such an input, the diagonal machine simulates the encoded machine on that same input for the indicated multiple of $t(n)$ steps and then reverses its answer. Time-constructibility supplies a deterministic clock for computing the cutoff, and the unary encoding of the multiplier keeps the total simulation within $O(t(n)^3)$. If a machine decided the constructed language in time $O(t(n))$, choosing a multiplier larger than its hidden constant gives a padded self-reference input on which the machine must disagree with itself. [/proofplan] [step:Fix encodings and define the diagonal inputs] Fix a finite binary encoding of deterministic Turing machines. For a machine $M$, write $\langle M\rangle \in \{0,1\}^*$ for its code. We assume the encoding is effective and prefix-decodable, so there is a deterministic parser which, on input $w \in \{0,1\}^*$, either rejects the parse or returns a triple $(M,a,z)$, where $M$ is a deterministic Turing machine, $a \in \mathbb{N}$ is encoded in unary as $1^a$, and $z \in \{0,1\}^*$ is padding. Concretely, let $D_{\mathrm{in}} \subseteq \{0,1\}^*$ denote the set of strings of the form \begin{align*} w = \langle M\rangle \# 1^a \# z, \end{align*} where $\#$ is a fixed separator symbol encoded over $\{0,1\}$ by a prefix-free convention. For such a string, define $|w|$ to be its binary length, and write $n := |w|$. Since the multiplier is encoded in unary, every valid input $w = \langle M\rangle \# 1^a \# z$ satisfies $a \leq C_{\mathrm{enc}} n$ for a fixed encoding constant $C_{\mathrm{enc}} \geq 1$. Enlarging constants in asymptotic estimates, we may write simply $a \leq C_{\mathrm{enc}} n$ throughout. [/step] [step:Construct the clocked diagonal machine] Let $C_t$ be a deterministic clock machine for $t$. By the standard clock form of a time-constructible function, there is a deterministic Turing machine $C_t$ which, on every input of length $n$, halts after exactly $t(n)$ steps. If the chosen definition instead gives a deterministic machine that writes the binary value of $t(n)$ within $O(t(n))$ steps, fix a constant $K_t \geq 1$ such that this outputting computation takes at most $K_t t(n)$ steps for all sufficiently large $n$. Replace the exact clock by a deterministic clock procedure that runs the outputting machine, reads its binary output as a counter value $T$, and then executes exactly $T$ dummy steps. This clock procedure takes at most $(K_t + 1)t(n)$ steps and lasts at least $t(n)$ steps. In that formulation, the diagonal simulation cutoff is understood to be at least $a t(n)$ and implemented within at most $(K_t + 1)a t(n)$ clock work; in the contradiction step we choose the multiplier $a$ larger than the hidden running-time constant of the alleged decider, and the extra constant $K_t + 1$ affects only the upper running-time bound of $D$. Define the simulation cutoff map $S: D_{\mathrm{in}} \to \mathbb{N}$ by \begin{align*} S(w) := a(w)\,t(|w|). \end{align*} Here $a(w) \in \mathbb{N}$ denotes the unary multiplier in the unique parse $w = \langle M\rangle \# 1^{a(w)} \# z$. Define a deterministic Turing machine $D$ as follows on input $w \in \{0,1\}^*$ of length $n$. If $w \notin D_{\mathrm{in}}$, then $D$ rejects. If $w = \langle M\rangle \# 1^a \# z$, then $D$ implements the cutoff $S(w) = a\,t(n)$ by running $a$ consecutive clock phases. In each phase, $D$ starts a fresh copy of $C_t$ on a fixed dummy input of length $n$ and advances the universal simulation of $M$ on $w$ by one simulated step for each step of that clock, stopping early if $M$ halts. Thus exactly $a\,t(n)$ simulated steps are permitted without needing a stored binary representation of $t(n)$. If the simulation halts and accepts within those $S(w)$ simulated steps, then $D$ rejects. If the simulation halts and rejects within those $S(w)$ simulated steps, then $D$ accepts. If the simulation has not halted after $S(w)$ simulated steps, then $D$ rejects. This defines the language \begin{align*} L_D := \{w \in \{0,1\}^* : D \text{ accepts } w\}. \end{align*} [guided] The diagonal machine must do two jobs at once. First, it must identify which machine it is diagonalizing against. That is the role of the code $\langle M\rangle$. Second, it must defeat not just machines running in at most $t(n)$ steps, but machines running in at most $c\,t(n)$ steps for an arbitrary constant $c > 0$. That is why the input includes the unary integer $a$: later, when a particular alleged decider has running time bounded by $c\,t(n)$, we choose $a > c$. Formally, on input $w \in \{0,1\}^*$ with length $n := |w|$, the machine $D$ first parses $w$. If the parsing fails, $D$ rejects. If the parsing succeeds, then \begin{align*} w = \langle M\rangle \# 1^a \# z \end{align*} for a deterministic Turing machine $M$, an integer $a \in \mathbb{N}$, and padding $z \in \{0,1\}^*$. The machine $D$ then invokes the clock for $t$ on length $n$. Time-constructibility is exactly the hypothesis that lets $D$ enforce a cutoff depending on $t(n)$ by deterministic computation. The simulation cutoff is the value of the already defined map $S: D_{\mathrm{in}} \to \mathbb{N}$ at $w$, namely \begin{align*} S(w) = a\,t(n). \end{align*} If the clock machine is given in the exact-time form, $D$ does not need to write $t(n)$ in binary. It runs $a$ clock phases, each lasting exactly $t(n)$ steps, and advances the simulation of $M$ on $w$ by one simulated step during each clock step. This permits exactly $a\,t(n)$ simulated steps. The machine $D$ simulates $M$ on the identical input $w$ for at most $S(w)$ simulated steps. If $M$ accepts within the cutoff, $D$ rejects; if $M$ rejects within the cutoff, $D$ accepts; and if $M$ does not halt within the cutoff, $D$ rejects. Thus the only time $D$ accepts is when the encoded machine definitely rejects its own diagonal input within the allotted time. This is the diagonal flip: whenever $M$ is given enough simulated time to exhibit its answer on $w$, the machine $D$ returns the opposite answer. [/guided] [/step] [step:Bound the running time of the diagonal machine by $O(t(n)^3)$] Let $n := |w|$. Parsing $w$ takes $O(n)$ time, hence $O(t(n))$ time for all sufficiently large $n$ because $t(n) \geq n$ eventually. Computing the clock value $t(n)$ takes $O(t(n))$ time by time-constructibility. On a valid input $w = \langle M\rangle \# 1^a \# z$, the unary encoding gives \begin{align*} a \leq C_{\mathrm{enc}} n. \end{align*} Since $t(n) \geq n$ for all sufficiently large $n$, the simulation cutoff satisfies \begin{align*} S(w) = a\,t(n) \leq C_{\mathrm{enc}} n\,t(n) \leq C_{\mathrm{enc}} t(n)^2 \end{align*} for all sufficiently large $n$. Use a fixed deterministic universal Turing machine $U$ implemented with the following conservative simulation convention. The code $\langle M\rangle$ contains the finite transition table of $M$. During each simulated step, $U$ scans this encoded table linearly to find the unique transition matching the simulated state and scanned tape symbols, then updates the simulated configuration of $M$ on its work tapes. Therefore there is a constant $C_U > 0$, depending only on the chosen encoding and on $U$, such that one simulated step of $M$ on input $w$ takes at most $C_U n$ steps whenever $|\langle M\rangle| \leq n$ and $|w| = n$. For the valid input $w = \langle M\rangle \# 1^a \# z$, the code length satisfies $|\langle M\rangle| \leq n$. The simulation estimate and the inequality $S(w) \leq C_{\mathrm{enc}}t(n)^2$ give \begin{align*} C_U n S(w) \leq C_U C_{\mathrm{enc}} n t(n)^2. \end{align*} Since $n \leq t(n)$ for all sufficiently large $n$, this implies \begin{align*} C_U n S(w) \leq C_U C_{\mathrm{enc}} t(n)^3. \end{align*} The clock work takes at most $(K_t + 1)a\,t(n)$ steps in the outputting-clock formulation, and exactly $a\,t(n)$ steps in the exact-clock formulation; in either case it is bounded by a constant multiple of $t(n)^2$ because $a \leq C_{\mathrm{enc}}n \leq C_{\mathrm{enc}}t(n)$ for all sufficiently large $n$. Adding the parsing, clock, and simulation costs, the total running time of $D$ is bounded by $O(t(n)^3)$. Hence $L_D$ is decidable in deterministic time $O(t(n)^3)$. [/step] [step:Assume an $O(t(n))$ decider and choose a large enough diagonal multiplier] Suppose, toward a contradiction, that $L_D$ is decidable by a deterministic Turing machine $M_0$ in time $O(t(n))$. Then there exist constants $c > 0$ and $n_0 \in \mathbb{N}$ such that, for every input $x \in \{0,1\}^*$ with $|x| \geq n_0$, the computation of $M_0$ on $x$ halts within \begin{align*} c\,t(|x|) \end{align*} steps. Choose an integer $a \in \mathbb{N}$ with $a > c$. Since padding strings may be chosen with arbitrary length, choose $z \in \{0,1\}^*$ so that the diagonal input \begin{align*} w_0 := \langle M_0\rangle \# 1^a \# z \end{align*} has length $n := |w_0| \geq n_0$ and is in the range where $t(n) \geq n$. For this input, the diagonal cutoff used by $D$ is \begin{align*} S(w_0) = a\,t(n). \end{align*} Since $a > c$, we have \begin{align*} c\,t(n) < a\,t(n) = S(w_0). \end{align*} Therefore the simulation performed by $D$ on input $w_0$ runs long enough to see the actual halting answer of $M_0$ on $w_0$. [guided] We now verify the running-time estimate using only a conservative universal simulation. Let $w \in \{0,1\}^*$ have length $n := |w|$. Parsing costs $O(n)$, and this is $O(t(n))$ for all sufficiently large $n$ because $t(n) \geq n$ eventually. If $w$ is valid, then $w = \langle M\rangle \# 1^a \# z$ and the unary block gives $a \leq C_{\mathrm{enc}}n$. Hence \begin{align*} S(w) = a t(n) \leq C_{\mathrm{enc}} n t(n) \leq C_{\mathrm{enc}} t(n)^2. \end{align*} A conservative universal simulation scans the encoded transition table of $M$ linearly during each simulated step. Since $|\langle M\rangle| \leq n$, one simulated step costs at most $C_U n$ steps for a constant $C_U > 0$ depending only on the fixed encoding and simulator. Thus the simulation of $S(w)$ steps costs at most \begin{align*} C_U n S(w) \leq C_U C_{\mathrm{enc}} n t(n)^2 \leq C_U C_{\mathrm{enc}} t(n)^3. \end{align*} The clock work is smaller than the cubic bound: it is either exactly $a t(n)$ in the exact-clock convention or at most $(K_t+1)a t(n)$ in the outputting-clock convention, and both are $O(t(n)^2)$. Therefore the total work of parsing, clocking, and simulating is $O(t(n)^3)$, so $L_D$ is decidable in deterministic time $O(t(n)^3)$. [/guided] [/step] [step:Derive the diagonal contradiction] Because $M_0$ decides $L_D$, for every input $x \in \{0,1\}^*$, \begin{align*} x \in L_D \iff M_0 \text{ accepts } x. \end{align*} In particular, \begin{align*} w_0 \in L_D \iff M_0 \text{ accepts } w_0. \end{align*} But on input $w_0 = \langle M_0\rangle \# 1^a \# z$, the machine $D$ simulates $M_0$ on $w_0$ for enough steps to observe its halting answer, and then reverses that answer. Hence \begin{align*} D \text{ accepts } w_0 \iff M_0 \text{ rejects } w_0. \end{align*} By definition of $L_D$, the left-hand side is equivalent to $w_0 \in L_D$. Thus \begin{align*} w_0 \in L_D \iff M_0 \text{ rejects } w_0. \end{align*} Combining this with the fact that $M_0$ decides $L_D$ gives \begin{align*} M_0 \text{ accepts } w_0 \iff M_0 \text{ rejects } w_0, \end{align*} which is impossible for a deterministic halting computation. Therefore no deterministic Turing machine decides $L_D$ in time $O(t(n))$. Since the previous step showed that $L_D$ is decidable in time $O(t(n)^3)$, the required language exists. [/step]