# turing machines – A synctactic property of the complexity class P

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…