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.
Best Answer
[Edit: A bug in the original proof has been fixed, thanks to a comment by Francois Dorais.]
The answer is no. This kind of thing can be proved by what I call a "gas tank" argument. First enumerate all Turing machines in some manner $N_1, N_2, N_3, \ldots$ Then construct a sequence of Turing machines $M_1, M_2, M_3, \ldots$ as follows. On an input of length $n$, $M_i$ simulates $N_i$ (on empty input) for up to $n$ steps. If $N_i$ does not halt within that time, then $M_i$ halts immediately after the $n$th step. However, if $N_i$ halts within the first $n$ steps, then $M_i$ "runs out of gas" and starts behaving erratically, which in this context means (say) that it continues running for $n^e$ steps before halting where $e$ is the number of steps that $N_i$ took to halt.
Now if we had a program $P$ that could compute a polynomial upper bound on any polytime machine, then we could determine whether $N_i$ halts by calling $P$ on $M_i$, reading off the exponent $e$, and simulating $N_i$ for (at most) $e$ steps. If $N_i$ doesn't halt by then, then we know it will never halt.
Of course this proof technique is very general; for example, $M_i$ can be made to simulate any fixed $M$ as long as it has gas but then do something else when it runs out of gas, proving that it will be undecidable whether an arbitrary given machine behaves like $M$.