Return to Question

For further technical discussion, see Joel David Hamkins' answer on MathOverflow to the question Can a problem be simultaneously polynomial time and undecidable? (recommended by Alex ten Brink).

These linked questions arise from the MathOverflow community wiki questions "What are the most attractive Turing undecidable problems in mathematics?" and "What notions are used but not clearly defined in modern mathematics?" In particular, Colin Tan requested that the question asked above be posted as a separate question.

For further technical discussion, see Joel David Hamkins' answer on MathOverflow to the question Can a problem be simultaneously polynomial time and undecidable? (recommended by Alex ten Brink).

These linked questions arise from the MathOverflow community wiki questions "What are the most attractive Turing undecidable problems in mathematics?" and "What notions are used but not clearly defined in modern mathematics?" In particular, Colin Tan requested that the question asked above be posted as a separate question.

• Q1: Do there exist languages $L$ that are recognized solely by those Turing machines in $P$ whose runtime exponents are undecidable?
• Q2: Can examples of these Turing machines be finitely constructed?
• Q3: Can these Turing machines be concretely instantiated? (e.g., by oracles that "guess" them rather than finitely construct them).
• Q4: What other attributes of P (besides runtime exponents) are presently known to be undecidable? For what attributes of $P$ is this question open?
• Q5: Do the undecidable attributes of $P$ pose an obstruction to the decidability of $P \ne NP$?

I have become aware that Juris Harmanis’ 1978 monograph Feasible Computations and Provable Complexity Properties can be read as an in-depth response to Q1–5. Moreover, the (excellent) Q1 and Q4 proof sketches provided below by Travis Service and by Alex ten Brink provide a modern affirmation and extension of Hartmanis' overall conclusions that:

For technical background see the TCS StackExchange question "Are runtime bounds in P decidable?", in particular Emanuele Viola's concise proof that the answer is "no". Note also that similar results are proved by Juris Hartmanis in his monograph Feasible computations and provable complexity properties (1978).

• Q1: Do there exist languages $L$ that are recognized solely by those Turing machines in $P$ whose runtime exponents are undecidable?
• Q2: Can examples of these Turing machines be finitely constructed?
• Q3: Can these Turing machines be concretely instantiated? (e.g., by oracles that "guess" them rather than finitely construct them).
• Q4: What other attributes of P (besides runtime exponents) are presently known to be undecidable? For what attributes of $P$ is this question open?
• Q5: Do the undecidable attributes of $P$ pose an obstruction to the decidability of $P \ne NP$?

I have become aware that Juris Harmanis’ 1978 monograph Feasible Computations and Provable Complexity Properties can be read as an in-depth response to Q1–5. Moreover, the (excellent) Q1 and Q4 proof sketches provided below by Travis Service and by Alex ten Brink provide a modern affirmation and extension of Hartmanis' overall conclusions that:

For technical background see the TCS StackExchange question "Are runtime bounds in P decidable?", in particular Emanuele Viola's concise proof that the answer is "no". Note also that similar results are proved by Juris Hartmanis in his monograph Feasible computations and provable complexity properties (1978).

Because the question is open, and because it is being discussed on multiple mathematical weblog threads (1,2,3,4,5), this question has been flagged for conversion to Community Wiki.

Because the question is open, and because it is being discussed on multiple mathematical weblog threads (1,2,3,4,5,6), this question has been flagged for conversion to Community Wiki.