Has Any Currently Open Problem in Mathematics Definitively Been Shown to be Decidable?

158 Views Asked by At

There is a fairly extensive list of problems in various fields that have been shown to be undecidable. For example, see

https://en.wikipedia.org/wiki/List_of_undecidable_problems

And certainly, an open question that is resolved by either a proof or a counter-example is decidable.

But my question is---is there any known unsolved problem in mathematics that is known for sure to be decidable?

Lastly, is a proof of the decidability of say, Goldbach's Conjecture, a possibility, or simply out of the question?

Thank you.

2

There are 2 best solutions below

0
On BEST ANSWER

There are open questions which could in principle be resolved by some finite (but extremely long) calculation, such as the value of the Ramsey number $R(5,5)$. Any problem which can be so resolved must be decidable.

0
On

Unsolved means a method may exist but has not been discovered yet. Decidable means a Turing machine that executes the procedure will halt.

An example is a polynomial time algorithm for factoring or discrete logarithm. No one has discovered them yet, or proven that a polynomial time algorithm is impossible. So, the polynomial time algorithm for the problem is unsolved. But the problem of factoring or discrete logarithm is decidable, just not in polynomial time. Just do exhaustive search or one of the best known algorithms for that problem.

On Goldbach's conjecture, no obstacle has been discovered that a proof is impossible.