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 Lance Fortnow'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 Travis Service and Alex ten Brink 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 [Travis Service](https://cstheory.stackexchange.com/questions/7059/do-the-undecidable-attributes-of-p-pose-an-obstruction-to-deciding-p-versus-np/7064#7064) and by [Alex ten Brink](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 Alex ten Brink). 

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 Travis Service and Alex ten Brink 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 Travis Service and Alex ten Brink) 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.stack.imgur.com/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 Lance Fortnow/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.