**Question.** Given a Turing-machine program $e$, which
is guaranteed to run in polynomial time, can we computably
find such a polynomial?

In other words, is there a computable function $e\mapsto p_e$, such that whenever $e$ is a Turing-machine program that runs in polynomial time, then $p_e$ is such a polynomial time bound? That is, $p_e$ is a polynomial over the integers in one variable and program $e$ on every input $n$ runs in time at most $p_e(|n|)$, where $|n|$ is the length of the input $n$.

(Note that I impose no requirement on $p_e$ when $e$ is not a polynomial-time program, and I am not asking whether the function $e\mapsto p_e$ is polynomial-time computable, but rather, just whether it is computable at all.)

In the field of complexity theory, it is common to treat polynomial-time algorithms as coming equipped with an explicit polynomial clock, that counts steps during the computation and forces a halt when expired. This convention allows for certain conveniences in the theory. In the field of computability theory, however, one does not usually assume that a polynomial-time algorithm comes equipped with such a counter. My question is whether we can computably produce such a counter just from the Turing machine program.

*I expect a negative answer.* I think there is no such
computable function $e\mapsto p_e$, and the question is
really about how we are to prove this. But I don't know...

Of course, given a program $e$, we can get finitely many sample points for a lower bound on the polynomial, but this doesn't seem helpful. Furthermore, it seems that the lesson of Rice's Theorem is that we cannot expect to compute nontrivial information by actually looking at the program itself, and I take this as evidence against an affirmative answer. At the same time, Rice's theorem does not directly apply, since the polynomial $p_e$ is not dependent on the set or function that $e$ computes, but rather on the way that it computes it. So I'm not sure.

Finally, let me mention that this question is related to and inspired by this recent interesting MO question about the impossibility of converting NP algorithms to P algorithms. Several of the proposed answers there hinged critically on whether the polynomial-time counter was part of the input or not. In particular, an affirmative answer to the present question leads to a solution of that question by those answers. My expectation, however, is for a negative answer here and an answer there ruling out a computable transformation.

1more comment