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?

  • 1
    $\begingroup$ By Rice's theorem, you also have that this language is undecidable (non trivial property). $\endgroup$
    – Tpecatte
    Commented Sep 8, 2013 at 17:59
  • 4
    $\begingroup$ Timot: No, Rice's theorem does not apply to the second language, because whether $M \in P$ is not a property of $L(M)$. OP: You can use the answer given in cstheory.stackexchange.com/questions/5004 $\endgroup$
    – sdcvvc
    Commented Sep 8, 2013 at 18:22
  • $\begingroup$ Why can't you use the same diagonalization proof as Rice's theorem ? $\endgroup$
    – Tpecatte
    Commented Sep 8, 2013 at 19:04
  • $\begingroup$ Timot: I think the proof cannot be reused since a non-P machine might decide a P language. The underlying idea is similar but IMO not the same. $\endgroup$
    – sdcvvc
    Commented Sep 8, 2013 at 20:47

2 Answers 2


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.

  • $\begingroup$ I have a doubt. If M run in halts in $O(2^n)$ then $M^{'}$ runs in polynomial time although $M^{'}$ halts. Am I missing something ? $\endgroup$ Commented Feb 22, 2016 at 12:02
  • $\begingroup$ @sasha I don't follow your question. $\endgroup$ Commented Feb 22, 2016 at 15:36
  • $\begingroup$ I am having trouble seeing if the reduction above also works for $L= \{ <M> \; | \; \text{M runs in P(n) steps where P(n) is some fixed polynomial} \}$. $\endgroup$ Commented Feb 22, 2016 at 16:07
  • $\begingroup$ @sasha I see no particular problem. $\endgroup$ Commented Feb 22, 2016 at 16:09
  • $\begingroup$ If $M$ halts on empty input in $2^n$, $M^{'}$ runs in polynomial time. Am I missing something ? $\endgroup$ Commented Feb 22, 2016 at 16:22

The way your second language is written is not exactly well formed in regards to normal standards. $P$ is a set of languages and not a set of machines. Based on what you said in the rest of your question, I assume that you are trying to make the distinction between machines that run in at most polynomial time and those which happen solve a problem in $P$. Perhaps this would be a better way to write it as:

$A=\left \{ \left \langle M \right \rangle | (\exists k \forall x) M(x) \text{ halts in } O \left ( |x|^{k}\right ) \text{ time} \right \}$

$O$ can be replaced with $\Theta$ if you want to exclude weaker machines such as log-time TMs.

Note that: $A\subset\{\langle M \rangle|L(M) \in P \}$

As observed by sdcvvc, Rice's theorem does not immediately apply and suffice here since the "non-trivial" property used has to be a property of $L(M)$. A time bound on a machine is not a property of the language, but rather is a property of that machine.

An answer for a predetermined $k$ was discussed the cstheory question question referred to in the comments. The choice of that constant was the key to proving the undecidability. In our language, we include any $k\in\mathbb{N}$ and therefore do not have a maximal $k$ to work with.

I have not had time to spend to sufficiently investigate, but I imagine that it would not be unreasonable to extend their results to any $k>2$ via straight forward induction.

A recent paper written by David Gajser, who was motivated by that the cstheory post, answers a more generalized version of this question:

Let $HALT_{T(n)} = \{ \langle M\rangle|\forall x M(x) \text{ halts in at most } T(n=|x|) \text{ time}\}$

For single tape Turing Machines: $HALT_{T(n)}$ is undecidable if $T(n)= \Omega(nlog(n))$

For multiple tape Turing Machines: $HALT_{T(n)}$ is decidable iff $T(n) \leq k+1$ for some $k\in \mathbb{N}$

He extends these undecidability results to classes with arbitrarily large constants (such as $P$). According to him, the answer to your question is that the language ($A$) is undecidable.

  • 1
    $\begingroup$ Your quantifiers appear in the wrong order: it should be $\exists k,C \forall x M(x) \text{ halts after at most $C|x|^k$ steps}$. $\endgroup$ Commented Sep 8, 2013 at 23:19
  • $\begingroup$ @YuvalFilmus: You are correct. I have updated the answer to reflect this. Thanks for pointing this out. $\endgroup$
    – mdxn
    Commented Sep 8, 2013 at 23:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.