In these lecture notes the authors mentions that **P** is a syntactic complexity class, as we can find a decidable set of encodings for all polynomial time Turing machines. Of course, given a deterministic Turing machine $M$ and a number $k$, we can construct a Turing machine that simulates $M$ for $|x|^k$ steps on input $x$, and, if $M$ halts in these number of steps, returns the same answer as $M$.

Now, every language in **P** is represented by such a Turing machine, and so, by encoding these Turing machines together with $k$ in a reasonable way, we have a decidable language representing **P**.

Then, the author defines

$$

L = { langle M, x rangle mid mbox{$M$ is a polynomial-time Turing machine which accepts $x in {0,1}^*$} },

$$

and then claims that $L$ is in **P**. His argument is that we can first check that we have a valid encoding of $M$ and then *run $M$ on input $x$*. However, if I assume I have a Turing machine to decide $L$ in time $O(n^k)$ and $M$ is a Turing machine accepting a language in time $n^{k+1}$, then how can the original Turing machine run $M$ on inputs of length that need strictly more time on $M$ than the machine is allowed to run? I somehow think this “diagonalization” argument shows that $L$ could not be in **P**?

So, what am I missing? I tried to describe as precisely as possible how I understood the claims made, maybe I have understood something wrong…