Return to Question

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.

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.

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

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.

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.

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

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

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

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:

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.

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.

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

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

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:

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.

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.

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

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.