11
$\begingroup$

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)".

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," 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 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.

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" 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", Scott Aaronson's weblog essay "Rosser’s Theorem via Turing machines" and Luca Trevisan's weblog post Two interesting questions.

On the existence of incomprehensible Turing machines

That incomprehensible Turing machines exist follows concretely from a construction by Emmanuele 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 (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 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.” 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 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) 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.

As Juris Hartmanis' monograph Feasible computations and provable complexity properties (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.

Improve this question
$\endgroup$
23
  • 1
    $\begingroup$ Please define the term “(a Turing machine) being decidably in P.” $\endgroup$
    – Tsuyoshi Ito
    Commented May 28, 2012 at 18:08
  • 2
    $\begingroup$ 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? $\endgroup$
    – Tsuyoshi Ito
    Commented May 28, 2012 at 18:49
  • 3
    $\begingroup$ 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$). $\endgroup$
    – Sasho Nikolov
    Commented May 28, 2012 at 19:04
  • 2
    $\begingroup$ 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 by Raphael and the link in it may be helpful. I voted to close this as not a real question. $\endgroup$
    – Tsuyoshi Ito
    Commented May 28, 2012 at 19:19
  • 2
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Commented May 29, 2012 at 15:32

3 Answers 3

Reset to default
11
$\begingroup$

(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. 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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ ------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. $\endgroup$
    – John Sidles
    Commented May 29, 2012 at 10:50
  • $\begingroup$ 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. $\endgroup$
    – John Sidles
    Commented May 29, 2012 at 11:01
  • $\begingroup$ 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. $\endgroup$
    – John Sidles
    Commented May 29, 2012 at 13:20
  • 1
    $\begingroup$ please check my updated answer $\endgroup$
    – Sasho Nikolov
    Commented May 29, 2012 at 15:40
  • $\begingroup$ 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. $\endgroup$
    – John Sidles
    Commented May 29, 2012 at 16:18
2
$\begingroup$

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".

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – John Sidles
    Commented May 29, 2012 at 14:26
  • 1
    $\begingroup$ @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)$?> $\endgroup$
    – Marzio De Biasi
    Commented May 29, 2012 at 14:51
  • $\begingroup$ 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. $\endgroup$
    – John Sidles
    Commented May 29, 2012 at 15:31
1
$\begingroup$

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.

Improve this answer
$\endgroup$
10
  • 1
    $\begingroup$ By the way, if you want a good example of a candidate for what you call an "incomprehensible" algorithm, see scholarpedia.org/article/Universal_search . The universal search algorithm for solving SAT adheres to your definition of incomprehensible iff P = NP is formally independent. $\endgroup$
    – Philip White
    Commented May 30, 2012 at 22:07
  • 1
    $\begingroup$ 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 $\endgroup$
    – Sasho Nikolov
    Commented May 31, 2012 at 0:56
  • $\begingroup$ @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! $\endgroup$
    – John Sidles
    Commented May 31, 2012 at 0:59
  • $\begingroup$ Oh, and since Sasho's comment overlapped mine, please let me express my appreciation of the final question in Sasho's answer, 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. $\endgroup$
    – John Sidles
    Commented May 31, 2012 at 1:21
  • $\begingroup$ 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. $\endgroup$
    – Philip White
    Commented May 31, 2012 at 1:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.