It seems to me that problems whose dedicability remains open for a long time, if resolved, tend to end up being undecidable. A prominent example would be (e.g.) Hilbert's tenth problem, whose decidability was open 21+ years (†) until proven decidable. Is there a similiar example of a problem whose decidability was open for a long time (receiving considerable attention) but was proven, in the end, to be decidable?

(†) Hard to put an exact figure on how long it was open. Originally stated in 1900 and proven in 1970, but the original statement was before the modern notion of undecidability.


I suspect there are many of them. Pick almost any recent paper that shows decidability of some problem, and I suspect chances are good you'll have an example. So, I doubt your heuristic that if decidability remains open for a long time, chances are that the problem is undecidable.

For example: The matrix mortality problem for non-singular 2x2 matrices was recently shown to be decidable (Decidability of the Membership Problem for 2 × 2 integer matrices, Potapov, Semukhin).

| cite | improve this answer | |
  • $\begingroup$ It seems you guessed (and refuted) my heuristic. $\endgroup$ – badroit Sep 25 '18 at 3:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.