Given an input problem P, can you construct an algorithm A to compute whether or not P is decidable or undecidable? In other words, is the undecidabiliy of a problem undecidable? My initial guess is that yes, undecidability of a given problem is undecidable, because the above algorithm seems reducible to the Halting problem which cannot be solved using a Turing machine. However, the human mind seems to be able to determine the undecidability of a given problem, and thus the above algorithm is constructable (Unless of course, there exist problems so unimaginably hard that it is impossible to determine if they are undecidable or not). So, which one of these guesses is the correct one, and why? Is undecidability undecidable or decidable?

  • 2
    $\begingroup$ How is $P$ given as an input? $\endgroup$ – Yuval Filmus May 14 '20 at 12:29
  • 1
    $\begingroup$ Related: Is Deciding Decidability Decidable?. But my head spins how they are exactly related. $\endgroup$ – Hendrik Jan May 14 '20 at 17:15
  • 1
    $\begingroup$ The human mind can determine decidability of some problems and not of others. $\endgroup$ – gnasher729 May 15 '20 at 7:32
  • $\begingroup$ Twin prime conjecture: Nobody knows if it is true, false, or undecidable. $\endgroup$ – gnasher729 May 15 '20 at 8:15
  • $\begingroup$ @gnasher729, hmm, well, there's always the possibility of solving these types of problems in finite time, however. Nonetheless, if these types of problems turn out to be undecidable or decidable or even worse undecidably undecidable, then could you construct an n-nested undecidably undecidable problem as n goes to infinity, and is such a problem n-undecidably undecidable as well, as n goes to infinity? And could you construct a problem which is not even in the set of n-undecidably undecidable problems, nor in the set of decidable problems? $\endgroup$ – ZeroMaxinumXZ May 15 '20 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.