### Answer: not known
Many thanks to all who helped refine this question and the definitions associated to it.
With a view to bringing closure to this topic — and because the question has turned out to be definition-centric rather than answer-centric — this question has been flagged for conversion to community wiki (CW).
### Follow-up
The definitions of this wiki provide the starting point for the open question "[Does P contain languages whose existence is independent of PA or ZFC?][independence]" The open question adopts the nomenclature *transcendental* $\Leftrightarrow$ *gnostic* TMs and languages in place of this wiki's *incomprehensible* $\Leftrightarrow$ *comprehensible*; the various definitions are otherwise identical.
### Further answers are welcome
Further answers are welcome (needless to say), and it is likely that further definitional tuning is appropriate. One main lesson has been that this class of questions is challenging to formulate and still more challenging to answer rigorously.
As background, [Sasho Nikolov's answer was rated "accepted,"][Sasho's answer] because it provided a formulation that captured the intent of the question: the answer to the question is (apparently) not known.
[Philip White's valuable answer][Philip White] motivated the graded definition of TMs that are incomprehensible, versus strongly incomprehensible, versus canonically incomprehensible (per the list "graded definitions of incomprehensibility" below).
The following statement of the question provisionally incorporates valuable insights and suggestions provided by Tsuyoshi Ito, Marzio De Biasi, Huck Bennett, Ricky Demer, Peter Shor, and also a valuable weblog post by [Luca Trevisan][Luca].
### Formal definition
<i>Incomprehensible Turing machines</i> are defined (within ZFC) as follows:
><b>D1</b> Given a Turing machine M that provably halts for all input strings, M is called <i>incomprehensible</i> iff the following statement is neither provable nor refutable for at least one positive semidefinite real number $r$:
>> <b>Statement:</b> M's runtime is ${O}(n^r)$ with respect to input length $n$
> Conversely, M is called <i>comprehensible</i> iff it is not incomprehensible.
### Disambiguating *decidable*
The Wikipedia entry "[Undecidable problem: Examples of undecidable statements][wiki undecidability]" concisely reviews the differing senses of the term "undecidable" that are customary in the proof-theoretic versus computability-theoretic literature. With a view to avoiding ambiguity, the definitions and questions asked employ exclusively the terminology "neither provable nor refutable."
Further references in this regard are Jeremy Avigad's course notes "[Incompleteness via the Halting Problem][Avigad]", Scott Aaronson's weblog essay "[Rosser’s Theorem via Turing machines][Aaronson]" and Luca Trevisan's weblog post [Two interesting questions][Luca].
### On the existence of incomprehensible Turing machines
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 provides, via the methods of [Jeremy Avigad's course notes][Avigad] (as I understand them), the following lemma:
><b>Lemma [Viola's Implication]</b><br> (if a language L is accepted by a comprehensible TM) $\to$<br> (L is accepted by an incomprehensible TM).
### Respecting naturality in defining incomprehensibility
It is natural to wonder whether the converse implication to Viola's Implication is true.
Considerations of naturality require that the converse implication be posed carefully, in that [Philip White's comment below][Philip White] shows how to trivially reduce incomprehensible TMs to comprehensible TMs via *polylimiters*, which are computational modules that (in effect) "pad" the runtime of an incomprehensible machine so as to reduce it to a comprehensible machine.
In particular, it is natural to require that we not “[unaesthetically mask old elements of incomprehensibility by introducing new elements of incomprehensibility][naturality].” The key challenge associated to the question asked amounts to "Does there exist a natural definition of incomprehensibility?" … which (given the discussion here of TCS) we should perhaps regard as a nontrivial meta-question that may have more than one natural answer.
With a view to this guiding naturality principle, graded definitions of incomprehensibility are specified as follows.
### Graded definitions of incomprehensibility
> <b>D2</b> We say that a Turing machine M is *efficient* iff it has a runtime exponent $r$ such that the language L that M accepts is accepted by no other TM having a runtime exponent smaller than $r$.
> <b>D3</b> We say that a language L is *incomprehensible* iff it is accepted by <b>(a)</b> at least one Turing machine M is that is both efficient and incomprehensible, and moreover <b>(b)</b> there is no efficient and comprehensible TM that provably (in ZFC) accepts L.
> <b>D4</b> We say that an incomprehensible TM is *strongly incomprehensible* iff the language it accepts is incomprehensible.
> <b>D5</b> We say that a strongly incomprehensible TM is *canonically incomprehensible* iff it is efficient.
These definitions ensure that every incomprehensible language is accepted by at least one TM that is canonically incomprehensible, and moreover — in view of <b>D3(a)</b> and <b>D3(b)</b> — there exists no trivial polylimiter reduction of a canonically incomprehensible TM to a comprehensible TM that provably recognizes the same language.
### The three questions asked
> <b>Q1</b> Does the <a href="http://en.wikipedia.org/wiki/P_%28complexity%29#Definition">complexity class P</a> contain incomprehensible languages?
> <b>Q2</b> Can at least one incomprehensible language be represented concretely? (if so, provide a constructive example).
> <b>Q3</b> Can at least one canonically incomprehensible TM be represented concretely? (if so, provide a constructive example).
----
### Motivation
The incomprehensible properties of the complexity class P obstructs the understanding of a broad class of problems that (for [the original proposer of this question][sidles]) 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].
As Juris Hartmanis' monograph *[Feasible computations and provable complexity properties][Hartmanis]* (1978) puts it:
> Results about the complexity of algorithms change quite radically if we consider only properties of computations which can be proven formally.
The struggle to construct well-posed definitions and postulates that capture Hartmanis' insight helps us to a better appreciation that the complexity class P has some exceedingly peculiar languages in it, that are recognized by exceedingly peculiar Turing machines, whose properties we are (at present) very far from grasping. It is striking that in a completely rigorous sense, it is not presently known whether the complexity class P is comprehensible.
Many thanks are extended to all who have contributed comments and answers.
[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-20565
[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
[Avigad]: http://www.andrew.cmu.edu/user/avigad/Teaching/halting.pdf
[Aaronson]: http://www.scottaaronson.com/blog/?p=710
[wiki undecidability]: http://en.wikipedia.org/wiki/Undecidable_problem#Examples_of_undecidable_statements
[Luca]: http://lucatrevisan.wordpress.com/2011/02/04/two-interesting-questions/#comment-2962
[Sasho's answer]: http://cstheory.stackexchange.com/a/11575/1519
[Hartmanis]: http://books.google.com/books?id=DTMrTZJH1NYC&pg=PA41
[Philip White]: http://cstheory.stackexchange.com/a/11592/1519
[sidles]: http://cstheory.stackexchange.com/users/1519/john-sidles
[naturality]: http://cstheory.stackexchange.com/questions/11570/does-p-contain-languages-decided-solely-by-incomprehensible-tms#comment31708_11592
[independence]: http://cstheory.stackexchange.com/q/11691/1519