<p>Yes you can build a machine that takes time DTIME($n^{i+1}$)-DTIME($n^i$) where $i$ is the number of steps taken by a specific Turing machine to halt on blank tape. Easy to construct and similar constructions hold for just about any non-trivial aspect of P. Tells us little about whether P v NP is undecidable: No problem proving P $\neq$ EXP despite the same issues. </p>

CC BY-SA 3.0
2011-06-20T20:15:30.683Z
Yes ... that trick is the essence of Emanuele Viola's and Juris Harmanis' proofs of P's runtime undecidability (for example).  On the other hand, it is trivially the case that the Turing machines that are constructed by this trick all recognize languages L that are *also* recognized by Turing machines in P whose runtimes *are* decidable.  This is why Q1 is phrased (carefully!) as a question about languages rather than about Turing machines ... precisely in order to *exclude* the Hartmanis/Viola construction ... without obstructing (per your comment) the existing proofs that P \ne EXP.
John Sidles
CC BY-SA 3.0
2011-06-20T20:39:11.203Z
... and just to mention, those language L that are recognized *solely* by Turing machines whose runtime exponents were undecidable, are interesting languages from a complexity-theoretic (and cryptographic) point-of-view ... they seemingly exist in a Godel-esque "gray region" between algorithmically compressible (but by definition not verifiably so) and incompressible (and yet by definition not in that class either).
John Sidles
CC BY-SA 3.0
2011-06-20T19:54:03.673Z
2011-06-20T19:54:03.673Z
Lance Fortnow
<p>For question 1 the answer is no. Let $L$ a language in $P$ and let $M$ be any polynomial time Turing machine recognizing $L$ (whose runtime is assumed to be undecidable). For each $k \in \mathbb{N}$ let $M_k$ be the Turing machine that on input $x$ of length $n$ first loops for $n^k$ steps then runs $M$ on $x$ for $n^k + k$ steps and accepts if $M$ accepts $x$ (within those $n^k + k$ steps) and rejects otherwise. The runtime of $M_k$ is $\Theta(n^k)$ for each $k$.</p>

<p>Since $M$ runs in polynomial time there is some $k&#39; \in \mathbb{N}$ such that $M$ runs in $O(n^{k&#39;})$ (even if we don't know what $k&#39;$ is) and hence for all $k$ large enough $M_k$ recognizes $L$ and has a decidable runtime.</p>

<p><strong>EDIT</strong></p>

<p>I think the following answer is more in spirit of what the original poster had intended with question 1. </p>

<p><strong>Theorem:</strong> There exists a language $L \in P$ such that if $N$ is any Turing Machine which decides $L$ then at least one of the following is true:</p>

<p>1) There does not exist a proof that $N$ accepts $L$, or</p>

<p>2) There does not exist a proof that $N$ halts in $f(n)$ steps (for any function $f(n)$).</p>

<p><strong>Proof Sketch:</strong>
Let $M$ be a Turing Machine that does not halt on the blank tape and for which there does not exist a proof that $M$ does not halt on the blank tape (Independence results in Computer Science by Hartmanis and Hopcroft shows such an $M$ can be effectively found).</p>

<p>Let $L = \{ n : \exists n&#39; \geq n \mbox{ s.t. } M \mbox{ halts in } n&#39; \mbox{ steps when run blank tape}\}$. </p>

<p>Since $M$ does not halt, $L$ is in fact the empty language but there is no proof of that (as that would prove that $M$ does not halt).</p>

<p>Let $N$ be any Turing Machine. If there exists both a proof that $N$ decides $L$ and a proof that $N$ runs in $f(n)$ steps then the execution of $N$ when run on input $1$ provides either a proof that $M$ halts (i.e., if $N$ accepts) or that $M$ does not halt (i.e., if $N$ rejects). Thus, if $N$ provably decides $L$ then $N$'s runtime is not decidable and vice versa.</p>

CC BY-SA 3.0
2011-06-20T22:10:22.653Z
Travis does answer the rephrased question, but this is a strange situation where there is a provable exponent but only for machines you cannot prove solves the problem.
Lance Fortnow
CC BY-SA 3.0
2011-06-21T01:45:19.163Z
This is a nice answer to Q1 ... and I completely agree with Lance that this algorithm is a very strange member of class P.  Part of the motivation of the question was to capture the intuition (via definitions that are nice for theorem-proving) that the algorithms in P that we "care about" (in some sense) are the algorithms whose performance we can "verify" (in some sense) ... this example utterly defeats that purpose!  Nice answer! :)
John Sidles
CC BY-SA 3.0
2011-06-21T07:18:14.773Z
This fine comment (which I am still thinking about) called to mind Felix Klein's remark "A concept which occurs with more or less precision in the naive perception of space, which we must add as a supplement to our system of geometry, is the *notion of an (arbitrary) curve*.  Every person believes that he knows what a curve is until he has learned so much mathematics that the countless possible abnormalities confuse them."  The point is that to make progress on P versus NP, perhaps a key step is to refine the definition of P to exclude "countless possible abnormalities."
John Sidles
CC BY-SA 3.0
2011-06-22T21:09:11.760Z
Your answer is very interesting. However, predicate 1 might be more accurately described as 'There does not exist a proof that $N$ accepts $L$ starting from the definition below.', since I can easily construct a TM deciding $L$ (which is the empty language), and prove it always halts and decides the empty language. I learned something nice again, and I'm going to check up on that reference you mentioned :D
Alex ten Brink
CC BY-SA 3.0
2011-06-23T13:27:55.060Z
Travis' edit of his already-good answer provides even *more* to think about. Since this process will take awhile (for me), I would like to express my appreciation and thanks now (and  technical remarks later) to both both Travis (Service) and Alex (ten Brink).  Though they are students, their comments (IMHO) have been mature and interesting. It's well-known that Alan Turing conceived his "On Computable Numbers, with an Application to the *Entscheidungsproblem*" between his 21st and 23rd years; thus students have attacked similar problems with success ... we may hope the same for Alex & Travis.
John Sidles
CC BY-SA 3.0
2011-06-20T21:08:49.053Z
2011-06-22T20:30:46.333Z
2011-06-22T20:30:46.333Z
Travis Service
<p>After thinking more on the subject, I think I found a (possible) answer for your <strong>Q4</strong>.</p>

<blockquote>
  <ul>
  <li><b>Q4:</b> What other attributes of $P$ (besides runtime exponents) are presently known to be undecidable? For what attributes of $P$ is this question open?</li>
  </ul>
</blockquote>

