<p>Just an extended comment trying to interpret the question.</p>

<p>Given a Turing machine $M$ that <del>is promised to halt</del> halts on all input strings; $M$ is called <em>incomprehensible</em> if and only if for at least one <del>positive semidefinite real number</del> integer $r$ the following <del>question</del> decision problem  $Q_{M,r}$ is undecidable (i.e. it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer):</p>

<p><strong>OPTION 1</strong></p>

<p>$Q_{M,r}(n)$ = "Does $M$ halts in less than $n^r$ steps on all inputs of length $n$ ?"</p>

<p>Trivially decidable (finite $2^n$ strings and $M$ always halts by hypothesis) $\Rightarrow$ there are no <em>incomprehensible</em> TMs</p>

<p><strong>OPTION 2</strong></p>

<p>$Q_{M,r}$ = "Is $M$ running time $O(n^r)$ ?"</p>

<p>Trivially decidable (1 or 0) $\Rightarrow$ there are no <em>incomprehensible</em> TMs</p>

<p>And if you ask: "Ok, but can we calculate the value 1 or 0 to build the algorithm that answer the question of Option 2?", then we fall back to this:</p>

<p>$Q_{r}(M)$ = "Is $M$ running time $O(n^r)$?" which is undecidable (using the standard definition of undecidable) as showed by Emanuele. But in this version M is an <em>input</em> of the problem and not the fixed $M$ for which you are defining the notion of "<em>incomprehensible</em>".</p>

CC BY-SA 3.0
2012-05-29T14:26:04.837Z
Marzo, thank you for this answer and for your comment above. The ambiguous term "decidable" already has been dropped---it meant different things to different communities---in favor of the proof-theoretic idiom "neither provable nor refutable". To the queue of clarifying amendments for tomorrow's edited version of the question (which hopefully will be the final rigorous posing of the question) the phrase "For all *n*" will be prepended, per your Option 1. And finally, appreciation and thanks are extended to you, and to everyone, for help in posing the question rigorously and clearly.
John Sidles
CC BY-SA 3.0
2012-05-29T14:51:13.043Z
@JohnSidles: ok, and in your new version don't forget to review the connection between ... $M$ is incomprehensible iif the *statement* <$M$ runtime is $O(n^r)$> is neither provable nor refutable in T ..." and the Emanuele Viola's answer which is about the "undecidable" (standard CS definition) *decision problem* <Is $M$ runtime $O(n^r)$?>
Marzio De Biasi
CC BY-SA 3.0
2012-05-29T15:31:26.943Z
Marzo, OK and thanks.  Also, on order to establish "Viola's Implication," we have to adjoin the argument from Section 3 of Jeremy Avigad's course notes (as linked in the question) to Viola's construction ... the amended question will clarify this point.  Needless to say, the process of clarifying definitions has been 10X++ more arduous than I originally anticipated ... which perhaps is a main point of the question.  Thanks, again.
John Sidles
CC BY-SA 3.0
2012-05-29T13:24:10.830Z
2012-05-29T13:37:47.380Z
2012-05-29T13:37:47.380Z
Marzio De Biasi
<p>The answer to your question #1 is definitely "no."  As I believe someone pointed out in the (very lengthy) comments section, you could easily add a "polylimiting" to a machine.  That is, even if you don't know what r is, if you guess any integer larger than r (this is definitely possible, obviously), you could set up an overhead machine that simulates your "incomprehensible" Turing machine, and force it to stop running in polynomial time...without changing the language that the Turing machine accepts at all.  In this fashion, you could convert any "incomprehensible" polynomial time Turing machine to a "comprehensible" polynomial time Turing machine, meaning that there is no language in P that can be decided by exclusively "incomprehensible" Turing machines.</p>

<p>I hope this helps.  Unless I've completely misinterpreted your question and your intent, my answer is quite certainly correct; it's not at all an open question.</p>

CC BY-SA 3.0
2012-05-30T22:07:27.893Z
By the way, if you want a good example of a candidate for what you call an "incomprehensible" algorithm, see http://www.scholarpedia.org/article/Universal_search .  The universal search algorithm for solving SAT adheres to your definition of incomprehensible iff P = NP is formally independent.
Philip White
CC BY-SA 3.0
2012-05-31T00:56:26.390Z
do you know anything about the final question from my answer? I believe that's the only question that is still not obviously trivial..to me that is
Sasho Nikolov
CC BY-SA 3.0
2012-05-31T00:59:57.137Z
@Philip White, the definition is carefully constructed to evade the construction you provide.  Because supposing that M's runtime is undecidable for some exponent *r*, and we guess a value *r'* > *r*, and we install a *r'*-polylimiter in a modified machine M' that recognizes the same language as M, then for M' the statement "the runtime of M' is O(n^r) with respect to input length n" *still* is undecidable.  I agree though, that we need to think carefully about whether *ALL* cat-and-mouse games with oracle-specified polylimiters are excluded (as is the intent)---and so I upvoted your answer!
John Sidles
CC BY-SA 3.0
2012-05-31T01:21:54.643Z
Oh, and since Sasho's comment overlapped mine, please let me express my appreciation of [the final question in Sasho's answer](http://cstheory.stackexchange.com/a/11575/1519), which (according to my present understanding of it) artfully obstructs the introduction of oracle-derived polylimiters.  As before, I will have to think about this for a day or two.  Thank you again, Philip.
John Sidles
CC BY-SA 3.0
2012-05-31T01:23:58.007Z
Sorry, I should have read Sasho Nikolov's answer more carefully; I just saw the word "yes," oops.  I'll look at the last question in a moment and see if I have anything useful to say.
Philip White
CC BY-SA 3.0
2012-05-31T01:53:37.720Z
@Sasho Nikolov:  I think the answer to the question is, as you suggest, "yes," by Rice's theorem.  I'm not going to write out the proof, but it should be relatively obvious.  Basically, start with the following question:  Is the question of whether or not a polytime machine M has associated with it any machine M' which decides the same language and runs in polynomial time decidable?  I think that's a useful avenue to pursue to answer the question you pose; it's generally quite hard to establish that any two Turing machines decide the same language, again due to Rice's theorem.
Philip White
CC BY-SA 3.0
2012-05-31T01:57:52.567Z
Thank you Philip!  Please let me mention an aesthetic objective: a well-crafted definition of *incomprehensible* should *not* permit the trivial reduction of an incomprehensible M to an comprehensible M' via by introducing a polylimiter whose sole function is to *slow* the computation, and/or whose design requires an oracle-supplied exponent --- on the grounds that such reductions unaesthetically mask old elements of incomprehensibility by introducing new elements of incomprehensibility.
John Sidles
CC BY-SA 3.0
2012-05-31T10:21:53.880Z
@Philip White, per your excellent comment the question now distinguishes "incomprehensible TMs" from "strongly incomprehensible TMs" with a view toward preserving the complexity-theoretic naturality of Q1–Q3.  Quite possibly further definitional tuning may be required ...that the present definitions are natural is not entirely evident (to me).
John Sidles
CC BY-SA 3.0
2012-05-31T18:55:49.253Z
@JohnSidles, I think I know what you're getting at, and universal search is going to be your best bet.  You're talking about algorithms that (might) run in O(n^k) where k is not known.  Unfortunately, your definition of strongly incomprehensible machines requires that the set of strongly incomprehensible machines is empty--there is no such thing as a strongly incomprehensible language, for the reason that Peter Shor gave, and that Sasho Nikolov and I later repeated.  Definitely look into dovetailing algorithms and Levin's algorithm; I think you would find that very  interesting.
Philip White
CC BY-SA 3.0
2012-05-31T19:26:30.927Z
@Philip White, having more-than-exhausted my own knowledge, the question is now flagged for conversion to community wiki, and I hope you (and others) will improve the definitions given. Note the graded definitions of incomprehensibility **D2-D5** (in particular definitions **D3a** and **D3b**) now are crafted to forestall trivial reductions via polylimiters, with a view toward respecting the naturality of the notion "incomprehensibility."  In my view, the key challenge now amounts to "Does there exist a natural definition of incomprehensibility?" which is a tough question. Over-and-out! :)
John Sidles
CC BY-SA 3.0
2012-05-30T21:59:18.823Z
2012-05-30T21:59:18.823Z
Philip White
<p>(I am retiring as no longer relevant the portion of the answer that just explained why there are no undecidable <em>instances</em> of a problem/no polytime algorithms with uncomputable time bound)</p>

