# Machines in P undecidable?

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?

• By Rice's theorem, you also have that this language is undecidable (non trivial property). – Tpecatte Sep 8 '13 at 17:59
• 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 – sdcvvc Sep 8 '13 at 18:22
• Why can't you use the same diagonalization proof as Rice's theorem ? – Tpecatte Sep 8 '13 at 19:04
• 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. – sdcvvc Sep 8 '13 at 20:47

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.

• 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 ? – sashas Feb 22 '16 at 12:02
• @sasha I don't follow your question. – Yuval Filmus Feb 22 '16 at 15:36
• 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} \}$. – sashas Feb 22 '16 at 16:07
• @sasha I see no particular problem. – Yuval Filmus Feb 22 '16 at 16:09
• If $M$ halts on empty input in $2^n$, $M^{'}$ runs in polynomial time. Am I missing something ? – sashas Feb 22 '16 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.

• 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}$. – Yuval Filmus Sep 8 '13 at 23:19
• @YuvalFilmus: You are correct. I have updated the answer to reflect this. Thanks for pointing this out. – mdxn Sep 8 '13 at 23:45