**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](http://en.wikipedia.org/wiki/Rice%27s_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](https://mathoverflow.net/questions/27867/non-existence-of-algorithm-converting-np-algorithm-to-p-algorithm).
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.



Given a polynomial-time algorithm, can we compute an explicit polynomial time bound just from the program?
[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$.


