[Solved]: Machines in P undecidable?

Problem Detail: 

Given a Turing machine $M$, we say that $L(M) \in P$ if the language decided by the machine can be decided by some machine in polynomial time. We say that $M \in P$ if the machine runs in polynomial time. Note that there can be machines that run needlessly long but still decide a language in $P$. By Rice's theorem, we know that

$\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) \in P \mbox{ } \}$ is undecidable. Is it known whether:

$\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }M \in P \mbox{ } \}$ is also undecidable?

Asked By : Nic

Answered By : Yuval Filmus

Here is a paraphrase of the proof in the cstheory answer. We reduce from the halting problem. Suppose that we are given a machine $M$, and we are to decide whether $M$ halts on the empty input. We construct a new machine $M'$ accepting a single input $x$, which operates as follows:

1. Let $n = |x|$.
2. $M'$ runs $M$ for $n$ steps.
3. If $M$ halted within $n$ steps then $M'$ runs a dummy loop taking exponential time $\Omega(2^n)$. Otherwise, $M'$ just halts.

Since Turing machines can be simulated with only polynomial overhead, if $M$ doesn't halt then $M'$ runs in polynomial time. If $M$ halts, then $M'$ takes exponential time. Hence $M$ halts iff $M'$ is not polynomial time.

---

More generally, this shows that even if we know that $M$ runs in time at most $f(n)$ for some superpolynomial time-constructible $f$, then we cannot decide whether $M$ runs in polynomial time.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14215