Adding the requirement of linear time on infinitely many inputs into the class $P$

Question

Is the following problem computable in polynomial time?

Input: $<M_1>$, encoding of a determinstic TM that runs in polynomial time ($L(M_1)\in P$)

Output: $<M_2>$, encoding of a determinstic TM that runs in polynomial time ($L(M_2)\in P$), and satisfies:

• $L(M_1)=L(M_2)$ (they decide the same language)
• $\forall n\exists w\in\{0,1\}^n : \text {Time} (M_2,w)=n$ (there exists an input of any length on which the TM runs in linear time)

Answer 1

[EDIT 2]

No, and in particular $M_2$ does not exist in general.

Consider only TM's (and languages) that do not distinguish between the letters $0$ and $1$. Let's call them monochrome. Thus, membership of a word $w$ in a monochrome language depends only on $|w|$. Now let $L$ be a non-regular monochrome language in P. For example, $L$ can be the set of all words whose length is a square number.

Next, we exploit the fact that we use Turing machines (and not RAMs or whatever) and that the time bound is exactly $n$ (and not $O(n)$). In that time bound, all the TM $M_2$ can do on the witness word $w$ (by which I mean the special input of a given length $n$ for which $M_2$ runs in time $n$) is to read the input once from left to right. If at any step it does not go right, it cannot discern the length of $w$. As $L$ is by nature neither finite nor co-finite, $M_2$ must measure the length exactly.

So, at least on the witness words, $M_2$ acts like a DFA. Then, construct an NFA $A_1$ which simulates $M_2$ as long as $M_2$ only goes right. The NFA $A_2$ is obtained from $A_1$ by replacing all edge labels by $\{0,1\}$. Then $A_2$ recognizes $L$: For any input, $A_2$ behaves just like $A_1$ does for the respective witness word, including acceptance or rejection.

Thus, $L$ is regular, contradicting the choice of $L$.