<p>Now the question has changed to a question about TMs whose running time is provable in some logical theory. For any (powerful enough) logical theory $T$, there exists a machine $M$ whose running time is polynomial but both the sentence "the running time of $M$ is polynomial" and its negation cannot be proved in $T$. In particular that means that there are polytime TMs whose running time bound cannot be proved in ZFC. This should follow from Viola's reduction with some additional tricks as in Scott's blog post. But rather than figure this out, look at the last comment by Luca in <a href="http://lucatrevisan.wordpress.com/2011/02/04/two-interesting-questions/#comment-2962" rel="nofollow">this blog post</a>. In a way, Luca answers your question here. He shows that:</p>

<ul>
<li>there exists a polytime machine $M$ such that ZFC cannot prove that $M$ does not take exponential time</li>
<li>for any polytime machine $M$ there exists a machine $M'$ which decides the same language and whose running time is provably (in ZFC say) polynomial (the simple simulation that proves this was also offered by Peter Shor in a comment)</li>
</ul>

<p>So it seems that the answer to your question is "no": any language decidable in polytime by some machine is decided by a provably polytime machine. But maybe your question should be:</p>

<ul>
<li>is there a polytime machine $M$ such that any machine $M'$ which decides the same language either cannot be proved (in ZFC) to decide the same language as $M$ or cannot be proved (in ZFC) to run in polynomial time.</li>
</ul>

<p>I suspect that the answer is yes, but right now I do not have any more time to devote to this.</p>