<p>I proved a variation on <a href="http://en.wikipedia.org/wiki/Rice%27s_theorem" rel="nofollow">Rice's theorem</a> that answers your question for most properties. I'll try to explain myself clearer this time (Travis Service's answer was much clearer and more general than my previous answer).</p>

<blockquote>
  <p><strong>Theorem:</strong> For any property holding on some nonempty set of decidable infinite languages (but on no finite languages), it is undecidable whether a given Turing Machine $E$ decides a language with that property, when promised that $E$ always halts in $O(f(n))$ time, where $f(n)=\Omega(n \log n)$ and $f(n)=\Omega(g(n))$, where $g(n)$ is the running time for some Turing Machine deciding some language with that property.</p>
</blockquote>

<p>Recall that a Turing Machine (TM from now on) decides a language if it accepts all strings in the language and rejects all strings outside the language. Note that we can take $f(n)$ to be something other than a polynomial, so the theorem is more general than just $P$.</p>

<p>We formalise the notion of a 'property' as some freely selectable set of languages $S$ 'with that property'. Deciding whether a language has the property is then equivalent to deciding whether the language is a member of $S$. Just like in Rice's theorem, we investigate if we can decide whether the language decided by the input TM has the specified property, and so is in $S$. Note that we require $S \subseteq R$, ie, that $S$ contains only decidable languages.</p>

<p>Please note that we are talking about properties of <em>languages</em>, not of TMs. Your question about runtime exponents is not a special case of this theorem. Properties of, say, $P$, studyable by taking $S \subseteq P$, may interest you more than properties of TMs running in polynomial time. You can do all sorts of cruel stuff to a TM, while retaining its correctness and running time, but you can't do the same to languages.</p>

<p>The requirement that all languages in $S$ have to be infinite is a technicality needed for the proof, but since all finite languages are decidable in constant time and are therefore usually uninteresting, I don't think it's a major one. I expect the generalised version that also allows finite languages to be true as well.</p>

<p><strong>Proof of the theorem</strong>. Assume we are given some TM $P(E)$ with a TM $E$ as parameter, such that $P$ always halts and accepts iff $E$ decides some language in $S$, and where $E$ is promised to always halt with running times as above. Let $(A, i)$ be an instance for the Halting Problem, ie, $A$ is a TM and $i$ is an input for $A$, and we now want to decide whether $A$ halts on $i$.</p>

<p>Since we assumed $S$ was nonempty, we have some $s \in S$. Since $S$ contains only decidable languages, there exists some TM $C$ deciding $s$. In particular, we choose the $C$ with running time $g(n)$ as assumed in the theorem. We now consider the following TM:</p>

<pre><code>function H(x)
h := simulate A on i for |X| steps and return whether it halted
if h == 'halted' then
    reject
else
    if C(x) accepts then
        accept
    else
        reject
    fi
fi
</code></pre>

<p>It is easily seen that the running time of this TM meets the requirements for the theorem, since TMs can be simulated in $O(n \log n)$ time.</p>

<p>We claim that $P(H)$ returns <em>no</em> iff $A$ halts on $i$. Assume $A$ halts on $i$ after $t$ steps. $H$ therefore rejects any $X$ with $|X| \geq t$. We therefore decide at most a finite language, and hence $H$ decides no language in $S$ and $P(H)$ will therefore return <em>no</em>.</p>

<p>Now assume $A$ does not halt on $i$. Then the variable <em>halt</em> will never get the value 'halted', so we decide the same language as $C$, which is exactly $s \in S$, so $P(H)$ will return true. This proves that $P(H)$ can solve the Halting Problem, which in turn proves the theorem.</p>

CC BY-SA 3.0
2011-06-22T10:35:52.343Z
This is a very powerful and flexible argument, and it will take awhile for me to grasp it ... there's a saying among farmers in the central USA "I feel like a pig being shown a wristwatch!" It appears (by your argument) that P is richly endowed with undecidable attributes; what I am having trouble grasping is whether the languages L recognized by P similarly are richly endowed with undecidable attributes ... the exercise of constructing concrete example languages having natural undecidable attributes is particularly frustrating (for me).  Thank you for an excellent, thought-provoking answer.
John Sidles
CC BY-SA 3.0
2011-06-22T12:17:53.130Z
I think you believe $P$ to be the set of TMs running in polynomial time. This is not the definition: $P$ is the set of *languages* decidable by some TM running in polynomial time.
Alex ten Brink
CC BY-SA 3.0
2011-06-22T15:34:56.137Z
Alex, I definitely confess to being confused ... but not about that!  What I would like to construct, or (less desirably) prove the existence/nonexistence of, would be (for example) a language L in P having the property that every Turing machine that accepts L either is *not* verifiably in P or does *not* verifiably accept L.  These languages L would belong to P   "oracularly" ... the possibility that P includes purely oracular languages is confusing to me ... especially since it is at all not obvious (to me) how such purely oracular languages could ever be concretely sampled and exhibited.
John Sidles
CC BY-SA 3.0
2011-06-22T17:09:48.800Z
Oh yeah ... and to ask the converse (also confusing) question ... for a given language L in NP that possibly is accepted solely by *oracular* Turing machines ... by what proof method could we possibly establish that L is not recognized by any of P's *oracular* Turing machines ... and thus separate P from NP?  Or suppose that we did prove the existence of a language L in NP not recognized by any Turing machine in P ... with the restriction that L was purely oracular ... and we could not exhibit that language ... should we be satisfied that P != NP?  These questions are confusing!
John Sidles
CC BY-SA 3.0
2011-06-21T19:51:10.323Z
2011-06-22T12:28:06.930Z
2011-06-22T12:28:06.930Z
Alex ten Brink
<p>I can answer your <strong>Q1</strong> in the negative, thereby also answering <strong>Q2</strong> and <strong>Q3</strong> in the negative. I'm not sure about <strong>Q4</strong> or <strong>Q5</strong> though.</p>

<blockquote>
  <ul>
  <li><strong>Q1:</strong> Do there exist languages $L$ that are recognized <strong>solely</strong> by those Turing machines in $P$ whose <a href="https://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no/5006#5006">runtime exponents are undecidable</a>?</li>
  </ul>
</blockquote>

<p>It seems you misunderstood exactly what Emanuele Viola proved in <a href="https://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no/5006#5006">his brilliant proof</a> you linked. He showed that there is no <em>single</em> Turing Machine $M$ capable of computing the runtime exponent for <em>any</em> Turing Machine $T$ presented to $M$, even under the promise that $T$ runs in polynomial time.</p>

<p>However, for any given Turing Machine $T$ running in polynomial time, there exists some $k$ such that $T$ has a running time of $O(n^k)$, and hence the Turing Machine $M$ returning $k$ (and nothing more) is able to 'tell' the running time exponent of $T$, even without having to look at $T$! Hence, <em>M</em> decides (in constant time even) what $k$ is <em>for this given Turing Machine</em> $T$. We may not know which Turing Machine decides it, but we know one exists.</p>

<p>Coming back to your question, if we are given a language $L$ in $P$, then there is some Turing Machine $T$ running in $O(n^k)$ for some $k$ that decides $L$, and hence there is the Turing Machine $M$ returning $k$ that decides the runtime exponent for $T$. This answers your question in the negative.</p>

<p>You might instead wonder about a different problem for a given language $L$ in $P$: given Turing Machine $T$ promised to run in polynomial time and promised to decide $L$, is it decidable to find the runtime exponent of $T$?</p>

<p>Unfortunately, this is also undecidable. Suppose we are given a language $L$ in $P$ and a TM (Turing Machine) $M$ capable of deciding for a given TM $T$ promised to run in polynomial time and promised to decide $L$, what the runtime exponent of $T$ is. We can prove this to be undecidable in a very similar way to what Emanuele Viola did: we use the exact TM he defined, and change it slightly: we now want this TM to decide $L$.</p>

<p>Since $L$ is in $P$, there is some TM deciding $L$ in $O(n^k)$ time. Our new TM $M$ first starts exactly as in Emanuele Viola's proof, running the (Halting Problem) TM for $n$ steps. It then loops either for $n^{k+1}$ steps or $n^{k+2}$ steps similarly to Emanuele Viola's TM. Finally, it solves $L$ on the given input and returns the answer.</p>

<p>$M$ is in $P$, decides $L$, and if we know the runtime exponent, we can decide the Halting Problem, so the above problem is also undecidable (for any language $L$). Note that we do not need to know $k$, we don't actually have to construct $M$, all we have to do is know it exists!</p>

<p>This kind of thinking about undecidability is quite common apparently, I remember a (blog?) post about a very similar issue: the question was "is it decidable whether Pi has a 'last zero'", so whether Pi stops having zeroes in its decimal representation if you go down far enough that representation. We currently don't know whether this is the case. We might not even be able to prove it, ever, or it might even be independent from our axiom systems (and thereby unprovable). But, since the answer is either true or false, a TM returning true and a TM returning false decide the issue either case and therefore the problem is decidable.</p>

<p>I'll see if I can find that post on the internet somewhere.</p>

<p>Edit:</p>

<p>I found it on <a href="https://mathoverflow.net/questions/48014/can-a-problem-be-simultaneously-polynomial-time-and-undecidable/48031#48031">Mathoverflow</a>.</p>

CC BY-SA 3.0
2011-06-21T07:34:57.740Z
your comment and Travis Service' account both are excellent.  It appears that in **Q1** the phrase "undecidable" is *not* synonymous with "not verifiably decidable" ... and it is not at all clear (to me) which definition (a) leads to the best theorems and (b) best captures our intuition of the class P.  Remarks on this question are welcome.
John Sidles
CC BY-SA 3.0
2011-06-28T13:04:26.353Z
Thank you Alex for the link (to the MOF question "Can a problem be simultaneously polynomial time and undecidable?") ... I have edited the main post to include that link.
John Sidles
CC BY-SA 3.0
2011-06-20T22:15:34.083Z
2011-06-27T17:33:14.403Z
2017-04-13T12:57:54.777Z
Alex ten Brink
<p>Five linked questions are asked, and a single integrated answer is hoped-for:</p>

<blockquote>
  <ul>
  <li><b>Q1:</b> Do there exist languages $L$ that are recognized <strong>solely</strong> by those Turing machines in&nbsp;$P$ whose <a href="https://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no/5006#5006">runtime exponents are undecidable</a>? </li>
  <li><b>Q2:</b> Can examples of these Turing machines be finitely constructed? </li>
  <li><b>Q3:</b> Can these Turing machines be concretely instantiated? (<i>e.g.</i>, by oracles that "guess" them rather than finitely construct them).</li>
  <li><b>Q4:</b> What other attributes of <em>P</em> (besides runtime exponents) are presently known to be undecidable? For what attributes of $P$ is this question open?</li>
  <li><b>Q5:</b> Do the undecidable attributes of $P$ pose an obstruction to <a href="http://www.blogger.com/comment.g?blogID=3722233&amp;postID=5334459752981812402" rel="nofollow noreferrer">the decidability of $P \ne NP$</a>?</li>
  </ul>
</blockquote>

<p>Note carefully the word "solely" in <strong>Q1</strong> (which excludes Lance Fortnow's suggested answer).</p>

<hr>

<p><strong>Conclusions and Conversion to Community Wiki</strong></p>

<ul>
<li><p>The question asked, "Do the undecidable attributes of P pose an obstruction to deciding P versus NP?", is open and believed to be difficult, as are numerous specific questions (like&nbsp;Q1&ndash;4 above) that are naturally associated to it.</p></li>
<li><p>Juris Hartmanis' 1978 monograph <em>Feasible Computations and Provable Complexity Properties</em> provides a good entr&eacute; into the literature and (apparently) there has been no review published since Hartmanis'.</p></li>
<li><p>This class of questions is sufficiently unexplored that the challenge of finding rigorous proofs is intimately admixed with the challenge of choosing good starting definitions. </p></li>
<li><p>The thoughtful remarks and insightful proof sketches provided by Travis Service and Alex ten Brink are acknowledged and appreciated.</p></li>
</ul>

<p>Because the question is open, and because it is being discussed on multiple mathematical weblog threads (<a href="http://blog.computationalcomplexity.org/2011/06/i-am-conducing-new-poll-on-p-vs-np.html" rel="nofollow noreferrer">1</a>,<a href="http://rjlipton.wordpress.com/2011/06/24/polls-and-predictions-and-pnp/" rel="nofollow noreferrer">2</a>,<a href="http://www.scottaaronson.com/blog/?p=686" rel="nofollow noreferrer">3</a>,<a href="http://www.scottaaronson.com/blog/?p=690" rel="nofollow noreferrer">4</a>,<a href="http://www.scottaaronson.com/blog/?p=697" rel="nofollow noreferrer">5</a>,<a href="http://rjlipton.wordpress.com/2011/07/04/getting-on-base-with-pnp/" rel="nofollow noreferrer">6</a>), this question has been flagged for conversion to Community Wiki.</p>

<hr>

<p><strong>Update II and Summary</strong></p>

<p>I have become aware that Juris Harmanis’ 1978 monograph <a href="http://books.google.com/books?id=DTMrTZJH1NYC" rel="nofollow noreferrer"><i>Feasible Computations and Provable Complexity Properties</i></a> can be read as an in-depth response to <b>Q1&ndash;5</b>. Moreover, the (excellent) <b>Q1</b> and <b>Q4</b> proof sketches provided below by <a href="https://cstheory.stackexchange.com/questions/7059/do-the-undecidable-attributes-of-p-pose-an-obstruction-to-deciding-p-versus-np/7064#7064">Travis Service</a> and by <a href="https://cstheory.stackexchange.com/questions/7059/do-the-undecidable-attributes-of-p-pose-an-obstruction-to-deciding-p-versus-np/7077#7077">Alex ten Brink</a> provide a modern affirmation and extension of Hartmanis' overall conclusions that:<blockquote><i>Results about the complexity of computations change quite radically if we consider only properties of computations which can be proven formally</i> (emphasis by Hartmanis)&nbsp;... </p>

<p>Thus we should expect that the results about the optimality of all programs computing the same function as a given program will differ from the optimality results about all programs which can be formally proven to be equivalent to the given program.&nbsp;... </p>

<p>We [should] consider the possibility that this famous problem [$P\overset{?}{=}NP$] may not be solvable in a formalized mathematical theory, such as set theory.</blockquote>Eventually I hope to post, as a formal <i>TCS StackExchange</i> "answer", further quotations from Hartmanis' (remarkably foresighted) monograph.  </p>

<p>It's evident from both Hartmanis' monograph and from the answers provided by Travis and Alex, that <b>Q1&ndash;5</b> are considerably beyond the present state-of-the-art in complexity theory.  Moreover these questions/answers evidently are sufficiently subtle as to require careful definitional adjustments and justify monograph-length expositions&nbsp;&hellip; which I hope will not discourage people from posting further answers. :)</p>

<p>For further technical discussion, see Joel David Hamkins' answer on <i>MathOverflow</i> to the question <a href="https://mathoverflow.net/questions/48014/can-a-problem-be-simultaneously-polynomial-time-and-undecidable/48031#48031">Can a problem be simultaneously polynomial time and undecidable?</a> (recommended by Alex ten Brink). </p>

<p>If in Hartmanis’ monograph one substitutes for “computation of functions” the phrase “simulation of dynamics”, the result can be read as a treatise on the complexity-theoretic limits to systems engineering&nbsp;&hellip; this is the practical reason why we engineers care about these issues.</p>

<p>A contrasting opinion to Hartmanis' was recently voiced by Oded Goldreich in a <a href="http://www.wisdom.weizmann.ac.il/~oded/on-cc.html" rel="nofollow noreferrer">letter to the CACM editor</a> titled <em>"On Computational Complexity"</em>:</p>

<blockquote>
  <p>Unfortunately, we currently lack good theoretical answers to most natural questions regarding efficient computation. This is the case not because we ask the wrong questions, but rather because these questions are very hard.</p>
</blockquote>

<p>It is (of course) perfectly conceivable that both Hartmanis' and Goldreich's opinions will prove to be correct, for example, a formal proof of the undecidability of the separability of PvsNP could reasonably be regarded as validating both points-of-view.</p>

<hr>

<p><strong>Update I</strong></p>

<p>Thoughtful comments (below) by Travis Service and Alex ten Brink suggest (in effect) that in <strong>Q1</strong> the phrase "undecidable" is not synonymous with "not verifiably decidable" and that the answers to  <strong>Q2&ndash;5</strong> may depend upon this distinction.  It is not at all clear (to me) which definitional choice would lead to the strongest  theorems, and also, best capture our intuition of the class P.   Answers and comments that address this question are welcome.  </p>

<p>A remark by Felix Klein in his <em>Elementary Mathematics from an Advanced Standpoint: Geometry</em> (1939) comes to mind:</p>

<blockquote>
  <p>Another example of a concept which occurs with more or less precision in the naive perception of space, which we must add as a supplement to our system of geometry, is the <em>notion of an (arbitrary) curve</em>.  Every person believes that he knows what a curve is until he has learned so much mathematics that the countless possible abnormalities confuse them.</p>
</blockquote>

<p>As with curves, so with the languages accepted by Turing machines in $P$&nbsp;&hellip; what once seemed (to me) like the simplest and most natural of all complexity classes now confuses me by the (countless?) unverifiable and/or undecidable attributes of its members.  The broad motivation in asking <strong>Q1&ndash;5</strong> was to find a path through this confusing thicket, but the answers given so far (by Travis Service and Alex ten Brink) have provided further grounds for confusion!</p>

<p>Klein's generation of mathematicians labored mightily to find good definitions for curves and other fundamental elements of set theory, geometry and analysis.  An elementary-level overview can be found in the Wikipedia discussion of the <a href="http://en.wikipedia.org/wiki/Alexander_horned_sphere" rel="nofollow noreferrer">Alexander Horned Sphere</a></p>

<p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="https://i.sstatic.net/Z2mfM.png" alt="Image of Alexander&#39;s Horned Sphere"><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<i>An embedding of a sphere in R3</i></p>

<p>During the 20th century, analysis of "wild manifolds" like the Alexander sphere helped clarify the distinctions between topological manifolds, piecewise-continuous manifolds, and differential manifolds.  Similarly in the 21st century, perhaps refinements of the definitions associated to $P$ will help tame $P$'s wild languages and wild Turing machines&nbsp;&hellip; although specifying suitable refinements will be no easy task.</p>

<hr>

<p><strong>Background</strong></p>

<p>These linked questions arise from the <i>MathOverflow</i> community wiki questions "<a href="https://mathoverflow.net/questions/11540/what-are-the-most-attractive-turing-undecidable-problems-in-mathematics">What are the most attractive Turing undecidable problems in mathematics?</a>" and "<a href="https://mathoverflow.net/questions/56677/what-notions-are-used-but-not-clearly-defined-in-modern-mathematics">What notions are used but not clearly defined in modern mathematics?</a>" In particular, <a href="https://mathoverflow.net/questions/56677/what-notions-are-used-but-not-clearly-defined-in-modern-mathematics/57123#57123">Colin Tan requested</a> that the question asked above be posted as a separate question. </p>

<p>For technical background see the <i>TCS StackExchange</i> question "<a href="https://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no">Are runtime bounds in P decidable?</a>", in particular <a href="https://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no/5006#5006">Emanuele Viola's concise proof</a> that the answer is "no".  Note also that similar results are proved by Juris Hartmanis in his monograph <i>Feasible computations and provable complexity properties</i> (1978).</p>

<p>This week's Lance Fortnow/Bill GASARCH weblog <em>Computational Complexity</em> is hosting their decadal poll <em>"<a href="http://www.blogger.com/comment.g?blogID=3722233&amp;postID=5334459752981812402" rel="nofollow noreferrer">Does $P=NP$ or Not?</a>"</em> -- the fifth and final question asked invites commentary upon the Fortnow/GASARCH question.</p>

CC BY-SA 3.0
2011-06-21T02:47:55.383Z
as @Alex ten Brink points out, the Turing machines you talk about in Q1 are not well defined. I think you need to think about the $\forall$'s and $\exists$'s in your question as opposed to Viola's proof.
Sasho Nikolov
CC BY-SA 3.0
2011-06-21T08:42:47.087Z
@Shasho, thank you ... an acknowledgement and summary of Alex's points (and Travis Service's points too) has been added to the question asked.
John Sidles
CC BY-SA 3.0
2011-06-21T12:40:40.573Z
Note that Emanuele Viola's proof applies to a *very* broad range of problems: a generalised version proves for any time-constructible functions $f, g$ with $f(n) = \omega(n \log n)$ and $g(n) = \omega(f(n))$ that it is impossible for a TM for which it is promised it halts in $t(n)$ time and also that $t(n)=O(f(n))$, to decide whether $t(n) = \omega(f(n))$ and $t(n)=O(g(n))$. I don't really see the link to $P$ vs $NP$ here.
Alex ten Brink
CC BY-SA 3.0
2011-06-21T14:16:54.623Z
For me, the link to *P* vs *NP* arises by analogy to geometry. Definitions that formalize the notion of a continuum are broadly stratified from Kahler manifolds to Riemann manifolds to smooth manifolds to topological manifolds to point sets (with many further distinctions), and formalizing these distinctions was essential to progress in mathematics.  Similarly, the set of Turing machines in *P*, and the set of languages these machines accept, seemingly includes "wild" algorithms whose role in complexity theory is (perhaps?) broadly analogous to "exotic" point sets in geometry and topology.
John Sidles
CC BY-SA 3.0
2011-06-22T13:51:28.953Z
Just to mention, further thoughtful comments are appearing on the Lance Fortnow/Bill GASARCH weblog *Computational Complexity* under the topic "**I am conducting a NEW POLL on P vs NP**".  See the url: http://blog.computationalcomplexity.org/2011/06/i-am-conducing-new-poll-on-p-vs-np.html
John Sidles
CC BY-SA 3.0
2011-06-29T09:25:37.603Z
Two more weblogs have begun discussing this topic: Dick Lipton and Ken Regan under the topic [polls and predictions and P=NP][1]http://rjlipton.wordpress.com/2011/06/24/polls-and-predictions-and-pnp/
John Sidles
CC BY-SA 3.0
2011-06-29T09:32:49.253Z
Two more weblogs have begun discussing this topic: Dick Lipton and Ken Regan's *Godel's Lost Letter and P=NP* under the topic "Polls and Predictions and P=NP" (http://rjlipton.wordpress.com/2011/06/24/polls-and-predictions-and-pnp/) and Scott Aaronson's *Shtetl Optimized* under the consecutive topics "Spouting Buhl", "My responses to GASARCH’s P vs. NP poll", and "What Alan T. did for his PhD".  The consensus of weblogs is that the question "Do the undecidable attributes of P pose an obstruction to deciding P versus NP?", apparently asked first by Hartmanis, remains an open question.
John Sidles
CC BY-SA 3.0
2011-06-29T16:37:50.973Z
@John, I've seen hints of these thoughts in your (various earlier.. maybe much earlier) blog comments, and I'm quite pleased to see how far you've progressed down the line with it. Cool!
Daniel Apon
CC BY-SA 3.0
2011-06-30T21:02:04.203Z
Thank you Daniel!  As it turns out, almost all of the ideas associated to this particular question *are* in the literature ... but it is a considerable labor to dig them out and link them together.  Eventually I hope these complexity-theoretic ideas and open questions will link-up naturally with a broad class of ideas and open questions that are associated to the emerging geometric understanding of dynamical simulation and spin imaging ... that's the plan (or rather, hope) for coming months anyway.
John Sidles
<cc.complexity-theory>
Do the undecidable attributes of P pose an obstruction to deciding P versus NP? (answer: maybe)
John Sidles
# Do the undecidable attributes of P pose an obstruction to deciding P versus NP? (answer: maybe)

(Asked by: username_0 on 2011-06-20)

Five linked questions are asked, and a single integrated answer is hoped-for:

> * **Q1:** Do there exist languages $L$ that are recognized **solely** by those Turing machines in $P$ whose [runtime exponents are undecidable](https://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no/5006#5006)?
> * **Q2:** Can examples of these Turing machines be finitely constructed?
> * **Q3:** Can these Turing machines be concretely instantiated? (*e.g.*, by oracles that "guess" them rather than finitely construct them).
> * **Q4:** What other attributes of *P* (besides runtime exponents) are presently known to be undecidable? For what attributes of $P$ is this question open?
> * **Q5:** Do the undecidable attributes of $P$ pose an obstruction to [the decidability of $P \ne NP$](http://www.blogger.com/comment.g?blogID=3722233&postID=5334459752981812402)?

Note carefully the word "solely" in **Q1** (which excludes username_4's suggested answer).

---

**Conclusions and Conversion to Community Wiki**

* The question asked, "Do the undecidable attributes of P pose an obstruction to deciding P versus NP?", is open and believed to be difficult, as are numerous specific questions (like Q1–4 above) that are naturally associated to it.
* Juris Hartmanis' 1978 monograph *Feasible Computations and Provable Complexity Properties* provides a good entré into the literature and (apparently) there has been no review published since Hartmanis'.
* This class of questions is sufficiently unexplored that the challenge of finding rigorous proofs is intimately admixed with the challenge of choosing good starting definitions.
* The thoughtful remarks and insightful proof sketches provided by username_5 and username_2 are acknowledged and appreciated.

Because the question is open, and because it is being discussed on multiple mathematical weblog threads ([1](http://blog.computationalcomplexity.org/2011/06/i-am-conducing-new-poll-on-p-vs-np.html),[2](http://rjlipton.wordpress.com/2011/06/24/polls-and-predictions-and-pnp/),[3](http://www.scottaaronson.com/blog/?p=686),[4](http://www.scottaaronson.com/blog/?p=690),[5](http://www.scottaaronson.com/blog/?p=697),[6](http://rjlipton.wordpress.com/2011/07/04/getting-on-base-with-pnp/)), this question has been flagged for conversion to Community Wiki.

---

**Update II and Summary**

I have become aware that Juris Harmanis’ 1978 monograph [*Feasible Computations and Provable Complexity Properties*](http://books.google.com/books?id=DTMrTZJH1NYC) can be read as an in-depth response to **Q1–5**. Moreover, the (excellent) **Q1** and **Q4** proof sketches provided below by [username_5](https://cstheory.stackexchange.com/questions/7059/do-the-undecidable-attributes-of-p-pose-an-obstruction-to-deciding-p-versus-np/7064#7064) and by [username_2](https://cstheory.stackexchange.com/questions/7059/do-the-undecidable-attributes-of-p-pose-an-obstruction-to-deciding-p-versus-np/7077#7077) provide a modern affirmation and extension of Hartmanis' overall conclusions that:
> *Results about the complexity of computations change quite radically if we consider only properties of computations which can be proven formally* (emphasis by Hartmanis) ...

Thus we should expect that the results about the optimality of all programs computing the same function as a given program will differ from the optimality results about all programs which can be formally proven to be equivalent to the given program. ...

We [should] consider the possibility that this famous problem [$P\overset{?}{=}NP$] may not be solvable in a formalized mathematical theory, such as set theory.Eventually I hope to post, as a formal *TCS StackExchange* "answer", further quotations from Hartmanis' (remarkably foresighted) monograph.

It's evident from both Hartmanis' monograph and from the answers provided by Travis and Alex, that **Q1–5** are considerably beyond the present state-of-the-art in complexity theory. Moreover these questions/answers evidently are sufficiently subtle as to require careful definitional adjustments and justify monograph-length expositions … which I hope will not discourage people from posting further answers. :)

For further technical discussion, see Joel David Hamkins' answer on *MathOverflow* to the question [Can a problem be simultaneously polynomial time and undecidable?](https://mathoverflow.net/questions/48014/can-a-problem-be-simultaneously-polynomial-time-and-undecidable/48031#48031) (recommended by username_2).

If in Hartmanis’ monograph one substitutes for “computation of functions” the phrase “simulation of dynamics”, the result can be read as a treatise on the complexity-theoretic limits to systems engineering … this is the practical reason why we engineers care about these issues.

A contrasting opinion to Hartmanis' was recently voiced by Oded Goldreich in a [letter to the CACM editor](http://www.wisdom.weizmann.ac.il/~oded/on-cc.html) titled *"On Computational Complexity"*:

> Unfortunately, we currently lack good theoretical answers to most natural questions regarding efficient computation. This is the case not because we ask the wrong questions, but rather because these questions are very hard.

It is (of course) perfectly conceivable that both Hartmanis' and Goldreich's opinions will prove to be correct, for example, a formal proof of the undecidability of the separability of PvsNP could reasonably be regarded as validating both points-of-view.

---

**Update I**

Thoughtful comments (below) by username_5 and username_2 suggest (in effect) that in **Q1** the phrase "undecidable" is not synonymous with "not verifiably decidable" and that the answers to **Q2–5** may depend upon this distinction. It is not at all clear (to me) which definitional choice would lead to the strongest theorems, and also, best capture our intuition of the class P. Answers and comments that address this question are welcome.

A remark by Felix Klein in his *Elementary Mathematics from an Advanced Standpoint: Geometry* (1939) comes to mind:

> Another example of a concept which occurs with more or less precision in the naive perception of space, which we must add as a supplement to our system of geometry, is the *notion of an (arbitrary) curve*. Every person believes that he knows what a curve is until he has learned so much mathematics that the countless possible abnormalities confuse them.

As with curves, so with the languages accepted by Turing machines in $P$ … what once seemed (to me) like the simplest and most natural of all complexity classes now confuses me by the (countless?) unverifiable and/or undecidable attributes of its members. The broad motivation in asking **Q1–5** was to find a path through this confusing thicket, but the answers given so far (by username_5 and username_2) have provided further grounds for confusion!

Klein's generation of mathematicians labored mightily to find good definitions for curves and other fundamental elements of set theory, geometry and analysis. An elementary-level overview can be found in the Wikipedia discussion of the [Alexander Horned Sphere](http://en.wikipedia.org/wiki/Alexander_horned_sphere)

![Image of Alexander's Horned Sphere](https://i.sstatic.net/Z2mfM.png)  
      *An embedding of a sphere in R3*

During the 20th century, analysis of "wild manifolds" like the Alexander sphere helped clarify the distinctions between topological manifolds, piecewise-continuous manifolds, and differential manifolds. Similarly in the 21st century, perhaps refinements of the definitions associated to $P$ will help tame $P$'s wild languages and wild Turing machines … although specifying suitable refinements will be no easy task.

---

**Background**

These linked questions arise from the *MathOverflow* community wiki questions "[What are the most attractive Turing undecidable problems in mathematics?](https://mathoverflow.net/questions/11540/what-are-the-most-attractive-turing-undecidable-problems-in-mathematics)" and "[What notions are used but not clearly defined in modern mathematics?](https://mathoverflow.net/questions/56677/what-notions-are-used-but-not-clearly-defined-in-modern-mathematics)" In particular, [Colin Tan requested](https://mathoverflow.net/questions/56677/what-notions-are-used-but-not-clearly-defined-in-modern-mathematics/57123#57123) that the question asked above be posted as a separate question.

For technical background see the *TCS StackExchange* question "[Are runtime bounds in P decidable?](https://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no)", in particular [Emanuele Viola's concise proof](https://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no/5006#5006) that the answer is "no". Note also that similar results are proved by Juris Hartmanis in his monograph *Feasible computations and provable complexity properties* (1978).

This week's username_4/Bill GASARCH weblog *Computational Complexity* is hosting their decadal poll *"[Does $P=NP$ or Not?](http://www.blogger.com/comment.g?blogID=3722233&postID=5334459752981812402)"* -- the fifth and final question asked invites commentary upon the Fortnow/GASARCH question.

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: as @username_2 points out, the Turing machines you talk about in Q1 are not well defined. I think you need to think about the $\forall$'s and $\exists$'s in your question as opposed to Viola's proof.  
> **username_0**: @Shasho, thank you ... an acknowledgement and summary of Alex's points (and username_5's points too) has been added to the question asked.  
> **username_2**: Note that Emanuele Viola's proof applies to a *very* broad range of problems: a generalised version proves for any time-constructible functions $f, g$ with $f(n) = \omega(n \log n)$ and $g(n) = \omega(f(n))$ that it is impossible for a TM for which it is promised it halts in $t(n)$ time and also that $t(n)=O(f(n))$, to decide whether $t(n) = \omega(f(n))$ and $t(n)=O(g(n))$. I don't really see the link to $P$ vs $NP$ here.  
> **username_0**: For me, the link to *P* vs *NP* arises by analogy to geometry. Definitions that formalize the notion of a continuum are broadly stratified from Kahler manifolds to Riemann manifolds to smooth manifolds to topological manifolds to point sets (with many further distinctions), and formalizing these distinctions was essential to progress in mathematics.  Similarly, the set of Turing machines in *P*, and the set of languages these machines accept, seemingly includes "wild" algorithms whose role in complexity theory is (perhaps?) broadly analogous to "exotic" point sets in geometry and topology.  
> **username_0**: Just to mention, further thoughtful comments are appearing on the username_4/Bill GASARCH weblog *Computational Complexity* under the topic "**I am conducting a NEW POLL on P vs NP**".  See the url: http://blog.computationalcomplexity.org/2011/06/i-am-conducing-new-poll-on-p-vs-np.html  
> **username_0**: Two more weblogs have begun discussing this topic: Dick Lipton and Ken Regan under the topic [polls and predictions and P=NP][1]http://rjlipton.wordpress.com/2011/06/24/polls-and-predictions-and-pnp/  
> **username_0**: Two more weblogs have begun discussing this topic: Dick Lipton and Ken Regan's *Godel's Lost Letter and P=NP* under the topic "Polls and Predictions and P=NP" (http://rjlipton.wordpress.com/2011/06/24/polls-and-predictions-and-pnp/) and Scott Aaronson's *Shtetl Optimized* under the consecutive topics "Spouting Buhl", "My responses to GASARCH’s P vs. NP poll", and "What Alan T. did for his PhD".  The consensus of weblogs is that the question "Do the undecidable attributes of P pose an obstruction to deciding P versus NP?", apparently asked first by Hartmanis, remains an open question.  
> **username_3**: @John, I've seen hints of these thoughts in your (various earlier.. maybe much earlier) blog comments, and I'm quite pleased to see how far you've progressed down the line with it. Cool!  
> **username_0**: Thank you Daniel!  As it turns out, almost all of the ideas associated to this particular question *are* in the literature ... but it is a considerable labor to dig them out and link them together.  Eventually I hope these complexity-theoretic ideas and open questions will link-up naturally with a broad class of ideas and open questions that are associated to the emerging geometric understanding of dynamical simulation and spin imaging ... that's the plan (or rather, hope) for coming months anyway.  

---

## 4 answers

### Answer by username_5 on 2011-06-20. Score: 15

For question 1 the answer is no. Let $L$ a language in $P$ and let $M$ be any polynomial time Turing machine recognizing $L$ (whose runtime is assumed to be undecidable). For each $k \in \mathbb{N}$ let $M\_k$ be the Turing machine that on input $x$ of length $n$ first loops for $n^k$ steps then runs $M$ on $x$ for $n^k + k$ steps and accepts if $M$ accepts $x$ (within those $n^k + k$ steps) and rejects otherwise. The runtime of $M\_k$ is $\Theta(n^k)$ for each $k$.

Since $M$ runs in polynomial time there is some $k' \in \mathbb{N}$ such that $M$ runs in $O(n^{k'})$ (even if we don't know what $k'$ is) and hence for all $k$ large enough $M\_k$ recognizes $L$ and has a decidable runtime.

**EDIT**

I think the following answer is more in spirit of what the original poster had intended with question 1.

**Theorem:** There exists a language $L \in P$ such that if $N$ is any Turing Machine which decides $L$ then at least one of the following is true:

1) There does not exist a proof that $N$ accepts $L$, or

2) There does not exist a proof that $N$ halts in $f(n)$ steps (for any function $f(n)$).

**Proof Sketch:**
Let $M$ be a Turing Machine that does not halt on the blank tape and for which there does not exist a proof that $M$ does not halt on the blank tape (Independence results in Computer Science by Hartmanis and Hopcroft shows such an $M$ can be effectively found).

Let $L = \{ n : \exists n' \geq n \mbox{ s.t. } M \mbox{ halts in } n' \mbox{ steps when run blank tape}\}$.

Since $M$ does not halt, $L$ is in fact the empty language but there is no proof of that (as that would prove that $M$ does not halt).

Let $N$ be any Turing Machine. If there exists both a proof that $N$ decides $L$ and a proof that $N$ runs in $f(n)$ steps then the execution of $N$ when run on input $1$ provides either a proof that $M$ halts (i.e., if $N$ accepts) or that $M$ does not halt (i.e., if $N$ rejects). Thus, if $N$ provably decides $L$ then $N$'s runtime is not decidable and vice versa.

> **Comments:**
> **username_4**: Travis does answer the rephrased question, but this is a strange situation where there is a provable exponent but only for machines you cannot prove solves the problem.  
> **username_0**: This is a nice answer to Q1 ... and I completely agree with Lance that this algorithm is a very strange member of class P.  Part of the motivation of the question was to capture the intuition (via definitions that are nice for theorem-proving) that the algorithms in P that we "care about" (in some sense) are the algorithms whose performance we can "verify" (in some sense) ... this example utterly defeats that purpose!  Nice answer! :)  
> **username_0**: This fine comment (which I am still thinking about) called to mind Felix Klein's remark "A concept which occurs with more or less precision in the naive perception of space, which we must add as a supplement to our system of geometry, is the *notion of an (arbitrary) curve*.  Every person believes that he knows what a curve is until he has learned so much mathematics that the countless possible abnormalities confuse them."  The point is that to make progress on P versus NP, perhaps a key step is to refine the definition of P to exclude "countless possible abnormalities."  
> **username_2**: Your answer is very interesting. However, predicate 1 might be more accurately described as 'There does not exist a proof that $N$ accepts $L$ starting from the definition below.', since I can easily construct a TM deciding $L$ (which is the empty language), and prove it always halts and decides the empty language. I learned something nice again, and I'm going to check up on that reference you mentioned :D  
> **username_0**: Travis' edit of his already-good answer provides even *more* to think about. Since this process will take awhile (for me), I would like to express my appreciation and thanks now (and  technical remarks later) to both both Travis (Service) and Alex (ten Brink).  Though they are students, their comments (IMHO) have been mature and interesting. It's well-known that Alan Turing conceived his "On Computable Numbers, with an Application to the *Entscheidungsproblem*" between his 21st and 23rd years; thus students have attacked similar problems with success ... we may hope the same for Alex & Travis.  

---

### Answer by username_4 on 2011-06-20. Score: 13

Yes you can build a machine that takes time DTIME($n^{i+1}$)-DTIME($n^i$) where $i$ is the number of steps taken by a specific Turing machine to halt on blank tape. Easy to construct and similar constructions hold for just about any non-trivial aspect of P. Tells us little about whether P v NP is undecidable: No problem proving P $\neq$ EXP despite the same issues.

> **Comments:**
> **username_0**: Yes ... that trick is the essence of Emanuele Viola's and Juris Harmanis' proofs of P's runtime undecidability (for example).  On the other hand, it is trivially the case that the Turing machines that are constructed by this trick all recognize languages L that are *also* recognized by Turing machines in P whose runtimes *are* decidable.  This is why Q1 is phrased (carefully!) as a question about languages rather than about Turing machines ... precisely in order to *exclude* the Hartmanis/Viola construction ... without obstructing (per your comment) the existing proofs that P \ne EXP.  
> **username_0**: ... and just to mention, those language L that are recognized *solely* by Turing machines whose runtime exponents were undecidable, are interesting languages from a complexity-theoretic (and cryptographic) point-of-view ... they seemingly exist in a Godel-esque "gray region" between algorithmically compressible (but by definition not verifiably so) and incompressible (and yet by definition not in that class either).  

---

### Answer by username_2 on 2011-06-21. Score: 8

After thinking more on the subject, I think I found a (possible) answer for your Q4.


Q4: What other attributes of $P$ (besides runtime exponents) are presently known to be undecidable? For what attributes of $P$ is this question open?


I proved a variation on Rice's theorem that answers your question for most properties. I'll try to explain myself clearer this time (username_5's answer was much clearer and more general than my previous answer).

Theorem: For any property holding on some nonempty set of decidable infinite languages (but on no finite languages), it is undecidable whether a given Turing Machine $E$ decides a language with that property, when promised that $E$ always halts in $O(f(n))$ time, where $f(n)=\Omega(n \log n)$ and $f(n)=\Omega(g(n))$, where $g(n)$ is the running time for some Turing Machine deciding some language with that property.

Recall that a Turing Machine (TM from now on) decides a language if it accepts all strings in the language and rejects all strings outside the language. Note that we can take $f(n)$ to be something other than a polynomial, so the theorem is more general than just $P$.
We formalise the notion of a 'property' as some freely selectable set of languages $S$ 'with that property'. Deciding whether a language has the property is then equivalent to deciding whether the language is a member of $S$. Just like in Rice's theorem, we investigate if we can decide whether the language decided by the input TM has the specified property, and so is in $S$. Note that we require $S \subseteq R$, ie, that $S$ contains only decidable languages.
Please note that we are talking about properties of languages, not of TMs. Your question about runtime exponents is not a special case of this theorem. Properties of, say, $P$, studyable by taking $S \subseteq P$, may interest you more than properties of TMs running in polynomial time. You can do all sorts of cruel stuff to a TM, while retaining its correctness and running time, but you can't do the same to languages.
The requirement that all languages in $S$ have to be infinite is a technicality needed for the proof, but since all finite languages are decidable in constant time and are therefore usually uninteresting, I don't think it's a major one. I expect the generalised version that also allows finite languages to be true as well.
Proof of the theorem. Assume we are given some TM $P(E)$ with a TM $E$ as parameter, such that $P$ always halts and accepts iff $E$ decides some language in $S$, and where $E$ is promised to always halt with running times as above. Let $(A, i)$ be an instance for the Halting Problem, ie, $A$ is a TM and $i$ is an input for $A$, and we now want to decide whether $A$ halts on $i$.
Since we assumed $S$ was nonempty, we have some $s \in S$. Since $S$ contains only decidable languages, there exists some TM $C$ deciding $s$. In particular, we choose the $C$ with running time $g(n)$ as assumed in the theorem. We now consider the following TM:
function H(x)
h := simulate A on i for |X| steps and return whether it halted
if h == 'halted' then
    reject
else
    if C(x) accepts then
        accept
    else
        reject
    fi
fi

It is easily seen that the running time of this TM meets the requirements for the theorem, since TMs can be simulated in $O(n \log n)$ time.
We claim that $P(H)$ returns no iff $A$ halts on $i$. Assume $A$ halts on $i$ after $t$ steps. $H$ therefore rejects any $X$ with $|X| \geq t$. We therefore decide at most a finite language, and hence $H$ decides no language in $S$ and $P(H)$ will therefore return no.
Now assume $A$ does not halt on $i$. Then the variable halt will never get the value 'halted', so we decide the same language as $C$, which is exactly $s \in S$, so $P(H)$ will return true. This proves that $P(H)$ can solve the Halting Problem, which in turn proves the theorem.

> **Comments:**
> **username_0**: This is a very powerful and flexible argument, and it will take awhile for me to grasp it ... there's a saying among farmers in the central USA "I feel like a pig being shown a wristwatch!" It appears (by your argument) that P is richly endowed with undecidable attributes; what I am having trouble grasping is whether the languages L recognized by P similarly are richly endowed with undecidable attributes ... the exercise of constructing concrete example languages having natural undecidable attributes is particularly frustrating (for me).  Thank you for an excellent, thought-provoking answer.  
> **username_2**: I think you believe $P$ to be the set of TMs running in polynomial time. This is not the definition: $P$ is the set of *languages* decidable by some TM running in polynomial time.  
> **username_0**: Alex, I definitely confess to being confused ... but not about that!  What I would like to construct, or (less desirably) prove the existence/nonexistence of, would be (for example) a language L in P having the property that every Turing machine that accepts L either is *not* verifiably in P or does *not* verifiably accept L.  These languages L would belong to P   "oracularly" ... the possibility that P includes purely oracular languages is confusing to me ... especially since it is at all not obvious (to me) how such purely oracular languages could ever be concretely sampled and exhibited.  
> **username_0**: Oh yeah ... and to ask the converse (also confusing) question ... for a given language L in NP that possibly is accepted solely by *oracular* Turing machines ... by what proof method could we possibly establish that L is not recognized by any of P's *oracular* Turing machines ... and thus separate P from NP?  Or suppose that we did prove the existence of a language L in NP not recognized by any Turing machine in P ... with the restriction that L was purely oracular ... and we could not exhibit that language ... should we be satisfied that P != NP?  These questions are confusing!  

---

### Answer by username_2 on 2011-06-20. Score: 4

I can answer your **Q1** in the negative, thereby also answering **Q2** and **Q3** in the negative. I'm not sure about **Q4** or **Q5** though.

> * **Q1:** Do there exist languages $L$ that are recognized **solely** by those Turing machines in $P$ whose [runtime exponents are undecidable](https://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no/5006#5006)?

It seems you misunderstood exactly what Emanuele Viola proved in [his brilliant proof](https://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no/5006#5006) you linked. He showed that there is no *single* Turing Machine $M$ capable of computing the runtime exponent for *any* Turing Machine $T$ presented to $M$, even under the promise that $T$ runs in polynomial time.

However, for any given Turing Machine $T$ running in polynomial time, there exists some $k$ such that $T$ has a running time of $O(n^k)$, and hence the Turing Machine $M$ returning $k$ (and nothing more) is able to 'tell' the running time exponent of $T$, even without having to look at $T$! Hence, *M* decides (in constant time even) what $k$ is *for this given Turing Machine* $T$. We may not know which Turing Machine decides it, but we know one exists.

Coming back to your question, if we are given a language $L$ in $P$, then there is some Turing Machine $T$ running in $O(n^k)$ for some $k$ that decides $L$, and hence there is the Turing Machine $M$ returning $k$ that decides the runtime exponent for $T$. This answers your question in the negative.

You might instead wonder about a different problem for a given language $L$ in $P$: given Turing Machine $T$ promised to run in polynomial time and promised to decide $L$, is it decidable to find the runtime exponent of $T$?

Unfortunately, this is also undecidable. Suppose we are given a language $L$ in $P$ and a TM (Turing Machine) $M$ capable of deciding for a given TM $T$ promised to run in polynomial time and promised to decide $L$, what the runtime exponent of $T$ is. We can prove this to be undecidable in a very similar way to what Emanuele Viola did: we use the exact TM he defined, and change it slightly: we now want this TM to decide $L$.

Since $L$ is in $P$, there is some TM deciding $L$ in $O(n^k)$ time. Our new TM $M$ first starts exactly as in Emanuele Viola's proof, running the (Halting Problem) TM for $n$ steps. It then loops either for $n^{k+1}$ steps or $n^{k+2}$ steps similarly to Emanuele Viola's TM. Finally, it solves $L$ on the given input and returns the answer.

$M$ is in $P$, decides $L$, and if we know the runtime exponent, we can decide the Halting Problem, so the above problem is also undecidable (for any language $L$). Note that we do not need to know $k$, we don't actually have to construct $M$, all we have to do is know it exists!

This kind of thinking about undecidability is quite common apparently, I remember a (blog?) post about a very similar issue: the question was "is it decidable whether Pi has a 'last zero'", so whether Pi stops having zeroes in its decimal representation if you go down far enough that representation. We currently don't know whether this is the case. We might not even be able to prove it, ever, or it might even be independent from our axiom systems (and thereby unprovable). But, since the answer is either true or false, a TM returning true and a TM returning false decide the issue either case and therefore the problem is decidable.

I'll see if I can find that post on the internet somewhere.

Edit:

I found it on [Mathoverflow](https://mathoverflow.net/questions/48014/can-a-problem-be-simultaneously-polynomial-time-and-undecidable/48031#48031).

> **Comments:**
> **username_0**: your comment and username_5' account both are excellent.  It appears that in **Q1** the phrase "undecidable" is *not* synonymous with "not verifiably decidable" ... and it is not at all clear (to me) which definition (a) leads to the best theorems and (b) best captures our intuition of the class P.  Remarks on this question are welcome.  
> **username_0**: Thank you Alex for the link (to the MOF question "Can a problem be simultaneously polynomial time and undecidable?") ... I have edited the main post to include that link.  

---

