¿Se ha demostrado definitivamente que algún problema abierto en matemáticas es decidible?

Question

Existe una lista bastante extensa de problemas en diversos campos que han demostrado ser indecidibles. Por ejemplo, véase

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

Y ciertamente, una cuestión abierta que se resuelve mediante una prueba o un contraejemplo es decidible.

Pero mi pregunta es: ¿hay algún problema conocido no resuelto en matemáticas que se sepa con seguridad que es decidible?

Por último, es una prueba de la decidibilidad de say, Conjetura de Goldbach ¿es una posibilidad, o simplemente está descartada?

Gracias.

Answer 1

Hay cuestiones abiertas que en principio podrían resolverse con algún cálculo finito (pero extremadamente largo), como el valor del Número de Ramsey $R(5,5)$ . Cualquier problema que pueda resolverse así debe ser decidible.

Answer 2

Sin resolver significa que puede existir un método pero que aún no se ha descubierto. Decidible significa que una máquina de Turing que ejecute el procedimiento se detendrá.

Un ejemplo es un algoritmo de tiempo polinómico para la factorización o el logaritmo discreto. Nadie los ha descubierto todavía, ni ha demostrado que un algoritmo de tiempo polinómico sea imposible. Por lo tanto, el algoritmo de tiempo polinómico para el problema no está resuelto. Pero el problema de la factorización o del logaritmo discreto es decidible, sólo que no en tiempo polinómico. Basta con hacer una búsqueda exhaustiva o uno de los mejores algoritmos conocidos para ese problema.

Sobre la conjetura de Goldbach, no se ha descubierto ningún obstáculo que haga imposible su demostración.