CC BY-SA 3.0
2012-05-29T10:50:14.617Z
------There are two distinct senses of the word *undecidable* in mathematics and computer science. The first of these is the proof-theoretic sense used in relation to Gödel's theorems, that of a statement being neither provable nor refutable in a specified deductive system. ... Because of the two meanings of the word undecidable, the term *independent* is sometimes used instead of undecidable for the "neither provable nor refutable" sense.
John Sidles
CC BY-SA 3.0
2012-05-29T11:01:22.833Z
Thanks, Sasho! I came to this appreciation too, yet the postulate can be amended via Wikipedia's distinction: "There are two distinct senses of the word *undecidable* in mathematics and computer science. The first of these is the proof-theoretic sense used in relation to Gödel's theorems, that of a statement being neither provable nor refutable in a specified deductive system ... Because of the two meanings of the word undecidable, the term *independent* is sometimes used instead of undecidable for the 'neither provable nor refutable' sense." Thus I hope to clarify the question later today.
John Sidles
CC BY-SA 3.0
2012-05-29T13:20:38.007Z
Prompted very largely by your thoughtful comments, the ambiguous attribute "decidable" now has been replaced by the (hopefully unambiguous) attribute 'neither provable nor refutable.'  For which your help is appreciated and thanks are given.
John Sidles
CC BY-SA 3.0
2012-05-29T15:40:15.667Z
please check my updated answer
Sasho Nikolov
CC BY-SA 3.0
2012-05-29T16:18:04.190Z
Thank you, Sasho.  I too have to take a break until tomorrow, however on first reading your final suggestion seems very fruitful, and I hope to respond to it soon.  Thanks again.
John Sidles
CC BY-SA 3.0
2012-05-30T13:04:30.347Z
I have rated your answer as "accepted", and edited the statement of the question to acknowledge your (and others') contributions.  Thank you.
John Sidles
CC BY-SA 3.0
2012-05-29T05:43:54.927Z
2012-05-30T01:51:42.573Z
2012-05-30T01:51:42.573Z
Sasho Nikolov
<h3>Answer: not known</h3>
<p>Many thanks to all who helped refine this question and the definitions associated to it.</p>
<p>The definitions of this wiki provided the starting point for the more recent TCS wiki &quot;<a href="https://cstheory.stackexchange.com/q/11691/1519">Does P contain languages whose existence is independent of PA or ZFC? (TCS community wiki)</a>&quot;.</p>
<p>The more recent wiki is preferred because its definitions and nomenclature are substantially more sophisticated than those of this older wiki.</p>
<p>In particular, this older wiki's nomenclature <em>incomprehensible</em> <span class="math-container">$\Leftrightarrow$</span> <em>comprehensible</em>  languages and TMs is supplanted in the newer wiki by <em>cryptic</em> <span class="math-container">$\Leftrightarrow$</span> <em>gnostic</em>.  Aside from definitional details — which however are important — the two wikis address a similar class of questions.</p>
<h3>Further answers are welcome</h3>
<p>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.</p>
<p>As background, <a href="https://cstheory.stackexchange.com/a/11575/1519">Sasho Nikolov's answer was rated  &quot;accepted,&quot;</a> because it provided a formulation that captured the intent of the question: the answer to the question is (apparently) not known.</p>
<p><a href="https://cstheory.stackexchange.com/a/11592/1519">Philip White's valuable answer</a> motivated the graded definition of TMs that are incomprehensible, versus strongly incomprehensible, versus canonically incomprehensible (per the list &quot;graded definitions of incomprehensibility&quot; below).</p>
<p>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 <a href="http://lucatrevisan.wordpress.com/2011/02/04/two-interesting-questions/#comment-2962" rel="nofollow noreferrer">Luca Trevisan</a>.</p>
<h3>Formal definition</h3>
<p><i>Incomprehensible Turing machines</i> are defined (within ZFC) as follows:</p>
<blockquote>
<p><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 <span class="math-container">$r$</span>:</p>
<blockquote>
<p><b>Statement:</b> M's runtime is <span class="math-container">${O}(n^r)$</span> with respect to input length <span class="math-container">$n$</span></p>
</blockquote>
<p>Conversely, M is called <i>comprehensible</i> iff it is not incomprehensible.</p>
</blockquote>
<h3>Disambiguating <em>decidable</em></h3>
<p>The Wikipedia entry &quot;<a href="http://en.wikipedia.org/wiki/Undecidable_problem#Examples_of_undecidable_statements" rel="nofollow noreferrer">Undecidable problem: Examples of undecidable statements</a>&quot; concisely reviews the differing senses of the term &quot;undecidable&quot; 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 &quot;neither provable nor refutable.&quot;</p>
<p>Further references in this regard are Jeremy Avigad's course notes &quot;<a href="http://www.andrew.cmu.edu/user/avigad/Teaching/halting.pdf" rel="nofollow noreferrer">Incompleteness via the Halting Problem</a>&quot;, Scott Aaronson's weblog essay &quot;<a href="http://www.scottaaronson.com/blog/?p=710" rel="nofollow noreferrer">Rosser’s Theorem via Turing machines</a>&quot; and Luca Trevisan's weblog post <a href="http://lucatrevisan.wordpress.com/2011/02/04/two-interesting-questions/#comment-2962" rel="nofollow noreferrer">Two interesting questions</a>.</p>
<h3>On the existence of incomprehensible Turing machines</h3>
<p>That incomprehensible Turing machines exist follows concretely from <a href="https://cstheory.stackexchange.com/a/5006/1519">a construction by Emmanuele Viola</a> and broadly from the complexity-theoretic framework of Juris Hartmanis.  In particular, Viola's construction provides, via the methods of <a href="http://www.andrew.cmu.edu/user/avigad/Teaching/halting.pdf" rel="nofollow noreferrer">Jeremy Avigad's course notes</a> (as I understand them), the following lemma:</p>
<blockquote>
<p><b>Lemma [Viola's Implication]</b><br>    (if a language L is accepted by a comprehensible TM) <span class="math-container">$\to$</span><br>        (L is accepted by an incomprehensible TM).</p>
</blockquote>
<h3>Respecting naturality in defining incomprehensibility</h3>
<p>It is natural to wonder whether the converse implication to Viola's Implication is true.</p>
<p>Considerations of naturality require that the converse implication be posed carefully, in that <a href="https://cstheory.stackexchange.com/a/11592/1519">Philip White's comment below</a> shows how to trivially reduce incomprehensible TMs to comprehensible TMs via <em>polylimiters</em>, which are computational modules that (in effect) &quot;pad&quot; the runtime of an incomprehensible machine so as to reduce it to a comprehensible machine.</p>
<p>In particular, it is natural to require that we not “<a href="https://cstheory.stackexchange.com/questions/11570/does-p-contain-languages-decided-solely-by-incomprehensible-tms#comment31708_11592">unaesthetically mask old elements of incomprehensibility by introducing new elements of incomprehensibility</a>.” The key challenge associated to the question asked amounts to &quot;Does there exist a natural definition of incomprehensibility?&quot; … which (given the discussion here of TCS) we should perhaps regard as a nontrivial meta-question that may have more than one natural answer.</p>
<p>With a view to this guiding naturality principle, graded definitions of incomprehensibility are specified as follows.</p>
<h3>Graded definitions of incomprehensibility</h3>
<blockquote>
<p><b>D2</b>  We say that a Turing machine M is <em>efficient</em> iff it has a runtime exponent <span class="math-container">$r$</span> such that the language L that M accepts is accepted by no other TM having a runtime exponent smaller than <span class="math-container">$r$</span>.</p>
<p><b>D3</b>  We say that a language L is <em>incomprehensible</em> 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.</p>
<p><b>D4</b>  We say that an incomprehensible TM is <em>strongly incomprehensible</em> iff the language it accepts is incomprehensible.</p>
<p><b>D5</b>  We say that a strongly incomprehensible TM is <em>canonically incomprehensible</em> iff it is efficient.</p>
</blockquote>
<p>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.</p>
<h3>The three questions asked</h3>
<blockquote>
<p><b>Q1</b>  Does the <a href="http://en.wikipedia.org/wiki/P_%28complexity%29#Definition" rel="nofollow noreferrer">complexity class P</a> contain incomprehensible languages?</p>
<p><b>Q2</b>  Can at least one incomprehensible language be represented concretely? (if so, provide a constructive example).</p>
<p><b>Q3</b>  Can at least one canonically incomprehensible TM be represented concretely? (if so, provide a constructive example).</p>
</blockquote>
<hr />
<h3>Motivation</h3>
<p>The incomprehensible properties of the complexity class P obstructs the understanding of a broad class of problems that (for <a href="https://cstheory.stackexchange.com/users/1519/john-sidles">the original proposer of this question</a>) includes Terry Tao's <a href="http://terrytao.wordpress.com/2011/04/07/the-blue-eyed-islanders-puzzle-repost/" rel="nofollow noreferrer">Blue-Eyed Islanders Puzzle</a>,  Dick Lipton and Ken Regan's <a href="http://rjlipton.wordpress.com/2012/05/23/beyond-las-vegas-and-monte-carlo-algorithms/#comment-20565" rel="nofollow noreferrer">Urn-Choice Game</a>, and their hybridization in the context of Newcomb's Paradox via the <a href="http://philtcs.wordpress.com/2011/12/04/class-12b-newcombs-paradox-and-free-will/#comment-539" rel="nofollow noreferrer">Balanced Advantage Newcomb Game</a>.</p>
<p>As Juris Hartmanis' monograph <em><a href="http://books.google.com/books?id=DTMrTZJH1NYC&amp;pg=PA41" rel="nofollow noreferrer">Feasible computations and provable complexity properties</a></em> (1978) puts it:</p>
<blockquote>
<p>Results about the complexity of algorithms change quite radically if we consider only properties of computations which can be proven formally.</p>
</blockquote>
<p>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.</p>
<p>Many thanks are extended to all who have contributed comments and answers.</p>

CC BY-SA 3.0
2012-05-28T18:08:30.957Z
Please define the term “(a Turing machine) being decidably in P.”
Tsuyoshi Ito
CC BY-SA 3.0
2012-05-28T18:49:43.107Z
In the problem stated in the definition of “incomprehensible in P,” what exactly is the input?  Is the Turing machine part of the input or fixed?  In addition, how is a real number specified as a string?
Tsuyoshi Ito
CC BY-SA 3.0
2012-05-28T19:04:25.487Z
The definition makes no sense, I am afraid. Viola's reduction shows that when the Turing machine is part of the input together with $r$, its running time is undecidable. But if we take the Turing machine out of the input and fix a language for any Turing machine, then the problem becomes decidable (because we're allowed to construct a deciding TM specifically for a Turing machine $M$).
Sasho Nikolov
CC BY-SA 3.0
2012-05-28T19:09:10.213Z
@Sasho Nikolov: I agree.  I guess that it is a common error to interpret the undecidability of a problem as existence of an “undecidable instance” of the problem.
Tsuyoshi Ito
CC BY-SA 3.0
2012-05-28T19:15:15.673Z
@Ito (and Sasho), thank you for your inputs.  The definitions and phrasing of the question have been amended so that it is now (hopefully) well-posed ... please suggest any further adjustments as needed.
John Sidles
CC BY-SA 3.0
2012-05-28T19:19:45.737Z
As Sasho explained preemptively, the problem stated in the definition of “incomprehensible” in revision 4 is decidable for every M.  I am afraid that you are making an elementary error here.  If you still have trouble understanding it, [this post](http://cstheory.stackexchange.com/questions/2802/are-there-any-counterintuitive-results-in-theoretical-computer-science/2825#2825) by Raphael and the link in it may be helpful.  I voted to close this as not a real question.
Tsuyoshi Ito
CC BY-SA 3.0
2012-05-28T19:48:32.390Z
@Sasho Nikolov especially ... TCS StackExchange colleagues, we are at-risk of falling out of phase, in that I have just finished responding to Sasho's most recent comment! In particular, it appears that Sasho and I may have been speaking to mutually converse (hence mutually independent) implications---hopefully the most recent version (which features "Viola's implication") has clarified this point.  It seems like a good idea to let further comments accumulate until tomorrow morning, rather than deal with them one-by-one.  Please let me thank everyone for good comments.
John Sidles
CC BY-SA 3.0
2012-05-29T00:09:59.110Z
Progress: changes in-the-pipeline for an edit tomorrow (Tuesday) are: (1) amend the notation to match Arora and Boas by substituting "recognized" -> "decided", and (2) in the sentence after Q1 substitute "incomprehensible" -> "strongly incomprehensible" so as to read: "Assuming Q1 is true, we call the languages in this subset of P *strongly incomprehensible languages* and similarly TMs that decide these languages are called *strongly incomprehensible TMs*."  Then in Q2 and Q3 substitute "incomprehensible" -> "strongly incomprehensible".  Further suggestions are welcome, needless to say!
John Sidles
CC BY-SA 3.0
2012-05-29T00:25:11.427Z
@Tsuyoshi Ito, after (1) carefully reviewing the link you provided, and (2) further reviewing  Hartmanis' monograph *Feasible Computations and Provable Complexity Properties* (1978), and finally (3) scrupulously embracing the definitions and notational conventions of Arora and Barak's *Computational Complexity: a Modern Approach* (2009), it is my present impression that the questions-asked and definitions-provided reasonably satisfy all criteria of the TCS StackExchange charter.  If in your opinion flaws remain, please describe them in a comment, and I will do my best to address them.
John Sidles
CC BY-SA 3.0
2012-05-29T00:33:49.847Z
You did not address the flaw which I pointed out at all.  To repeat myself: According to the current definition (revision 6), every Turing machine is “comprehensible.”  Both Sasho and I already explained this.  And please do not expect that I will read further comments.
Tsuyoshi Ito
CC BY-SA 3.0
2012-05-29T01:31:55.250Z
@Sasho Nikolov, per your and Tsuyoshi Ito's remarks, tomorrow's edit of the question will note that Emmanuele Viola's method constructs an explicit TM for which the question "Is the runtime O(n^2)?" is undecidable.  The TM that Viola gives is---by the definition given---*incomprehensible* and thus the set of incomprehensible TMs is non-empty.  If you (or anyone) feels that this point requires further explanation or correction ... well ... please provide that explanation or correction as an answer!
John Sidles
CC BY-SA 3.0
2012-05-29T02:44:26.877Z
@JohnSidles: I think (referencing Rafael's revision) the reduction shows that the *language* P (not the best letter choice) is undecidable, and does not give an explicit TM for which "run time bounds in P" is undecidable. M* (not fixed) is part of the input.
Huck Bennett
CC BY-SA 3.0
2012-05-29T03:18:17.900Z
@Huck Bennett, per your post and Raphael's example, everyone is clear that the question at the focus of the definition---namely "Is M's runtime O(n^r) with respect to input length n?"---has a *computable* answer (that answer being either "yes" or "no", both of which are computable).  But the definition is not concerned with the answer's computability, but rather the answer's *decidability*.  And as I read Viola's construction, instances of an (undecidable) halting problem are uniformly reduceable to instances of a runtime exponent problem (hence also undecidable).
John Sidles
CC BY-SA 3.0
2012-05-29T11:49:28.840Z
Per Sasho's answer (below), and in accord with Wikipedia conventions, another edit in the queue will disambiguate the word "undecidable" with respect to its proof-theoretic versus computability-theoretic senses, via the substitution (undecidable) -> (independent).
John Sidles
CC BY-SA 3.0
2012-05-29T13:55:53.300Z
@JohnSidles: reading the last version of your question: why don't you get rid of the word "question" and use something like this: "... M is called incomprehensible in T iff the following **statement** is neither provable nor refutable in T for at least one positive semidefinite real number r: "$M$'s runtime is $O(n^r)$" (Gödel's First Incompleteness Theorem is completely unconcerned with the question of truth).
Marzio De Biasi
CC BY-SA 3.0
2012-05-29T14:18:18.077Z
@ Marzio De Biasi, your suggestion is excellent, and so I have added it to the queue of amendments for tomorrow's edited version of the question, which (hopefully) will be the final, rigorous posing of the question.  Many thanks to everyone, for help in posing the question rigorously and clearly.
John Sidles
CC BY-SA 3.0
2012-05-29T15:32:25.660Z
Your definition is still bad. Given an incomprehensible Turing machine in P, you can turn it into a comprehensible Turing machine in P by putting a timer on it which counts $Cn^k$ steps, and if it doesn't halt by then, stops it and rejects. For any incomprehensible Turing machine in P, there is a $C$ and $k$ which will turn it into a comprehensible Turing machine accepting the same language. Of course, you can't prove that it accepts the same language, and you can't find the right values of *C* and *k*, but I don't see how you can incorporate this into your definition.
Peter Shor 
CC BY-SA 3.0
2012-05-29T16:04:46.140Z
@Peter Shor, your method for *(incomprehensible)* -> *(comprehensible)* reduction is intriguing.  Since the reduction method requires an non-realizable oracle (to specify *k*), I will contemplate blocking oracle-dependent reductions by substituting in the definition *(promised to halt)* -> *(provably halts)*.  Needless to say (as noted in my response to Marzio De Biasi) clarifying the definitions associated to this question has been 10X++ more arduous than I originally anticipated ... which qualifies as a valuable lesson-learned ... and that is why I am *very* grateful to all who are helping.
John Sidles
CC BY-SA 3.0
2012-05-29T16:14:11.357Z
Also addressing Peter's (excellent) point is Sasho Nikolov's amended answer (below).  Like Sasho, further responses on my part with regard to these many tough-but-rich comments and answers will have to wait until tomorrow ... it simply takes a considerable time to understand and integrate them.  Thanks again, to everyone.
John Sidles
CC BY-SA 3.0
2012-05-29T16:25:58.893Z
think there is a big connection between compressibility & class separations incl P vs NP that is not well researched/formulated so far, and not nec exactly using the kolmogorov sense of compressibility. here is an early formulation of this problem, [compression of a TM run sequence](http://mathoverflow.net/questions/86339/compression-of-a-turing-machine-run-sequence)
vzn
CC BY-SA 3.0
2012-05-30T16:37:51.137Z
The question is now finalized and Sasho Nikolov's answer is "accepted" because it provided a formulation that captured the intent of the question: the answer to the question itself is (apparently) not known.  Regarding game-theoretic (or even cryptographic) applications of strong incomprehensibility (if it exists), see the *Gödel's Lost Letter* weblog topic "[Beyond Las Vegas And Monte Carlo Algorithms](https://rjlipton.wordpress.com/2012/05/23/beyond-las-vegas-and-monte-carlo-algorithms/#comment-20590)."  My thanks are extended to everyone for their comments and suggestions.
John Sidles
CC BY-SA 3.0
2012-05-31T15:49:42.587Z
A [new answer by Philip White](http://cstheory.stackexchange.com/a/11592/1519) has clarified (for me) a trivial "polylimiting" reduction *incomprehensible* -> *comprehensible* that was noted too by Sasho Nikolov and Peter Shor. In light of this trivial reduction, the definition of "strongly incomprehensible" has been suitably amended with a view to preserving the naturality of Q1–Q3.  To bring closure to this question, I'll wait until the weekend for further answers / comments, and if the question remains open (as seems likely) it will be converted to a community wiki.  Many thanks to all!
John Sidles
<cc.complexity-theory><complexity-classes><turing-machines><decidability>
Does P contain incomprehensible languages? (TCS community wiki)
John Sidles
# Does P contain incomprehensible languages? (TCS community wiki)

(Asked by: username_0 on 2012-05-28)

### Answer: not known

Many thanks to all who helped refine this question and the definitions associated to it.

The definitions of this wiki provided the starting point for the more recent TCS wiki "[Does P contain languages whose existence is independent of PA or ZFC? (TCS community wiki)](https://cstheory.stackexchange.com/q/11691/1519)".

The more recent wiki is preferred because its definitions and nomenclature are substantially more sophisticated than those of this older wiki.

In particular, this older wiki's nomenclature *incomprehensible* $\Leftrightarrow$ *comprehensible* languages and TMs is supplanted in the newer wiki by *cryptic* $\Leftrightarrow$ *gnostic*. Aside from definitional details — which however are important — the two wikis address a similar class of questions.

### 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,"](https://cstheory.stackexchange.com/a/11575/1519) 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](https://cstheory.stackexchange.com/a/11592/1519) 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](http://lucatrevisan.wordpress.com/2011/02/04/two-interesting-questions/#comment-2962).

### Formal definition

*Incomprehensible Turing machines* are defined (within ZFC) as follows:

> **D1**  Given a Turing machine M that provably halts for all input strings, M is called *incomprehensible* iff the following statement is neither provable nor refutable for at least one positive semidefinite real number $r$:
>
> > **Statement:** M's runtime is ${O}(n^r)$ with respect to input length $n$
>
> Conversely, M is called *comprehensible* iff it is not incomprehensible.

### Disambiguating *decidable*

The Wikipedia entry "[Undecidable problem: Examples of undecidable statements](http://en.wikipedia.org/wiki/Undecidable_problem#Examples_of_undecidable_statements)" 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](http://www.andrew.cmu.edu/user/avigad/Teaching/halting.pdf)", Scott Aaronson's weblog essay "[Rosser’s Theorem via Turing machines](http://www.scottaaronson.com/blog/?p=710)" and Luca Trevisan's weblog post [Two interesting questions](http://lucatrevisan.wordpress.com/2011/02/04/two-interesting-questions/#comment-2962).

### On the existence of incomprehensible Turing machines

That incomprehensible Turing machines exist follows concretely from [a construction by Emmanuele Viola](https://cstheory.stackexchange.com/a/5006/1519) 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](http://www.andrew.cmu.edu/user/avigad/Teaching/halting.pdf) (as I understand them), the following lemma:

> **Lemma [Viola's Implication]**  
>     (if a language L is accepted by a comprehensible TM) $\to$  
>         (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](https://cstheory.stackexchange.com/a/11592/1519) 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](https://cstheory.stackexchange.com/questions/11570/does-p-contain-languages-decided-solely-by-incomprehensible-tms#comment31708_11592).” 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

> **D2**  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$.
>
> **D3**  We say that a language L is *incomprehensible* iff it is accepted by **(a)** at least one Turing machine M is that is both efficient and incomprehensible, and moreover **(b)** there is no efficient and comprehensible TM that provably (in ZFC) accepts L.
>
> **D4**  We say that an incomprehensible TM is *strongly incomprehensible* iff the language it accepts is incomprehensible.
>
> **D5**  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 **D3(a)** and **D3(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

> **Q1**  Does the [complexity class P](http://en.wikipedia.org/wiki/P_%28complexity%29#Definition) contain incomprehensible languages?
>
> **Q2**  Can at least one incomprehensible language be represented concretely? (if so, provide a constructive example).
>
> **Q3**  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](https://cstheory.stackexchange.com/users/1519/john-sidles)) includes Terry Tao's [Blue-Eyed Islanders Puzzle](http://terrytao.wordpress.com/2011/04/07/the-blue-eyed-islanders-puzzle-repost/), Dick Lipton and Ken Regan's [Urn-Choice Game](http://rjlipton.wordpress.com/2012/05/23/beyond-las-vegas-and-monte-carlo-algorithms/#comment-20565), and their hybridization in the context of Newcomb's Paradox via the [Balanced Advantage Newcomb Game](http://philtcs.wordpress.com/2011/12/04/class-12b-newcombs-paradox-and-free-will/#comment-539).

As Juris Hartmanis' monograph *[Feasible computations and provable complexity properties](http://books.google.com/books?id=DTMrTZJH1NYC&pg=PA41)* (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.

**Tags:** cc.complexity-theory, complexity-classes, turing-machines, decidability
> **Comments:**
> **username_1**: Please define the term “(a Turing machine) being decidably in P.”  
> **username_1**: In the problem stated in the definition of “incomprehensible in P,” what exactly is the input?  Is the Turing machine part of the input or fixed?  In addition, how is a real number specified as a string?  
> **username_2**: The definition makes no sense, I am afraid. Viola's reduction shows that when the Turing machine is part of the input together with $r$, its running time is undecidable. But if we take the Turing machine out of the input and fix a language for any Turing machine, then the problem becomes decidable (because we're allowed to construct a deciding TM specifically for a Turing machine $M$).  
> **username_1**: @Sasho Nikolov: I agree.  I guess that it is a common error to interpret the undecidability of a problem as existence of an “undecidable instance” of the problem.  
> **username_0**: @Ito (and Sasho), thank you for your inputs.  The definitions and phrasing of the question have been amended so that it is now (hopefully) well-posed ... please suggest any further adjustments as needed.  
> **username_1**: As Sasho explained preemptively, the problem stated in the definition of “incomprehensible” in revision 4 is decidable for every M.  I am afraid that you are making an elementary error here.  If you still have trouble understanding it, [this post](http://cstheory.stackexchange.com/questions/2802/are-there-any-counterintuitive-results-in-theoretical-computer-science/2825#2825) by Raphael and the link in it may be helpful.  I voted to close this as not a real question.  
> **username_0**: @Sasho Nikolov especially ... TCS StackExchange colleagues, we are at-risk of falling out of phase, in that I have just finished responding to Sasho's most recent comment! In particular, it appears that Sasho and I may have been speaking to mutually converse (hence mutually independent) implications---hopefully the most recent version (which features "Viola's implication") has clarified this point.  It seems like a good idea to let further comments accumulate until tomorrow morning, rather than deal with them one-by-one.  Please let me thank everyone for good comments.  
> **username_0**: Progress: changes in-the-pipeline for an edit tomorrow (Tuesday) are: (1) amend the notation to match Arora and Boas by substituting "recognized" -> "decided", and (2) in the sentence after Q1 substitute "incomprehensible" -> "strongly incomprehensible" so as to read: "Assuming Q1 is true, we call the languages in this subset of P *strongly incomprehensible languages* and similarly TMs that decide these languages are called *strongly incomprehensible TMs*."  Then in Q2 and Q3 substitute "incomprehensible" -> "strongly incomprehensible".  Further suggestions are welcome, needless to say!  
> **username_0**: @Tsuyoshi Ito, after (1) carefully reviewing the link you provided, and (2) further reviewing  Hartmanis' monograph *Feasible Computations and Provable Complexity Properties* (1978), and finally (3) scrupulously embracing the definitions and notational conventions of Arora and Barak's *Computational Complexity: a Modern Approach* (2009), it is my present impression that the questions-asked and definitions-provided reasonably satisfy all criteria of the TCS StackExchange charter.  If in your opinion flaws remain, please describe them in a comment, and I will do my best to address them.  
> **username_1**: You did not address the flaw which I pointed out at all.  To repeat myself: According to the current definition (revision 6), every Turing machine is “comprehensible.”  Both Sasho and I already explained this.  And please do not expect that I will read further comments.  
> **username_0**: @Sasho Nikolov, per your and Tsuyoshi Ito's remarks, tomorrow's edit of the question will note that Emmanuele Viola's method constructs an explicit TM for which the question "Is the runtime O(n^2)?" is undecidable.  The TM that Viola gives is---by the definition given---*incomprehensible* and thus the set of incomprehensible TMs is non-empty.  If you (or anyone) feels that this point requires further explanation or correction ... well ... please provide that explanation or correction as an answer!  
> **username_3**: @JohnSidles: I think (referencing Rafael's revision) the reduction shows that the *language* P (not the best letter choice) is undecidable, and does not give an explicit TM for which "run time bounds in P" is undecidable. M* (not fixed) is part of the input.  
> **username_0**: @Huck Bennett, per your post and Raphael's example, everyone is clear that the question at the focus of the definition---namely "Is M's runtime O(n^r) with respect to input length n?"---has a *computable* answer (that answer being either "yes" or "no", both of which are computable).  But the definition is not concerned with the answer's computability, but rather the answer's *decidability*.  And as I read Viola's construction, instances of an (undecidable) halting problem are uniformly reduceable to instances of a runtime exponent problem (hence also undecidable).  
> **username_0**: Per Sasho's answer (below), and in accord with Wikipedia conventions, another edit in the queue will disambiguate the word "undecidable" with respect to its proof-theoretic versus computability-theoretic senses, via the substitution (undecidable) -> (independent).  
> **username_4**: @JohnSidles: reading the last version of your question: why don't you get rid of the word "question" and use something like this: "... M is called incomprehensible in T iff the following **statement** is neither provable nor refutable in T for at least one positive semidefinite real number r: "$M$'s runtime is $O(n^r)$" (Gödel's First Incompleteness Theorem is completely unconcerned with the question of truth).  
> **username_0**: @ Marzio De Biasi, your suggestion is excellent, and so I have added it to the queue of amendments for tomorrow's edited version of the question, which (hopefully) will be the final, rigorous posing of the question.  Many thanks to everyone, for help in posing the question rigorously and clearly.  
> **username_5**: Your definition is still bad. Given an incomprehensible Turing machine in P, you can turn it into a comprehensible Turing machine in P by putting a timer on it which counts $Cn^k$ steps, and if it doesn't halt by then, stops it and rejects. For any incomprehensible Turing machine in P, there is a $C$ and $k$ which will turn it into a comprehensible Turing machine accepting the same language. Of course, you can't prove that it accepts the same language, and you can't find the right values of *C* and *k*, but I don't see how you can incorporate this into your definition.  
> **username_0**: @Peter Shor, your method for *(incomprehensible)* -> *(comprehensible)* reduction is intriguing.  Since the reduction method requires an non-realizable oracle (to specify *k*), I will contemplate blocking oracle-dependent reductions by substituting in the definition *(promised to halt)* -> *(provably halts)*.  Needless to say (as noted in my response to Marzio De Biasi) clarifying the definitions associated to this question has been 10X++ more arduous than I originally anticipated ... which qualifies as a valuable lesson-learned ... and that is why I am *very* grateful to all who are helping.  
> **username_0**: Also addressing Peter's (excellent) point is Sasho Nikolov's amended answer (below).  Like Sasho, further responses on my part with regard to these many tough-but-rich comments and answers will have to wait until tomorrow ... it simply takes a considerable time to understand and integrate them.  Thanks again, to everyone.  
> **username_6**: think there is a big connection between compressibility & class separations incl P vs NP that is not well researched/formulated so far, and not nec exactly using the kolmogorov sense of compressibility. here is an early formulation of this problem, [compression of a TM run sequence](http://mathoverflow.net/questions/86339/compression-of-a-turing-machine-run-sequence)  
> **username_0**: The question is now finalized and Sasho Nikolov's answer is "accepted" because it provided a formulation that captured the intent of the question: the answer to the question itself is (apparently) not known.  Regarding game-theoretic (or even cryptographic) applications of strong incomprehensibility (if it exists), see the *Gödel's Lost Letter* weblog topic "[Beyond Las Vegas And Monte Carlo Algorithms](https://rjlipton.wordpress.com/2012/05/23/beyond-las-vegas-and-monte-carlo-algorithms/#comment-20590)."  My thanks are extended to everyone for their comments and suggestions.  
> **username_0**: A [new answer by Philip White](http://cstheory.stackexchange.com/a/11592/1519) has clarified (for me) a trivial "polylimiting" reduction *incomprehensible* -> *comprehensible* that was noted too by Sasho Nikolov and Peter Shor. In light of this trivial reduction, the definition of "strongly incomprehensible" has been suitably amended with a view to preserving the naturality of Q1–Q3.  To bring closure to this question, I'll wait until the weekend for further answers / comments, and if the question remains open (as seems likely) it will be converted to a community wiki.  Many thanks to all!  

---

## 3 answers

### Answer by username_2 on 2012-05-29. Score: 11 | Accepted answer

(I am retiring as no longer relevant the portion of the answer that just explained why there are no undecidable *instances* of a problem/no polytime algorithms with uncomputable time bound)

Now the question has changed to a question about TMs whose running time is provable in some logical theory. For any (powerful enough) logical theory $T$, there exists a machine $M$ whose running time is polynomial but both the sentence "the running time of $M$ is polynomial" and its negation cannot be proved in $T$. In particular that means that there are polytime TMs whose running time bound cannot be proved in ZFC. This should follow from Viola's reduction with some additional tricks as in Scott's blog post. But rather than figure this out, look at the last comment by Luca in [this blog post](http://lucatrevisan.wordpress.com/2011/02/04/two-interesting-questions/#comment-2962). In a way, Luca answers your question here. He shows that:

* there exists a polytime machine $M$ such that ZFC cannot prove that $M$ does not take exponential time
* for any polytime machine $M$ there exists a machine $M'$ which decides the same language and whose running time is provably (in ZFC say) polynomial (the simple simulation that proves this was also offered by Peter Shor in a comment)

So it seems that the answer to your question is "no": any language decidable in polytime by some machine is decided by a provably polytime machine. But maybe your question should be:

* is there a polytime machine $M$ such that any machine $M'$ which decides the same language either cannot be proved (in ZFC) to decide the same language as $M$ or cannot be proved (in ZFC) to run in polynomial time.

I suspect that the answer is yes, but right now I do not have any more time to devote to this.

> **Comments:**
> **username_0**: ------There are two distinct senses of the word *undecidable* in mathematics and computer science. The first of these is the proof-theoretic sense used in relation to Gödel's theorems, that of a statement being neither provable nor refutable in a specified deductive system. ... Because of the two meanings of the word undecidable, the term *independent* is sometimes used instead of undecidable for the "neither provable nor refutable" sense.  
> **username_0**: Thanks, Sasho! I came to this appreciation too, yet the postulate can be amended via Wikipedia's distinction: "There are two distinct senses of the word *undecidable* in mathematics and computer science. The first of these is the proof-theoretic sense used in relation to Gödel's theorems, that of a statement being neither provable nor refutable in a specified deductive system ... Because of the two meanings of the word undecidable, the term *independent* is sometimes used instead of undecidable for the 'neither provable nor refutable' sense." Thus I hope to clarify the question later today.  
> **username_0**: Prompted very largely by your thoughtful comments, the ambiguous attribute "decidable" now has been replaced by the (hopefully unambiguous) attribute 'neither provable nor refutable.'  For which your help is appreciated and thanks are given.  
> **username_2**: please check my updated answer  
> **username_0**: Thank you, Sasho.  I too have to take a break until tomorrow, however on first reading your final suggestion seems very fruitful, and I hope to respond to it soon.  Thanks again.  
> **username_0**: I have rated your answer as "accepted", and edited the statement of the question to acknowledge your (and others') contributions.  Thank you.  

---

### Answer by username_4 on 2012-05-29. Score: 2

Just an extended comment trying to interpret the question.

Given a Turing machine $M$ that ~~is promised to halt~~ halts on all input strings; $M$ is called *incomprehensible* if and only if for at least one ~~positive semidefinite real number~~ integer $r$ the following ~~question~~ decision problem $Q\_{M,r}$ is undecidable (i.e. it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer):

**OPTION 1**

$Q\_{M,r}(n)$ = "Does $M$ halts in less than $n^r$ steps on all inputs of length $n$ ?"

Trivially decidable (finite $2^n$ strings and $M$ always halts by hypothesis) $\Rightarrow$ there are no *incomprehensible* TMs

**OPTION 2**

$Q\_{M,r}$ = "Is $M$ running time $O(n^r)$ ?"

Trivially decidable (1 or 0) $\Rightarrow$ there are no *incomprehensible* TMs

And if you ask: "Ok, but can we calculate the value 1 or 0 to build the algorithm that answer the question of Option 2?", then we fall back to this:

$Q\_{r}(M)$ = "Is $M$ running time $O(n^r)$?" which is undecidable (using the standard definition of undecidable) as showed by Emanuele. But in this version M is an *input* of the problem and not the fixed $M$ for which you are defining the notion of "*incomprehensible*".

> **Comments:**
> **username_0**: Marzo, thank you for this answer and for your comment above. The ambiguous term "decidable" already has been dropped---it meant different things to different communities---in favor of the proof-theoretic idiom "neither provable nor refutable". To the queue of clarifying amendments for tomorrow's edited version of the question (which hopefully will be the final rigorous posing of the question) the phrase "For all *n*" will be prepended, per your Option 1. And finally, appreciation and thanks are extended to you, and to everyone, for help in posing the question rigorously and clearly.  
> **username_4**: @JohnSidles: ok, and in your new version don't forget to review the connection between ... $M$ is incomprehensible iif the *statement* <$M$ runtime is $O(n^r)$> is neither provable nor refutable in T ..." and the Emanuele Viola's answer which is about the "undecidable" (standard CS definition) *decision problem* <Is $M$ runtime $O(n^r)$?>  
> **username_0**: Marzo, OK and thanks.  Also, on order to establish "Viola's Implication," we have to adjoin the argument from Section 3 of Jeremy Avigad's course notes (as linked in the question) to Viola's construction ... the amended question will clarify this point.  Needless to say, the process of clarifying definitions has been 10X++ more arduous than I originally anticipated ... which perhaps is a main point of the question.  Thanks, again.  

---

### Answer by username_7 on 2012-05-30. Score: 1

The answer to your question #1 is definitely "no." As I believe someone pointed out in the (very lengthy) comments section, you could easily add a "polylimiting" to a machine. That is, even if you don't know what r is, if you guess any integer larger than r (this is definitely possible, obviously), you could set up an overhead machine that simulates your "incomprehensible" Turing machine, and force it to stop running in polynomial time...without changing the language that the Turing machine accepts at all. In this fashion, you could convert any "incomprehensible" polynomial time Turing machine to a "comprehensible" polynomial time Turing machine, meaning that there is no language in P that can be decided by exclusively "incomprehensible" Turing machines.

I hope this helps. Unless I've completely misinterpreted your question and your intent, my answer is quite certainly correct; it's not at all an open question.

> **Comments:**
> **username_7**: By the way, if you want a good example of a candidate for what you call an "incomprehensible" algorithm, see http://www.scholarpedia.org/article/Universal_search .  The universal search algorithm for solving SAT adheres to your definition of incomprehensible iff P = NP is formally independent.  
> **username_2**: do you know anything about the final question from my answer? I believe that's the only question that is still not obviously trivial..to me that is  
> **username_0**: @Philip White, the definition is carefully constructed to evade the construction you provide.  Because supposing that M's runtime is undecidable for some exponent *r*, and we guess a value *r'* > *r*, and we install a *r'*-polylimiter in a modified machine M' that recognizes the same language as M, then for M' the statement "the runtime of M' is O(n^r) with respect to input length n" *still* is undecidable.  I agree though, that we need to think carefully about whether *ALL* cat-and-mouse games with oracle-specified polylimiters are excluded (as is the intent)---and so I upvoted your answer!  
> **username_0**: Oh, and since Sasho's comment overlapped mine, please let me express my appreciation of [the final question in Sasho's answer](http://cstheory.stackexchange.com/a/11575/1519), which (according to my present understanding of it) artfully obstructs the introduction of oracle-derived polylimiters.  As before, I will have to think about this for a day or two.  Thank you again, Philip.  
> **username_7**: Sorry, I should have read Sasho Nikolov's answer more carefully; I just saw the word "yes," oops.  I'll look at the last question in a moment and see if I have anything useful to say.  
> **username_7**: @Sasho Nikolov:  I think the answer to the question is, as you suggest, "yes," by Rice's theorem.  I'm not going to write out the proof, but it should be relatively obvious.  Basically, start with the following question:  Is the question of whether or not a polytime machine M has associated with it any machine M' which decides the same language and runs in polynomial time decidable?  I think that's a useful avenue to pursue to answer the question you pose; it's generally quite hard to establish that any two Turing machines decide the same language, again due to Rice's theorem.  
> **username_0**: Thank you Philip!  Please let me mention an aesthetic objective: a well-crafted definition of *incomprehensible* should *not* permit the trivial reduction of an incomprehensible M to an comprehensible M' via by introducing a polylimiter whose sole function is to *slow* the computation, and/or whose design requires an oracle-supplied exponent --- on the grounds that such reductions unaesthetically mask old elements of incomprehensibility by introducing new elements of incomprehensibility.  
> **username_0**: @Philip White, per your excellent comment the question now distinguishes "incomprehensible TMs" from "strongly incomprehensible TMs" with a view toward preserving the complexity-theoretic naturality of Q1–Q3.  Quite possibly further definitional tuning may be required ...that the present definitions are natural is not entirely evident (to me).  
> **username_7**: @JohnSidles, I think I know what you're getting at, and universal search is going to be your best bet.  You're talking about algorithms that (might) run in O(n^k) where k is not known.  Unfortunately, your definition of strongly incomprehensible machines requires that the set of strongly incomprehensible machines is empty--there is no such thing as a strongly incomprehensible language, for the reason that Peter Shor gave, and that Sasho Nikolov and I later repeated.  Definitely look into dovetailing algorithms and Levin's algorithm; I think you would find that very  interesting.  
> **username_0**: @Philip White, having more-than-exhausted my own knowledge, the question is now flagged for conversion to community wiki, and I hope you (and others) will improve the definitions given. Note the graded definitions of incomprehensibility **D2-D5** (in particular definitions **D3a** and **D3b**) now are crafted to forestall trivial reductions via polylimiters, with a view toward respecting the naturality of the notion "incomprehensibility."  In my view, the key challenge now amounts to "Does there exist a natural definition of incomprehensibility?" which is a tough question. Over-and-out! :)  

---

