En la teoría de cómputo, ¿los términos intercambiable demostrable y resoluble? ¿Significan lo mismo?Does Provable == Decidable?
Por ejemplo, a menudo se ve la pregunta de si algo se puede demostrar como un problema de decisión (Das Entscheidungsproblem).
Estos son diferentes. De hecho, se refieren a áreas completamente diferentes.
Decidable significa que un problema de decisión puede ser resuelto para todas las entradas posibles por una máquina de Turing, que saca 'aceptar' o 'rechazar'.
Probable significa que una declaración matemática puede ser probada por, bueno, una prueba matemática.
De hecho, no puede comparar 'decidible' y 'comprobable', ya que estos atributos se refieren a cosas completamente diferentes.
Tienes que demostrar que la decisión de la máquina funciona correctamente;) – Dario
¿Quizás una pregunta adecuada para mathoverflow.net? –
Pensé en eso, pero como comp. El curso de teoría (y complejidad) se puede encontrar en casi todos los cursos de CS \ SE que pensé que serían más adecuados. –