Formal definitions
Prompted by Tsuyoshi Ito's query (below) we define incomprehensible TM's as follows:
Definition A Turing machine (TM) is called incomprehensible in P iff the following question is undecidable for at least one positive semidefinite real number $r$ that we call the runtime exponent:
Given a runtime exponent $r$ and Turing machine TM promised to be in P, is the TM's runtime ${O}(n^r)$ with respect to input length $n$ ?
That incomprehensible TMs exist follows concretely from a construction by Emmanuele Viola, and broadly from the complexity-theoretic framework of Juris Hartmanis.
Three questions
Three questions are asked:
Q1 Does P contain languages that are recognized solely by incomprehensible TM's?
Assuming Q1 is true, we call the languages in this subset of P incomprehensible languages.
Two natural further questions are:
Q2 Can at least one incomprehensible language be represented concretely?
(if so, provide a constructive example).
Q3 Can at least one incomprehensible TM be represented concretely?
(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, Dick Lipton and Ken Regan's Urn-Choice Game, and their hybridization in the context of Newcomb's Paradox via the Balanced Advantage Newcomb Game.
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.