Skip to main content
1 of 4
Post Made Community Wiki
Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k

What are the most attractive Turing undecidable problems in mathematics?

What are the most attractive Turing undecidable problems in mathematics?

There are thousands of examples, so please post here only the most attractive, best examples. Some examples already appear on the Wikipedia page.

Standard community wiki rules. One example per post please. I will `accept' the answer I find to be the most attractive, according to the following criteria:

  • Examples must be undecidable in the sense of Turing computability, not in the sense of logical independence. That is, think of word problem, not Continuum Hypothesis.

  • The best examples will arise from natural mathematical questions.

  • The best examples will be easy to describe, and understandable by most or all mathematicians.

  • (Challenge) The very best examples, if any, will in addition have intermediate Turing degree, strictly below the halting problem. That is, they will be undecidable, but not because the halting problem reduces to them.

Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k