### Formal definitions
Prompted by [Tsuyoshi Ito's query (below)][Ito] we define <i>incomprehensible TM's</i> to be the set of all Turing Machines M that satisfy the following definition:
><b>Definitions</b> Given a Turing machine M that is promised to halt for all input strings, M is called <i>incomprehensible</i> iff the following question is undecidable for at least one positive semidefinite real number $r$:
>> Is M's runtime ${O}(n^r)$ with respect to input length $n$ ?
> Conversely, M is called <i>comprehensible</i> iff it is not incomprehensible.
That incomprehensible Turing machines exist follows concretely from [a construction by Emmanuele Viola][Viola], and broadly from the complexity-theoretic framework of Juris Hartmanis. In particular, Viola's construction proves the following lemma:
><b>Lemma</b> (if a language L is recognized by a comprehensible TM) then (L is recognized by an incomprehensible TM).
[Per Sasho Nikolov's query][Sasho], is natural to wonder about the (logically independent) question: is the converse implication true also?
### Three questions
The preceding considerations motivate the following three questions.
> <b>Q1</b> Does the <a href="http://en.wikipedia.org/wiki/P_%28complexity%29#Definition">complexity class P</a> contain languages that are recognized <i>solely</i> by incomprehensible TM's?
Assuming Q1 is true, we call the languages in this subset of P <i>incomprehensible languages</i>.
Two natural further questions are:
> <b>Q2</b> Can at least one incomprehensible language be represented concretely? <br> (if so, provide a constructive example).
> <b>Q3</b> Can at least one incomprehensible TM be represented concretely? <br> (if so, provide a constructive example).
To the best of my (decidedly non-expert) knowledge, these are an open questions in complexity theory … definitive references to the literature especially are desired.
----
### Motivation
The lack of an answer presently obstructs my own understanding of a broad class of problems that includes Terry Tao's [Blue-Eyed Islanders Puzzle][islanders], Dick Lipton and Ken Regan's [Urn-Choice Game][urn], and their hybridization in the context of Newcomb's Paradox via the [Balanced Advantage Newcomb Game][Newcomb].
More broadly, rigorous and/or constructive answers to these three questions would improve my appreciation of Juris Hartmanis' work in relation to proof technologies and/or decidability obstructions to settling P vs NP.
[Ito]: http://cstheory.stackexchange.com/questions/11570/does-p-contain-languages-recognized-solely-by-incomprehensible-tms#comment31612_11570
[urn]: http://rjlipton.wordpress.com/2012/05/23/beyond-las-vegas-and-monte-carlo-algorithms/#comment-20525
[islanders]: http://terrytao.wordpress.com/2011/04/07/the-blue-eyed-islanders-puzzle-repost/
[Newcomb]: http://philtcs.wordpress.com/2011/12/04/class-12b-newcombs-paradox-and-free-will/#comment-539
[Viola]: http://cstheory.stackexchange.com/a/5006/1519
[Sasho]: http://cstheory.stackexchange.com/questions/11570/does-p-contain-languages-recognized-solely-by-incomprehensible-tms#comment31620_11570