Est-ce que prouvable == décidable?

Question

Dans la théorie de calcul sont les termes prouvable et décidable interchangable? Est-ce qu'ils veulent dire la même chose?

Par exemple, vous voyez souvent la question de savoir si quelque chose est prouvable appelé problème de décision (Das Entscheidungsproblem).

Answer 1

Elles sont différentes. En fait, ils se réfèrent à des zones complètement différentes.

signifie décidables, qu'un problème de décision peut être résolu pour toutes les entrées possibles par une machine de Turing, qui met à « accepter » ou « refuser ».

moyens démontrable, qu'une déclaration mathématique peut être prouvée par, eh bien, une preuve mathématique.

En fait, vous ne pouvez pas comparer les « décidable » et « prouvable », comme ces attributs font référence à des choses complètement différentes.