Skip to main content
3 of 18
Minor edit to improve readability
John Sidles
  • 1.5k
  • 1
  • 12
  • 28

Does P contain languages recognized solely by "incomprehensible" TMs?

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.

John Sidles
  • 1.5k
  • 1
  • 12
  • 28