Hace demostrable == decidable?

Question

En la teoría de la computación son los términos y demostrable decidable intercambiables? Qué significan la misma cosa?

Por ejemplo, usted ve a menudo la cuestión de si algo es demostrable conoce como un problema de decisión (Das Entscheidungsproblem).

Answer 1

Estos son diferentes. De hecho, se refieren a áreas completamente diferentes.

decidable medios, que un problema de decisión puede ser resuelta para todas las posibles entradas por una máquina de Turing, que pone a cabo 'aceptar' o 'rechazar'.

medios probable, que un enunciado matemático puede ser probada por, además, una prueba matemática.

De hecho, no se puede comparar 'decidible' y 'comprobable', ya que estos atributos se refieren a cosas completamente diferentes.