Does Provable == Decidable?
In computation theory are the terms Provable and Decidable interchangable? Do they mean the same thing?
For example you often see the question whether something is provable referred to as a decision problem (Das Entscheidu开发者_开发技巧ngsproblem).
These are different. In fact, they refer to completely different areas.
Decidable means, that a decision problem can be solved for all possible inputs by a Turing machine, which puts out 'accept' or 'reject'.
Provable means, that a mathematical statement can be proven by, well, a mathematical proof.
In fact, you cannot compare 'decidable' and 'provable', as these attributes refer to completely different things.
精彩评论